Back to index

python-biopython  1.60
MultiGraph.py
Go to the documentation of this file.
00001 # Copyright 2001 by Tarjei Mikkelsen.  All rights reserved.
00002 # This code is part of the Biopython distribution and governed by its
00003 # license.  Please see the LICENSE file that should have been included
00004 # as part of this package.
00005 
00006 # get set abstraction for graph representation
00007 
00008 #TODO - Subclass graph?
00009 class MultiGraph(object):
00010     """A directed multigraph abstraction with labeled edges."""
00011 
00012     def __init__(self, nodes = []):
00013         """Initializes a new MultiGraph object."""
00014         self._adjacency_list = {}    # maps parent -> set of (child, label) pairs
00015         for n in nodes:
00016             self._adjacency_list[n] = set()
00017         self._label_map = {}         # maps label -> set of (parent, child) pairs
00018 
00019     def __eq__(self, g):
00020         """Returns true if g is equal to this graph."""
00021         return isinstance(g, MultiGraph) and \
00022                (self._adjacency_list == g._adjacency_list) and \
00023                (self._label_map == g._label_map)
00024 
00025     def __ne__(self, g):
00026         """Returns true if g is not equal to this graph."""
00027         return not self.__eq__(g)
00028 
00029     def __repr__(self):
00030         """Returns an unique string representation of this graph."""
00031         s = "<MultiGraph: "
00032         keys = sorted(self._adjacency_list.keys())
00033         for key in keys:
00034             values = sorted(self._adjacency_list[key])
00035             s += "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")" 
00036         return s + ">"
00037 
00038     def __str__(self):
00039         """Returns a concise string description of this graph."""
00040         nodenum = len(self._adjacency_list)
00041         edgenum = reduce(lambda x,y: x+y,
00042                          map(len, self._adjacency_list.values()))
00043         labelnum = len(self._label_map)
00044         return "<MultiGraph: " + \
00045                str(nodenum) + " node(s), " + \
00046                str(edgenum) + " edge(s), " + \
00047                str(labelnum) + " unique label(s)>"
00048 
00049     def add_node(self, node):
00050         """Adds a node to this graph."""
00051         if node not in self._adjacency_list:
00052             self._adjacency_list[node] = set()
00053 
00054     def add_edge(self, source, to, label = None):
00055         """Adds an edge to this graph."""
00056         if source not in self._adjacency_list:
00057             raise ValueError("Unknown <from> node: " + str(source))
00058         if to not in self._adjacency_list:
00059             raise ValueError("Unknown <to> node: " + str(to))
00060         edge = (to, label)
00061         self._adjacency_list[source].add(edge)
00062         if label not in self._label_map:
00063             self._label_map[label] = set()
00064         self._label_map[label].add((source,to))
00065 
00066     def child_edges(self, parent):
00067         """Returns a list of (child, label) pairs for parent."""
00068         if parent not in self._adjacency_list:
00069             raise ValueError("Unknown <parent> node: " + str(parent))
00070         return sorted(self._adjacency_list[parent])
00071 
00072     def children(self, parent):
00073         """Returns a list of unique children for parent."""
00074         return sorted(set([x[0] for x in self.child_edges(parent)]))
00075 
00076     def edges(self, label):
00077         """Returns a list of all the edges with this label."""
00078         if label not in self._label_map:
00079             raise ValueError("Unknown label: " + str(label))
00080         return sorted(self._label_map[label])
00081 
00082     def labels(self):
00083         """Returns a list of all the edge labels in this graph."""
00084         return self._label_map.keys()
00085 
00086     def nodes(self):
00087         """Returns a list of the nodes in this graph."""
00088         return self._adjacency_list.keys()
00089 
00090     def parent_edges(self, child):
00091         """Returns a list of (parent, label) pairs for child."""
00092         if child not in self._adjacency_list:
00093             raise ValueError("Unknown <child> node: " + str(child))
00094         parents = []
00095         for parent, children in self._adjacency_list.iteritems():
00096             for x in children:
00097                 if x[0] is child:
00098                     parents.append((parent, x[1]))
00099         return sorted(parents)
00100 
00101     def parents(self, child):
00102         """Returns a list of unique parents for child."""
00103         return sorted(set([x[0] for x in self.parent_edges(child)]))
00104 
00105     def remove_node(self, node):
00106         """Removes node and all edges connected to it."""
00107         if node not in self._adjacency_list:
00108             raise ValueError("Unknown node: " + str(node))
00109         # remove node (and all out-edges) from adjacency list
00110         del self._adjacency_list[node]
00111         # remove all in-edges from adjacency list
00112         for n in self._adjacency_list:
00113             self._adjacency_list[n] = set(x for x in self._adjacency_list[n] \
00114                                           if x[0] is not node)
00115         # remove all refering pairs in label map
00116         for label in self._label_map.keys():
00117             lm = set(x for x in self._label_map[label] \
00118                      if (x[0] is not node) and (x[1] is not node))
00119             # remove the entry completely if the label is now unused
00120             if lm:
00121                 self._label_map[label] = lm
00122             else:
00123                 del self._label_map[label]
00124 
00125     def remove_edge(self, parent, child, label):
00126         """Removes edge. -- NOT IMPLEMENTED"""
00127         # hm , this is a multigraph - how should this be implemented?
00128         raise NotImplementedError("remove_edge is not yet implemented")
00129 
00130 # auxilliary graph functions
00131 
00132 def df_search(graph, root = None):
00133     """Depth first search of g.
00134 
00135     Returns a list of all nodes that can be reached from the root node
00136     in depth-first order.
00137 
00138     If root is not given, the search will be rooted at an arbitrary node.
00139     """
00140     seen = {}
00141     search = []
00142     if len(graph.nodes()) < 1:
00143         return search
00144     if root is None:
00145         root = (graph.nodes())[0]
00146     seen[root] = 1
00147     search.append(root)
00148     current = graph.children(root)
00149     while len(current) > 0:
00150         node = current[0]
00151         current = current[1:]
00152         if node not in seen:
00153             search.append(node)
00154             seen[node] = 1
00155             current = graph.children(node) + current
00156     return search   
00157 
00158 def bf_search(graph, root = None):
00159     """Breadth first search of g.
00160 
00161     Returns a list of all nodes that can be reached from the root node
00162     in breadth-first order.
00163 
00164     If root is not given, the search will be rooted at an arbitrary node.
00165     """
00166     seen = {}
00167     search = []
00168     if len(graph.nodes()) < 1:
00169         return search
00170     if root is None:
00171         root = (graph.nodes())[0]
00172     seen[root] = 1
00173     search.append(root)
00174     current = graph.children(root)
00175     while len(current) > 0:
00176         node = current[0]
00177         current = current[1:]
00178         if node not in seen:
00179             search.append(node)
00180             seen[node] = 1
00181             current.extend(graph.children(node))
00182     return search
00183