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

Idiom # 130: Depth-first traversing in a graph

Code

depth_first_traverse(queue Sequence vertex, visited container.Set vertex) Sequence vertex =>
  match queue.as_list
    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] ++ depth_first_traverse (neighbors ++ c.tail) (visited.add c.head)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
depth_first_traverse(queue Sequence vertex, visited container.Set vertex) Sequence vertex =>
  match queue.as_list
    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] ++ depth_first_traverse (neighbors ++ c.tail) (visited.add c.head)
(depth_first_traverse [v1] (container.ps_set vertex).empty) ! say
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

What are effects?

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 Sequence vertex, visited container.Set vertex) Sequence vertex =>
    match queue.as_list
      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] ++ depth_first_traverse (neighbors ++ c.tail) (visited.add c.head)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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 Sequence vertex, visited container.Set vertex) Sequence vertex =>
    match queue.as_list
      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] ++ depth_first_traverse (neighbors ++ c.tail) (visited.add c.head)
  (depth_first_traverse [v1] (container.ps_set vertex).empty) ! say
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

What are effects?

last changed: 2024-07-01

next: Idiom # 131: Successive conditions