TEES.Core.SimpleGraph

1 """ 2 For representing the event argument and dependency graphs. Should be deterministic. 3 """ 4 import sys 5

6 -class Graph:

7 """ 8 One edge per-associated data per direction 9 """

10 - def __init__(self, directed=True):

11 self.__directed = directed 12 self.nodes = [] 13 self.edges = [] 14 self.__matrix = {} 15 self.__resetAnalyses()

16

17 - def __resetAnalyses(self):

18 self.__distances = None 19 self.__nextInPath = None

20

21 - def isDirected(self):

22 return self.__directed

23

24 - def toUndirected(self):

25 g = Graph(False) 26 g.addNodes(self.nodes) 27 g.addEdges(self.edges) 28 return g

29

30 - def addNode(self, node):

31 if node in self.__matrix: 32 return False 33 self.__resetAnalyses() 34 self.nodes.append(node) 35 self.__matrix[node] = {} 36 return True

37

38 - def addNodes(self, nodes):

39 self.__resetAnalyses() 40 nodesAdded = False 41 for node in nodes: 42 if node not in self.__matrix: 43 nodesAdded = True 44 self.nodes.append(node) 45 self.__matrix[node] = {} 46 return nodesAdded

47

48 - def addEdge(self, node1, node2, data=None):

49 self.__resetAnalyses() 50 self.addNode(node1) 51 self.addNode(node2) 52 # add forward edge 53 forward = not self.hasEdge(node1, node2, data) 54 if forward: 55 self.__insertEdge(node1, node2, data) 56 # add reverse edge 57 reverse = False 58 if not self.isDirected(): 59 reverse = not self.hasEdge(node2, node1, data) 60 if reverse: 61 self.__insertEdge(node2, node1, data) 62 return forward or reverse

63

64 - def addEdgeTuple(self, edge):

65 self.__resetAnalyses() 66 self.addNode(edge[0]) 67 self.addNode(edge[1]) 68 # add forward edge 69 forward = not self.hasEdgeTuple(edge) #not edge in self.edges 70 if forward: 71 self.edges.append(edge) 72 if not edge[1] in self.__matrix[edge[0]]: 73 self.__matrix[edge[0]][edge[1]] = [] 74 self.__matrix[edge[0]][edge[1]].append(edge) 75 # add reverse edge 76 reverse = False 77 if not self.isDirected(): 78 reverse = not self.hasEdge(edge[1], edge[0], edge[2]) 79 if reverse: 80 self.__insertEdge(edge[1], edge[0], edge[2]) 81 return forward or reverse

82

83 - def addEdges(self, edges):

84 for edge in edges: 85 self.addEdgeTuple(edge)

86

87 - def __insertEdge(self, node1, node2, data):

88 """ 89 Assumes edge doesn't exist already 90 """ 91 edge = (node1, node2, data) 92 self.edges.append(edge) 93 if not node2 in self.__matrix[node1]: 94 self.__matrix[node1][node2] = [] 95 self.__matrix[node1][node2].append(edge)

96

97 - def hasEdges(self, node1, node2):

98 assert node1 in self.__matrix, "Missing node 1: " + str(node1) 99 assert node2 in self.__matrix, "Missing node 2: " + str(node2) 100 #if not node1 in self.__matrix: 101 # return False 102 if not node2 in self.__matrix[node1]: 103 return False 104 elif len(self.__matrix[node1][node2]) > 0: 105 return True 106 else: 107 return False

108

109 - def hasEdge(self, node1, node2, data):

110 assert node1 in self.__matrix, "Missing node 1: " + str(node1) 111 assert node2 in self.__matrix, "Missing node 2: " + str(node2) 112 #if not node1 in self.__matrix: 113 # return False 114 if not node2 in self.__matrix[node1]: 115 return False 116 for edge in self.__matrix[node1][node2]: 117 if edge[2] == data: 118 return True 119 return False

120

121 - def hasEdgeTuple(self, edge):

122 assert edge[0] in self.__matrix, "Missing node 1: " + str(edge[0]) 123 assert edge[1] in self.__matrix, "Missing node 2: " + str(edge[1]) 124 #if not edge[0] in self.__matrix: 125 # return False 126 if not edge[1] in self.__matrix[edge[0]]: 127 return False 128 elif edge in self.__matrix[edge[0]][edge[1]]: 129 return True 130 else: 131 return False

132

133 - def getEdges(self, node1, node2):

134 assert node1 in self.__matrix, "Missing node 1: " + str(node1) 135 assert node2 in self.__matrix, "Missing node 2: " + str(node2) 136 #if not node1 in self.__matrix: 137 # return [] 138 if not node2 in self.__matrix[node1]: 139 return [] 140 else: 141 return self.__matrix[node1][node2]

142

143 - def getInEdges(self, node):

144 assert node in self.__matrix, "Missing node: " + str(node) 145 assert self.__directed 146 inEdges = [] 147 for edge in self.edges: 148 if edge[1] == node: 149 inEdges.append(edge) 150 return inEdges

