Skip to content

Instantly share code, notes, and snippets.

@ptmcg
Last active February 11, 2020 10:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ptmcg/4a4b523006f18e2f09829970335030c4 to your computer and use it in GitHub Desktop.
Save ptmcg/4a4b523006f18e2f09829970335030c4 to your computer and use it in GitHub Desktop.
Graph algebra parser/evaluator
#
# 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
""")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment