Back to index

python-biopython  1.60
Graph.py
Go to the documentation of this file.
00001 # Copyright 2002 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 class Graph(object):
00009     """A directed graph abstraction with labeled edges."""
00010 
00011     def __init__(self, nodes = []):
00012         """Initializes a new Graph object."""
00013         self._adjacency_list = {}    # maps parent -> set of child objects
00014         for n in nodes:
00015             self._adjacency_list[n] = set()
00016         self._label_map = {}         # maps label -> set of (parent, child) pairs
00017         self._edge_map = {}          # maps (parent, child) pair -> label
00018 
00019     def __eq__(self, g):
00020         """Returns true if g is equal to this graph."""
00021         return isinstance(g, Graph) and \
00022                (self._adjacency_list == g._adjacency_list) and \
00023                (self._label_map == g._label_map) and \
00024                (self._edge_map == g._edge_map)
00025 
00026     def __ne__(self, g):
00027         """Returns true if g is not equal to this graph."""
00028         return not self.__eq__(g)
00029 
00030     def __repr__(self):
00031         """Returns an unique string representation of this graph."""
00032         s = "<Graph: "
00033         keys = self._adjacency_list.keys()
00034         keys.sort()
00035         for key in keys:
00036             values = [(x,self._edge_map[(key,x)]) \
00037                       for x in self._adjacency_list[key].list()]
00038             values.sort()
00039             s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")" 
00040         return s + ">"
00041 
00042     def __str__(self):
00043         """Returns a concise string description of this graph."""
00044         nodenum = len(self._adjacency_list.keys())
00045         edgenum = reduce(lambda x,y: x+y,
00046                          map(len, self._adjacency_list.values()))
00047         labelnum = len(self._label_map.keys())
00048         return "<Graph: " + \
00049                str(nodenum) + " node(s), " + \
00050                str(edgenum) + " edge(s), " + \
00051                str(labelnum) + " unique label(s)>"
00052 
00053     def add_node(self, node):
00054         """Adds a node to this graph."""
00055         if node not in self._adjacency_list:
00056             self._adjacency_list[node] = set()
00057 
00058     def add_edge(self, source, to, label = None):
00059         """Adds an edge to this graph."""
00060         if source not in self._adjacency_list:
00061             raise ValueError("Unknown <from> node: " + str(source))
00062         if to not in self._adjacency_list:
00063             raise ValueError("Unknown <to> node: " + str(to))
00064         if (source,to) in self._edge_map:
00065             raise ValueError(str(source) + " -> " + str(to) + " exists")
00066         self._adjacency_list[source].add(to)
00067         if label not in self._label_map:
00068             self._label_map[label] = set()
00069         self._label_map[label].add((source,to))
00070         self._edge_map[(source,to)] = label
00071 
00072     def child_edges(self, parent):
00073         """Returns a list of (child, label) pairs for parent."""
00074         if parent not in self._adjacency_list:
00075             raise ValueError("Unknown <parent> node: " + str(parent))
00076         return [(x, self._edge_map[(parent,x)]) \
00077                 for x in sorted(self._adjacency_list[parent])]
00078 
00079     def children(self, parent):
00080         """Returns a list of unique children for parent."""
00081         return sorted(self._adjacency_list[parent])
00082 
00083     def edges(self, label):
00084         """Returns a list of all the edges with this label."""
00085         if label not in self._label_map:
00086             raise ValueError("Unknown label: " + str(label))
00087         return self._label_map[label].list()
00088 
00089     def labels(self):
00090         """Returns a list of all the edge labels in this graph."""
00091         return self._label_map.keys()
00092 
00093     def nodes(self):
00094         """Returns a list of the nodes in this graph."""
00095         return self._adjacency_list.keys()
00096 
00097     def parent_edges(self, child):
00098         """Returns a list of (parent, label) pairs for child."""
00099         if child not in self._adjacency_list:
00100             raise ValueError("Unknown <child> node: " + str(child))
00101         parents = []
00102         for parent, children in self._adjacency_list.iteritems():
00103             for x in children:
00104                 if x is child:
00105                     parents.append((parent, self._edge_map[(parent, child)]))
00106         return sorted(parents)
00107 
00108     def parents(self, child):
00109         """Returns a list of unique parents for child."""
00110         return sorted(set([x[0] for x in self.parent_edges(child)]))
00111 
00112     def remove_node(self, node):
00113         """Removes node and all edges connected to it."""
00114         if node not in self._adjacency_list:
00115             raise ValueError("Unknown node: " + str(node))
00116         # remove node (and all out-edges) from adjacency list
00117         del self._adjacency_list[node]
00118         # remove all in-edges from adjacency list
00119         for n in self._adjacency_list.keys():
00120             self._adjacency_list[n] = set(x for x in self._adjacency_list[n] \
00121                                           if x is not node)
00122         # remove all refering pairs in label map
00123         for label in self._label_map.keys():
00124             lm = set(x for x in self._label_map[label] \
00125                      if (x[0] is not node) and (x[1] is not node))
00126             # remove the entry completely if the label is now unused
00127             if lm:
00128                 self._label_map[label] = lm
00129             else:
00130                 del self._label_map[label]
00131         # remove all refering entries in edge map
00132         for edge in self._edge_map.keys():
00133             if edge[0] is node or edge[1] is node:
00134                 del self._edge_map[edge]
00135         
00136     def remove_edge(self, parent, child, label):
00137         """Removes edge. -- NOT IMPLEMENTED"""
00138         # hm , this is a multigraph - how should this be implemented?
00139         raise NotImplementedError("remove_edge is not yet implemented")
00140 
00141 
00142