"""
Provides an implementation of directed, labelled graphs.
"""
from collections import Hashable
from libutilitaspy.metaclassconfig import MetaClass
from maps import Map
[docs]class Node(Hashable):
"""
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.
"""
__metaclass__ = MetaClass
def __init__(self, obj=None):
self.obj = obj
self.incoming = set() # Incoming edges
self.outgoing = set() # Outgoing edges
def __hash__(self):
return hash(id(self))
# Maybe we should keep identity instead?
# def __eq__(self, other):
# return self.obj == other.obj
[docs]class Edge(Hashable):
"""
Directed edges between nodes in a graph. An edge has source and target nodes, and possibly a label, which can be any object.
"""
__metaclass__ = MetaClass
def __init__(self, source=None, target=None, label=None):
assert source is None or isinstance(source, Node)
assert target is None or isinstance(target, Node)
self.source = source
self.target = target
self.label = label
def __hash__(self):
return hash(id(self))
# def __eq__(self, other):
# return self.source == other.source and self.target == other.target and self.label == other.label
[docs]class Graph(Hashable):
"""
This class supports two basic, equivalent, styles of defining graphs:
1) a graph is given by :math:`(N,E,src,trg)` where
* :math:`N` is a collection of nodes
* :math:`E` is a collection of edges
* :math:`src:E \\to N` is a map associating each edge :math:`e` in :math:`E` to its source node :math:`src(e)` in :math:`N`
* :math:`trg:E \\to N` is a map associating each edge :math:`e` in :math:`E` to its target node :math:`trg(e)` in :math:`N`
2) a graph is given by :math:`(N,E)` where
* :math:`N` is a collection of nodes
* :math:`E` is a collection of edges, where an edge :math:`e` is a triple :math:`(s,t,l)` with
- :math:`s` is the source node of :math:`e`,
- :math:`t` is the target node of :math:`e`,
- :math:`l` is some label (any object)
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
Invariants:
For any Graph g:
for every e in g.edges:
e.source == g.source(e) and
e.target == g.target(e) and
e in e.source.outgoing and
e in e.target.incoming
"""
__metaclass__ = MetaClass
def __init__(self, nodes, edges, source=None, target=None):
assert all(isinstance(node, Node) for node in nodes)
assert all(isinstance(edge, Edge) for edge in edges)
assert source is None and target is None or isinstance(source, Map) and isinstance(target, Map)
self.nodes = set(nodes)
self.edges = set(edges)
if source is None:
self.source = Map(lambda f: f.source)
# self.source = Map((f, f.source) for f in edges))
else:
self.source = source
if target is None:
self.target = Map(lambda f: f.target)
# self.target = Map((f, f.target) for f in edges))
else:
self.target = target
# This ensures that the edges source and target correspond to the given maps.
for edge in self.edges:
edge.source = self.source(edge)
edge.target = self.target(edge)
edge.source.outgoing.add(edge)
edge.target.incoming.add(edge)
def __hash__(self):
return hash(id(self))
def __contains__(self, item):
"""
Returns True if item is in the graph. The given item may be a node or an edge.
:param item: An item to search.
:type item: :py:class:`Node` or :py:class:`Edge`
:returns: item in self.nodes or item in self.edges
:rtype: bool
"""
if isinstance(item, Node):
return item in self.nodes
elif isinstance(item, Edge):
return item in self.edges
else:
return False
[docs] def add_node(self, node):
"""
Adds a node to the graph.
:param Node node: A node
"""
assert isinstance(node, Node)
self.nodes.add(node)
[docs] def add_edge(self, edge):
"""
Adds an edge to the graph. If the source and/or target nodes of the edge
are not already in the graph, they are also added.
:param Edge edge: An edge.
"""
assert isinstance(edge, Edge)
assert isinstance(edge.source, Node)
assert isinstance(edge.target, Node)
self.edges.add(edge)
self.nodes.add(edge.source)
self.nodes.add(edge.target)
self.source[edge] = edge.source
self.target[edge] = edge.target
def __eq__(self, other):
"""
Determines whether this graph and the other are equal in the sense that they contain the same nodes and edges.
:param Graph other: A graph.
:returns: self.nodes == other.nodes and self.edges == other.edges
:rtype: bool
"""
return self.nodes == other.nodes and self.edges == other.edges
[docs]class GraphHomomorphism(Map):
"""
A graph homomorphism :math:`h:G_1 \\to G_2` between two graphs :math:`G_1 = (N_1, E_1, src_1, trg_1)` and :math:`G_2 = (N_2, E_2, src_2, trg_2)`
is a pair of maps :math:`h = (h_N, h_E)` where :math:`h_N:N_1 \\to N_2` and :math:`h_E:E_1 \\to E_2` such that for all edges :math:`e \\in E_1`:
* :math:`src_2(h_E(e)) = h_N(src_1(e))`, and
* :math:`trg_2(h_E(e)) = h_N(trg_1(e))`
Equivalently, a graph homomorphism :math:`h:G_1 \\to G_2` between two graphs :math:`G_1 = (N_1, E_1)` and :math:`G_2 = (N_2, E_2)`
is a pair of maps :math:`h = (h_N, h_E)` where :math:`h_N:N_1 \\to N_2` and :math:`h_E:E_1 \\to E_2` such that for all edges :math:`e \\in E_1`:
* if :math:`e = (s,t,l) \\in E_1` then :math:`h_E(e) = (h_N(s),h_N(t),l) \\in E_2`.
"""
def __init__(self, source, target, nodemap, edgemap):
assert isinstance(source, Graph)
assert isinstance(target, Graph)
assert isinstance(nodemap, Map)
assert isinstance(edgemap, Map)
self.source = source
self.target = target
self.nodemap = nodemap
self.edgemap = edgemap
Map.__init__(self, self.map)
[docs] def map(self, x):
"""
:param x: A node or edge in the source graph
:type x: :py:class:`Node` or :py:class:`Edge`
:returns: x's image
:rtype: :py:class:`Node` if type(x) is :py:class:`Node`, :py:class:`Edge` if type(x) is :py:class:`Edge`
"""
if isinstance(x, Node):
assert x in self.source
n = self.nodemap(x)
assert n in self.target
return n
elif isinstance(x, Edge):
assert x in self.source
e = self.edgemap(x)
assert e in self.target
assert e.source == self.nodemap(x.source)
assert e.target == self.nodemap(x.target)
return e
else:
raise Exception("%s is neither a Node nor an Edge" % str(x))