bfs.xq

(: list of all persons and their neighbors :)
declare variable $persons :=
  for $scene in doc('http://www.ibiblio.org/xml/examples/shakespeare/r_and_j.xml')//SCENE
  let $speakers := distinct-values($scene/SPEECH/SPEAKER)
  for $p1 in $speakers, $p2 in $speakers
  where $p1 ne $p2
  group by $p1
  return <person name="{$p1}">{
    for $other in distinct-values($p2)
    return <neighbor name="{$other}"/>
  }</person>;


declare function local:BFS($start) {
  (: just starts the first round with the start node :)
  local:round(
    1,
    <speaker name="{$start}"><distance>0</distance></speaker>,
    ()
  )
};

declare function local:round($n, $last-round, $out) {
  if(empty($last-round)) then (
    (: last round found no new persons, we are finished :)
    $out
  ) else (
    let $current-round :=
      (: iterate over all persons found in the last round :)
      fold-left($last-round, (), function($current, $speaker) {
        (: iterate over their neighbors :)
        fold-left(
          (: ignore persons found in previous rounds :)
          $persons[@name=$speaker/@name]/neighbor/@name[not(. = $out/@name)],
          $current,
          function($current2, $neighbor) {
            if($current2/speaker[@name = $neighbor]) then (
              (: person was already found this round, ignore :)
              $current2
            ) else (
              (: append newly found person to this round's output :)
              $current2,
              <speaker name="{$neighbor}"><distance>{$n}</distance></speaker>
            )
          })
      })
    return local:round($n + 1, $current-round, ($out, $last-round))
  )
};

local:BFS("JULIET")