151

152 - def getOutEdges(self, node):

153 assert node in self.__matrix, "Missing node: " + str(node) 154 assert self.__directed 155 outEdges = [] 156 for edge in self.edges: 157 if edge[0] == node: 158 outEdges.append(edge) 159 return outEdges

160

161 - def FloydWarshall(self, filterCallback=None, callbackArgs={}):

162 """ 163 From Wikipedia, modified to return all paths 164 """ 165 n = len(self.nodes) 166 self.__distances = {} 167 infinity = sys.maxint # at least it's a really large number 168 # Init distance matrix 169 for n1 in self.nodes: 170 self.__distances[n1] = {} 171 for n2 in self.nodes: 172 if n1 == n2: 173 self.__distances[n1][n2] = 0 174 elif len(self.getEdges(n1, n2)) > 0: 175 if filterCallback != None: # permanent implementation of the DDI hack 176 edgeCount = 0 177 for edge in self.getEdges(n1, n2): 178 if not filterCallback(edge, **callbackArgs): 179 edgeCount += 1 180 if edgeCount == 0: 181 self.__distances[n1][n2] = infinity 182 else: 183 self.__distances[n1][n2] = 1 184 elif False: # temporary hack for DDI 185 edgeCount = 0 186 for edge in self.getEdges(n1, n2): 187 if edge[2].get("type") != "conj_and": 188 edgeCount += 1 189 if edgeCount == 0: 190 self.__distances[n1][n2] = infinity 191 else: 192 self.__distances[n1][n2] = 1 193 else: 194 self.__distances[n1][n2] = 1 195 else: 196 self.__distances[n1][n2] = infinity 197 # Init path traversal matrix 198 self.__nextInPath = {} 199 for n1 in self.nodes: 200 self.__nextInPath[n1] = {} 201 for n2 in self.nodes: 202 self.__nextInPath[n1][n2] = None 203 # Calculate distances 204 d = self.__distances 205 for k in self.nodes: 206 for i in self.nodes: 207 if d[i][k] == infinity: 208 continue 209 for j in self.nodes: 210 if d[k][j] == infinity: 211 continue 212 # equal 213 if d[i][k] + d[k][j] < d[i][j]: 214 d[i][j] = d[i][k] + d[k][j] 215 for k in self.nodes: 216 for i in self.nodes: 217 if d[i][k] == infinity: 218 continue 219 for j in self.nodes: 220 if d[k][j] == infinity: 221 continue 222 # shorter or equal 223 if d[i][k] + d[k][j] <= d[i][j]: 224 if d[i][k] == 1 and k != j: 225 if self.__nextInPath[i][j] == None or d[i][k] + d[k][j] < d[i][j]: 226 self.__nextInPath[i][j] = [] 227 self.__nextInPath[i][j].append(k)

228 #self.showAnalyses() 229

230 - def resetAnalyses(self):

231 self.__nextInPath = None 232 self.__distances = None 233 self.__nextInPath = None

234

235 - def showAnalyses(self):

236 if self.__nextInPath == None: 237 self.FloydWarshall() 238 print "distances" 239 for k in sorted(self.__distances.keys()): 240 print ">", k, self.__distances[k] 241 print "next" 242 for k in sorted(self.__nextInPath.keys()): 243 print ">", k, self.__nextInPath[k]

244

245 - def getPaths(self, i, j, depth=0):

246 if self.__nextInPath == None: 247 self.FloydWarshall() 248 if self.__distances[i][j] == sys.maxint: # no path 249 return [] 250 intermediates = self.__nextInPath[i][j] 251 if intermediates == None: 252 return [[i, j]] # there is an edge from i to j, with no vertices between 253 else: 254 segments = [] 255 for intermediate in intermediates: 256 segments.extend( self.getPaths(intermediate,j, depth+1) ) 257 rvs = [] 258 for segment in segments: 259 rvs.append( [i] + segment ) 260 return rvs

261

262 - def getPathOldSinglePath(self, i, j):

263 if self.__nextInPath == None: 264 self.FloydWarshall() 265 if self.__distances[i][j] == sys.maxint: 266 return None 267 intermediate = self.__nextInPath[i][j] 268 if intermediate == None: 269 return [i, j] #; /* there is an edge from i to j, with no vertices between */ 270 else: 271 segment = self.getPath(intermediate,j) 272 return [i] + segment

273

274 - def getWalks(self, path, directed=False):

275 if directed: 276 assert self.__directed 277 return self.__getWalks(path, directed=directed)

278

279 - def __getWalks(self, path, position=1, walk=None, directed=False):

