Fuzion • Idioms • Idiom # 130: Depth-first traversing in a graph

Idiom # 130: Depth-first traversing in a graph

Code

Running Example

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

    redef as_string => "v$id"

  edge(a, b vertex) is

  graph(edges Sequence edge) is
    neighbors(v vertex) container.Set vertex =>
      for
        r container.Set vertex := (container.ps_set 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 v2;
             edge v1 v3;
             edge v2 v4;
             edge v3 v4;
             edge v4 v5
            ]
  g := graph edges

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

  (depth_first_traverse [v1].as_list (container.ps_set vertex).empty) ! say

What are effects?

last changed: 2024-07-01

next: Idiom # 131: Successive conditions