1
2
3
4
5
6
7 from Bio.Pathway.Rep.HashSet import *
8
10 """A directed graph abstraction with labeled edges."""
11
13 """Initializes a new Graph object."""
14 self.__adjacency_list = {}
15 for n in nodes:
16 self.__adjacency_list[n] = HashSet()
17 self.__label_map = {}
18 self.__edge_map = {}
19
21 """Returns true if g is equal to this graph."""
22 return isinstance(g, Graph) and \
23 (self.__adjacency_list == g.__adjacency_list) and \
24 (self.__label_map == g.__label_map) and \
25 (self.__edge_map == g.__edge_map)
26
28 """Returns true if g is not equal to this graph."""
29 return not self.__eq__(g)
30
32 """Returns an unique string representation of this graph."""
33 s = "<Graph: "
34 keys = self.__adjacency_list.keys()
35 keys.sort()
36 for key in keys:
37 values = [(x,self.__edge_map[(key,x)]) \
38 for x in self.__adjacency_list[key].list()]
39 values.sort()
40 s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")"
41 return s + ">"
42
44 """Returns a concise string description of this graph."""
45 nodenum = len(self.__adjacency_list.keys())
46 edgenum = reduce(lambda x,y: x+y,
47 map(len, self.__adjacency_list.values()))
48 labelnum = len(self.__label_map.keys())
49 return "<Graph: " + \
50 str(nodenum) + " node(s), " + \
51 str(edgenum) + " edge(s), " + \
52 str(labelnum) + " unique label(s)>"
53
55 """Adds a node to this graph."""
56 if node not in self.__adjacency_list:
57 self.__adjacency_list[node] = HashSet()
58
59 - def add_edge(self, source, to, label = None):
60 """Adds an edge to this graph."""
61 if source not in self.__adjacency_list:
62 raise ValueError("Unknown <from> node: " + str(source))
63 if to not in self.__adjacency_list:
64 raise ValueError("Unknown <to> node: " + str(to))
65 if (source,to) in self.__edge_map:
66 raise ValueError(str(source) + " -> " + str(to) + " exists")
67 self.__adjacency_list[source].add(to)
68 if label not in self.__label_map:
69 self.__label_map[label] = HashSet()
70 self.__label_map[label].add((source,to))
71 self.__edge_map[(source,to)] = label
72
74 """Returns a list of (child, label) pairs for parent."""
75 if parent not in self.__adjacency_list:
76 raise ValueError("Unknown <parent> node: " + str(parent))
77 return [(x, self.__edge_map[(parent,x)]) \
78 for x in self.__adjacency_list[parent].list()]
79
81 """Returns a list of unique children for parent."""
82 return self.__adjacency_list[parent].list()
83
85 """Returns a list of all the edges with this label."""
86 if label not in self.__label_map:
87 raise ValueError("Unknown label: " + str(label))
88 return self.__label_map[label].list()
89
91 """Returns a list of all the edge labels in this graph."""
92 return self.__label_map.keys()
93
95 """Returns a list of the nodes in this graph."""
96 return self.__adjacency_list.keys()
97
99 """Returns a list of (parent, label) pairs for child."""
100 if child not in self.__adjacency_list:
101 raise ValueError("Unknown <child> node: " + str(child))
102 parents = []
103 for parent in self.__adjacency_list.keys():
104 children = self.__adjacency_list[parent]
105 for x in children.list():
106 if x is child:
107 parents.append((parent, self.__edge_map[(parent, child)]))
108 return parents
109
114
116 """Removes node and all edges connected to it."""
117 if node not in self.__adjacency_list:
118 raise ValueError("Unknown node: " + str(node))
119
120 del self.__adjacency_list[node]
121
122 for n in self.__adjacency_list.keys():
123 self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x is not node,
124 self.__adjacency_list[n].list()))
125
126 for label in self.__label_map.keys():
127 lm = HashSet(filter(lambda x,node=node: \
128 (x[0] is not node) and (x[1] is not node),
129 self.__label_map[label].list()))
130
131 if lm.empty():
132 del self.__label_map[label]
133 else:
134 self.__label_map[label] = lm
135
136 for edge in self.__edge_map.keys():
137 if edge[0] is node or edge[1] is node:
138 del self.__edge_map[edge]
139
141 """Removes edge. -- NOT IMPLEMENTED"""
142
143 raise NotImplementedError("remove_edge is not yet implemented")
144