280 """ 281 A path is defined by a list of tokens. But since there can be more than one edge 282 between the same two tokens, there are multiple ways of getting from the first 283 token to the last token. This function returns all of these "walks", i.e. the combinations 284 of edges that can be travelled to get from the first to the last token of the path. 285 """ 286 allWalks = [] 287 if walk == None: 288 walk = [] 289 290 node1 = path[position-1] 291 node2 = path[position] 292 if node2 in self.__matrix[node1]: 293 edges = self.__matrix[node1][node2][:] # copied so that joining with reverse won't change original 294 else: 295 edges = [] 296 if (not directed) and self.__directed: # an undirected graph already has the reverse edges 297 if node1 in self.__matrix[node2]: 298 edges += self.__matrix[node2][node1] 299 for edge in edges: 300 if position < len(path)-1: 301 allWalks.extend(self.__getWalks(path, position+1, walk + [edge], directed)) 302 else: 303 allWalks.append(walk + [edge]) 304 return allWalks

305

306 - def toGraphviz(self, filename=None):

307 s = "digraph SimpleGraph {\nnode [shape=box];\n" 308 for node in self.nodes: 309 s += str(node) + ";\n" 310 for edge in self.edges: 311 s += str(edge[0]) + "->" + str(edge[1]) + ";\n" 312 s += "overlap=false;\nfontsize=12;\n}" 313 if filename != None: 314 f = open(filename, "wt") 315 f.write(s) 316 f.close() 317 return s

318

319 -def evaluate(code, repeats):

320 import time 321 tSum = 0.0 322 for repeat in range(repeats): 323 t0= time.clock() 324 code() 325 t= time.clock() - t0 # t is CPU seconds elapsed (floating point) 326 tSum += t 327 return tSum / repeats

328

329 -def speedSimple():

330 edges = [('st_2', 'st_1', 'split_1'), ('st_4', 'st_2', 'split_2'), ('st_4', 'st_3', 'split_3'), ('st_78', 'st_4', 'split_4'), ('st_10', 'st_7', 'split_5'), ('st_10', 'st_9', 'split_6'), ('st_13', 'st_10', 'split_7'), ('st_13', 'st_11', 'split_8'), ('st_13', 'st_12', 'split_9'), ('st_4', 'st_13', 'split_10'), ('st_15', 'st_14', 'split_11'), ('st_13', 'st_15', 'split_12'), ('st_20', 'st_17', 'split_13'), ('st_20', 'st_18', 'split_14'), ('st_20', 'st_19', 'split_15'), ('st_13', 'st_20', 'split_16'), ('st_27', 'st_24', 'split_17'), ('st_27', 'st_25', 'split_18'), ('st_27', 'st_26', 'split_19'), ('st_13', 'st_27', 'split_20'), ('st_27', 'st_28', 'split_21'), ('st_30', 'st_29', 'split_22'), ('st_28', 'st_30', 'split_23'), ('st_34', 'st_32', 'split_24'), ('st_34', 'st_33', 'split_25'), ('st_44', 'st_34', 'split_26'), ('st_34', 'st_36', 'split_27'), ('st_40', 'st_39', 'split_28'), ('st_34', 'st_40', 'split_29'), ('st_44', 'st_40', 'split_30'), ('st_40', 'st_42', 'split_31'), ('st_30', 'st_44', 'split_32'), ('st_66', 'st_47', 'split_33'), ('st_66', 'st_50', 'split_34'), ('st_57', 'st_54', 'split_35'), ('st_57', 'st_55', 'split_36'), ('st_57', 'st_56', 'split_37'), ('st_50', 'st_57', 'split_38'), ('st_63', 'st_61', 'split_39'), ('st_63', 'st_62', 'split_40'), ('st_66', 'st_63', 'split_41'), ('st_66', 'st_64', 'split_42'), ('st_66', 'st_65', 'split_43'), ('st_13', 'st_66', 'split_44'), ('st_66', 'st_67', 'split_45'), ('st_72', 'st_68', 'split_46'), ('st_72', 'st_69', 'split_47'), ('st_72', 'st_70', 'split_48'), ('st_72', 'st_71', 'split_49'), ('st_67', 'st_72', 'split_50'), ('st_13', 'st_75', 'split_51'), ('st_4', 'st_77', 'split_52'), ('st_82', 'st_80', 'split_53'), ('st_82', 'st_81', 'split_54'), ('st_78', 'st_82', 'split_55'), ('st_87', 'st_86', 'split_56'), ('st_82', 'st_87', 'split_57'), ('st_87', 'st_89', 'split_58'), ('st_95', 'st_92', 'split_59'), ('st_95', 'st_94', 'split_60'), ('st_100', 'st_95', 'split_61'), ('st_95', 'st_97', 'split_62'), ('st_95', 'st_99', 'split_63'), ('st_97', 'st_99', 'split_64'), ('st_78', 'st_100', 'split_65'), ('st_105', 'st_101', 'split_66'), ('st_105', 'st_102', 'split_67'), ('st_105', 'st_103', 'split_68'), ('st_105', 'st_104', 'split_69'), ('st_100', 'st_105', 'split_70'), ('st_108', 'st_107', 'split_71'), ('st_105', 'st_108', 'split_72'), ('st_114', 'st_111', 'split_73'), ('st_114', 'st_112', 'split_74'), ('st_114', 'st_113', 'split_75'), ('st_100', 'st_114', 'split_76'), ('st_105', 'st_114', 'split_77'), ('st_114', 'st_116', 'split_78'), ('st_120', 'st_116', 'split_79'), ('st_120', 'st_118', 'split_80'), ('st_120', 'st_119', 'split_81'), ('st_116', 'st_120', 'split_82'), ('st_126', 'st_122', 'split_83'), ('st_126', 'st_123', 'split_84'), ('st_126', 'st_124', 'split_85'), ('st_126', 'st_125', 'split_86'), ('st_120', 'st_126', 'split_87'), ('st_132', 'st_129', 'split_88'), ('st_132', 'st_131', 'split_89'), ('st_136', 'st_132', 'split_90'), ('st_135', 'st_134', 'split_91'), ('st_132', 'st_135', 'split_92'), ('st_78', 'st_136', 'split_93'), ('st_141', 'st_137', 'split_94'), ('st_141', 'st_138', 'split_95'), ('st_141', 'st_139', 'split_96'), ('st_141', 'st_140', 'split_97'), ('st_136', 'st_141', 'split_98'), ('st_144', 'st_141', 'split_99'), ('st_144', 'st_143', 'split_100'), ('st_141', 'st_144', 'split_101'), ('st_146', 'st_145', 'split_102'), ('st_144', 'st_146', 'split_103'), ('st_144', 'st_148', 'split_104'), ('st_78', 'st_152', 'split_105'), ('st_78', 'st_154', 'split_106'), ('st_164', 'st_155', 'split_107'), ('st_160', 'st_157', 'split_108'), ('st_160', 'st_158', 'split_109'), ('st_160', 'st_159', 'split_110'), ('st_155', 'st_160', 'split_111'), ('st_163', 'st_162', 'split_112'), ('st_164', 'st_163', 'split_113'), ('st_78', 'st_164', 'split_114'), ('st_166', 'st_165', 'split_115'), ('st_164', 'st_166', 'split_116'), ('st_169', 'st_168', 'split_117'), ('st_164', 'st_169', 'split_118'), ('st_166', 'st_169', 'split_119'), ('st_54', 'st_52', None), ('st_61', 'st_59', None), ('st_86', 'st_84', None)] 331 g = Graph() 332 g.addEdges(edges)

