fuzion-lang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.
Fuzion
•
Idioms
•
Idiom # 130: Depth-first traversing in a graph
Idiom # 130: Depth-first traversing in a graph
See
programming-idioms.org
:
Code
depth_first_traverse(queue list vertex, visited ref container.ps_set vertex) list vertex => match queue nil => (list vertex).type.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_sets vertex).empty | vertex -> say vertex
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).type.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).type.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).type.empty) ! say
What are effects?
last changed: 2024-07-01
next: Idiom # 131: Successive conditions