fuzion-lang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.
Fuzion
•
Idioms
•
Idiom # 40: Graph with adjacency lists
Idiom # 40: Graph with adjacency lists
See
programming-idioms.org
:
Code
vertex(id i32) : has_total_order # must be ordered such that we can add it to a Set is # extract neighbors from edges in given graph neighbors(g graph) container.Set vertex => for r := container.ps_set (list vertex).type.empty, if (vertex.this = e.a) r.add e.b else if (vertex.this = e.b) r.add e.a else r e in g.edges else r # redefine `lteq` for parent feature's 'has_total_order' type feature fixed type.lteq (a, b ex40.vertex) bool => a.id <= b.id fixed type.equality(a, b ex40.vertex) bool => a.id = b.id # string representation redef as_string => "v$id" # edge connecting 'a' and 'b' edge(a, b vertex) is # a graph is just a collection o edges graph(edges Sequence edge) is
What are effects?
Running Example
ex40 is vertex(id i32) : property.orderable is # redefine `lteq` for parent feature's 'has_total_order' type feature fixed redef type.lteq (a, b ex40.vertex) bool => a.id <= b.id fixed redef type.equality(a, b ex40.vertex) bool => a.id = b.id redef as_string => "v$id" edge(a, b vertex) is graph(edges0 Sequence edge) is neighbors(v vertex) container.Set vertex => for # NYI use (ps_set vertex).type.empty, see #152 r container.Set vertex := (container.ps_set vertex).type.new (list vertex).type.empty, if (v = e.a) r.add e.b else if (v = e.b) r.add e.a else r e in edges0 else r v1 := vertex 1 v2 := vertex 2 v3 := vertex 3 v4 := vertex 4 v5 := vertex 5 vertices := [ v1; v2; v3; v4; v5 ] edges := [ edge v1 v2; edge v2 v4; edge v3 v4; edge v3 v5; edge v4 v5 ] g := graph edges say (g.neighbors v3)
What are effects?
last changed: 2024-07-01
next: Idiom # 41: Reverse a string