333

334 -def speedNX():

335 edges = [('st_2', 'st_1', 'split_1'), ('st_4', 'st_2', 'split_2'), ('st_4', 'st_3', 'split_3'), ('st_78', 'st_4', 'split_4'), ('st_10', 'st_7', 'split_5'), ('st_10', 'st_9', 'split_6'), ('st_13', 'st_10', 'split_7'), ('st_13', 'st_11', 'split_8'), ('st_13', 'st_12', 'split_9'), ('st_4', 'st_13', 'split_10'), ('st_15', 'st_14', 'split_11'), ('st_13', 'st_15', 'split_12'), ('st_20', 'st_17', 'split_13'), ('st_20', 'st_18', 'split_14'), ('st_20', 'st_19', 'split_15'), ('st_13', 'st_20', 'split_16'), ('st_27', 'st_24', 'split_17'), ('st_27', 'st_25', 'split_18'), ('st_27', 'st_26', 'split_19'), ('st_13', 'st_27', 'split_20'), ('st_27', 'st_28', 'split_21'), ('st_30', 'st_29', 'split_22'), ('st_28', 'st_30', 'split_23'), ('st_34', 'st_32', 'split_24'), ('st_34', 'st_33', 'split_25'), ('st_44', 'st_34', 'split_26'), ('st_34', 'st_36', 'split_27'), ('st_40', 'st_39', 'split_28'), ('st_34', 'st_40', 'split_29'), ('st_44', 'st_40', 'split_30'), ('st_40', 'st_42', 'split_31'), ('st_30', 'st_44', 'split_32'), ('st_66', 'st_47', 'split_33'), ('st_66', 'st_50', 'split_34'), ('st_57', 'st_54', 'split_35'), ('st_57', 'st_55', 'split_36'), ('st_57', 'st_56', 'split_37'), ('st_50', 'st_57', 'split_38'), ('st_63', 'st_61', 'split_39'), ('st_63', 'st_62', 'split_40'), ('st_66', 'st_63', 'split_41'), ('st_66', 'st_64', 'split_42'), ('st_66', 'st_65', 'split_43'), ('st_13', 'st_66', 'split_44'), ('st_66', 'st_67', 'split_45'), ('st_72', 'st_68', 'split_46'), ('st_72', 'st_69', 'split_47'), ('st_72', 'st_70', 'split_48'), ('st_72', 'st_71', 'split_49'), ('st_67', 'st_72', 'split_50'), ('st_13', 'st_75', 'split_51'), ('st_4', 'st_77', 'split_52'), ('st_82', 'st_80', 'split_53'), ('st_82', 'st_81', 'split_54'), ('st_78', 'st_82', 'split_55'), ('st_87', 'st_86', 'split_56'), ('st_82', 'st_87', 'split_57'), ('st_87', 'st_89', 'split_58'), ('st_95', 'st_92', 'split_59'), ('st_95', 'st_94', 'split_60'), ('st_100', 'st_95', 'split_61'), ('st_95', 'st_97', 'split_62'), ('st_95', 'st_99', 'split_63'), ('st_97', 'st_99', 'split_64'), ('st_78', 'st_100', 'split_65'), ('st_105', 'st_101', 'split_66'), ('st_105', 'st_102', 'split_67'), ('st_105', 'st_103', 'split_68'), ('st_105', 'st_104', 'split_69'), ('st_100', 'st_105', 'split_70'), ('st_108', 'st_107', 'split_71'), ('st_105', 'st_108', 'split_72'), ('st_114', 'st_111', 'split_73'), ('st_114', 'st_112', 'split_74'), ('st_114', 'st_113', 'split_75'), ('st_100', 'st_114', 'split_76'), ('st_105', 'st_114', 'split_77'), ('st_114', 'st_116', 'split_78'), ('st_120', 'st_116', 'split_79'), ('st_120', 'st_118', 'split_80'), ('st_120', 'st_119', 'split_81'), ('st_116', 'st_120', 'split_82'), ('st_126', 'st_122', 'split_83'), ('st_126', 'st_123', 'split_84'), ('st_126', 'st_124', 'split_85'), ('st_126', 'st_125', 'split_86'), ('st_120', 'st_126', 'split_87'), ('st_132', 'st_129', 'split_88'), ('st_132', 'st_131', 'split_89'), ('st_136', 'st_132', 'split_90'), ('st_135', 'st_134', 'split_91'), ('st_132', 'st_135', 'split_92'), ('st_78', 'st_136', 'split_93'), ('st_141', 'st_137', 'split_94'), ('st_141', 'st_138', 'split_95'), ('st_141', 'st_139', 'split_96'), ('st_141', 'st_140', 'split_97'), ('st_136', 'st_141', 'split_98'), ('st_144', 'st_141', 'split_99'), ('st_144', 'st_143', 'split_100'), ('st_141', 'st_144', 'split_101'), ('st_146', 'st_145', 'split_102'), ('st_144', 'st_146', 'split_103'), ('st_144', 'st_148', 'split_104'), ('st_78', 'st_152', 'split_105'), ('st_78', 'st_154', 'split_106'), ('st_164', 'st_155', 'split_107'), ('st_160', 'st_157', 'split_108'), ('st_160', 'st_158', 'split_109'), ('st_160', 'st_159', 'split_110'), ('st_155', 'st_160', 'split_111'), ('st_163', 'st_162', 'split_112'), ('st_164', 'st_163', 'split_113'), ('st_78', 'st_164', 'split_114'), ('st_166', 'st_165', 'split_115'), ('st_164', 'st_166', 'split_116'), ('st_169', 'st_168', 'split_117'), ('st_164', 'st_169', 'split_118'), ('st_166', 'st_169', 'split_119'), ('st_54', 'st_52', None), ('st_61', 'st_59', None), ('st_86', 'st_84', None)] 336 g = NX10.MultiDiGraph() 337 for edge in edges: 338 g.add_edge(edge[0], edge[1], data=edge[2])

