Fuzion • Idioms • Idiom # 129: Breadth-first traversing in a graph

Idiom # 129: Breadth-first traversing in a graph

Code

Running Example

ex129 is
  vertex(id i32): has_total_order is
    # redefine `lteq` for parent feature's 'has_total_order' type feature
    fixed type.lteq    (a, b ex129.vertex) bool is a.id <= b.id
    fixed type.equality(a, b ex129.vertex) bool is a.id =  b.id

    redef as_string => "v$id"

  edge(a, b vertex) is

  graph(edges Sequence edge) is
    neighbors(v vertex) Set vertex is
      for
        r ref ps_set vertex := (ps_sets vertex).empty, if      (v = e.a) r.add e.b
                                                       else if (v = e.b) r.add e.a
                                                       else              r
        e in g.edges
      else
        r

  v1 := vertex 1
  v2 := vertex 2
  v3 := vertex 3
  v4 := vertex 4
  v5 := vertex 5
  edges := [ edge v1 v5;
             edge v1 v3;
             edge v2 v4;
             edge v3 v4;
             edge v3 v4;
             edge v4 v5 ]
  g := graph edges

  breadth_first_traverse(queue list vertex, visited ref ps_set vertex) list vertex is
    match queue
      nil => lists.empty vertex
      c Cons =>
        # already visited? => skip adding to result
        if visited.contains c.head
          breadth_first_traverse c.tail visited
        else
          neighbors := g.neighbors c.head
          # result is the current element, the rest of the visitation queue and the neighbors
          [c.head].as_list ++ breadth_first_traverse (c.tail ++ neighbors) (visited.add c.head)

  breadth_first_traverse [v1].as_list (ps_sets vertex).empty | (vertex) -> say vertex

What are effects?

next: Idiom # 130: Depth-first traversing in a graph