CODEWITHSUNDEEP
xquery
J.doe
J.doe

Reputation: 373

Recursion with XQuery with example

I have a database that look like this (access it via $database): 

<country car_code="F" area="547030" capital="cty-france-paris">
  <name>France</name>
  <border country="AND" length="60"/>
  <border country="E" length="623"/>
  <border country="D" length="451"/>
  <border country="I" length="488"/>
  <border country="CH" length="573"/>
  <border country="B" length="620"/>
  <border country="L" length="73"/>
  <border country="MC" length="4.4"/>
</country>

.....
other countries

I would like to write a function that gives the names of all countries reachable from France (or any other country) via land borders. A first attempt (probably with plenty of syntax errors and other errors, but the semantics of the program should be "more clear"):

declare function local:reachable($country as element())
  as (return value should be a sequence of countries  )
{
  if $country == ()   (:if empty, it doesn't border to any other country:)
    then ()

  else(
    $country/name  UNION (for $bord in $country/border/@country  return
    local:reachable ($database/country/car_code = @bord ))
  )
}

The call to that function:

local:reachable($database/country[@car_code = "F"])

The bordering countries to France should be:

  <border country="AND" length="60"/>
  <border country="E" length="623"/>
  <border country="D" length="451"/>
  <border country="I" length="488"/>
  <border country="CH" length="573"/>
  <border country="B" length="620"/>
  <border country="L" length="73"/>
  <border country="MC" length="4.4"/>

But we also need to find the bordering countries for these countries. the final output should be "F", "AND", "E", "D", "I", "CH", "B", "L", "MC"..., X, Y, Z, (and other countries that border to these countries).

Upvotes: 3

Views: 2156

Answers (1)

Florent Georges
Florent Georges

Reputation: 2327

Before we start

Here are a few comments on your code:

  • $country as element() defines a variable which MUST contain exactly one element, so it never can be empty; use element()? if the element is optional, element()* if there can be any number of them, or element()+ if there must be one or more

  • the sequence operator , can be used to construct sequences from other sequences: (1,2) , (3,4) constructs 2 sequences: (1,2) and (3,4), then constructs another one containing all items in the others, resulting in: (1,2,3,4)

Data

Let me change slightly the countries element, so I remove the noise, and make it a bit simpler for this demonstration. Also, I create a simple, yet complete map. Let us say we have 2 adjacent countries U and K, and 4 others forming a square (each country is neighbourgh to 2 others): N, G, B, and F. Any similarity to existing geography or politics is only in your eyes :-)

<!--
Map:   U K | N G
             B F
-->
<countries>
   <country id="U">
      <name>Over the top</name>
      <border idref="K"/>
   </country>
   <country id="K">
      <name>Beyond the see</name>
      <border idref="U"/>
   </country>
   <country id="N">
      <name>Flatland</name>
      <border idref="B"/>
      <border idref="G"/>
   </country>
   <country id="G">
      <name>Marxhome</name>
      <border idref="N"/>
      <border idref="F"/>
   </country>
   <country id="B">
      <name>Beerium</name>
      <border idref="N"/>
      <border idref="F"/>
   </country>
   <country id="F">
      <name>Grapeandcheese</name>
      <border idref="B"/>
      <border idref="G"/>
   </country>
</countries>

Solution

The solution includes a recursive function, that consumes a queue of countries to handle. Meanwhile, it accumulates the result list one country at a time. It takes the first country in the queue, add it to the result, then recurse on all adjacent countries which are not already in the queue nor the current result. The augmented result is passed down as well.

xquery version "3.0";

declare variable $countries :=
<countries>
   <!-- as above, just copy and paste it -->
</countries>;

declare function local:reachable(
   $queue  as element(country)*,
   $result as element(country)*   
) as element(country)*
{
   if ( empty($queue) ) then (
      (: we do not consider one country reachable from itself :)
      tail($result)
   )
   else (
      let $this := head($queue)
      let $rest := tail($queue)
      let $more := $this/border/@idref[not(. = ($queue, $result)/@id)]
      return
         local:reachable(
            ( $rest, $countries/country[@id = $more] ),
            ( $result, $this ))
   )
};

(: for each countries, display its reachable countries
 :)
for $c in $countries/country
order by $c/@id
let $r := local:reachable($c, ())
return
   $c/name || ': ' || string-join($r/@id, ', ')

Result

Beerium: N, G, F
Grapeandcheese: N, G, B
Marxhome: N, B, F
Beyond the see: U
Flatland: G, B, F
Over the top: K

Upvotes: 6

Related Questions