339 340 if __name__=="__main__": 341 from optparse import OptionParser 342 # Import Psyco if available 343 try: 344 import psyco 345 psyco.full() 346 print >> sys.stderr, "Found Psyco, using" 347 except ImportError: 348 print >> sys.stderr, "Psyco not installed" 349 350 if True: 351 g = Graph() 352 print g 353 g.addNodes([1, 2, 3, 4, 5, 6]) 354 g.addEdge(1,2) 355 g.addEdge(2,3) 356 g.addEdge(1,4) 357 g.addEdge(4,3) 358 g.addEdge(4,3,"Test") 359 g.addEdge(3,6) 360 g.addEdge(6,1) 361 print "nodes", g.nodes 362 print "edges", g.edges 363 u = g.toUndirected() 364 paths = g.getPaths(1,3) 365 print g.showAnalyses() 366 print "undir nodes", u.nodes 367 print "undir edges", u.edges 368 print u.showAnalyses() 369 print "Paths 1->3", paths 370 print "Undirected Paths 1->3", u.getPaths(1,3) 371 print "Paths 4->3", g.getPaths(4,3) 372 print "Paths 4->5", g.getPaths(4,5) 373 print "Walks 1->3" 374 for p in paths: 375 print "Walks for path", p, ":", g.getWalks(p) 376 print "Walks 4->5", g.getWalks([4,5]) 377 print "Walks 1->6->3", g.getWalks([1,6,3], True) 378 print "Walks 1->6->3 (undirected walks from directed graph)", g.getWalks([1,6,3]) 379 print "Walks 1->6->3 from undirected", u.getWalks([1,6,3]) 380 print "Hard case" 381 g = Graph() 382 #g.addEdges([('st_4', 'st_3', 'split_1'), ('st_1', 'st_4', 'split_2'), ('st_11', 'st_6', 'split_3'), ('st_6', 'st_8', 'split_4'), ('st_11', 'st_10', 'split_5'), ('st_1', 'st_11', 'split_6'), ('st_4', 'st_11', 'split_7'), ('st_14', 'st_13', 'split_8'), ('st_1', 'st_14', 'split_9'), ('st_17', 'st_16', 'split_10'), ('st_14', 'st_17', 'split_11'), ('st_21', 'st_19', 'split_12'), ('st_21', 'st_20', 'split_13'), ('st_14', 'st_21', 'split_14'), ('st_26', 'st_23', 'split_15'), ('st_26', 'st_24', 'split_16'), ('st_26', 'st_25', 'split_17'), ('st_21', 'st_26', 'split_18'), ('st_26', 'st_27', 'split_19')]) 383 g.addEdges([('st_2', 'st_1', 'split_1'), ('st_4', 'st_2', 'split_2'), ('st_4', 'st_3', 'split_3'), ('st_78', 'st_4', 'split_4'), ('st_10', 'st_7', 'split_5'), ('st_10', 'st_9', 'split_6'), ('st_13', 'st_10', 'split_7'), ('st_13', 'st_11', 'split_8'), ('st_13', 'st_12', 'split_9'), ('st_4', 'st_13', 'split_10'), ('st_15', 'st_14', 'split_11'), ('st_13', 'st_15', 'split_12'), ('st_20', 'st_17', 'split_13'), ('st_20', 'st_18', 'split_14'), ('st_20', 'st_19', 'split_15'), ('st_13', 'st_20', 'split_16'), ('st_27', 'st_24', 'split_17'), ('st_27', 'st_25', 'split_18'), ('st_27', 'st_26', 'split_19'), ('st_13', 'st_27', 'split_20'), ('st_27', 'st_28', 'split_21'), ('st_30', 'st_29', 'split_22'), ('st_28', 'st_30', 'split_23'), ('st_34', 'st_32', 'split_24'), ('st_34', 'st_33', 'split_25'), ('st_44', 'st_34', 'split_26'), ('st_34', 'st_36', 'split_27'), ('st_40', 'st_39', 'split_28'), ('st_34', 'st_40', 'split_29'), ('st_44', 'st_40', 'split_30'), ('st_40', 'st_42', 'split_31'), ('st_30', 'st_44', 'split_32'), ('st_66', 'st_47', 'split_33'), ('st_66', 'st_50', 'split_34'), ('st_57', 'st_54', 'split_35'), ('st_57', 'st_55', 'split_36'), ('st_57', 'st_56', 'split_37'), ('st_50', 'st_57', 'split_38'), ('st_63', 'st_61', 'split_39'), ('st_63', 'st_62', 'split_40'), ('st_66', 'st_63', 'split_41'), ('st_66', 'st_64', 'split_42'), ('st_66', 'st_65', 'split_43'), ('st_13', 'st_66', 'split_44'), ('st_66', 'st_67', 'split_45'), ('st_72', 'st_68', 'split_46'), ('st_72', 'st_69', 'split_47'), ('st_72', 'st_70', 'split_48'), ('st_72', 'st_71', 'split_49'), ('st_67', 'st_72', 'split_50'), ('st_13', 'st_75', 'split_51'), ('st_4', 'st_77', 'split_52'), ('st_82', 'st_80', 'split_53'), ('st_82', 'st_81', 'split_54'), ('st_78', 'st_82', 'split_55'), ('st_87', 'st_86', 'split_56'), ('st_82', 'st_87', 'split_57'), ('st_87', 'st_89', 'split_58'), ('st_95', 'st_92', 'split_59'), ('st_95', 'st_94', 'split_60'), ('st_100', 'st_95', 'split_61'), ('st_95', 'st_97', 'split_62'), ('st_95', 'st_99', 'split_63'), ('st_97', 'st_99', 'split_64'), ('st_78', 'st_100', 'split_65'), ('st_105', 'st_101', 'split_66'), ('st_105', 'st_102', 'split_67'), ('st_105', 'st_103', 'split_68'), ('st_105', 'st_104', 'split_69'), ('st_100', 'st_105', 'split_70'), ('st_108', 'st_107', 'split_71'), ('st_105', 'st_108', 'split_72'), ('st_114', 'st_111', 'split_73'), ('st_114', 'st_112', 'split_74'), ('st_114', 'st_113', 'split_75'), ('st_100', 'st_114', 'split_76'), ('st_105', 'st_114', 'split_77'), ('st_114', 'st_116', 'split_78'), ('st_120', 'st_116', 'split_79'), ('st_120', 'st_118', 'split_80'), ('st_120', 'st_119', 'split_81'), ('st_116', 'st_120', 'split_82'), ('st_126', 'st_122', 'split_83'), ('st_126', 'st_123', 'split_84'), ('st_126', 'st_124', 'split_85'), ('st_126', 'st_125', 'split_86'), ('st_120', 'st_126', 'split_87'), ('st_132', 'st_129', 'split_88'), ('st_132', 'st_131', 'split_89'), ('st_136', 'st_132', 'split_90'), ('st_135', 'st_134', 'split_91'), ('st_132', 'st_135', 'split_92'), ('st_78', 'st_136', 'split_93'), ('st_141', 'st_137', 'split_94'), ('st_141', 'st_138', 'split_95'), ('st_141', 'st_139', 'split_96'), ('st_141', 'st_140', 'split_97'), ('st_136', 'st_141', 'split_98'), ('st_144', 'st_141', 'split_99'), ('st_144', 'st_143', 'split_100'), ('st_141', 'st_144', 'split_101'), ('st_146', 'st_145', 'split_102'), ('st_144', 'st_146', 'split_103'), ('st_144', 'st_148', 'split_104'), ('st_78', 'st_152', 'split_105'), ('st_78', 'st_154', 'split_106'), ('st_164', 'st_155', 'split_107'), ('st_160', 'st_157', 'split_108'), ('st_160', 'st_158', 'split_109'), ('st_160', 'st_159', 'split_110'), ('st_155', 'st_160', 'split_111'), ('st_163', 'st_162', 'split_112'), ('st_164', 'st_163', 'split_113'), ('st_78', 'st_164', 'split_114'), ('st_166', 'st_165', 'split_115'), ('st_164', 'st_166', 'split_116'), ('st_169', 'st_168', 'split_117'), ('st_164', 'st_169', 'split_118'), ('st_166', 'st_169', 'split_119'), ('st_54', 'st_52', None), ('st_61', 'st_59', None), ('st_86', 'st_84', None)]) 384 #print "Paths 'st_14'->'st_6'", g.getPaths('st_14','st_6') 385 u = g.toUndirected() 386 #print "Undirected Paths 'st_14'->'st_6'", u.getPaths('st_14','st_6') 387 #print "Undirected Paths 'st_14'->'st_11'", u.getPaths('st_14','st_11') 388 #print "Walks", g.getWalks(['st_14', 'st_1', 'st_11']) 389 #print "Walks", g.getWalks(['st_14', 'st_1', 'st_11']) 390 #print "Walks", g.getWalks(['st_14', 'st_1', 'st_11']) 391 #print u.showAnalyses() 392 u.toGraphviz("vis.gv") 393 if True: 394 import timeit 395 edges = [('st_2', 'st_1', 'split_1'), ('st_4', 'st_2', 'split_2'), ('st_4', 'st_3', 'split_3'), ('st_78', 'st_4', 'split_4'), ('st_10', 'st_7', 'split_5'), ('st_10', 'st_9', 'split_6'), ('st_13', 'st_10', 'split_7'), ('st_13', 'st_11', 'split_8'), ('st_13', 'st_12', 'split_9'), ('st_4', 'st_13', 'split_10'), ('st_15', 'st_14', 'split_11'), ('st_13', 'st_15', 'split_12'), ('st_20', 'st_17', 'split_13'), ('st_20', 'st_18', 'split_14'), ('st_20', 'st_19', 'split_15'), ('st_13', 'st_20', 'split_16'), ('st_27', 'st_24', 'split_17'), ('st_27', 'st_25', 'split_18'), ('st_27', 'st_26', 'split_19'), ('st_13', 'st_27', 'split_20'), ('st_27', 'st_28', 'split_21'), ('st_30', 'st_29', 'split_22'), ('st_28', 'st_30', 'split_23'), ('st_34', 'st_32', 'split_24'), ('st_34', 'st_33', 'split_25'), ('st_44', 'st_34', 'split_26'), ('st_34', 'st_36', 'split_27'), ('st_40', 'st_39', 'split_28'), ('st_34', 'st_40', 'split_29'), ('st_44', 'st_40', 'split_30'), ('st_40', 'st_42', 'split_31'), ('st_30', 'st_44', 'split_32'), ('st_66', 'st_47', 'split_33'), ('st_66', 'st_50', 'split_34'), ('st_57', 'st_54', 'split_35'), ('st_57', 'st_55', 'split_36'), ('st_57', 'st_56', 'split_37'), ('st_50', 'st_57', 'split_38'), ('st_63', 'st_61', 'split_39'), ('st_63', 'st_62', 'split_40'), ('st_66', 'st_63', 'split_41'), ('st_66', 'st_64', 'split_42'), ('st_66', 'st_65', 'split_43'), ('st_13', 'st_66', 'split_44'), ('st_66', 'st_67', 'split_45'), ('st_72', 'st_68', 'split_46'), ('st_72', 'st_69', 'split_47'), ('st_72', 'st_70', 'split_48'), ('st_72', 'st_71', 'split_49'), ('st_67', 'st_72', 'split_50'), ('st_13', 'st_75', 'split_51'), ('st_4', 'st_77', 'split_52'), ('st_82', 'st_80', 'split_53'), ('st_82', 'st_81', 'split_54'), ('st_78', 'st_82', 'split_55'), ('st_87', 'st_86', 'split_56'), ('st_82', 'st_87', 'split_57'), ('st_87', 'st_89', 'split_58'), ('st_95', 'st_92', 'split_59'), ('st_95', 'st_94', 'split_60'), ('st_100', 'st_95', 'split_61'), ('st_95', 'st_97', 'split_62'), ('st_95', 'st_99', 'split_63'), ('st_97', 'st_99', 'split_64'), ('st_78', 'st_100', 'split_65'), ('st_105', 'st_101', 'split_66'), ('st_105', 'st_102', 'split_67'), ('st_105', 'st_103', 'split_68'), ('st_105', 'st_104', 'split_69'), ('st_100', 'st_105', 'split_70'), ('st_108', 'st_107', 'split_71'), ('st_105', 'st_108', 'split_72'), ('st_114', 'st_111', 'split_73'), ('st_114', 'st_112', 'split_74'), ('st_114', 'st_113', 'split_75'), ('st_100', 'st_114', 'split_76'), ('st_105', 'st_114', 'split_77'), ('st_114', 'st_116', 'split_78'), ('st_120', 'st_116', 'split_79'), ('st_120', 'st_118', 'split_80'), ('st_120', 'st_119', 'split_81'), ('st_116', 'st_120', 'split_82'), ('st_126', 'st_122', 'split_83'), ('st_126', 'st_123', 'split_84'), ('st_126', 'st_124', 'split_85'), ('st_126', 'st_125', 'split_86'), ('st_120', 'st_126', 'split_87'), ('st_132', 'st_129', 'split_88'), ('st_132', 'st_131', 'split_89'), ('st_136', 'st_132', 'split_90'), ('st_135', 'st_134', 'split_91'), ('st_132', 'st_135', 'split_92'), ('st_78', 'st_136', 'split_93'), ('st_141', 'st_137', 'split_94'), ('st_141', 'st_138', 'split_95'), ('st_141', 'st_139', 'split_96'), ('st_141', 'st_140', 'split_97'), ('st_136', 'st_141', 'split_98'), ('st_144', 'st_141', 'split_99'), ('st_144', 'st_143', 'split_100'), ('st_141', 'st_144', 'split_101'), ('st_146', 'st_145', 'split_102'), ('st_144', 'st_146', 'split_103'), ('st_144', 'st_148', 'split_104'), ('st_78', 'st_152', 'split_105'), ('st_78', 'st_154', 'split_106'), ('st_164', 'st_155', 'split_107'), ('st_160', 'st_157', 'split_108'), ('st_160', 'st_158', 'split_109'), ('st_160', 'st_159', 'split_110'), ('st_155', 'st_160', 'split_111'), ('st_163', 'st_162', 'split_112'), ('st_164', 'st_163', 'split_113'), ('st_78', 'st_164', 'split_114'), ('st_166', 'st_165', 'split_115'), ('st_164', 'st_166', 'split_116'), ('st_169', 'st_168', 'split_117'), ('st_164', 'st_169', 'split_118'), ('st_166', 'st_169', 'split_119'), ('st_54', 'st_52', None), ('st_61', 'st_59', None), ('st_86', 'st_84', None)] 396 import Graph.networkx_v10rc1 as NX10 397 398 print "SimpleGraph: %.4f" % evaluate(speedSimple, 100) 399 print "NXGraph: %.4f" % evaluate(speedNX, 100) 400 401 # With full adjacency matrix: 402 # 403 # jari@jari-laptop:~/cvs_checkout/JariSandbox/ComplexPPI/Source/Core$ python SimpleGraph.py 404 # Found Psyco, using 405 # SimpleGraph: 0.0126 406 # NXGraph: 0.0011 407 # 408 # With adjancency matrix that doesn't have all keys: 409 # 410 # jari@jari-laptop:~/cvs_checkout/JariSandbox/ComplexPPI/Source/Core$ python SimpleGraph.py 411 # Found Psyco, using 412 # SimpleGraph: 0.0017 413 # NXGraph: 0.0010 414 # 415 # After replacing addEdgeTuple's "not edge in self.edges" with 416 # new method self.hasEdgeTuple(edge) 417 # 418 # jari@jari-laptop:~/cvs_checkout/JariSandbox/ComplexPPI/Source/Core$ python SimpleGraph.py 419 # Found Psyco, using 420 # SimpleGraph: 0.0005 421 # NXGraph: 0.0010 422

Source Code for Module TEES.Core.SimpleGraph