1 """
2 Base class for graphs.
3
4 Examples
5 ========
6
7 Create an empty graph structure (a "null graph") with
8 zero nodes and zero edges.
9
10 >>> from networkx import *
11 >>> G=Graph()
12
13 G can be grown in several ways.
14 By adding one node at a time:
15
16 >>> G.add_node(1)
17
18 by adding a list of nodes:
19
20 >>> G.add_nodes_from([2,3])
21
22 by using an iterator:
23
24 >>> G.add_nodes_from(xrange(100,110))
25
26 or by adding any container of nodes
27
28 >>> H=path_graph(10)
29 >>> G.add_nodes_from(H)
30
31 H can be another graph, or dict, or set, or even a file.
32 Any hashable object (except None) can represent a node, e.g. a Graph,
33 a customized node object, etc.
34
35 >>> G.add_node(H)
36
37 G can also be grown by adding one edge at a time:
38
39 >>> G.add_edge( (1,2) )
40
41 by adding a list of edges:
42
43 >>> G.add_edges_from([(1,2),(1,3)])
44
45 or by adding any ebunch of edges (see above definition of an ebunch):
46
47 >>> G.add_edges_from(H.edges())
48
49 There are no complaints when adding existing nodes or edges:
50
51 >>> G=Graph()
52 >>> G.add_edge([(1,2),(1,3)])
53
54 will add new nodes as required.
55
56
57 """
58 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
59
60
61
62
63
64
65
66 from networkx.exception import NetworkXException, NetworkXError
67 import networkx.convert as convert
68
70 """Graph is a simple graph without any multiple (parallel) edges
71 or self-loops. Attempting to add either will not change
72 the graph and will not report an error.
73
74 """
76 """Initialize Graph.
77
78 >>> G=Graph(name="empty")
79
80 creates empty graph G with G.name="empty"
81
82 """
83 self.adj={}
84
85 if data is not None:
86 convert.from_whatever(data,create_using=self)
87 self.name=name
88
91
93 """Return an iterator over the nodes in G.
94
95 This is the iterator for the underlying adjacency dict.
96 (Allows the expression 'for n in G')
97 """
98 return self.adj.iterkeys()
99
101 """Return True if n is a node in graph.
102
103 Allows the expression 'n in G'.
104
105 Testing whether an unhashable object, such as a list, is in the
106 dict datastructure (self.adj) will raise a TypeError.
107 Rather than propagate this to the calling method, just
108 return False.
109
110 """
111 try:
112 return n in self.adj
113 except TypeError:
114 return False
115
117 """Return the number of nodes in graph."""
118 return len(self.adj)
119
121 """Return the neighbors of node n as a list.
122
123 This provides graph G the natural property that G[n] returns
124 the neighbors of G.
125
126 """
127 try:
128 return self.adj[n].keys()
129 except KeyError:
130 raise NetworkXError, "node %s not in graph"%(n,)
131
133 """
134 Return a sequence (or iterator) of nodes contained
135 in nbunch which are also in the graph.
136
137 The input nbunch can be a single node, a sequence or
138 iterator of nodes or None (omitted). If None, all
139 nodes in the graph are returned.
140
141 Note: This routine exhausts any iterator nbunch.
142
143 Note: To test whether nbunch is a single node,
144 one can use "if nbunch in self:", even after processing
145 with this routine.
146
147 Note: This routine returns an empty list if
148 nbunch is not either a node, sequence, iterator, or None.
149 You can catch this exception if you want to change this
150 behavior.
151 """
152 if nbunch is None:
153 bunch=self.nodes_iter()
154 elif nbunch in self:
155 bunch=[nbunch]
156 else:
157 try:
158 bunch=[n for n in nbunch if n in self]
159
160 except TypeError:
161 bunch=[]
162 return bunch
163
164 - def info(self, n=None):
165 """Print short info for graph G or node n."""
166 import textwrap
167 width_left = 18
168
169 if n is None:
170 print ("Name:").ljust(width_left), self.name
171 type_name = [type(self).__name__]
172 try:
173 if self.selfloops:
174 type_name.append("self-loops")
175 except:
176 pass
177 try:
178 if self.multiedges:
179 type_name.append("multi-edges")
180 except:
181 pass
182
183 print ("Type:").ljust(width_left), ",".join(type_name)
184 print ("Number of nodes:").ljust(width_left), self.number_of_nodes()
185 print ("Number of edges:").ljust(width_left), self.number_of_edges()
186 if len(self) > 0:
187 print ("Average degree:").ljust(width_left), \
188 round( 2*self.size()/float(len(self)), 4)
189 else:
190 try:
191 list_neighbors = self.neighbors(n)
192 print "\nNode", n, "has the following properties:"
193 print ("Degree:").ljust(width_left), self.degree(n)
194 str_neighbors = str(list_neighbors)
195 str_neighbors = str_neighbors[1:len(str_neighbors)-1]
196 wrapped_neighbors = textwrap.wrap(str_neighbors, 50)
197 num_line = 0
198 for i in wrapped_neighbors:
199 if num_line == 0:
200 print ("Neighbors:").ljust(width_left), i
201 else:
202 print "".ljust(width_left), i
203 num_line += 1
204 except (KeyError, TypeError):
205 raise NetworkXError, "node %s not in graph"%(n,)
206
207
209 """
210 Add a single node n to the graph.
211
212 The node n can be any hashable object except None.
213
214 A hashable object is one that can be used as a key in a Python
215 dictionary. This includes strings, numbers, tuples of strings
216 and numbers, etc. On many platforms this also includes
217 mutables such as Graphs e.g., though one should be careful the
218 hash doesn't change on mutables.
219
220 Example:
221
222 >>> from networkx import *
223 >>> G=Graph()
224 >>> K3=complete_graph(3)
225 >>> G.add_node(1)
226 >>> G.add_node('Hello')
227 >>> G.add_node(K3)
228 >>> G.number_of_nodes()
229 3
230
231 """
232 if n not in self.adj:
233 self.adj[n]={}
234
235
237 """Add multiple nodes to the graph.
238
239 nlist:
240 A container of nodes that will be iterated through once
241 (thus it should be an iterator or be iterable).
242 Each element of the container should be a valid node type:
243 any hashable type except None. See add_node for details.
244
245 Examples:
246
247 >>> from networkx import *
248 >>> G=Graph()
249 >>> K3=complete_graph(3)
250 >>> G.add_nodes_from('Hello')
251 >>> G.add_nodes_from(K3)
252 >>> sorted(G.nodes())
253 [0, 1, 2, 'H', 'e', 'l', 'o']
254
255 """
256 for n in nlist:
257 if n not in self.adj:
258 self.adj[n]={}
259
260
262 """Delete node n from graph.
263 Attempting to delete a non-existent node will raise an exception.
264
265 """
266 try:
267 for u in self.adj[n].keys():
268 del self.adj[u][n]
269
270 del self.adj[n]
271 except KeyError:
272 raise NetworkXError, "node %s not in graph"%(n,)
273
275 """Remove nodes in nlist from graph.
276
277 nlist:
278 an iterable or iterator containing valid node names.
279
280 Attempting to delete a non-existent node will raise an exception.
281 This could mean some nodes got deleted and other valid nodes did
282 not.
283
284 """
285 for n in nlist:
286 try:
287 for u in self.adj[n].keys():
288 del self.adj[u][n]
289
290 del self.adj[n]
291 except KeyError:
292 raise NetworkXError, "node %s not in graph"%(n,)
293
294
296 """Return an iterator over the graph nodes."""
297 return self.adj.iterkeys()
298
300 """Return a copy of the graph nodes in a list."""
301 return self.adj.keys()
302
304 """Return number of nodes."""
305 return len(self.adj)
306
308 """Return True if graph has node n.
309
310 (duplicates self.__contains__)
311 "n in G" is a more readable version of "G.has_node(n)"?
312
313 """
314 try:
315 return n in self.adj
316 except TypeError:
317 return False
318
320 """Return the order of a graph = number of nodes."""
321 return len(self.adj)
322
323
325 """Add a single edge (u,v) to the graph.
326
327 >> G.add_edge(u,v)
328 and
329 >>> G.add_edge( (u,v) )
330 are equivalent forms of adding a single edge between nodes u and v.
331 The nodes u and v will be automatically added if not already in
332 the graph. They must be a hashable (except None) Python object.
333
334 The following examples all add the edge (1,2) to graph G.
335
336 >>> G=Graph()
337 >>> G.add_edge( 1, 2 ) # explicit two node form
338 >>> G.add_edge( (1,2) ) # single edge as tuple of two nodes
339 >>> G.add_edges_from( [(1,2)] ) # add edges from iterable container
340
341 """
342 if v is None:
343 (u,v)=u
344
345 if u not in self.adj:
346 self.adj[u]={}
347 if v not in self.adj:
348 self.adj[v]={}
349
350 if u==v:
351 return
352 self.adj[u][v]=None
353 self.adj[v][u]=None
354
355
357 """Add all the edges in ebunch to the graph.
358
359 ebunch: Container of 2-tuples (u,v). The container must be
360 iterable or an iterator. It is iterated over once. Adding the
361 same edge twice has no effect and does not raise an exception.
362
363 """
364 for e in ebunch:
365 (u,v)=e
366
367 if u not in self.adj:
368 self.adj[u]={}
369 if v not in self.adj:
370 self.adj[v]={}
371
372 if u==v:
373 continue
374 self.adj[u][v]=None
375 self.adj[v][u]=None
376
377
379 """Delete the single edge (u,v).
380
381 Can be used in two basic forms:
382 >>> G.delete_edge(u,v)
383 and
384 >> G.delete_edge( (u,v) )
385 are equivalent ways of deleting a single edge between nodes u and v.
386
387 Return without complaining if the nodes or the edge do not exist.
388
389 """
390 if v is None:
391 (u,v)=u
392 if self.adj.has_key(u) and self.adj[u].has_key(v):
393 del self.adj[u][v]
394 del self.adj[v][u]
395
397 """Delete the edges in ebunch from the graph.
398
399 ebunch: an iterator or iterable of 2-tuples (u,v).
400
401 Edges that are not in the graph are ignored.
402
403 """
404 for (u,v) in ebunch:
405 if self.adj.has_key(u) and self.adj[u].has_key(v):
406 del self.adj[u][v]
407 del self.adj[v][u]
408
410 """Return True if graph contains the edge u-v, return False otherwise."""
411 if v is None:
412 (u,v)=u
413 return self.adj.has_key(u) and self.adj[u].has_key(v)
414
416 """Return True if node u has neighbor v.
417
418 This is equivalent to has_edge(u,v).
419
420 """
421 return self.adj.has_key(u) and self.adj[u].has_key(v)
422
423
425 """Return 1 if graph contains the edge u-v.
426 Raise an exception otherwise.
427
428 """
429
430 if v is None:
431 (u,v)=u
432
433 if self.has_edge(u,v):
434 return 1
435 else:
436 return None
437
438
439
441 """Return an iterator over all neighbors of node n. """
442 try:
443 return self.adj[n].iterkeys()
444 except KeyError:
445 raise NetworkXError, "node %s not in graph"%(n,)
446
448 """Return a list of nodes connected to node n. """
449
450 try:
451 return self.adj[n].keys()
452 except KeyError:
453 raise NetworkXError, "node %s not in graph"%(n,)
454
456 """Return iterator that iterates once over each edge adjacent
457 to nodes in nbunch, or over all edges in graph if no
458 nodes are specified.
459
460 If nbunch is None return all edges in the graph.
461 The argument nbunch can be any single node, or
462 any sequence or iterator of nodes.
463 Nodes in nbunch that are not in the graph will be (quietly) ignored.
464
465 """
466
467 if nbunch is None:
468 bunch=self.nodes_iter()
469 elif nbunch in self:
470 bunch=[nbunch]
471 else:
472 try: bunch=[n for n in nbunch if n in self]
473 except TypeError:
474 bunch=[]
475
476 seen={}
477 for n1 in bunch:
478 for n2 in self.adj[n1]:
479 if n2 not in seen:
480 yield (n1,n2)
481 seen[n1]=1
482 del(seen)
483
484
485
486 - def edges(self, nbunch=None):
487 """Return list of all edges that are adjacent to a node in nbunch,
488 or a list of all edges in graph if no nodes are specified.
489
490 If nbunch is None return all edges in the graph.
491 The argument nbunch can be any single node, or
492 any sequence or iterator of nodes.
493 Nodes in nbunch that are not in the graph will be (quietly) ignored.
494
495 For digraphs, edges=out_edges
496
497 """
498 return list(self.edges_iter(nbunch))
499
501 """Return list of edges (n1,n2) with n1 in nbunch1 and n2 in
502 nbunch2. If nbunch2 is omitted or nbunch2=None, then nbunch2
503 is all nodes not in nbunch1.
504
505 Nodes in nbunch1 and nbunch2 that are not in the graph are
506 ignored.
507
508 nbunch1 and nbunch2 are usually meant to be disjoint,
509 but in the interest of speed and generality, that is
510 not required here.
511
512 This routine is faster if nbunch1 is smaller than nbunch2.
513
514 """
515 if nbunch2 is None:
516 ndict1=dict.fromkeys([n for n in nbunch1 if n in self])
517 return [(n1,n2) for n1 in ndict1 for n2 in self.adj[n1] \
518 if n2 not in ndict1]
519
520 ndict2=dict.fromkeys(nbunch2)
521 return [(n1,n2) for n1 in nbunch1 if n1 in self for n2 in self.adj[n1] \
522 if n2 in ndict2]
523
525 """Return list of all nodes on external boundary of nbunch1 that are
526 in nbunch2. If nbunch2 is omitted or nbunch2=None, then nbunch2
527 is all nodes not in nbunch1.
528
529 Note that by definition the node_boundary is external to nbunch1.
530
531 Nodes in nbunch1 and nbunch2 that are not in the graph are
532 ignored.
533
534 nbunch1 and nbunch2 are usually meant to be disjoint,
535 but in the interest of speed and generality, that is
536 not required here.
537
538 This routine is faster if nbunch1 is smaller than nbunch2.
539
540 """
541 if nbunch2 is None:
542 ndict1=dict.fromkeys([n for n in nbunch1 if n in self])
543 bdy={}
544 for n1 in ndict1:
545 for n2 in self.adj[n1]:
546 if n2 not in ndict1:
547 bdy[n2]=1
548 return bdy.keys()
549
550 ndict2=dict.fromkeys(nbunch2)
551 bdy=[]
552 for n1 in [n for n in nbunch1 if n in self]:
553 for n2 in self.adj[n1]:
554 if n2 in ndict2:
555 bdy.append(n2)
556 del ndict2[n2]
557 return bdy
558
559 - def degree(self, nbunch=None, with_labels=False):
560 """Return degree of single node or of nbunch of nodes.
561 If nbunch is omitted or nbunch=None, then return
562 degrees of *all* nodes.
563
564 The degree of a node is the number of edges attached to that
565 node.
566
567 Can be called in three ways:
568
569 G.degree(n): return the degree of node n
570 G.degree(nbunch): return a list of values, one for each n in nbunch
571 (nbunch is any iterable container of nodes.)
572 G.degree(): same as nbunch = all nodes in graph.
573
574 If with_labels==True, then return a dict that maps each n
575 in nbunch to degree(n).
576
577 Any nodes in nbunch that are not in the graph are
578 (quietly) ignored.
579
580 """
581 if with_labels:
582 return dict(self.degree_iter(nbunch,with_labels))
583 elif nbunch in self:
584 return self.degree_iter(nbunch,with_labels).next()
585 else:
586 return list(self.degree_iter(nbunch,with_labels))
587
589 """Return iterator that return degree(n) or (n,degree(n))
590 for all n in nbunch. If nbunch is ommitted, then iterate
591 over all nodes.
592
593 Can be called in three ways:
594 G.degree_iter(n): return iterator the degree of node n
595 G.degree_iter(nbunch): return a list of values,
596 one for each n in nbunch (nbunch is any iterable container of nodes.)
597 G.degree_iter(): same as nbunch = all nodes in graph.
598
599 If with_labels==True, iterator will return an (n,degree(n)) tuple of
600 node and degree.
601
602 Any nodes in nbunch that are not in the graph are
603 (quietly) ignored.
604
605 """
606
607 if nbunch is None:
608 bunch=self.nodes_iter()
609 elif nbunch in self:
610 bunch=[nbunch]
611 else:
612 try: bunch=[n for n in nbunch if n in self]
613 except TypeError:
614 bunch=[]
615
616 if with_labels:
617 for n in bunch:
618 yield (n,len(self.adj[n]))
619 else:
620 for n in bunch:
621 yield len(self.adj[n])
622
624 """Remove name and delete all nodes and edges from graph."""
625 self.name=''
626 self.adj.clear()
627
629 """Return a (shallow) copy of the graph.
630
631 Identical to dict.copy() of adjacency dict adj, with name
632 copied as well.
633
634 """
635 H=self.__class__()
636 H.name=self.name
637 H.adj=self.adj.copy()
638 for v in H.adj:
639 H.adj[v]=self.adj[v].copy()
640 return H
641
643 """Return the undirected representation of the graph G.
644
645 This graph is undirected, so merely return a copy.
646
647 """
648 return self.copy()
649
650
652 """Return a directed representation of the graph G.
653
654 A new digraph is returned with the same name, same nodes and
655 with each edge u-v represented by two directed edges
656 u->v and v->u.
657
658 """
659 from networkx.digraph import DiGraph
660 H=DiGraph()
661 H.name=self.name
662 H.adj=self.adj.copy()
663 H.succ=H.adj
664 for v in H.adj:
665 H.pred[v]=self.adj[v].copy()
666 H.succ[v]=self.adj[v].copy()
667 return H
668
669
670 - def subgraph(self, nbunch, inplace=False, create_using=None):
671 """
672 Return the subgraph induced on nodes in nbunch.
673
674 nbunch: can be a single node or any iterable container of
675 of nodes. (It can be an iterable or an iterator, e.g. a list,
676 set, graph, file, numeric array, etc.)
677
678 Setting inplace=True will return the induced subgraph in the
679 original graph by deleting nodes not in nbunch. This overrides
680 create_using. Warning: this can destroy the graph.
681
682 Unless otherwise specified, return a new graph of the same
683 type as self. Use (optional) create_using=R to return the
684 resulting subgraph in R. R can be an existing graph-like
685 object (to be emptied) or R can be a call to a graph object,
686 e.g. create_using=DiGraph(). See documentation for empty_graph()
687
688 Note: use subgraph(G) rather than G.subgraph() to access the more
689 general subgraph() function from the operators module.
690
691 """
692 bunch=self.prepare_nbunch(nbunch)
693
694 if inplace:
695
696 bunch=dict.fromkeys(bunch)
697 self.delete_nodes_from([n for n in self if n not in bunch])
698 self.name="Subgraph of (%s)"%(self.name)
699 return self
700
701
702 if create_using is None:
703 H=self.__class__()
704 else:
705 H=create_using
706 H.clear()
707 H.name="Subgraph of (%s)"%(self.name)
708 H.add_nodes_from(bunch)
709
710
711 H_adj=H.adj
712 self_adj=self.adj
713 dict_fromkeys=dict.fromkeys
714 for n in H:
715 H_adj[n]=dict_fromkeys([u for u in self_adj[n] if u in H_adj], None)
716 return H
717
718
719
720
721
722
723
724
726 """Add the path through the nodes in nlist to graph"""
727 fromv = nlist[0]
728 for tov in nlist[1:]:
729 self.add_edge(fromv,tov)
730 fromv=tov
731
733 """Add the cycle of nodes in nlist to graph"""
734 self.add_path(nlist)
735 self.add_edge(nlist[-1],nlist[0])
736
738 """ Return True if graph is directed."""
739 return False
740
742 """Return the size of a graph = number of edges. """
743 return sum(self.degree_iter())/2
744
746 """Return the number of edges between nodes u and v.
747
748 If u and v are not specified return the number of edges in the
749 entire graph.
750
751 The edge argument e=(u,v) can be specified as
752 G.number_of_edges(u,v) or G.number_of_edges(e)
753
754 """
755 if u is None: return self.size()
756 if v is None: (u,v)=u
757 if self.has_edge(u,v):
758 return 1
759 else:
760 return 0
761
763 import doctest
764 suite = doctest.DocFileSuite('tests/graph_Graph.txt',
765 package='networkx')
766 return suite
767
768
769 if __name__ == "__main__":
770 import os
771 import sys
772 import unittest
773 if sys.version_info[:2] < (2, 4):
774 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
775 sys.exit(-1)
776
777 nxbase=sys.path[0]+os.sep+os.pardir
778 sys.path.insert(0,nxbase)
779 unittest.TextTestRunner().run(_test_suite())
780