Fuzion • Idioms • Idiom # 40: Graph with adjacency lists

Idiom # 40: Graph with adjacency lists

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) Set vertex  is
    for
      r := ps_set (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 `lteq` for parent feature's 'has_total_order' type feature
  fixed type.lteq    (a, b ex40.vertex) bool is a.id <= b.id
  fixed type.equality(a, b ex40.vertex) bool is 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) : has_total_order
  is
    # redefine `lteq` for parent feature's 'has_total_order' type feature
    fixed type.lteq    (a, b ex40.vertex) bool is a.id <= b.id
    fixed type.equality(a, b ex40.vertex) bool is a.id =  b.id

    redef as_string => "v$id"

  edge(a, b vertex) is

  graph(edges Sequence edge) is
    neighbors(v vertex) Set vertex  is
      for
        r := ps_set (lists.empty vertex), if      (v = e.a) r.add e.b
                                          else if (v = e.b) r.add e.a
                                          else                        r
        e in edges
      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?

next: Idiom # 41: Reverse a string