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) container.Set vertex =>
    for
      r := container.ps_set (list vertex).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).empty, see #152
        r container.Set vertex := (container.ps_set vertex).new (list vertex).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