1 """
2 Base class for XGraph.
3
4 XGraph allows self-loops and multiple edges
5 with arbitrary (hashable) objects as
6 nodes and arbitrary objects associated with edges.
7
8 Examples
9 ========
10
11 Create an empty graph structure (a "null graph") with no nodes and no edges
12
13 >>> from networkx import *
14 >>> G=XGraph() # default no self-loops, no multiple edges
15
16 You can add nodes in the same way as the simple Graph class
17 >>> G.add_nodes_from(xrange(100,110))
18
19 You can add edges as for simple Graph class, but with optional edge
20 data/labels/objects.
21
22 >>> G.add_edges_from([(1,2,0.776),(1,3,0.535)])
23
24 For graph coloring problems, one could use
25 >>> G.add_edges_from([(1,2,"blue"),(1,3,"red")])
26
27 """
28 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
29
30
31
32
33
34
35
36
37
38
39 from networkx.graph import Graph
40 from networkx.exception import NetworkXException, NetworkXError
41 import networkx.convert as convert
42
44 """A class implementing general undirected graphs, allowing
45 (optional) self-loops, multiple edges, arbitrary (hashable)
46 objects as nodes and arbitrary objects associated with
47 edges.
48
49 An XGraph edge is specified by a 3-tuple e=(n1,n2,x),
50 where n1 and n2 are nodes (hashable objects) and x is an
51 arbitrary (and not necessarily unique) object associated with that
52 edge.
53
54 >>> G=XGraph()
55
56 creates an empty simple and undirected graph (no self-loops or
57 multiple edges allowed). It is equivalent to the expression:
58
59 >>> G=XGraph(name='',selfloops=False,multiedges=False)
60
61 >>> G=XGraph(name="empty",multiedges=True)
62
63 creates an empty graph with G.name="empty", that does not allow
64 the addition of self-loops but does allow for multiple edges.
65
66 See also the XDiGraph class.
67
68
69 XGraph inherits from Graph, overriding the following methods:
70
71 - __init__
72 - add_edge
73 - add_edges_from
74 - has_edge, has_neighbor
75 - get_edge
76 - edges_iter
77 - delete_edge
78 - delete_edges_from
79 - degree_iter
80 - to_directed
81 - copy
82 - subgraph
83
84 XGraph adds the following methods to those of Graph:
85
86 - delete_multiedge
87 - nodes_with_selfloops
88 - selfloop_edges
89 - number_of_selfloops
90 - allow_selfloops
91 - remove_all_selfloops
92 - ban_selfloops
93 - allow_multiedges
94 - remove_all_multiedges
95 - ban_multiedges
96
97 """
98
99
100 - def __init__(self, data=None, name='', selfloops=False, multiedges=False):
101 """Initialize XGraph.
102
103 Optional arguments::
104 name: graph name (default='')
105 selfloops: if True selfloops are allowed (default=False)
106 multiedges: if True multiple edges are allowed (default=False)
107
108 """
109 self.adj={}
110 self.selfloops=selfloops
111 self.multiedges=multiedges
112 if data is not None:
113 self=convert.from_whatever(data,create_using=self)
114 self.name=name
115
117 """Return the neighbors of node n as a list.
118
119 This provides graph G the natural property that G[n] returns
120 the neighbors of G.
121
122 """
123 return list(self.neighbors_iter(n))
124
125 - def add_edge(self, n1, n2=None, x=None):
126 """Add a single edge to the graph.
127
128 Can be called as G.add_edge(n1,n2,x) or as
129 G.add_edge(e), where e=(n1,n2,x).
130
131 n1,n2 are node objects, and are added to the Graph if not already
132 present. Nodes must be hashable Python objects (except None).
133
134 x is an arbitrary (not necessarily hashable) object associated
135 with this edge. It can be used to associate one or more:
136 labels, data records, weights or any arbirary objects to
137 edges. The default is the Python None.
138
139 For example, if the graph G was created with
140
141 >>> G=XGraph()
142
143 then G.add_edge(1,2,"blue") will add the edge (1,2,"blue").
144
145 If G.multiedges=False, then a subsequent G.add_edge(1,2,"red")
146 will change the above edge (1,2,"blue") into the edge (1,2,"red").
147
148
149 If G.multiedges=True, then two successive calls to
150 G.add_edge(1,2,"red") will result in 2 edges of the form
151 (1,2,"red") that can not be distinguished from one another.
152
153 G.add_edge(1,2,"green") will add both edges (1,2,X) and (2,1,X).
154
155 If self.selfloops=False, then calling add_edge(n1,n1,x) will have no
156 effect on the Graph.
157
158 Objects associated to an edge can be retrieved using edges(),
159 edge_iter(), or get_edge().
160
161 """
162 if n2 is None:
163 if len(n1)==3:
164 n1,n2,x=n1
165 else:
166 n1,n2=n1
167
168
169 if not self.multiedges and self.has_edge(n1,n2,x):
170 return
171
172
173 if n1 not in self.adj:
174 self.adj[n1]={}
175 if n2 not in self.adj:
176 self.adj[n2]={}
177
178
179 if not self.selfloops and n1==n2:
180 return
181
182 if self.multiedges:
183
184 self.adj[n1][n2]=self.adj[n1].get(n2,[])+ [x]
185 if n1!=n2:
186 self.adj[n2][n1]=self.adj[n2].get(n1,[])+ [x]
187 else:
188 self.adj[n1][n2]=x
189 if n1!=n2:
190 self.adj[n2][n1]=x
191
192
193
195 """Add multiple edges to the graph.
196
197 ebunch: Container of edges. Each edge must be a 3-tuple
198 (n1,n2,x) or a 2-tuple (n1,n2). See add_edge documentation.
199
200 The container must be iterable or an iterator. It is iterated
201 over once.
202
203 """
204 for e in ebunch:
205 self.add_edge(e)
206
207 - def has_edge(self, n1, n2=None, x=None):
208 """Return True if graph contains edge (n1,n2,x).
209
210 Can be called as G.has_edge(n1,n2,x)
211 or as G.has_edge(e), where e=(n1,n2,x).
212
213 If x is unspecified or None, i.e. if called with an edge of the form
214 e=(n1,n2), then return True if there exists ANY edge between
215 n1 and n2 (equivalent to has_neighbor(n1,n2))
216
217 """
218 if n2 is None:
219
220 if len(n1)==3:
221 n1,n2,x=n1
222 else:
223 n1,n2=n1
224 return self.has_neighbor(n1,n2)
225 else:
226 if x is None:
227
228
229
230 return self.has_neighbor(n1,n2)
231
232 if self.multiedges:
233 return (self.adj.has_key(n1) and
234 self.adj[n1].has_key(n2) and
235 x in self.adj[n1][n2])
236 else:
237 return (self.adj.has_key(n1) and
238 self.adj[n1].has_key(n2) and
239 x==self.adj[n1][n2])
240
241
243 """Return True if node n1 has neighbor n2.
244
245 Note that this returns True if there exists ANY edge (n1,n2,x)
246 for some x.
247
248 """
249 return (self.adj.has_key(n1) and
250 self.adj[n1].has_key(n2))
251
253 """Return an iterator of nodes connected to node n.
254
255 Returns the same data as edges(n) but in a different format.
256
257 """
258 if not self.multiedges:
259 try:
260 for nbr in self.adj[n].iterkeys():
261 yield nbr
262 except KeyError:
263 raise NetworkXError, "node %s not in graph"%(n,)
264 else:
265 if n not in self:
266 raise NetworkXError, "node %s not in graph"%(n,)
267 for (u,v,d) in self.edges_iter(n):
268 yield v
269
271 """Return a list of nodes connected to node n. """
272 return list(self.neighbors_iter(n))
273
275 """Return an iterator over the objects associated with each edge
276 from node u to node v.
277
278 """
279 try:
280 data = self.adj[u][v]
281 except KeyError:
282 raise NetworkXError, "Edge (%s,%s) requested via get_edge_iter does not exist."%(u,v)
283 if self.multiedges:
284 for d in data:
285 yield d
286 else:
287 yield data
288
290 """Return the objects associated with each edge from node u to node v.
291
292 If multiedges=False, a single object is returned.
293 If multiedges=True, a list of objects is returned.
294 If no edge exists, None is returned.
295
296 """
297 try:
298 data=self.adj[u][v]
299 except KeyError:
300 raise NetworkXError, "Edge (%s,%s) requested via get_edge does not exist."%(u,v)
301 if self.multiedges:
302 return data[:]
303 return data
304
306 """Return iterator that iterates once over each edge adjacent
307 to nodes in nbunch, or over all nodes in graph if nbunch=None.
308
309 If nbunch is None return all edges in the graph.
310 The argument nbunch can be any single node, or
311 any sequence or iterator of nodes.
312 Nodes in nbunch that are not in the graph will be (quietly) ignored.
313
314 """
315
316 if nbunch is None:
317 bunch=self.nodes_iter()
318 elif nbunch in self:
319 bunch=[nbunch]
320 else:
321 try: bunch=[n for n in nbunch if n in self]
322 except TypeError:
323 bunch=[]
324
325 seen={}
326 if self.multiedges:
327 for n1 in bunch:
328 for n2,elist in self.adj[n1].iteritems():
329 if n2 not in seen:
330 for data in elist:
331 yield (n1,n2,data)
332 seen[n1]=1
333 else:
334 for n1 in bunch:
335 for n2,data in self.adj[n1].iteritems():
336 if n2 not in seen:
337 yield (n1,n2,data)
338 seen[n1]=1
339 del(seen)
340
341
343 """ Delete all edges between nodes n1 and n2.
344
345 When there is only a single edge allowed between nodes
346 (multiedges=False), this just calls delete_edge(n1,n2)
347 otherwise (multiedges=True) all edges between n1 and n2 are deleted.
348 """
349 if self.multiedges:
350 for x in self.get_edge(n1, n2):
351 self.delete_edge(n1, n2, x)
352 else:
353 self.delete_edge(n1, n2)
354 return
355
357 """Delete the edge (n1,n2,x) from the graph.
358
359 Can be called either as
360
361 >>> G.delete_edge(n1,n2,x)
362 or
363 >>> G.delete_edge(e)
364
365 where e=(n1,n2,x).
366
367 The default edge data is x=None
368
369 If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2)
370 then the edge (n1,n2,None) will be deleted.
371
372 If the edge does not exist, do nothing.
373
374 To delete *all* edges between n1 and n2 use
375 >>> G.delete_multiedges(n1,n2)
376
377 """
378 if n2 is None:
379 if len(n1)==3:
380 n1,n2,x=n1
381 else:
382 n1,n2=n1
383
384 if self.multiedges:
385 if (self.adj.has_key(n1)
386 and self.adj[n1].has_key(n2)
387 and x in self.adj[n1][n2]):
388 self.adj[n1][n2].remove(x)
389 if n1!=n2:
390 self.adj[n2][n1].remove(x)
391 if len(self.adj[n1][n2])==0:
392 del self.adj[n1][n2]
393 if n1!=n2:
394 del self.adj[n2][n1]
395 else:
396 if self.has_neighbor(n1,n2):
397 del self.adj[n1][n2]
398 if n1!=n2:
399 del self.adj[n2][n1]
400 return
401
403 """Delete edges in ebunch from the graph.
404
405 ebunch: Container of edges. Each edge must be a 3-tuple
406 (n1,n2,x) or a 2-tuple (n1,n2). In the latter case all edges
407 between n1 and n2 will be deleted. See delete_edge.
408
409 The container must be iterable or an iterator, and
410 is iterated over once. Edges that are not in the graph are ignored.
411
412 """
413 for e in ebunch:
414
415
416 self.delete_edge(e)
417
419 """This is the degree() method returned in iterator form.
420 If with_labels=True, iterator yields 2-tuples of form (n,degree(n))
421 (like iteritems() on a dict.)
422 """
423
424 if nbunch is None:
425 bunch=self.nodes_iter()
426 elif nbunch in self:
427 bunch=[nbunch]
428 else:
429 try: bunch=[n for n in nbunch if n in self]
430 except TypeError:
431 bunch=[]
432
433 if self.multiedges:
434 for n in bunch:
435 deg = sum([len(e) for e in self.adj[n].itervalues()])
436 if self.selfloops and self.adj[n].has_key(n):
437 deg+= len(self.adj[n][n])
438 if with_labels:
439 yield (n,deg)
440 else:
441 yield deg
442 else:
443 for n in bunch:
444 deg=len(self.adj[n])
445 deg+= self.adj[n].has_key(n)
446 if with_labels:
447 yield (n,deg)
448 else:
449 yield deg
450
452 """Return a (shallow) copy of the graph.
453
454 Return a new XGraph with same name and same attributes for
455 selfloop and multiededges. Each node and each edge in original
456 graph are added to the copy.
457
458 """
459 H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops)
460 H.name=self.name
461 for n in self:
462 H.add_node(n)
463 for e in self.edges_iter():
464 H.add_edge(e)
465 return H
466
468 """Return a directed representation of the XGraph G.
469
470 A new XDigraph is returned with the same name, same nodes and
471 with each edge (u,v,x) replaced by two directed edges
472 (u,v,x) and (v,u,x).
473
474 """
475 from networkx.xdigraph import XDiGraph
476 H=XDiGraph(selfloops=self.selfloops,multiedges=self.multiedges)
477 H.name=self.name
478 for n in self:
479 H.add_node(n)
480 for e in self.edges_iter():
481 H.add_edge(e[0],e[1],e[2])
482 H.add_edge(e[1],e[0],e[2])
483 return H
484
486 """Return list of all nodes having self-loops."""
487 if not self.selfloops:
488 return []
489 else:
490 return [n for n in self if self.adj[n].has_key(n)]
491
493 """Return all edges that are self-loops."""
494 nlist=self.nodes_with_selfloops()
495 if self.multiedges:
496 return [ (n,n,x) for n in nlist for x in self.adj[n][n]]
497 else:
498 return [ (n,n,self.adj[n][n]) for n in nlist ]
499
501 """Return number of self-loops in graph."""
502 nlist=self.nodes_with_selfloops()
503 if self.multiedges:
504 return sum([ len(self.adj[n][n]) for n in nlist])
505 else:
506 return len(nlist)
507
509 """Henceforth allow addition of self-loops
510 (edges from a node to itself).
511
512 This doesn't change the graph structure, only what you can do to it.
513 """
514 self.selfloops=True
515
517 """Remove self-loops from the graph (edges from a node to itself)."""
518 if not self.selfloops:
519
520 return
521 for n in self.adj:
522 if self.adj[n].has_key(n):
523 del self.adj[n][n]
524
526 """Remove self-loops from the graph and henceforth do not allow
527 their creation.
528 """
529 self.remove_all_selfloops()
530 self.selfloops=False
531
532
534 """Henceforth allow addition of multiedges (more than one
535 edge between two nodes).
536
537 Warning: This causes all edge data to be converted to lists.
538 """
539 if self.multiedges: return
540 self.multiedges=True
541 for v in self.adj:
542 for (u,edgedata) in self.adj[v].iteritems():
543 self.adj[v][u]=[edgedata]
544
546
547 """Remove multiedges retaining the data from the first edge"""
548 if not self.multiedges:
549 return
550 for v in self.adj:
551 for (u,edgedata) in self.adj[v].iteritems():
552 if len(edgedata)>1:
553 self.adj[v][u]=[edgedata[0]]
554
556 """Remove multiedges retaining the data from the first edge.
557 Henceforth do not allow multiedges.
558 """
559 if not self.multiedges:
560 return
561 self.multiedges=False
562 for v in self.adj:
563 for (u,edgedata) in self.adj[v].iteritems():
564 self.adj[v][u]=edgedata[0]
565
566 - def subgraph(self, nbunch, inplace=False, create_using=None):
567 """Return the subgraph induced on nodes in nbunch.
568
569 nbunch: can be a single node or any iterable container of
570 of nodes. (It can be an iterable or an iterator, e.g. a list,
571 set, graph, file, numeric array, etc.)
572
573 Setting inplace=True will return induced subgraph in original
574 graph by deleting nodes not in nbunch. It overrides any setting
575 of create_using.
576
577 WARNING: specifying inplace=True makes it easy to destroy the graph.
578
579 Unless otherwise specified, return a new graph of the same
580 type as self. Use (optional) create_using=R to return the
581 resulting subgraph in R. R can be an existing graph-like
582 object (to be emptied) or R can be a call to a graph object,
583 e.g. create_using=DiGraph(). See documentation for
584 empty_graph()
585
586 Note: use subgraph(G) rather than G.subgraph() to access the more
587 general subgraph() function from the operators module.
588
589 """
590 bunch=self.prepare_nbunch(nbunch)
591
592
593 if inplace:
594
595 bunch=dict.fromkeys(bunch)
596 self.delete_nodes_from([n for n in self if n not in bunch])
597 self.name="Subgraph of (%s)"%(self.name)
598 return self
599
600
601 if create_using is None:
602
603
604 H=self.__class__(multiedges=self.multiedges,
605 selfloops=self.selfloops)
606 else:
607
608
609
610 H=create_using
611 H.clear()
612 H.name="Subgraph of (%s)"%(self.name)
613 H.add_nodes_from(bunch)
614
615
616 H_adj=H.adj
617 self_adj=self.adj
618 if self.multiedges:
619 for n in H:
620 H_adj[n]=dict([(u,d[:]) for u,d in self_adj[n].iteritems() if u in H_adj])
621 else:
622 for n in H:
623 H_adj[n]=dict([(u,d) for u,d in self_adj[n].iteritems() if u in H_adj])
624 return H
625
626
628 """Return the number of edges between nodes u and v.
629
630 If u and v are not specified return the number of edges in the
631 entire graph.
632
633 The edge argument e=(u,v) can be specified as
634 G.number_of_edges(u,v) or G.number_of_edges(e)
635
636 """
637 if u is None: return self.size()
638 if v is None:
639 if len(u)==3:
640 (u,v,x)=u
641 else:
642 (u,v)=u
643
644 if self.has_edge(u,v,x):
645 if self.multiedges:
646 if x is None:
647 return len(self.get_edge(u,v))
648 else:
649 return len([d for d in self.get_edge(u,v) if d is x])
650 else:
651 return 1
652 else:
653 return 0
654
655
656
658 import doctest
659 suite = doctest.DocFileSuite(
660 'tests/xgraph_XGraph.txt',
661 'tests/xgraph_XGraph_multiedges_selfloops.txt',
662 package='networkx')
663 return suite
664
665
666 if __name__ == "__main__":
667 import os
668 import sys
669 import unittest
670 if sys.version_info[:2] < (2, 4):
671 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
672 sys.exit(-1)
673
674 nxbase=sys.path[0]+os.sep+os.pardir
675 sys.path.insert(0,nxbase)
676 unittest.TextTestRunner().run(_test_suite())
677