7
Create an empty graph structure (a "null graph") with
8
zero nodes and zero edges.
10
>>> from networkx import *
13
G can be grown in several ways.
14
By adding one node at a time:
18
by adding a list of nodes:
20
>>> G.add_nodes_from([2,3])
24
>>> G.add_nodes_from(xrange(100,110))
26
or by adding any container of nodes
29
>>> G.add_nodes_from(H)
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.
37
G can also be grown by adding one edge at a time:
39
>>> G.add_edge( (1,2) )
41
by adding a list of edges:
43
>>> G.add_edges_from([(1,2),(1,3)])
45
or by adding any ebunch of edges (see above definition of an ebunch):
47
>>> G.add_edges_from(H.edges())
49
There are no complaints when adding existing nodes or edges:
52
>>> G.add_edge([(1,2),(1,3)])
54
will add new nodes as required.
58
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
59
# Copyright (C) 2004-206 by
60
# Aric Hagberg <hagberg@lanl.gov>
61
# Dan Schult <dschult@colgate.edu>
62
# Pieter Swart <swart@lanl.gov>
63
# Distributed under the terms of the GNU Lesser General Public License
64
# http://www.gnu.org/copyleft/lesser.html
66
from networkx.exception import NetworkXException, NetworkXError
67
import networkx.convert as convert
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.
75
def __init__(self, data=None, name=''):
78
>>> G=Graph(name="empty")
80
creates empty graph G with G.name="empty"
83
self.adj={} # empty adjacency hash
84
# attempt to load graph with data
86
convert.from_whatever(data,create_using=self)
93
"""Return an iterator over the nodes in G.
95
This is the iterator for the underlying adjacency dict.
96
(Allows the expression 'for n in G')
98
return self.adj.iterkeys()
100
def __contains__(self,n):
101
"""Return True if n is a node in graph.
103
Allows the expression 'n in G'.
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
117
"""Return the number of nodes in graph."""
120
def __getitem__(self,n):
121
"""Return the neighbors of node n as a list.
123
This provides graph G the natural property that G[n] returns
128
return self.adj[n].keys()
130
raise NetworkXError, "node %s not in graph"%(n,)
132
def prepare_nbunch(self,nbunch=None):
134
Return a sequence (or iterator) of nodes contained
135
in nbunch which are also in the graph.
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.
141
Note: This routine exhausts any iterator nbunch.
143
Note: To test whether nbunch is a single node,
144
one can use "if nbunch in self:", even after processing
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
152
if nbunch is None: # include all nodes via iterator
153
bunch=self.nodes_iter()
154
elif nbunch in self: # if nbunch is a single node
156
else: # if nbunch is a sequence of nodes
157
try: # capture error for nonsequence/iterator entries.
158
bunch=[n for n in nbunch if n in self]
159
# bunch=(n for n in nbunch if n in self) # need python 2.4
164
def info(self, n=None):
165
"""Print short info for graph G or node n."""
170
print ("Name:").ljust(width_left), self.name
171
type_name = [type(self).__name__]
174
type_name.append("self-loops")
179
type_name.append("multi-edges")
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()
187
print ("Average degree:").ljust(width_left), \
188
round( 2*self.size()/float(len(self)), 4)
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)
198
for i in wrapped_neighbors:
200
print ("Neighbors:").ljust(width_left), i
202
print "".ljust(width_left), i
204
except (KeyError, TypeError):
205
raise NetworkXError, "node %s not in graph"%(n,)
208
def add_node(self, n):
210
Add a single node n to the graph.
212
The node n can be any hashable object except None.
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.
222
>>> from networkx import *
224
>>> K3=complete_graph(3)
226
>>> G.add_node('Hello')
228
>>> G.number_of_nodes()
232
if n not in self.adj:
236
def add_nodes_from(self, nlist):
237
"""Add multiple nodes to the graph.
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.
247
>>> from networkx import *
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']
257
if n not in self.adj:
261
def delete_node(self,n):
262
"""Delete node n from graph.
263
Attempting to delete a non-existent node will raise an exception.
267
for u in self.adj[n].keys():
268
del self.adj[u][n] # (faster) remove all edges n-u in graph
269
# self.delete_edge(n,u)# remove all edges n-u in graph
270
del self.adj[n] # now remove node
271
except KeyError: # NetworkXError if n not in self
272
raise NetworkXError, "node %s not in graph"%(n,)
274
def delete_nodes_from(self,nlist):
275
"""Remove nodes in nlist from graph.
278
an iterable or iterator containing valid node names.
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
287
for u in self.adj[n].keys():
288
del self.adj[u][n] # (faster) remove all edges n-u in graph
289
# self.delete_edge(n,u)# remove all edges n-u in graph
290
del self.adj[n] # now remove node
291
except KeyError: # NetworkXError if n not in self
292
raise NetworkXError, "node %s not in graph"%(n,)
295
def nodes_iter(self):
296
"""Return an iterator over the graph nodes."""
297
return self.adj.iterkeys()
300
"""Return a copy of the graph nodes in a list."""
301
return self.adj.keys()
303
def number_of_nodes(self):
304
"""Return number of nodes."""
307
def has_node(self,n):
308
"""Return True if graph has node n.
310
(duplicates self.__contains__)
311
"n in G" is a more readable version of "G.has_node(n)"?
320
"""Return the order of a graph = number of nodes."""
324
def add_edge(self, u, v=None):
325
"""Add a single edge (u,v) to the graph.
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.
334
The following examples all add the edge (1,2) to graph G.
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
343
(u,v)=u # no v given, assume u is an edge tuple
345
if u not in self.adj:
347
if v not in self.adj:
349
# don't create self loops, fail silently, nodes are still added
356
def add_edges_from(self, ebunch):
357
"""Add all the edges in ebunch to the graph.
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.
367
if u not in self.adj:
369
if v not in self.adj:
371
# don't create self loops, fail silently, nodes are still added
375
self.adj[v][u]=None # add both u-v and v-u
378
def delete_edge(self, u, v=None):
379
"""Delete the single edge (u,v).
381
Can be used in two basic forms:
382
>>> G.delete_edge(u,v)
384
>> G.delete_edge( (u,v) )
385
are equivalent ways of deleting a single edge between nodes u and v.
387
Return without complaining if the nodes or the edge do not exist.
392
if self.adj.has_key(u) and self.adj[u].has_key(v):
396
def delete_edges_from(self, ebunch):
397
"""Delete the edges in ebunch from the graph.
399
ebunch: an iterator or iterable of 2-tuples (u,v).
401
Edges that are not in the graph are ignored.
405
if self.adj.has_key(u) and self.adj[u].has_key(v):
409
def has_edge(self, u, v=None):
410
"""Return True if graph contains the edge u-v, return False otherwise."""
412
(u,v)=u # split tuple in first position
413
return self.adj.has_key(u) and self.adj[u].has_key(v)
415
def has_neighbor(self, u, v):
416
"""Return True if node u has neighbor v.
418
This is equivalent to has_edge(u,v).
421
return self.adj.has_key(u) and self.adj[u].has_key(v)
424
def get_edge(self, u, v=None):
425
"""Return 1 if graph contains the edge u-v.
426
Raise an exception otherwise.
429
# useful for helping build adjacency matrix representation
433
if self.has_edge(u,v):
440
def neighbors_iter(self,n):
441
"""Return an iterator over all neighbors of node n. """
443
return self.adj[n].iterkeys()
445
raise NetworkXError, "node %s not in graph"%(n,)
447
def neighbors(self, n):
448
"""Return a list of nodes connected to node n. """
449
# return lists now, was dictionary for with_labels=True
451
return self.adj[n].keys()
453
raise NetworkXError, "node %s not in graph"%(n,)
455
def edges_iter(self, nbunch=None):
456
"""Return iterator that iterates once over each edge adjacent
457
to nodes in nbunch, or over all edges in graph if no
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.
467
if nbunch is None: # include all nodes via iterator
468
bunch=self.nodes_iter()
469
elif nbunch in self: # if nbunch is a single node
471
else: # if nbunch is a sequence of nodes
472
try: bunch=[n for n in nbunch if n in self]
476
seen={} # helper dict to keep track of multiply stored edges
478
for n2 in self.adj[n1]:
482
del(seen) # clear copy of temp dictionary
483
# iterators can remain after they finish returning values.
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.
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.
495
For digraphs, edges=out_edges
498
return list(self.edges_iter(nbunch))
500
def edge_boundary(self, nbunch1, nbunch2=None):
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.
505
Nodes in nbunch1 and nbunch2 that are not in the graph are
508
nbunch1 and nbunch2 are usually meant to be disjoint,
509
but in the interest of speed and generality, that is
512
This routine is faster if nbunch1 is smaller than nbunch2.
515
if nbunch2 is None: # Then nbunch2 is complement of nbunch1
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] \
520
ndict2=dict.fromkeys(nbunch2)
521
return [(n1,n2) for n1 in nbunch1 if n1 in self for n2 in self.adj[n1] \
524
def node_boundary(self, nbunch1, nbunch2=None):
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.
529
Note that by definition the node_boundary is external to nbunch1.
531
Nodes in nbunch1 and nbunch2 that are not in the graph are
534
nbunch1 and nbunch2 are usually meant to be disjoint,
535
but in the interest of speed and generality, that is
538
This routine is faster if nbunch1 is smaller than nbunch2.
541
if nbunch2 is None: # Then nbunch2 is complement of nbunch1
542
ndict1=dict.fromkeys([n for n in nbunch1 if n in self])
545
for n2 in self.adj[n1]:
547
bdy[n2]=1 # make dict to avoid duplicates
550
ndict2=dict.fromkeys(nbunch2)
552
for n1 in [n for n in nbunch1 if n in self]:
553
for n2 in self.adj[n1]:
556
del ndict2[n2] # avoid duplicates
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.
564
The degree of a node is the number of edges attached to that
567
Can be called in three ways:
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.
574
If with_labels==True, then return a dict that maps each n
575
in nbunch to degree(n).
577
Any nodes in nbunch that are not in the graph are
581
if with_labels: # return a dict
582
return dict(self.degree_iter(nbunch,with_labels))
583
elif nbunch in self: # return a single node
584
return self.degree_iter(nbunch,with_labels).next()
585
else: # return a list
586
return list(self.degree_iter(nbunch,with_labels))
588
def degree_iter(self,nbunch=None,with_labels=False):
589
"""Return iterator that return degree(n) or (n,degree(n))
590
for all n in nbunch. If nbunch is ommitted, then iterate
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.
599
If with_labels==True, iterator will return an (n,degree(n)) tuple of
602
Any nodes in nbunch that are not in the graph are
607
if nbunch is None: # include all nodes via iterator
608
bunch=self.nodes_iter()
609
elif nbunch in self: # if nbunch is a single node
611
else: # if nbunch is a sequence of nodes
612
try: bunch=[n for n in nbunch if n in self]
618
yield (n,len(self.adj[n])) # tuple (n,degree)
621
yield len(self.adj[n]) # just degree
624
"""Remove name and delete all nodes and edges from graph."""
629
"""Return a (shallow) copy of the graph.
631
Identical to dict.copy() of adjacency dict adj, with name
637
H.adj=self.adj.copy()
639
H.adj[v]=self.adj[v].copy()
642
def to_undirected(self):
643
"""Return the undirected representation of the graph G.
645
This graph is undirected, so merely return a copy.
651
def to_directed(self):
652
"""Return a directed representation of the graph G.
654
A new digraph is returned with the same name, same nodes and
655
with each edge u-v represented by two directed edges
659
from networkx.digraph import DiGraph
662
H.adj=self.adj.copy() # copy nodes
663
H.succ=H.adj # fix pointer again
665
H.pred[v]=self.adj[v].copy() # copy adj list to predecessor
666
H.succ[v]=self.adj[v].copy() # copy adj list to successor
670
def subgraph(self, nbunch, inplace=False, create_using=None):
672
Return the subgraph induced on nodes in nbunch.
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.)
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.
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()
688
Note: use subgraph(G) rather than G.subgraph() to access the more
689
general subgraph() function from the operators module.
692
bunch=self.prepare_nbunch(nbunch)
694
if inplace: # demolish all nodes (and attached edges) not in nbunch
695
# override any setting of create_using
696
bunch=dict.fromkeys(bunch) # make a dict
697
self.delete_nodes_from([n for n in self if n not in bunch])
698
self.name="Subgraph of (%s)"%(self.name)
702
if create_using is None: # Graph object of the same type as current graph
704
else: # user specified graph
707
H.name="Subgraph of (%s)"%(self.name)
708
H.add_nodes_from(bunch)
712
self_adj=self.adj # cache
713
dict_fromkeys=dict.fromkeys
715
H_adj[n]=dict_fromkeys([u for u in self_adj[n] if u in H_adj], None)
721
# End of basic operations (under the hood and close to the datastructure)
722
# The following remaining Graph methods use the above methods and not the
723
# datastructure directly
725
def add_path(self, nlist):
726
"""Add the path through the nodes in nlist to graph"""
728
for tov in nlist[1:]:
729
self.add_edge(fromv,tov)
732
def add_cycle(self, nlist):
733
"""Add the cycle of nodes in nlist to graph"""
735
self.add_edge(nlist[-1],nlist[0]) # wrap first element
737
def is_directed(self):
738
""" Return True if graph is directed."""
742
"""Return the size of a graph = number of edges. """
743
return sum(self.degree_iter())/2
745
def number_of_edges(self, u=None, v=None):
746
"""Return the number of edges between nodes u and v.
748
If u and v are not specified return the number of edges in the
751
The edge argument e=(u,v) can be specified as
752
G.number_of_edges(u,v) or G.number_of_edges(e)
755
if u is None: return self.size()
756
if v is None: (u,v)=u
757
if self.has_edge(u,v):
764
suite = doctest.DocFileSuite('tests/graph_Graph.txt',
769
if __name__ == "__main__":
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]
776
# directory of networkx package (relative to this)
777
nxbase=sys.path[0]+os.sep+os.pardir
778
sys.path.insert(0,nxbase) # prepend to search path
779
unittest.TextTestRunner().run(_test_suite())
added
removed
networkx/graph.py
