Source code for libutilitaspy.data_structures.graphs

"""
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))