flang.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) : ordered vertex # must be ordered such that we can add it to a Set is # extract neighbors from edges in given graph neighbors(g graph) Set vertex is for r := psSet (lists.empty vertex), 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 'infix <=' for parent feature 'ordered' redef infix <= (b vertex) => id <= b.id # string representation redef asString => "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) : ordered vertex is neighbors(g graph) Set vertex is for r := psSet (lists.empty vertex), 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 redef infix <= (b vertex) => id <= b.id redef asString => "v$id" redef orderedThis => vertex id # NYI: may be removed when type 'like this' is supported edge(a, b vertex) is graph(edges Sequence edge) is 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 (v3.neighbors g)
What are effects?
next: Idiom # 41: Reverse a string