Provides an implementation of directed, labelled graphs.
Nodes of a graph. A node may have an object associated with it, and accessible through its obj atribute.
A node also has a set of incoming edges and a set of outgoing edges.
Directed edges between nodes in a graph. An edge has source and target nodes, and possibly a label, which can be any object.
This class supports two basic, equivalent, styles of defining graphs:
is a collection of nodes
In the first style, the connections of an edge are stored in the graph, whereas in the second style, each edge stores a reference to its source and target.
This implementation allows both styles. For example, using style 1) we have:
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
N = [n1, n2, n3]
e1 = Edge(label='a')
e2 = Edge(label='b')
e3 = Edge(label='a')
E = [e1, e2, e3]
src = Map({e1: n1, e2: n1, e3: n3})
trg = Map({e1: n2, e2: n3, e3: n3})
g = Graph(N, E, src, trg)
On the other hand, using style 2) we have:
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
N = [n1, n2, n3]
e1 = Edge(n1, n2, label='a')
e2 = Edge(n1, n3, label='b')
e3 = Edge(n3, n3, label='a')
E = [e1, e2, e3]
g = Graph(N, E)
In both cases you can access (where g is a Graph, e is an Edge, and n is a Node):
g.nodes # this is a set of edges
g.edges # this is a set of edges
g.source(e) # this is a Node
g.target(e) # this is a Node
e.source # this is a Node
e.target # this is a Node
n.incoming # this is a set of edges
n.outgoing # this is a set of edges
A graph homomorphism between two graphs
and
is a pair of maps
where
and
such that for all edges
:
Equivalently, a graph homomorphism between two graphs
and
is a pair of maps
where
and
such that for all edges
: