« back to all changes in this revision
Viewing changes to networkx/xbase.py
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Cyril Brulebois
- Date: 2008-03-02 01:06:32 UTC
- mfrom: (1.2.1 upstream) (3.1.3 hardy)
- Revision ID: james.westby@ubuntu.com-20080302010632-1lp6qe1orf59jl8b
* debian/control:
+ Replace python-setuptools with python-pkg-resources in the
“Recommends:” since pkg_resources is now available in this
separate package, thanks Matthias Klose (Closes: #468721).
* debian/copyright:
+ Use “© $years $name” instead of invalid “$name, $years” and
“(C) $years, $name”, thanks to lintian.
+ Replace python-setuptools with python-pkg-resources in the
“Recommends:” since pkg_resources is now available in this
separate package, thanks Matthias Klose (Closes: #468721).
* debian/copyright:
+ Use “© $years $name” instead of invalid “$name, $years” and
“(C) $years, $name”, thanks to lintian.
- files added:
- MANIFEST.in
- networkx/readwrite
- networkx/tests/readwrite
- files removed:
- debian/patches/00list
- networkx.egg-info
- networkx/tests/data
- scripts
- files modified:
- PKG-INFO
added
removed
networkx/xbase.py
1
""" Methods for general graphs (XGraph) and digraphs (XDiGraph)
2
allowing self-loops, multiple edges, arbitrary (hashable) objects as
3
nodes and arbitrary objects associated with edges.
4
5
The XGraph and XDiGraph classes are extensions of the Graph and
6
DiGraph classes in base.py. The key difference is that an XGraph edge
7
is a 3-tuple e=(n1,n2,x), representing an undirected edge between
8
nodes n1 and n2 that is decorated with the object x. Here n1 and n2
9
are (hashable) node objects and x is a (not necessarily hashable) edge
10
object. Since the edge is undirected, edge (n1,n2,x) is equivalent to
11
edge (n2,n1,x).
12
13
An XDiGraph edge is a similar 3-tuple e=(n1,n2,x), with the additional
14
property of directedness. I.e. e=(n1,n2,x) is a directed edge from n1 to
15
n2 decorated with the object x, and is not equivalent to the edge (n2,n1,x).
16
17
Whether a graph or digraph allow self-loops or multiple edges is
18
determined at the time of object instantiation via specifying the
19
parameters selfloops=True/False and multiedges=True/False. For
20
example,
21
22
an empty XGraph is created with:
23
24
>>> G=XGraph()
25
26
which is equivalent to
27
28
>>> G=XGraph(name="No Name", selfloops=False, multiedges=False)
29
30
and similarly for XDiGraph.
31
32
>>> G=XDiGraph(name="empty", multiedges=True)
33
34
creates an empty digraph G with G.name="empty", that do not
35
allow the addition of selfloops but do allow for multiple edges.
36
37
38
XGraph and XDiGraph are implemented using a data structure based on an
39
adjacency list implemented as a dictionary of dictionaries. The outer
40
dictionary is keyed by node to an inner dictionary keyed by
41
neighboring nodes to the edge data/labels/objects (which default to None
42
to correspond the datastructure used in classes Graph and DiGraph).
43
If multiedges=True, a list of edge data/labels/objects is stored as
44
the value of the inner dictionary. This double dict structure mimics
45
a sparse matrix and allows fast addition, deletion and lookup of nodes
46
and neighbors in large graphs. The underlying datastructure should
47
only be visible in this module. In all other modules, graph-like
48
objects are manipulated solely via the methods defined here and not by
49
acting directly on the datastructure.
50
51
Similarities between XGraph and Graph
52
53
XGraph and Graph differ fundamentally; XGraph edges are 3-tuples
54
(n1,n2,x) and Graph edges are 2-tuples (n1,n2). XGraph inherits from the
55
Graph class, and XDiGraph from the DiGraph class.
56
57
They do share important similarities.
58
59
1. Edgeless graphs are the same in XGraph and Graph.
60
For an edgeless graph, represented by G (member of the Graph class)
61
and XG (member of XGraph class), there is no difference between
62
the datastructures G.adj and XG.adj, other than in the ordering of the
63
keys in the adj dict.
64
65
2. Basic graph construction code for G=Graph() will also work for
66
G=XGraph(). In the Graph class, the simplest graph construction
67
consists of a graph creation command G=Graph() followed by a list
68
of graph construction commands, consisting of successive calls to
69
the methods:
70
71
G.add_node, G.add_nodes_from, G.add_edge, G.add_edges, G.add_path,
72
G.add_cycle G.delete_node, G.delete_nodes_from, G.delete_edge,
73
G.delete_edges_from
74
75
with all edges specified as 2-tuples,
76
77
If one replaces the graph creation command with G=XGraph(), and then
78
apply the identical list of construction commands, the resulting XGraph
79
object will be a simple graph G with identical datastructure G.adj. This
80
property ensures reuse of code developed for graph generation in the
81
Graph class.
82
83
84
Notation
85
86
The following shorthand is used throughout NetworkX documentation and code:
87
(we use mathematical notation n,v,w,... to indicate a node, v=vertex=node).
88
89
G,G1,G2,H,etc:
90
Graphs
91
92
n,n1,n2,u,v,v1,v2:
93
nodes (vertices)
94
95
nlist:
96
a list of nodes (vertices)
97
98
nbunch:
99
a "bunch" of nodes (vertices).
100
an nbunch is any iterable (non-string) container
101
of nodes that is not itself a node of the graph.
102
103
e=(n1,n2):
104
an edge (a python "2-tuple"), also written n1-n2 (if undirected)
105
and n1->n2 (if directed). Note that 3-tuple edges of the form
106
(n1,n2,x) are used in the XGraph and XDiGraph classes. If G is an
107
XGraph, then G.add_edge(n1,n2) will add the edge (n1,n2,None), and
108
G.delete_edge(n1,n2) will attempt to delete the edge (n1,n2,None).
109
In the case of multiple edges between nodes n1 and n2, one can use
110
G.delete_multiedge(n1,n2) to delete all edges between n1 and n2.
111
112
e=(n1,n2,x):
113
an edge triple ("3-tuple") containing the two nodes connected and the
114
edge data/label/object stored associated with the edge. The object x,
115
or a list of objects (if multiedges=True), can be obtained using
116
G.get_edge(n1,n2)
117
118
elist:
119
a list of edges (as 2- or 3-tuples)
120
121
ebunch:
122
a bunch of edges (as 2- or 3-tuples)
123
an ebunch is any iterable (non-string) container
124
of edge-tuples (either 2-tuples, 3-tuples or a mixture).
125
(similar to nbunch, also see add_edge).
126
127
Warning:
128
- The ordering of objects within an arbitrary nbunch/ebunch can be
129
machine-dependent.
130
- Algorithms should treat an arbitrary nbunch/ebunch as
131
once-through-and-exhausted iterable containers.
132
- len(nbunch) and len(ebunch) need not be defined.
133
134
135
Methods
136
=======
137
138
The XGraph class provides rudimentary graph operations:
139
140
Mutating Graph methods
141
----------------------
142
143
- G.add_node(n), G.add_nodes_from(nbunch)
144
- G.delete_node(n), G.delete_nodes_from(nbunch)
145
- G.add_edge(n1,n2), G.add_edge(n1,n2,x), G.add_edge(e),
146
- G.add_edges_from(ebunch)
147
- G.delete_edge(n1,n2), G.delete_edge(n1,n2,x), G.delete_edge(e),
148
- G.delete_edges_from(ebunch)
149
- G.delete_multiedge(n1,n2)
150
- G.add_path(nlist)
151
- G.add_cycle(nlist)
152
153
- G.to_directed()
154
- G.ban_multiedges()
155
- G.allow_multiedges()
156
- G.remove_all_multiedges()
157
- G.ban_selfloops()
158
- G.allow_selfloops()
159
- G.remove_all_selfloops()
160
- G.clear()
161
- G.subgraph(nbunch, inplace=True)
162
163
Non-mutating Graph methods
164
--------------------------
165
166
- G.has_node(n)
167
- G.nodes()
168
- G.nodes_iter()
169
- G.order()
170
- G.neighbors(n), G.neighbors_iter(n)
171
- G.has_edge(n1,n2,x), G.has_neighbor(n1,n2)
172
- G.edges(), G.edges(nbunch)
173
G.edges_iter(), G.edges_iter(nbunch,
174
- G.size()
175
- G.get_edge(n1,n2)
176
- G.degree(), G.degree(n), G.degree(nbunch)
177
- G.degree_iter(), G.degree_iter(n), G.degree_iter(nbunch)
178
- G.number_of_selfloops()
179
- G.nodes_with_selfloops()
180
- G.selfloop_edges()
181
- G.copy()
182
- G.subgraph(nbunch)
183
184
Examples
185
========
186
187
Create an empty graph structure (a "null graph") with no nodes and no edges
188
189
>>> from networkx import *
190
>>> G=XGraph() # default no self-loops, no multiple edges
191
192
You can add nodes in the same way as the simple Graph class
193
>>> G.add_nodes_from(xrange(100,110))
194
195
You can add edges as for simple Graph class, but with optional edge
196
data/labels/objects.
197
198
>>> G.add_edges_from([(1,2,0.776),(1,3,0.535)])
199
200
For graph coloring problems, one could use
201
>>> G.add_edges_from([(1,2,"blue"),(1,3,"red")])
202
203
"""
204
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
205
206
# Copyright (C) 2004-2006 by
207
# Aric Hagberg <hagberg@lanl.gov>
208
# Dan Schult <dschult@colgate.edu>
209
# Pieter Swart <swart@lanl.gov>
210
# Distributed under the terms of the GNU Lesser General Public License
211
# http://www.gnu.org/copyleft/lesser.html
212
#
213
214
from networkx.base import Graph, DiGraph, NetworkXException, NetworkXError
215
import networkx.convert as convert
216
217
class XGraph(Graph):
218
"""A class implementing general undirected graphs, allowing
219
(optional) self-loops, multiple edges, arbitrary (hashable)
220
objects as nodes and arbitrary objects associated with
221
edges.
222
223
An XGraph edge is specified by a 3-tuple e=(n1,n2,x),
224
where n1 and n2 are nodes (hashable objects) and x is an
225
arbitrary (and not necessarily unique) object associated with that
226
edge.
227
228
>>> G=XGraph()
229
230
creates an empty simple and undirected graph (no self-loops or
231
multiple edges allowed). It is equivalent to the expression:
232
233
>>> G=XGraph(name="No Name",selfloops=False,multiedges=False)
234
235
>>> G=XGraph(name="empty",multiedges=True)
236
237
creates an empty graph with G.name="empty", that do not allow the
238
addition of self-loops but do allow for multiple edges.
239
240
See also the XDiGraph class below.
241
242
"""
243
244
245
def __init__(self,data=None,**kwds):
246
"""Initialize XGraph.
247
248
Optional arguments::
249
name: graph name (default="No Name")
250
selfloops: if True selfloops are allowed (default=False)
251
multiedges: if True multiple edges are allowed (default=False)
252
253
"""
254
self.name=kwds.get("name","No Name")
255
self.selfloops=kwds.get("selfloops",False) # no self-loops
256
self.multiedges=kwds.get("multiedges",False) # no multiedges
257
258
# dna is a dictionary attached to each graph and used to store
259
# information about the graph structure. In this version the
260
# dna is provided as a user-defined variable and should not be
261
# relied on.
262
self.dna={}
263
self.dna["datastructure"]="xgraph_dict_of_dicts"
264
265
self.adj={} # adjacency list
266
267
if data is not None:
268
self=convert.from_whatever(data,create_using=self)
269
270
271
def __getitem__(self,n):
272
"""Return the neighbors of node n as a list.
273
274
This provides graph G the natural property that G[n] returns
275
the neighbors of G.
276
277
"""
278
return self.neighbors(n)
279
280
def add_edge(self, n1, n2=None, x=None):
281
"""Add a single edge to the graph.
282
283
Can be called as G.add_edge(n1,n2,x) or as
284
G.add_edge(e), where e=(n1,n2,x).
285
286
n1,n2 are node objects, and are added to the Graph if not already
287
present. Nodes must be hashable Python objects (except None).
288
289
x is an arbitrary (not necessarily hashable) object associated
290
with this edge. It can be used to associate one or more:
291
labels, data records, weights or any arbirary objects to
292
edges. The default is the Python None.
293
294
For example, if the graph G was created with
295
296
>>> G=XGraph()
297
298
then G.add_edge(1,2,"blue") will add the edge (1,2,"blue").
299
300
If G.multiedges=False, then a subsequent G.add_edge(1,2,"red")
301
will change the above edge (1,2,"blue") into the edge (1,2,"red").
302
303
304
If G.multiedges=True, then two successive calls to
305
G.add_edge(1,2,"red") will result in 2 edges of the form
306
(1,2,"red") that can not be distinguished from one another.
307
308
G.add_edge(1,2,"green") will add both edges (1,2,X) and (2,1,X).
309
310
If self.selfloops=False, then calling add_edge(n1,n1,x) will have no
311
effect on the Graph.
312
313
Objects associated to an edge can be retrieved using edges(),
314
edge_iter(), or get_edge().
315
316
"""
317
if n2 is None: # add_edge was called as add_edge(e), with e=(n1,n2,x)
318
if len(n1)==3: # case e=(n1,n2,x)
319
n1,n2,x=n1
320
else: # assume e=(n1,n2)
321
n1,n2=n1 # x=None
322
323
# if edge exists, quietly return if multiple edges are not allowed
324
if not self.multiedges and self.has_edge(n1,n2,x):
325
return
326
327
# add nodes
328
if n1 not in self.adj:
329
self.adj[n1]={}
330
if n2 not in self.adj:
331
self.adj[n2]={}
332
333
# self loop? quietly return if not allowed
334
if not self.selfloops and n1==n2:
335
return
336
337
if self.multiedges: # add x to the end of the list of objects
338
# that defines the edges between n1 and n2
339
self.adj[n1][n2]=self.adj[n1].get(n2,[])+ [x]
340
if n1!=n2:
341
self.adj[n2][n1]=self.adj[n2].get(n1,[])+ [x]
342
else: # x is the new object assigned to single edge between n1 and n2
343
self.adj[n1][n2]=x
344
if n1!=n2:
345
self.adj[n2][n1]=x # a copy would be required to avoid
346
# modifying both at the same time
347
# when doing a delete_edge
348
349
def add_edges_from(self, ebunch):
350
"""Add multiple edges to the graph.
351
352
ebunch: Container of edges. Each edge must be a 3-tuple
353
(n1,n2,x) or a 2-tuple (n1,n2). See add_edge documentation.
354
355
The container must be iterable or an iterator. It is iterated
356
over once.
357
358
"""
359
for e in ebunch:
360
self.add_edge(e)
361
362
def has_edge(self, n1, n2=None, x=None):
363
"""Return True if graph contains edge (n1,n2,x).
364
365
Can be called as G.has_edge(n1,n2,x)
366
or as G.has_edge(e), where e=(n1,n2,x).
367
368
If x is unspecified or None, i.e. if called with an edge of the form
369
e=(n1,n2), then return True if there exists ANY edge between
370
n1 and n2 (equivalent to has_neighbor(n1,n2))
371
372
"""
373
if n2 is None:
374
# has_edge was called as has_edge(e)
375
if len(n1)==3: #case e=(n1,n2,x)
376
n1,n2,x=n1
377
else: # assume e=(n1,n2)
378
n1,n2=n1
379
return self.has_neighbor(n1,n2)
380
else:
381
if x is None:
382
# has_edge was called as has_edge(n1,n2)
383
# return True if there exists ANY
384
# edge between n1 and n2
385
return self.has_neighbor(n1,n2)
386
# case where x is specified
387
if self.multiedges:
388
return (self.adj.has_key(n1) and
389
self.adj[n1].has_key(n2) and
390
x in self.adj[n1][n2])
391
else:
392
return (self.adj.has_key(n1) and
393
self.adj[n1].has_key(n2) and
394
x==self.adj[n1][n2])
395
396
397
def has_neighbor(self, n1, n2):
398
"""Return True if node n1 has neighbor n2.
399
400
Note that this returns True if there exists ANY edge (n1,n2,x)
401
for some x.
402
403
"""
404
return (self.adj.has_key(n1) and
405
self.adj[n1].has_key(n2))
406
407
408
def neighbors_iter(self, n):
409
"""Return an iterator of nodes connected to node n.
410
411
Returns the same data as edges(n) but in a different format.
412
413
"""
414
if n not in self:
415
raise NetworkXError, "node %s not in graph"%n
416
for (u,v,d) in self.edges_iter(n):
417
yield v
418
419
def neighbors(self, n):
420
"""Return a list of nodes connected to node n.
421
422
Returns the same data as edges(n) but in a different format.
423
424
"""
425
return list(self.neighbors_iter(n))
426
427
def get_edge(self, n1, n2):
428
"""Return the objects associated with each edge between n1 and n2.
429
430
If multiedges=False, a single object is returned.
431
If multiedges=True, a list of objects is returned.
432
If no edge exists, raise an exception.
433
434
"""
435
try:
436
result = self.adj[n1][n2] # raises KeyError if edge not found
437
except KeyError:
438
raise NetworkXError, "no edge (%s,%s) in graph"%(n1,n2)
439
if self.multiedges:
440
return result[:] # return a copy so user can't mess up list
441
return result
442
443
def edges_iter(self, nbunch=None):
444
"""Return iterator that iterates once over each edge adjacent
445
to nodes in nbunch, or over all nodes in graph if nbunch=None.
446
447
See add_node for definition of nbunch.
448
449
Nodes in nbunch that are not in the graph will be (quietly) ignored.
450
451
"""
452
# prepare nbunch
453
if nbunch is None: # include all nodes via iterator
454
bunch=self.nodes_iter()
455
elif nbunch in self: # if nbunch is a single node
456
bunch=[nbunch]
457
else: # if nbunch is a sequence of nodes
458
try: bunch=[n for n in nbunch if n in self]
459
except TypeError:
460
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
461
# nbunch ready
462
seen={} # helper dict used to avoid duplicate edges
463
if self.multiedges:
464
for n1 in bunch:
465
for n2,elist in self.adj[n1].iteritems():
466
if n2 not in seen:
467
for data in elist:
468
yield (n1,n2,data)
469
seen[n1]=1
470
else:
471
for n1 in bunch:
472
for n2,data in self.adj[n1].iteritems():
473
if n2 not in seen:
474
yield (n1,n2,data)
475
seen[n1]=1
476
del(seen) # clear copy of temp dictionary
477
# iterators can remain after they finish returning values.
478
479
def edges(self, nbunch=None):
480
"""Return a list of all edges that originate at a node in nbunch,
481
or a list of all edges if nbunch=None.
482
483
See add_node for definition of nbunch.
484
485
Nodes in nbunch that are not in the graph will be (quietly) ignored.
486
487
For digraphs, edges=out_edges
488
489
"""
490
return list(self.edges_iter(nbunch))
491
492
def delete_multiedge(self, n1, n2):
493
""" Delete all edges between nodes n1 and n2.
494
495
When there is only a single edge allowed between nodes
496
(multiedges=False), this just calls delete_edge(n1,n2)
497
otherwise (multiedges=True) all edges between n1 and n2 are deleted.
498
"""
499
if self.multiedges:
500
for x in self.get_edge(n1, n2):
501
self.delete_edge(n1, n2, x)
502
else:
503
self.delete_edge(n1, n2)
504
return
505
506
507
def delete_edge(self, n1, n2=None, x=None):
508
"""Delete the edge (n1,n2,x) from the graph.
509
510
Can be called either as
511
512
>>> G.delete_edge(n1,n2,x)
513
or
514
>>> G.delete_edge(e)
515
516
where e=(n1,n2,x).
517
518
The default edge data is x=None
519
520
If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2)
521
then the edge (n1,n2,None) will be deleted.
522
523
If the edge does not exist, do nothing.
524
525
To delete *all* edges between n1 and n2 use
526
>>> G.delete_multiedges(n1,n2)
527
528
"""
529
if n2 is None: # was called as delete_edge(e)
530
if len(n1)==3: # case e=(n1,n2,x)
531
n1,n2,x=n1
532
else: # assume e=(n1,n2), x unspecified, set to None
533
n1,n2=n1 # x=None
534
535
if self.multiedges:
536
if (self.adj.has_key(n1)
537
and self.adj[n1].has_key(n2)
538
and x in self.adj[n1][n2]): # if (n1,n2,x) is an edge;
539
self.adj[n1][n2].remove(x) # remove the edge item from list
540
if n1!=n2: # and if not self loop
541
self.adj[n2][n1].remove(x) # remove n2->n1 entry
542
if len(self.adj[n1][n2])==0: # if last edge between n1 and n2
543
del self.adj[n1][n2] # was deleted, remove all trace
544
if n1!=n2: # and if not self loop
545
del self.adj[n2][n1] # remove n2->n1 entry
546
else: # delete single edge
547
if self.has_neighbor(n1,n2):
548
del self.adj[n1][n2]
549
if n1!=n2:
550
del self.adj[n2][n1]
551
return
552
553
def delete_edges_from(self, ebunch):
554
"""Delete edges in ebunch from the graph.
555
556
ebunch: Container of edges. Each edge must be a 3-tuple
557
(n1,n2,x) or a 2-tuple (n1,n2). In the latter case all edges
558
between n1 and n2 will be deleted. See delete_edge.
559
560
The container must be iterable or an iterator, and
561
is iterated over once. Edges that are not in the graph are ignored.
562
563
"""
564
for e in ebunch:
565
# the function-call-in-a-loop cost can be avoided by pasting
566
# in the code from delete_edge, do we have a good reason ?
567
self.delete_edge(e)
568
569
def degree(self, nbunch=None, with_labels=False):
570
"""Return degree of single node or of nbunch of nodes.
571
If nbunch is omitted or nbunch=None, then return
572
degrees of *all* nodes.
573
574
The degree of a node is the number of edges attached to that
575
node.
576
577
Can be called in three ways:
578
- G.degree(n): return the degree of node n
579
- G.degree(nbunch): return a list of values,
580
one for each n in nbunch
581
(nbunch is any iterable container of nodes.)
582
- G.degree(): same as nbunch = all nodes in graph.
583
Always return a list.
584
585
If with_labels==True, then return a dict that maps each n
586
in nbunch to degree(n).
587
588
Any nodes in nbunch that are not in the graph are
589
(quietly) ignored.
590
591
"""
592
# prepare nbunch
593
if nbunch is None: # include all nodes via iterator
594
bunch=self.nodes_iter()
595
elif nbunch in self: # if nbunch is a single node
596
bunch=[nbunch]
597
else: # if nbunch is a sequence of nodes
598
try: bunch=[n for n in nbunch if n in self]
599
except TypeError:
600
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
601
# nbunch ready
602
d={}
603
if self.multiedges:
604
for n in bunch:
605
deg = sum([len(e) for e in self.adj[n].itervalues()])
606
if self.adj[n].has_key(n) and self.selfloops:
607
deg+= len(self.adj[n][n]) # double count self-loops
608
d[n]=deg
609
else:
610
for n in bunch:
611
deg=len(self.adj[n])
612
deg+= self.adj[n].has_key(n) # double count self-loop
613
d[n]=deg
614
if with_labels: return d # return the dict
615
elif nbunch in self: return d.values()[0] # single node, so single value
616
return d.values() # return a list
617
618
def degree_iter(self,nbunch=None,with_labels=False):
619
"""This is the degree() method returned in iterator form.
620
If with_labels=True, iterator yields 2-tuples of form (n,degree(n))
621
(like iteritems() on a dict.)
622
"""
623
# prepare nbunch
624
if nbunch is None: # include all nodes via iterator
625
bunch=self.nodes_iter()
626
elif nbunch in self: # if nbunch is a single node
627
bunch=[nbunch]
628
else: # if nbunch is a sequence of nodes
629
try: bunch=[n for n in nbunch if n in self]
630
except TypeError:
631
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
632
# nbunch ready
633
if self.multiedges:
634
for n in bunch:
635
deg = sum([len(e) for e in self.adj[n].itervalues()])
636
if self.selfloops and self.adj[n].has_key(n):
637
deg+= len(self.adj[n][n]) # double count self-loops
638
if with_labels:
639
yield (n,deg) # tuple (n,degree)
640
else:
641
yield deg
642
else:
643
for n in bunch:
644
deg=len(self.adj[n])
645
deg+= self.adj[n].has_key(n) # double count self-loop
646
if with_labels:
647
yield (n,deg) # tuple (n,degree)
648
else:
649
yield deg
650
651
652
def number_of_edges(self):
653
"""Return number of edges"""
654
return sum(self.degree_iter())/2
655
656
# def size(self):
657
# """Return the size of a graph = number of edges. """
658
# return self.number_of_edges()
659
660
def copy(self):
661
"""Return a (shallow) copy of the graph.
662
663
Return a new XGraph with same name and same attributes for
664
selfloop and multiededges. Each node and each edge in original
665
graph are added to the copy.
666
667
"""
668
H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops)
669
H.name=self.name
670
H.dna=self.dna.copy()
671
for n in self:
672
H.add_node(n)
673
for e in self.edges_iter():
674
H.add_edge(e)
675
return H
676
677
def to_directed(self):
678
"""Return a directed representation of the XGraph G.
679
680
A new XDigraph is returned with the same name, same nodes and
681
with each edge (u,v,x) replaced by two directed edges
682
(u,v,x) and (v,u,x).
683
684
"""
685
H=XDiGraph(selfloops=self.selfloops,multiedges=self.multiedges)
686
H.name=self.name
687
H.dna=self.dna.copy()
688
for n in self:
689
H.add_node(n)
690
for e in self.edges_iter():
691
H.add_edge(e[0],e[1],e[2])
692
H.add_edge(e[1],e[0],e[2])
693
return H
694
695
def nodes_with_selfloops(self):
696
"""Return list of all nodes having self-loops."""
697
if not self.selfloops:
698
return []
699
else:
700
return [n for n in self if self.adj[n].has_key(n)]
701
702
def selfloop_edges(self):
703
"""Return all edges that are self-loops."""
704
nlist=self.nodes_with_selfloops()
705
loops=[]
706
for n in nlist:
707
if self.multiedges:
708
for x in self.adj[n][n]:
709
loops.append((n,n,x))
710
else:
711
loops.append((n,n,self.adj[n][n]))
712
return loops
713
714
def number_of_selfloops(self):
715
"""Return number of self-loops in graph."""
716
return len(self.selfloop_edges())
717
718
def allow_selfloops(self):
719
"""Henceforth allow addition of self-loops
720
(edges from a node to itself).
721
722
This doesn't change the graph structure, only what you can do to it.
723
"""
724
self.selfloops=True
725
726
def remove_all_selfloops(self):
727
"""Remove self-loops from the graph (edges from a node to itself)."""
728
if not self.selfloops:
729
# nothing to do
730
return
731
for n in self.adj:
732
if self.adj[n].has_key(n):
733
del self.adj[n][n]
734
735
def ban_selfloops(self):
736
"""Remove self-loops from the graph and henceforth do not allow
737
their creation.
738
"""
739
self.remove_all_selfloops()
740
self.selfloops=False
741
742
743
def allow_multiedges(self):
744
"""Henceforth allow addition of multiedges (more than one
745
edge between two nodes).
746
747
Warning: This causes all edge data to be converted to lists.
748
"""
749
if self.multiedges: return # already multiedges
750
self.multiedges=True
751
for v in self.adj:
752
for (u,edgedata) in self.adj[v].iteritems():
753
self.adj[v][u]=[edgedata]
754
755
def remove_all_multiedges(self):
756
# FIXME, write tests
757
"""Remove multiedges retaining the data from the first edge"""
758
if not self.multiedges: # nothing to do
759
return
760
for v in self.adj:
761
for (u,edgedata) in self.adj[v].iteritems():
762
if len(edgedata)>1:
763
self.adj[v][u]=[edgedata[0]]
764
765
def ban_multiedges(self):
766
"""Remove multiedges retaining the data from the first edge.
767
Henceforth do not allow multiedges.
768
"""
769
if not self.multiedges: # nothing to do
770
return
771
self.multiedges=False
772
for v in self.adj:
773
for (u,edgedata) in self.adj[v].iteritems():
774
self.adj[v][u]=edgedata[0]
775
776
def subgraph(self, nbunch, inplace=False, create_using=None):
777
"""Return the subgraph induced on nodes in nbunch.
778
779
nbunch: either a singleton node, a string (which is treated
780
as a singleton node), or any non-string iterable or iterator.
781
(It can be an iterable or an iterator, e.g. a list,
782
set, graph, file, numeric array, etc.)
783
784
785
Setting inplace=True will return induced subgraph in original
786
graph by deleting nodes not in nbunch. It overrides any setting
787
of create_using.
788
789
WARNING: specifying inplace=True makes it easy to destroy the graph.
790
791
Unless otherwise specified, return a new graph of the same
792
type as self. Use (optional) create_using=R to return the
793
resulting subgraph in R. R can be an existing graph-like
794
object (to be emptied) or R can be a call to a graph object,
795
e.g. create_using=DiGraph(). See documentation for
796
empty_graph()
797
798
Note: use subgraph(G) rather than G.subgraph() to access the more
799
general subgraph() function from the operators module.
800
801
"""
802
bunch=self.prepare_nbunch(nbunch)
803
804
# WARNING: setting inplace=True destroys the graph.
805
if inplace: # demolish all nodes (and attached edges) not in nbunch
806
# override any setting of create_using
807
bunch=dict.fromkeys(bunch) # make a dict
808
self.delete_nodes_from([n for n in self if n not in bunch])
809
self.name="Subgraph of (%s)"%(self.name)
810
return self
811
812
# Create new graph
813
if create_using is None:
814
# return a Graph object of the same type as current graph
815
# subgraph inherits multiedges and selfloops settings
816
H=self.__class__(multiedges=self.multiedges,
817
selfloops=self.selfloops)
818
else:
819
# Recreate subgraph with create_using.
820
# Currently create_using must be an XGraph type object
821
# or a multi-edge list will be copied as a single edge
822
H=create_using
823
H.clear()
824
H.name="Subgraph of (%s)"%(self.name)
825
H.add_nodes_from(bunch)
826
827
# add edges
828
H_adj=H.adj # store in local variables
829
self_adj=self.adj
830
if self.multiedges:
831
for n in H: # create neighbor dict with copy of data list from self
832
H_adj[n]=dict([(u,d[:]) for u,d in self_adj[n].iteritems() if u in H_adj])
833
else: # no multiedges
834
for n in H: # create neighbor dict with edge data from self
835
H_adj[n]=dict([(u,d) for u,d in self_adj[n].iteritems() if u in H_adj])
836
return H
837
838
839
840
# End of basic operations (under the hood and close to the datastructure)
841
# The following remaining Graph methods use the above methods and not the
842
# datastructure directly
843
844
def add_path(self, nlist):
845
"""Add the path through the nodes in nlist to graph"""
846
nfrom = nlist.pop(0)
847
while len(nlist) > 0:
848
nto=nlist.pop(0)
849
self.add_edge(nfrom,nto)
850
nfrom=nto
851
852
def add_cycle(self, nlist):
853
"""Add the cycle of nodes in nlist to graph"""
854
self.add_path(nlist+[nlist[0]]) # wrap first element
855
856
class XDiGraph(DiGraph):
857
""" A class implementing general digraphs, allowing
858
(optional) self-loops, (optional) multiple edges,
859
arbitrary (hashable) objects as nodes, and arbitrary
860
objects associated with edges.
861
862
As in XGraph, an XDiGraph edge is uniquely specified by a 3-tuple
863
e=(n1,n2,x), where n1 and n2 are (hashable) objects (nodes) and x
864
is an arbitrary (and not necessarily unique) object associated with
865
that edge.
866
867
See the documentation of XGraph for the use of the optional
868
parameters selfloops (defaults is False) and multiedges
869
(default is False).
870
871
XDiGraph inherits from DiGraph, with all purely node-specific methods
872
identical to those of DiGraph. XDiGraph edges are identical to XGraph
873
edges, except that they are directed rather than undirected.
874
XDiGraph replaces the following DiGraph methods:
875
876
- __init__: read multiedges and selfloops kwds.
877
- add_edge
878
- add_edges_from
879
- delete_edge
880
- delete_edges_from
881
- delete_multiedge
882
- has_edge
883
- edges_iter
884
- degree_iter
885
- degree
886
- copy
887
- clear
888
- subgraph
889
- is_directed
890
- to_directed
891
892
XDiGraph also adds the following methods to those of DiGraph:
893
894
- allow_selfloops
895
- remove_all_selfloops
896
- ban_selfloops
897
- allow_multiedges
898
- ban_multiedges
899
- remove_all_multiedges
900
901
XDigraph adds the following methods to those of XGraph:
902
903
- has_successor
904
- successors
905
- successors_iter
906
- has_predecessor
907
- predecessors
908
- predecessors_iter
909
- out_degree
910
- out_degree_iter
911
- in_degree
912
- in_degree_iter
913
- to_undirected
914
- is_directed
915
916
"""
917
# XDiGraph, like DiGraph, uses two adjacency lists:
918
# predecessors of node n are stored in the dict
919
# self.pred successors of node n are stored in the
920
# dict self.succ=self.adj
921
#
922
# For each edge (n1,n2,x) in self.succ there exists a corresponding edge
923
# (n2,n1,x) in self.pred
924
925
def __init__(self,data=None,**kwds):
926
"""Initialize XDiGraph.
927
928
Optional arguments::
929
name: digraph name (default="No Name")
930
selfloops: if True then selfloops are allowed (default=False)
931
multiedges: if True then multiple edges are allowed (default=False)
932
933
"""
934
self.name=kwds.get("name","No Name")
935
self.selfloops=kwds.get("selfloops",False) # no self-loops
936
self.multiedges=kwds.get("multiedges",False) # no multiedges
937
938
# dna is a dictionary attached to each graph and used to store
939
# information about the graph structure. In this version the
940
# dna is provided as a user-defined variable and should not be
941
# relied on.
942
self.dna={}
943
self.dna["datastructure"]="xgraph_dict_of_dicts"
944
945
self.adj={} # adjacency list
946
self.pred={} # predecessor
947
self.succ=self.adj # successor is same as adj
948
949
if data is not None:
950
self=convert.from_whatever(data,create_using=self)
951
952
953
954
955
def add_edge(self, n1, n2=None, x=None):
956
"""Add a single directed edge to the digraph.
957
958
Can be called as G.add_edge(n1,n2,x)
959
or as G.add_edge(e), where e=(n1,n2,x).
960
961
If called as G.add_edge(n1,n2) or G.add_edge(e), with e=(n1,n2),
962
then this is interpreted as adding the edge (n1,n2,None) to
963
be compatible with the Graph and DiGraph classes.
964
965
n1,n2 are node objects, and are added to the Graph if not already
966
present. Nodes must be hashable Python objects (except None).
967
968
x is an arbitrary (not necessarily hashable) object associated
969
with this edge. It can be used to associate one or more,
970
labels, data records, weights or any arbirary objects to
971
edges. The default is the Python None.
972
973
For example, if the graph G was created with
974
975
>>> G=XDiGraph()
976
977
then G.add_edge(1,2,"blue") will add the directed edge (1,2,"blue").
978
979
If G.multiedges=False, then a subsequent G.add_edge(1,2,"red")
980
will change the above edge (1,2,"blue") into the edge (1,2,"red").
981
982
On the other hand, if G.multiedges=True, then two successive calls to
983
G.add_edge(1,2,"red") will result in 2 edges of the form
984
(1,2,"red") that can not be distinguished from one another.
985
986
If self.selfloops=False, then any attempt to create a self-loop
987
with add_edge(n1,n1,x) will have no effect on the digraph and
988
will not elicit a warning.
989
990
Objects imbedded in the edges from n1 to n2 (if any), can be
991
retrieved using get_edge(n1,n2), or calling edges(n1) or
992
edge_iter(n1) to return all edges attached to n1.
993
994
"""
995
996
if n2 is None: # add_edge was called as add_edge(e), with e a tuple
997
if len(n1)==3: #case e=(n1,n2,x)
998
n1,n2,x=n1
999
else: # assume e=(n1,n2)
1000
n1,n2=n1 # x=None
1001
1002
1003
# if edge exists, quietly return if multiple edges are not allowed
1004
if not self.multiedges and self.has_edge(n1,n2,x):
1005
return
1006
1007
# add nodes
1008
if n1 not in self.succ:
1009
self.succ[n1]={}
1010
if n1 not in self.pred:
1011
self.pred[n1]={}
1012
if n2 not in self.succ:
1013
self.succ[n2]={}
1014
if n2 not in self.pred:
1015
self.pred[n2]={}
1016
1017
# self loop? quietly return if not allowed
1018
if not self.selfloops and n1==n2:
1019
return
1020
1021
if self.multiedges: # append x to the end of the list of objects
1022
# that defines the edges between n1 and n2
1023
self.succ[n1][n2]=self.succ[n1].get(n2,[])+ [x]
1024
self.pred[n2][n1]=self.pred[n2].get(n1,[])+ [x]
1025
else: # x is the new object assigned to single edge between n1 and n2
1026
self.succ[n1][n2]=x
1027
self.pred[n2][n1]=x # note that the same object is referred to
1028
# from both succ and pred
1029
1030
def add_edges_from(self, ebunch):
1031
"""Add multiple directed edges to the digraph.
1032
ebunch: Container of edges. Each edge e in container will be added
1033
using add_edge(e). See add_edge documentation.
1034
The container must be iterable or an iterator.
1035
It is iterated over once.
1036
"""
1037
for e in ebunch:
1038
# the function-call-in-a-loop cost can be avoided by pasting
1039
# in the code from add_edge, do we have a good reason ?
1040
self.add_edge(e)
1041
1042
def has_edge(self, n1, n2=None, x=None):
1043
"""Return True if digraph contains directed edge (n1,n2,x).
1044
1045
Can be called as G.has_edge(n1,n2,x)
1046
or as G.has_edge(e), where e=(n1,n2,x).
1047
1048
If x is unspecified, i.e. if called with an edge of the form
1049
e=(n1,n2), then return True if there exists ANY edge from n1
1050
to n2 (equivalent to has_successor(n1,n2)).
1051
1052
"""
1053
# parse args
1054
if n2 is None:
1055
# has_edge was called as has_edge(e)
1056
if len(n1)==3: # case e=(n1,n2,x)
1057
n1,n2,x=n1
1058
else: # case=(n1,n2)
1059
n1,n2=n1 # return True if there exists ANY edge n1->n2
1060
return self.has_successor(n1,n2)
1061
else:
1062
if x is None:
1063
# has_edge was called as has_edge(n1,n2)
1064
# return True if there exists ANY edge n1->n2
1065
return self.has_successor(n1,n2)
1066
# case where x is specified
1067
if self.multiedges:
1068
return (self.succ.has_key(n1) and
1069
self.succ[n1].has_key(n2) and
1070
x in self.succ[n1][n2])
1071
else:
1072
return (self.succ.has_key(n1) and
1073
self.succ[n1].has_key(n2) and
1074
x==self.succ[n1][n2])
1075
1076
def has_successor(self, n1, n2):
1077
"""Return True if node n1 has a successor n2.
1078
1079
Return True if there exists ANY edge (n1,n2,x) for some x.
1080
1081
"""
1082
return (self.succ.has_key(n1) and
1083
self.succ[n1].has_key(n2))
1084
1085
def has_predecessor(self, n1, n2):
1086
"""Return True if node n1 has a predecessor n2.
1087
1088
Return True if there exists ANY edge (n2,n1,x) for some x.
1089
1090
"""
1091
return (self.pred.has_key(n1) and
1092
self.pred[n1].has_key(n2))
1093
1094
1095
def get_edge(self, n1, n2):
1096
"""Return the objects associated with each edge between n1 and n2.
1097
1098
If multiedges=False, a single object is returned.
1099
If multiedges=True, a list of objects is returned.
1100
If no edge exists, raise an exception.
1101
1102
"""
1103
try:
1104
result = self.adj[n1][n2] # raises KeyError if edge not found
1105
except KeyError:
1106
raise NetworkXError, "no edge (%s,%s) in graph"%(n1,n2)
1107
if self.multiedges:
1108
return result[:] # return a copy so user can't mess up list
1109
return result
1110
1111
1112
def delete_multiedge(self, n1, n2):
1113
""" Delete all edges between nodes n1 and n2.
1114
1115
When there is only a single edge allowed between nodes
1116
(multiedges=False), this just calls delete_edge(n1,n2),
1117
otherwise (multiedges=True) all edges between n1 and n2 are deleted.
1118
"""
1119
if self.multiedges:
1120
for x in self.get_edge(n1,n2):
1121
self.delete_edge(n1,n2,x)
1122
else:
1123
self.delete_edge(n1,n2)
1124
return
1125
1126
1127
def delete_edge(self, n1, n2=None, x=None, all=False):
1128
"""Delete the directed edge (n1,n2,x) from the graph.
1129
1130
Can be called either as
1131
>>> G.delete_edge(n1,n2,x)
1132
or as
1133
>>> G.delete_edge(e)
1134
where e=(n1,n2,x).
1135
1136
If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2)
1137
then the edge (n1,n2,None) will be deleted.
1138
1139
If the edge does not exist, do nothing.
1140
1141
To delete *all* edges between n1 and n2 use
1142
>>> G.delete_multiedges(n1,n2)
1143
1144
"""
1145
if n2 is None: # was called as delete_edge(e)
1146
if len(n1)==3: #case e=(n1,n2,x)
1147
n1,n2,x=n1
1148
else: # assume e=(n1,n2)
1149
n1,n2=n1 # x=None
1150
1151
if self.multiedges: # multiedges are stored as a list
1152
if (self.succ.has_key(n1)
1153
and self.succ[n1].has_key(n2)
1154
and x in self.succ[n1][n2]):
1155
self.succ[n1][n2].remove(x) # remove the edge item from list
1156
self.pred[n2][n1].remove(x)
1157
if len(self.succ[n1][n2])==0: # if last edge between n1 and n2
1158
del self.succ[n1][n2] # was deleted, remove all trace
1159
del self.pred[n2][n1]
1160
else: # delete single edge
1161
if self.has_successor(n1,n2):
1162
del self.succ[n1][n2]
1163
del self.pred[n2][n1]
1164
return
1165
1166
def delete_edges_from(self, ebunch):
1167
"""Delete edges in ebunch from the graph.
1168
1169
ebunch: Container of edges. Each edge must be a 3-tuple
1170
(n1,n2,x) or a 2-tuple (n1,n2). The container must be
1171
iterable or an iterator, and is iterated over once.
1172
1173
Edges that are not in the graph are ignored.
1174
1175
"""
1176
for e in ebunch:
1177
self.delete_edge(e)
1178
1179
def out_edges_iter(self, nbunch=None):
1180
"""Return iterator that iterates once over each edge pointing
1181
out of nodes in nbunch, or over all edges in digraph if no
1182
nodes are specified.
1183
1184
See add_node for definition of nbunch.
1185
1186
Nodes in nbunch that are not in the graph will be (quietly) ignored.
1187
1188
"""
1189
# prepare nbunch
1190
if nbunch is None: # include all nodes via iterator
1191
bunch=self.nodes_iter()
1192
elif nbunch in self: # if nbunch is a single node
1193
bunch=[nbunch]
1194
else: # if nbunch is a sequence of nodes
1195
try: bunch=[n for n in nbunch if n in self]
1196
except TypeError:
1197
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
1198
# nbunch ready
1199
if self.multiedges:
1200
for n1 in bunch:
1201
for n2,elist in self.succ[n1].iteritems():
1202
for data in elist:
1203
yield (n1,n2,data)
1204
else:
1205
for n1 in bunch:
1206
for n2,data in self.succ[n1].iteritems():
1207
yield (n1,n2,data)
1208
1209
def in_edges_iter(self, nbunch=None):
1210
"""Return iterator that iterates once over each edge pointing in
1211
to nodes in nbunch, or over all edges in digraph if no
1212
nodes are specified.
1213
1214
See add_node for definition of nbunch.
1215
1216
Nodes in nbunch that are not in the graph will be (quietly) ignored.
1217
1218
"""
1219
# prepare nbunch
1220
if nbunch is None: # include all nodes via iterator
1221
bunch=self.nodes_iter()
1222
elif nbunch in self: # if nbunch is a single node
1223
bunch=[nbunch]
1224
else: # if nbunch is a sequence of nodes
1225
try: bunch=[n for n in nbunch if n in self]
1226
except TypeError:
1227
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
1228
# nbunch ready
1229
if self.multiedges:
1230
for n1 in bunch:
1231
for n2,elist in self.pred[n1].iteritems():
1232
for data in elist:
1233
yield (n2,n1,data)
1234
else:
1235
for n1 in bunch:
1236
for n2,data in self.pred[n1].iteritems():
1237
yield (n2,n1,data)
1238
1239
def out_edges(self, nbunch=None):
1240
"""Return a list of all edges that point out of nodes in nbunch,
1241
or a list of all edges if nbunch=None.
1242
1243
See add_node for definition of nbunch.
1244
1245
Nodes in nbunch that are not in the graph will be (quietly) ignored.
1246
1247
"""
1248
return list(self.out_edges_iter(nbunch))
1249
1250
1251
def in_edges(self, nbunch=None):
1252
"""Return a list of all edges that point in to nodes in nbunch,
1253
or a list of all edges if nbunch=None.
1254
1255
See add_node for definition of nbunch.
1256
1257
Nodes in nbunch that are not in the graph will be (quietly) ignored.
1258
1259
"""
1260
return list(self.in_edges_iter(nbunch))
1261
1262
1263
edges_iter=out_edges_iter
1264
edges=out_edges
1265
1266
1267
def successors_iter(self, n):
1268
"""Return an iterator of nodes pointing out of node n.
1269
1270
Returns the same data as out_edges(n) but in a different format.
1271
1272
"""
1273
if n not in self:
1274
raise NetworkXError, "node %s not in graph"%n
1275
for (u,v,d) in self.out_edges_iter(n):
1276
yield v
1277
1278
def predecessors_iter(self, n):
1279
"""Return an iterator of nodes pointing in to node n.
1280
1281
Returns the same data as out_edges(n) but in a different format.
1282
1283
"""
1284
if n not in self:
1285
raise NetworkXError, "node %s not in graph"%n
1286
for (u,v,d) in self.in_edges_iter(n):
1287
yield u
1288
1289
def in_degree(self, nbunch=None, with_labels=False):
1290
"""Return the in-degree of single node or of nbunch of nodes.
1291
If nbunch is omitted or nbunch=None, then return
1292
in-degrees of *all* nodes.
1293
1294
If with_labels=True, then return a dict that maps each n
1295
in nbunch to in_degree(n).
1296
1297
Any nodes in nbunch that are not in the graph are
1298
(quietly) ignored.
1299
1300
"""
1301
# prepare nbunch
1302
if nbunch is None: # include all nodes via iterator
1303
bunch=self.nodes_iter()
1304
elif nbunch in self: # if nbunch is a single node
1305
bunch=[nbunch]
1306
else: # if nbunch is a sequence of nodes
1307
try: bunch=[n for n in nbunch if n in self]
1308
except TypeError:
1309
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
1310
# nbunch ready
1311
d={}
1312
if self.multiedges:
1313
for n in bunch:
1314
d[n] = sum([len(edge) for edge in self.pred[n].itervalues()])
1315
else:
1316
for n in bunch:
1317
d[n]=len(self.pred[n])
1318
1319
if with_labels: return d # return the dict
1320
elif nbunch in self: return d.values()[0] # single node, so single value
1321
return d.values() # return a list
1322
1323
def out_degree(self, nbunch=None, with_labels=False):
1324
"""Return the out-degree of single node or of nbunch of nodes.
1325
If nbunch is omitted or nbunch=None, then return
1326
out-degrees of *all* nodes.
1327
1328
If with_labels=True, then return a dict that maps each n
1329
in nbunch to out_degree(n).
1330
1331
Any nodes in nbunch that are not in the graph are
1332
(quietly) ignored.
1333
1334
"""
1335
# prepare nbunch
1336
if nbunch is None: # include all nodes via iterator
1337
bunch=self.nodes_iter()
1338
elif nbunch in self: # if nbunch is a single node
1339
bunch=[nbunch]
1340
else: # if nbunch is a sequence of nodes
1341
try: bunch=[n for n in nbunch if n in self]
1342
except TypeError:
1343
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
1344
# nbunch ready
1345
d={}
1346
if self.multiedges:
1347
for n in bunch:
1348
d[n] = sum([len(edge) for edge in self.succ[n].itervalues()])
1349
else:
1350
for n in bunch:
1351
d[n]=len(self.succ[n])
1352
1353
if with_labels: return d # return the dict
1354
elif nbunch in self: return d.values()[0] # single node, so single value
1355
return d.values() # return a list
1356
1357
def degree(self, nbunch=None, with_labels=False):
1358
"""Return the out-degree of single node or of nbunch of nodes.
1359
If nbunch is omitted or nbunch=None, then return
1360
out-degrees of *all* nodes.
1361
1362
If with_labels=True, then return a dict that maps each n
1363
in nbunch to out_degree(n).
1364
1365
Any nodes in nbunch that are not in the graph are
1366
(quietly) ignored.
1367
1368
"""
1369
# prepare nbunch
1370
if nbunch is None: # include all nodes via iterator
1371
bunch=self.nodes_iter()
1372
elif nbunch in self: # if nbunch is a single node
1373
bunch=[nbunch]
1374
else: # if nbunch is a sequence of nodes
1375
try: bunch=[n for n in nbunch if n in self]
1376
except TypeError:
1377
raise NetworkXError, "nbunch is not a node or a sequence of nodes."
1378
# nbunch ready
1379
d={}
1380
if self.multiedges:
1381
for n in bunch:
1382
d[n]=sum([len(e) for e in self.succ[n].itervalues()]) + \
1383
sum([len(e) for e in self.pred[n].itervalues()])
1384
else:
1385
for n in bunch:
1386
d[n]=len(self.succ[n])+len(self.pred[n])
1387
if with_labels: return d # return the dict
1388
elif nbunch in self: return d.values()[0] # single node, so single value
1389
return d.values() # return a list
1390
1391
def nodes_with_selfloops(self):
1392
"""Return list of all nodes having self-loops."""
1393
if not self.selfloops:
1394
return []
1395
else:
1396
# only need to do this for succ
1397
return [n for n in self if self.succ[n].has_key(n)]
1398
1399
def selfloop_edges(self):
1400
"""Return all edges that are self-loops."""
1401
nlist=self.nodes_with_selfloops()
1402
loops=[]
1403
for n in nlist:
1404
if self.multiedges:
1405
for x in self.succ[n][n]:
1406
loops.append((n,n,x))
1407
else:
1408
loops.append((n,n,self.succ[n][n]))
1409
return loops
1410
1411
def number_of_selfloops(self):
1412
"""Return number of self-loops in graph."""
1413
return len(self.selfloop_edges())
1414
1415
def allow_selfloops(self):
1416
"""Henceforth allow addition of self-loops
1417
(edges from a node to itself).
1418
1419
This doesn't change the graph structure, only what you can do to it.
1420
"""
1421
self.selfloops=True
1422
1423
def remove_all_selfloops(self):
1424
"""Remove self-loops from the graph (edges from a node to itself)."""
1425
for n in self.succ:
1426
if self.succ[n].has_key(n):
1427
del self.succ[n][n]
1428
del self.pred[n][n]
1429
1430
def ban_selfloops(self):
1431
"""Remove self-loops from the graph and henceforth do not allow
1432
their creation.
1433
"""
1434
self.remove_all_selfloops()
1435
self.selfloops=False
1436
1437
1438
def allow_multiedges(self):
1439
"""Henceforth allow addition of multiedges (more than one
1440
edge between two nodes).
1441
1442
Warning: This causes all edge data to be converted to lists.
1443
"""
1444
if self.multiedges: return # already multiedges
1445
self.multiedges=True
1446
for v in self.succ:
1447
for (u,edgedata) in self.succ[v].iteritems():
1448
self.succ[v][u]=[edgedata]
1449
self.pred[u][v]=[edgedata]
1450
1451
def remove_all_multiedges(self):
1452
# FIXME, write tests
1453
"""Remove multiedges retaining the data from the first edge"""
1454
if not self.multiedges: # nothing to do
1455
return
1456
for v in self.succ:
1457
for (u,edgedata) in self.succ[v].iteritems():
1458
if len(edgedata)>1:
1459
self.succ[v][u]=[edgedata[0]]
1460
self.pred[u][v]=[edgedata[0]]
1461
1462
def ban_multiedges(self):
1463
"""Remove multiedges retaining the data from the first edge.
1464
Henceforth do not allow multiedges.
1465
"""
1466
if not self.multiedges: # nothing to do
1467
return
1468
self.multiedges=False
1469
for v in self.succ:
1470
for (u,edgedata) in self.succ[v].iteritems():
1471
self.succ[v][u]=edgedata[0]
1472
self.pred[u][v]=edgedata[0]
1473
1474
def subgraph(self, nbunch, inplace=False, create_using=None):
1475
"""Return the subgraph induced on nodes in nbunch.
1476
1477
nbunch: can be a singleton node, a string (which is treated
1478
as a singleton node), or any iterable container of
1479
of nodes. (It can be an iterable or an iterator, e.g. a list,
1480
set, graph, file, numeric array, etc.)
1481
1482
Setting inplace=True will return induced subgraph in original
1483
graph by deleting nodes not in nbunch. It overrides any setting
1484
of create_using.
1485
1486
WARNING: specifying inplace=True makes it easy to destroy the graph.
1487
1488
Unless otherwise specified, return a new graph of the same
1489
type as self. Use (optional) create_using=R to return the
1490
resulting subgraph in R. R can be an existing graph-like
1491
object (to be emptied) or R can be a call to a graph object,
1492
e.g. create_using=DiGraph(). See documentation for
1493
empty_graph()
1494
1495
Note: use subgraph(G) rather than G.subgraph() to access the more
1496
general subgraph() function from the operators module.
1497
1498
"""
1499
bunch=self.prepare_nbunch(nbunch)
1500
1501
# WARNING: setting inplace=True destroys the graph.
1502
if inplace: # demolish all nodes (and attached edges) not in nbunch
1503
# override any setting of create_using
1504
bunch=dict.fromkeys(bunch) # make a dict
1505
self.delete_nodes_from([n for n in self if n not in bunch])
1506
self.name="Subgraph of (%s)"%(self.name)
1507
return self
1508
1509
# create new graph
1510
if create_using is None:
1511
# return a Graph object of the same type as current graph
1512
# subgraph inherits multiedges and selfloops settings
1513
H=self.__class__(multiedges=self.multiedges,
1514
selfloops=self.selfloops)
1515
else:
1516
# Recreate subgraph with create_using.
1517
# Currently create_using must be an XGraph type object
1518
# or a multi-edge list will be copied as a single edge
1519
H=create_using
1520
H.clear()
1521
H.name="Subgraph of (%s)"%(self.name)
1522
H.add_nodes_from(bunch)
1523
1524
# add edges
1525
H_succ=H.succ # store in local variables
1526
H_pred=H.pred
1527
self_succ=self.succ
1528
self_pred=self.pred
1529
if self.multiedges:
1530
for n in H: # create dicts with copies of edge data list from self
1531
H_succ[n]=dict([(u,d[:]) for u,d in self_succ[n].iteritems() if u in H_succ])
1532
H_pred[n]=dict([(u,d[:]) for u,d in self_pred[n].iteritems() if u in H_pred])
1533
else: # no multiedges
1534
for n in H: # create dicts with edge data from self
1535
H_succ[n]=dict([(u,d) for u,d in self_succ[n].iteritems() if u in H_succ])
1536
H_pred[n]=dict([(u,d) for u,d in self_pred[n].iteritems() if u in H_pred])
1537
return H
1538
1539
def copy(self):
1540
"""Return a (shallow) copy of the digraph.
1541
1542
Return a new XDiGraph with same name and same attributes for
1543
selfloop and multiededges. Each node and each edge in original
1544
graph are added to the copy.
1545
1546
"""
1547
H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops)
1548
H.name=self.name
1549
H.dna=self.dna.copy()
1550
for n in self:
1551
H.add_node(n)
1552
for e in self.edges_iter():
1553
H.add_edge(e)
1554
return H
1555
1556
def to_undirected(self):
1557
"""Return the underlying graph of G.
1558
1559
The underlying graph is its undirected representation: each directed
1560
edge is replaced with an undirected edge.
1561
1562
If multiedges=True, then an XDiGraph with only two directed
1563
edges (1,2,"red") and (2,1,"blue") will be converted into an
1564
XGraph with two undirected edges (1,2,"red") and (1,2,"blue").
1565
Two directed edges (1,2,"red") and (2,1,"red") will result in
1566
in two undirected edges (1,2,"red") and (1,2,"red").
1567
1568
If multiedges=False, then two directed edges (1,2,"red") and
1569
(2,1,"blue") can only result in one undirected edge, and there
1570
is no guarantee which one it is.
1571
1572
"""
1573
H=XGraph(multiedges=self.multiedges,selfloops=self.selfloops)
1574
H.name=self.name
1575
H.dna=self.dna.copy()
1576
for n in self:
1577
H.add_node(n) # copy nodes
1578
for e in self.edges_iter():
1579
H.add_edge(e) # convert each edge
1580
return H
1581
1582
1583
def _test_suite():
1584
import doctest
1585
suite = doctest.DocFileSuite(
1586
'tests/xbase_Graph.txt',
1587
'tests/xbase_PseudoGraph.txt',
1588
'tests/xbase_DiGraph.txt',
1589
package='networkx')
1590
return suite
1591
1592
1593
if __name__ == "__main__":
1594
import os
1595
import sys
1596
import unittest
1597
if sys.version_info[:2] < (2, 4):
1598
print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
1599
sys.exit(-1)
1600
# directory of networkx package (relative to this)
1601
nxbase=sys.path[0]+os.sep+os.pardir
1602
sys.path.insert(0,nxbase) # prepend to search path
1603
unittest.TextTestRunner().run(_test_suite())
1604
Loggerhead is a web-based interface for Breezy
Version: 2.0.1