Graph algebra parser/evaluator

graph_algebra.py

#
# graph_algebra.py
#
# A rough implementation of a graph algebra.
#
# References:
#     https://statagroup.com/articles/an-algebra-for-graph-structures
#     https://www.youtube.com/watch?v=EdQGLewU-8k
#
# Copyright 2020, Paul McGuire
#

"""
BNF:

vertex := ident | number
graph_decl := '<' [vertex]... '>'
graph_ref := graph_decl | ident
assignment := ident '=' graph_expr
graph_expr := graph_term ('+' graph_term)...
graph_term := graph_atom ('->' graph_atom)...
graph_atom := graph_ref | '(' graph_expr ')'
"""
from itertools import product


class Graph:
    def __init__(self, verts):
        self.vertices = verts[:]
        self.edges = []

    def connect(self, other):
        ret = Graph(sorted(set(self.vertices + other.vertices)))
        ret.edges = sorted(set(self.edges
                             + other.edges
                             + list(product(self.vertices, other.vertices)))
                        )
        return ret

    def overlay(self, other):
        ret = Graph(sorted(set(self.vertices + other.vertices)))
        ret.edges = sorted(set(self.edges + other.edges))
        return ret

    def __repr__(self):
        return "Graph({}, {})".format(self.vertices, self.edges)

    def plot(self):
        import networkx
        out = networkx.Graph()
        out.add_nodes_from(self.vertices)
        out.add_edges_from(self.edges)
        print("nx.Graph(", out.nodes, ',', out.edges, ")")
        # networkx.draw(out)


import pyparsing as pp

LPAR, RPAR, EQ = map(pp.Suppress, '()=')
ident = pp.pyparsing_common.identifier
graph_ident = ident()
vertex = graph_ident | pp.originalTextFor(pp.pyparsing_common.number)
GRAPH_BEGIN, GRAPH_END = map(pp.Suppress, "<>")
graph_decl = pp.Group(GRAPH_BEGIN + vertex[...] + GRAPH_END)
graph_ref = graph_decl | graph_ident

ident_map = {}

graph_decl.addParseAction(lambda t: Graph(*t))
graph_ident.addParseAction(lambda t: ident_map.get(t[0]))
def connect_pa(t):
    ret = t[0][0]
    for operand in t[0][2::2]:
        ret = ret.connect(operand)
    return ret

def overlay_pa(t):
    ret = t[0][0]
    for operand in t[0][2::2]:
        ret = ret.overlay(operand)
    return ret

graph_expr = pp.infixNotation(graph_ref, [
    (pp.oneOf('-> →'), 2, pp.opAssoc.LEFT, connect_pa),
    ('+', 2, pp.opAssoc.LEFT, overlay_pa),
    ])

assignment = ident("lhs") + EQ + graph_expr("rhs")
def assign_graph_value(t):
    ident_map[t.lhs] = t.rhs
assignment.addParseAction(assign_graph_value)

SHOW = pp.CaselessKeyword("show")
show_command = SHOW + graph_expr

PLOT = pp.CaselessKeyword("plot")
plot_command = PLOT + graph_expr('graph')
plot_command.addParseAction(lambda t: t.graph.plot())

parser = assignment | show_command | plot_command | graph_expr

parser.runTests("""
    g1 = <A B C> + <C> -> <F>
    show <A B C> -> <F>
    g2 = <A> -> <D> -> <E>
    g3 = g1 + g2
    g4 = <>
    g5 = g4 → g3
    g3
    plot g5
    """)