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<vertex>, if (e.a = vertex.this) r.add e.b else if (e.b = vertex.this) 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
Running Example
ex40 is vertex(id i32) : ordered<vertex> is neighbors(g graph) Set<vertex> is for r ref psSet<vertex> := psSet<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.this # 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)
next: Idiom # 41: Reverse a string
