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 List<edge>) is

Running Example

ex40 is vertex(id i32) : ordered<vertex> is 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 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 List<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)