1 """
2 Base class for XDiGraph.
3
4 XDiGraph allows directed graphs with self-loops, multiple edges,
5 arbitrary (hashable) objects as nodes, and arbitrary objects
6 associated with edges.
7
8
9 """
10 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
11
12
13
14
15
16
17
18
19
20 from networkx.digraph import DiGraph
21 from networkx.exception import NetworkXException, NetworkXError
22 import networkx.convert as convert
23
25 """
26 Digraphs with (optional) self-loops, (optional) multiple edges,
27 arbitrary (hashable) objects as nodes, and arbitrary
28 objects associated with edges.
29
30 An XDiGraph edge is uniquely specified by a 3-tuple
31 e=(n1,n2,x), where n1 and n2 are (hashable) objects (nodes) and x
32 is an arbitrary (and not necessarily unique) object associated with
33 that edge.
34
35 See the documentation of XGraph for the use of the optional
36 parameters selfloops (defaults is False) and multiedges
37 (default is False).
38
39 XDiGraph inherits from DiGraph, with all purely node-specific methods
40 identical to those of DiGraph. XDiGraph edges are identical to XGraph
41 edges, except that they are directed rather than undirected.
42 XDiGraph replaces the following DiGraph methods:
43
44 - __init__: read multiedges and selfloops optional args.
45 - add_edge
46 - add_edges_from
47 - delete_edge
48 - delete_edges_from
49 - has_edge
50 - has_predecessor
51 - has_successor
52 - get_edge
53 - edges_iter
54 - in_edges_iter
55 - out_edges_iter
56 - neighbors_iter
57 - successors_iter
58 - predecessors_iter
59 - degree_iter
60 - out_degree_iter
61 - in_degree_iter
62 - subgraph
63 - copy
64 - to_undirected
65 - reverse
66
67 XDiGraph also adds the following methods to those of DiGraph:
68
69 - allow_selfloops
70 - remove_all_selfloops
71 - ban_selfloops
72 - nodes_with_selfloops
73 - self_loop_edges
74 - number_of_selfloops
75
76 - delete_multiedge
77 - allow_multiedges
78 - ban_multiedges
79 - remove_all_multiedges
80
81 While XDiGraph does not inherit from XGraph, we compare them here.
82 XDigraph adds the following methods to those of XGraph:
83
84 - has_successor
85 - successors
86 - successors_iter
87 - has_predecessor
88 - predecessors
89 - predecessors_iter
90 - out_degree
91 - out_degree_iter
92 - in_degree
93 - in_degree_iter
94 - reverse
95
96 """
97
98
99
100
101
102
103
104
105 - def __init__(self, data=None, name='', selfloops=False, multiedges=False):
106 """Initialize XDiGraph.
107
108 Optional arguments::
109 name: digraph name (default="No Name")
110 selfloops: if True then selfloops are allowed (default=False)
111 multiedges: if True then multiple edges are allowed (default=False)
112
113 """
114 self.adj={}
115 self.pred={}
116 self.succ=self.adj
117 self.selfloops=selfloops
118 self.multiedges=multiedges
119 if data is not None:
120 convert.from_whatever(data,create_using=self)
121 self.name=name
122
123
124 - def add_edge(self, n1, n2=None, x=None):
125 """Add a single directed edge to the digraph.
126
127 Can be called as G.add_edge(n1,n2,x)
128 or as G.add_edge(e), where e=(n1,n2,x).
129
130 If called as G.add_edge(n1,n2) or G.add_edge(e), with e=(n1,n2),
131 then this is interpreted as adding the edge (n1,n2,None) to
132 be compatible with the Graph and DiGraph classes.
133
134 n1,n2 are node objects, and are added to the Graph if not already
135 present. Nodes must be hashable Python objects (except None).
136
137 x is an arbitrary (not necessarily hashable) object associated
138 with this edge. It can be used to associate one or more,
139 labels, data records, weights or any arbirary objects to
140 edges. The default is the Python None.
141
142 For example, if the graph G was created with
143
144 >>> G=XDiGraph()
145
146 then G.add_edge(1,2,"blue") will add the directed edge (1,2,"blue").
147
148 If G.multiedges=False, then a subsequent G.add_edge(1,2,"red")
149 will change the above edge (1,2,"blue") into the edge (1,2,"red").
150
151 On the other hand, if G.multiedges=True, then two successive calls to
152 G.add_edge(1,2,"red") will result in 2 edges of the form
153 (1,2,"red") that can not be distinguished from one another.
154
155 If self.selfloops=False, then any attempt to create a self-loop
156 with add_edge(n1,n1,x) will have no effect on the digraph and
157 will not elicit a warning.
158
159 Objects imbedded in the edges from n1 to n2 (if any), can be
160 retrieved using get_edge(n1,n2), or calling edges(n1) or
161 edge_iter(n1) to return all edges attached to n1.
162
163 """
164
165 if n2 is None:
166 if len(n1)==3:
167 n1,n2,x=n1
168 else:
169 n1,n2=n1
170
171
172
173 if not self.multiedges and self.has_edge(n1,n2,x):
174 return
175
176
177 if n1 not in self.succ:
178 self.succ[n1]={}
179 if n1 not in self.pred:
180 self.pred[n1]={}
181 if n2 not in self.succ:
182 self.succ[n2]={}
183 if n2 not in self.pred:
184 self.pred[n2]={}
185
186
187 if not self.selfloops and n1==n2:
188 return
189
190 if self.multiedges:
191
192 self.succ[n1][n2]=self.succ[n1].get(n2,[])+ [x]
193 self.pred[n2][n1]=self.pred[n2].get(n1,[])+ [x]
194 else:
195 self.succ[n1][n2]=x
196 self.pred[n2][n1]=x
197
198
200 """Add multiple directed edges to the digraph.
201 ebunch: Container of edges. Each edge e in container will be added
202 using add_edge(e). See add_edge documentation.
203 The container must be iterable or an iterator.
204 It is iterated over once.
205 """
206 for e in ebunch:
207
208
209 self.add_edge(e)
210
211 - def has_edge(self, n1, n2=None, x=None):
212 """Return True if digraph contains directed edge (n1,n2,x).
213
214 Can be called as G.has_edge(n1,n2,x)
215 or as G.has_edge(e), where e=(n1,n2,x).
216
217 If x is unspecified, i.e. if called with an edge of the form
218 e=(n1,n2), then return True if there exists ANY edge from n1
219 to n2 (equivalent to has_successor(n1,n2)).
220
221 """
222
223 if n2 is None:
224
225 if len(n1)==3:
226 n1,n2,x=n1
227 else:
228 n1,n2=n1
229 return self.has_successor(n1,n2)
230 else:
231 if x is None:
232
233
234 return self.has_successor(n1,n2)
235
236 if self.multiedges:
237 return (self.succ.has_key(n1) and
238 self.succ[n1].has_key(n2) and
239 x in self.succ[n1][n2])
240 else:
241 return (self.succ.has_key(n1) and
242 self.succ[n1].has_key(n2) and
243 x==self.succ[n1][n2])
244
246 """Return True if node n1 has a successor n2.
247
248 Return True if there exists ANY edge (n1,n2,x) for some x.
249
250 """
251 return (self.succ.has_key(n1) and
252 self.succ[n1].has_key(n2))
253
255 """Return True if node n1 has a predecessor n2.
256
257 Return True if there exists ANY edge (n2,n1,x) for some x.
258
259 """
260 return (self.pred.has_key(n1) and
261 self.pred[n1].has_key(n2))
262
263
265 """Return an iterator over the objects associated with each edge
266 from node u to node v.
267
268 """
269 if v is None:
270 (u,v)=u
271 try:
272 data = self.adj[u][v]
273 except KeyError:
274 raise NetworkXError, "Edge (%s,%s) requested via get_edge_iter does not exist."%(u,v)
275 if self.multiedges:
276 for d in data:
277 yield d
278 else:
279 yield data
280
282 """Return the objects associated with each edge from node u to node v.
283
284 If multiedges=False, a single object is returned.
285 If multiedges=True, a list of objects is returned.
286 If no edge exists, None is returned.
287
288 """
289 if v is None:
290 (u,v)=u
291 try:
292 data=self.adj[u][v]
293 except KeyError:
294 raise NetworkXError, "Edge (%s,%s) requested via get_edge does not exist."%(u,v)
295 if self.multiedges:
296 return data[:]
297 return data
298
300 """ Delete all edges between nodes n1 and n2.
301
302 When there is only a single edge allowed between nodes
303 (multiedges=False), this just calls delete_edge(n1,n2),
304 otherwise (multiedges=True) all edges between n1 and n2 are deleted.
305 """
306 if self.multiedges:
307 for x in self.get_edge(n1,n2):
308 self.delete_edge(n1,n2,x)
309 else:
310 self.delete_edge(n1,n2)
311 return
312
313
314 - def delete_edge(self, n1, n2=None, x=None, all=False):
315 """Delete the directed edge (n1,n2,x) from the graph.
316
317 Can be called either as
318 >>> G.delete_edge(n1,n2,x)
319 or as
320 >>> G.delete_edge(e)
321 where e=(n1,n2,x).
322
323 If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2)
324 then the edge (n1,n2,None) will be deleted.
325
326 If the edge does not exist, do nothing.
327
328 To delete *all* edges between n1 and n2 use
329 >>> G.delete_multiedges(n1,n2)
330
331 """
332 if n2 is None:
333 if len(n1)==3:
334 n1,n2,x=n1
335 else:
336 n1,n2=n1
337
338 if self.multiedges:
339 if (self.succ.has_key(n1)
340 and self.succ[n1].has_key(n2)
341 and x in self.succ[n1][n2]):
342 self.succ[n1][n2].remove(x)
343 self.pred[n2][n1].remove(x)
344 if len(self.succ[n1][n2])==0:
345 del self.succ[n1][n2]
346 del self.pred[n2][n1]
347 else:
348 if self.has_successor(n1,n2):
349 del self.succ[n1][n2]
350 del self.pred[n2][n1]
351 return
352
354 """Delete edges in ebunch from the graph.
355
356 ebunch: Container of edges. Each edge must be a 3-tuple
357 (n1,n2,x) or a 2-tuple (n1,n2). The container must be
358 iterable or an iterator, and is iterated over once.
359
360 Edges that are not in the graph are ignored.
361
362 """
363 for e in ebunch:
364 self.delete_edge(e)
365
367 """Return iterator that iterates once over each edge pointing
368 out of nodes in nbunch, or over all edges in digraph if no
369 nodes are specified.
370
371 See edges() for definition of nbunch.
372
373 Nodes in nbunch that are not in the graph will be (quietly) ignored.
374
375 """
376
377 if nbunch is None:
378 bunch=self.nodes_iter()
379 elif nbunch in self:
380 bunch=[nbunch]
381 else:
382 try: bunch=[n for n in nbunch if n in self]
383 except TypeError:
384 bunch=[]
385
386 if self.multiedges:
387 for n1 in bunch:
388 for n2,elist in self.succ[n1].iteritems():
389 for data in elist:
390 yield (n1,n2,data)
391 else:
392 for n1 in bunch:
393 for n2,data in self.succ[n1].iteritems():
394 yield (n1,n2,data)
395
397 """Return iterator that iterates once over each edge pointing in
398 to nodes in nbunch, or over all edges in digraph if no
399 nodes are specified.
400
401 See edges() for definition of nbunch.
402
403 Nodes in nbunch that are not in the graph will be (quietly) ignored.
404
405 """
406
407 if nbunch is None:
408 bunch=self.nodes_iter()
409 elif nbunch in self:
410 bunch=[nbunch]
411 else:
412 try: bunch=[n for n in nbunch if n in self]
413 except TypeError:
414 bunch=[]
415
416 if self.multiedges:
417 for n1 in bunch:
418 for n2,elist in self.pred[n1].iteritems():
419 for data in elist:
420 yield (n2,n1,data)
421 else:
422 for n1 in bunch:
423 for n2,data in self.pred[n1].iteritems():
424 yield (n2,n1,data)
425
427 """Return an iterator of nodes pointing out of node n.
428
429 Returns the same data as out_edges(n) but in a different format.
430
431 """
432 try:
433 if self.multiedges:
434 for nbr,elist in self.succ[n].iteritems():
435 for data in elist:
436 yield nbr
437 else:
438 for nbr in self.succ[n].iterkeys():
439 yield nbr
440 except KeyError:
441 raise NetworkXError, "node %s not in graph"%(n,)
442
444 """Return an iterator of nodes pointing in to node n.
445
446 Returns the same data as in_edges(n) but in a different format.
447
448 """
449 try:
450 if self.multiedges:
451 for nbr,elist in self.pred[n].iteritems():
452 for data in elist:
453 yield nbr
454 else:
455 for nbr in self.pred[n].iterkeys():
456 yield nbr
457 except KeyError:
458 raise NetworkXError, "node %s not in graph"%(n,)
459
460 edges_iter=out_edges_iter
461 neighbors_iter=successors_iter
462
466
468 """Return sucessor nodes of n."""
469 return list(self.successors_iter(n))
470
471 neighbors=successors
472
474 """Return iterator for in_degree(n) or (n,in_degree(n))
475 for all n in nbunch.
476
477 If nbunch is ommitted, then iterate over *all* nodes.
478
479 See degree_iter method for more details.
480 """
481
482 if nbunch is None:
483 bunch=self.nodes_iter()
484 elif nbunch in self:
485 bunch=[nbunch]
486 else:
487 try: bunch=[n for n in nbunch if n in self]
488 except TypeError:
489 bunch=[]
490
491 if self.multiedges:
492 if with_labels:
493 for n in bunch:
494 yield (n,sum([len(edge) for edge in self.pred[n].itervalues()]))
495 else:
496 for n in bunch:
497 yield sum([len(edge) for edge in self.pred[n].itervalues()])
498 else:
499 if with_labels:
500 for n in bunch:
501 yield (n,len(self.pred[n]))
502 else:
503 for n in bunch:
504 yield len(self.pred[n])
505
507 """Return iterator for out_degree(n) or (n,out_degree(n))
508 for all n in nbunch.
509
510 If nbunch is ommitted, then iterate over *all* nodes.
511
512 See degree_iter method for more details.
513 """
514
515 if nbunch is None:
516 bunch=self.nodes_iter()
517 elif nbunch in self:
518 bunch=[nbunch]
519 else:
520 try: bunch=[n for n in nbunch if n in self]
521 except TypeError:
522 bunch=[]
523
524 if self.multiedges:
525 if with_labels:
526 for n in bunch:
527 yield (n,sum([len(edge) for edge in self.succ[n].itervalues()]))
528 else:
529 for n in bunch:
530 yield sum([len(edge) for edge in self.succ[n].itervalues()])
531 else:
532 if with_labels:
533 for n in bunch:
534 yield (n,len(self.succ[n]))
535 else:
536 for n in bunch:
537 yield len(self.succ[n])
538
539 - def degree_iter(self, nbunch=None, with_labels=False):
540 """Return iterator that returns in_degree(n)+out_degree(n)
541 or (n,in_degree(n)+out_degree(n)) for all n in nbunch.
542 If nbunch is ommitted, then iterate over *all* nodes.
543
544 Can be called in three ways:
545 G.degree_iter(n): return iterator the degree of node n
546 G.degree_iter(nbunch): return a list of values,
547 one for each n in nbunch (nbunch is any iterable container of nodes.)
548 G.degree_iter(): same as nbunch = all nodes in graph.
549
550 If with_labels=True, iterator will return an
551 (n,in_degree(n)+out_degree(n)) tuple of node and degree.
552
553 Any nodes in nbunch but not in the graph will be (quietly) ignored.
554
555 """
556
557 if nbunch is None:
558 bunch=self.nodes_iter()
559 elif nbunch in self:
560 bunch=[nbunch]
561 else:
562 try: bunch=[n for n in nbunch if n in self]
563 except TypeError:
564 bunch=[]
565
566 if self.multiedges:
567 for n in bunch:
568 d=sum([len(e) for e in self.succ[n].itervalues()]) + \
569 sum([len(e) for e in self.pred[n].itervalues()])
570 if with_labels:
571 yield (n,d)
572 else:
573 yield d
574 else:
575 for n in bunch:
576 d=len(self.succ[n])+len(self.pred[n])
577 if with_labels:
578 yield (n,d)
579 else:
580 yield d
581
583 """Return list of all nodes having self-loops."""
584 if not self.selfloops:
585 return []
586 else:
587
588 return [n for n in self if self.succ[n].has_key(n)]
589
591 """Return all edges that are self-loops."""
592 nlist=self.nodes_with_selfloops()
593 if self.multiedges:
594 return [ (n,n,x) for n in nlist for x in self.adj[n][n]]
595 else:
596 return [ (n,n,self.adj[n][n]) for n in nlist ]
597
599 """Return number of self-loops in graph."""
600 nlist=self.nodes_with_selfloops()
601 if self.multiedges:
602 return sum([ len(self.adj[n][n]) for n in nlist])
603 else:
604 return len(nlist)
605
607 """Henceforth allow addition of self-loops
608 (edges from a node to itself).
609
610 This doesn't change the graph structure, only what you can do to it.
611 """
612 self.selfloops=True
613
615 """Remove self-loops from the graph (edges from a node to itself)."""
616 for n in self.succ:
617 if self.succ[n].has_key(n):
618 del self.succ[n][n]
619 del self.pred[n][n]
620
622 """Remove self-loops from the graph and henceforth do not allow
623 their creation.
624 """
625 self.remove_all_selfloops()
626 self.selfloops=False
627
628
630 """Henceforth allow addition of multiedges (more than one
631 edge between two nodes).
632
633 Warning: This causes all edge data to be converted to lists.
634 """
635 if self.multiedges: return
636 self.multiedges=True
637 for v in self.succ:
638 for (u,edgedata) in self.succ[v].iteritems():
639 self.succ[v][u]=[edgedata]
640 self.pred[u][v]=[edgedata]
641
643
644 """Remove multiedges retaining the data from the first edge"""
645 if not self.multiedges:
646 return
647 for v in self.succ:
648 for (u,edgedata) in self.succ[v].iteritems():
649 if len(edgedata)>1:
650 self.succ[v][u]=[edgedata[0]]
651 self.pred[u][v]=[edgedata[0]]
652
654 """Remove multiedges retaining the data from the first edge.
655 Henceforth do not allow multiedges.
656 """
657 if not self.multiedges:
658 return
659 self.multiedges=False
660 for v in self.succ:
661 for (u,edgedata) in self.succ[v].iteritems():
662 self.succ[v][u]=edgedata[0]
663 self.pred[u][v]=edgedata[0]
664
665 - def subgraph(self, nbunch, inplace=False, create_using=None):
666 """Return the subgraph induced on nodes in nbunch.
667
668 nbunch: can be a single node or any iterable container of
669 of nodes. (It can be an iterable or an iterator, e.g. a list,
670 set, graph, file, numeric array, etc.)
671
672 Setting inplace=True will return induced subgraph in original
673 graph by deleting nodes not in nbunch. It overrides any setting
674 of create_using.
675
676 WARNING: specifying inplace=True makes it easy to destroy the graph.
677
678 Unless otherwise specified, return a new graph of the same
679 type as self. Use (optional) create_using=R to return the
680 resulting subgraph in R. R can be an existing graph-like
681 object (to be emptied) or R can be a call to a graph object,
682 e.g. create_using=DiGraph(). See documentation for
683 empty_graph()
684
685 Note: use subgraph(G) rather than G.subgraph() to access the more
686 general subgraph() function from the operators module.
687
688 """
689 bunch=self.prepare_nbunch(nbunch)
690
691
692 if inplace:
693
694 bunch=dict.fromkeys(bunch)
695 self.delete_nodes_from([n for n in self if n not in bunch])
696 self.name="Subgraph of (%s)"%(self.name)
697 return self
698
699
700 if create_using is None:
701
702
703 H=self.__class__(multiedges=self.multiedges,
704 selfloops=self.selfloops)
705 else:
706
707
708
709 H=create_using
710 H.clear()
711 H.name="Subgraph of (%s)"%(self.name)
712 H.add_nodes_from(bunch)
713
714
715 H_succ=H.succ
716 H_pred=H.pred
717 self_succ=self.succ
718 self_pred=self.pred
719 if self.multiedges:
720 for n in H:
721 H_succ[n]=dict([(u,d[:]) for u,d in self_succ[n].iteritems() if u in H_succ])
722 H_pred[n]=dict([(u,d[:]) for u,d in self_pred[n].iteritems() if u in H_pred])
723 else:
724 for n in H:
725 H_succ[n]=dict([(u,d) for u,d in self_succ[n].iteritems() if u in H_succ])
726 H_pred[n]=dict([(u,d) for u,d in self_pred[n].iteritems() if u in H_pred])
727 return H
728
730 """Return a (shallow) copy of the digraph.
731
732 Return a new XDiGraph with same name and same attributes for
733 selfloop and multiededges. Each node and each edge in original
734 graph are added to the copy.
735
736 """
737 H=self.__class__(name=self.name, multiedges=self.multiedges, selfloops=self.selfloops)
738 H.add_nodes_from(self)
739 H.add_edges_from(self.edges_iter())
740 return H
741
743 """Return the underlying graph of G.
744
745 The underlying graph is its undirected representation: each directed
746 edge is replaced with an undirected edge.
747
748 If multiedges=True, then an XDiGraph with only two directed
749 edges (1,2,"red") and (2,1,"blue") will be converted into an
750 XGraph with two undirected edges (1,2,"red") and (1,2,"blue").
751 Two directed edges (1,2,"red") and (2,1,"red") will result in
752 in two undirected edges (1,2,"red") and (1,2,"red").
753
754 If multiedges=False, then two directed edges (1,2,"red") and
755 (2,1,"blue") can only result in one undirected edge, and there
756 is no guarantee which one it is.
757
758 """
759 from networkx.xgraph import XGraph
760 H=XGraph(name=self.name, multiedges=self.multiedges, selfloops=self.selfloops)
761 H.add_nodes_from(self)
762 H.add_edges_from(self.edges_iter())
763 return H
764
766 """
767 Return a new digraph with the same vertices and edges
768 as self but with the directions of the edges reversed.
769 """
770 H=self.__class__(name="Reverse of (%s)"%self.name,\
771 multiedges=self.multiedges, selfloops=self.selfloops)
772 H.add_nodes_from(self)
773 H.add_edges_from( [ (v,u,d) for (u,v,d) in self.edges_iter() ] )
774 return H
775
777 """Return the number of edges between nodes u and v.
778
779 If u and v are not specified return the number of edges in the
780 entire graph.
781
782 The edge argument e=(u,v) can be specified as
783 G.number_of_edges(u,v) or G.number_of_edges(e)
784
785 """
786 if u is None: return self.size()
787 if v is None:
788 if len(u)==3:
789 (u,v,x)=u
790 else:
791 (u,v)=u
792
793 if self.has_edge(u,v,x):
794 if self.multiedges:
795 if x is None:
796 return len(self.get_edge(u,v))
797 else:
798 return len([d for d in self.get_edge(u,v) if d is x])
799 else:
800 return 1
801 else:
802 return 0
803
804
805
806
808 import doctest
809 suite = doctest.DocFileSuite(
810 'tests/xdigraph_XDiGraph.txt',
811 package='networkx')
812 return suite
813
814
815 if __name__ == "__main__":
816 import os
817 import sys
818 import unittest
819 if sys.version_info[:2] < (2, 4):
820 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
821 sys.exit(-1)
822
823 nxbase=sys.path[0]+os.sep+os.pardir
824 sys.path.insert(0,nxbase)
825 unittest.TextTestRunner().run(_test_suite())
826