ioftools / networkxMiCe / networkxmaster / networkx / classes / multigraph.py @ 5cef0f13
History  View  Annotate  Download (39.7 KB)
1 
# Copyright (C) 20042019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
#

8 
# Authors: Aric Hagberg <hagberg@lanl.gov>

9 
# Dan Schult <dschult@colgate.edu>

10 
# Pieter Swart <swart@lanl.gov>

11 
"""Base class for MultiGraph."""

12 
from copy import deepcopy 
13  
14 
import networkx as nx 
15 
from networkx.classes.graph import Graph 
16 
from networkx.classes.coreviews import MultiAdjacencyView 
17 
from networkx.classes.reportviews import MultiEdgeView, MultiDegreeView 
18 
from networkx import NetworkXError 
19 
from networkx.utils import iterable 
20  
21  
22 
class MultiGraph(Graph): 
23 
"""

24 
An undirected graph class that can store multiedges.

25 

26 
Multiedges are multiple edges between two nodes. Each edge

27 
can hold optional data or attributes.

28 

29 
A MultiGraph holds undirected edges. Self loops are allowed.

30 

31 
Nodes can be arbitrary (hashable) Python objects with optional

32 
key/value attributes. By convention `None` is not used as a node.

33 

34 
Edges are represented as links between nodes with optional

35 
key/value attributes.

36 

37 
Parameters

38 


39 
incoming_graph_data : input graph (optional, default: None)

40 
Data to initialize graph. If None (default) an empty

41 
graph is created. The data can be any format that is supported

42 
by the to_networkx_graph() function, currently including edge list,

43 
dict of dicts, dict of lists, NetworkX graph, NumPy matrix

44 
or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.

45 

46 
attr : keyword arguments, optional (default= no attributes)

47 
Attributes to add to graph as key=value pairs.

48 

49 
See Also

50 


51 
Graph

52 
DiGraph

53 
MultiDiGraph

54 
OrderedMultiGraph

55 

56 
Examples

57 


58 
Create an empty graph structure (a "null graph") with no nodes and

59 
no edges.

60 

61 
>>> G = nx.MultiGraph()

62 

63 
G can be grown in several ways.

64 

65 
**Nodes:**

66 

67 
Add one node at a time:

68 

69 
>>> G.add_node(1)

70 

71 
Add the nodes from any container (a list, dict, set or

72 
even the lines from a file or the nodes from another graph).

73 

74 
>>> G.add_nodes_from([2, 3])

75 
>>> G.add_nodes_from(range(100, 110))

76 
>>> H = nx.path_graph(10)

77 
>>> G.add_nodes_from(H)

78 

79 
In addition to strings and integers any hashable Python object

80 
(except None) can represent a node, e.g. a customized node object,

81 
or even another Graph.

82 

83 
>>> G.add_node(H)

84 

85 
**Edges:**

86 

87 
G can also be grown by adding edges.

88 

89 
Add one edge,

90 

91 
>>> key = G.add_edge(1, 2)

92 

93 
a list of edges,

94 

95 
>>> keys = G.add_edges_from([(1, 2), (1, 3)])

96 

97 
or a collection of edges,

98 

99 
>>> keys = G.add_edges_from(H.edges)

100 

101 
If some edges connect nodes not yet in the graph, the nodes

102 
are added automatically. If an edge already exists, an additional

103 
edge is created and stored using a key to identify the edge.

104 
By default the key is the lowest unused integer.

105 

106 
>>> keys = G.add_edges_from([(4,5,{'route':28}), (4,5,{'route':37})])

107 
>>> G[4]

108 
AdjacencyView({3: {0: {}}, 5: {0: {}, 1: {'route': 28}, 2: {'route': 37}}})

109 

110 
**Attributes:**

111 

112 
Each graph, node, and edge can hold key/value attribute pairs

113 
in an associated attribute dictionary (the keys must be hashable).

114 
By default these are empty, but can be added or changed using

115 
add_edge, add_node or direct manipulation of the attribute

116 
dictionaries named graph, node and edge respectively.

117 

118 
>>> G = nx.MultiGraph(day="Friday")

119 
>>> G.graph

120 
{'day': 'Friday'}

121 

122 
Add node attributes using add_node(), add_nodes_from() or G.nodes

123 

124 
>>> G.add_node(1, time='5pm')

125 
>>> G.add_nodes_from([3], time='2pm')

126 
>>> G.nodes[1]

127 
{'time': '5pm'}

128 
>>> G.nodes[1]['room'] = 714

129 
>>> del G.nodes[1]['room'] # remove attribute

130 
>>> list(G.nodes(data=True))

131 
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

132 

133 
Add edge attributes using add_edge(), add_edges_from(), subscript

134 
notation, or G.edges.

135 

136 
>>> key = G.add_edge(1, 2, weight=4.7 )

137 
>>> keys = G.add_edges_from([(3, 4), (4, 5)], color='red')

138 
>>> keys = G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])

139 
>>> G[1][2][0]['weight'] = 4.7

140 
>>> G.edges[1, 2, 0]['weight'] = 4

141 

142 
Warning: we protect the graph data structure by making `G.edges[1, 2]` a

143 
readonly dictlike structure. However, you can assign to attributes

144 
in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change

145 
data attributes: `G.edges[1, 2]['weight'] = 4`

146 
(For multigraphs: `MG.edges[u, v, key][name] = value`).

147 

148 
**Shortcuts:**

149 

150 
Many common graph features allow python syntax to speed reporting.

151 

152 
>>> 1 in G # check if node in graph

153 
True

154 
>>> [n for n in G if n<3] # iterate through nodes

155 
[1, 2]

156 
>>> len(G) # number of nodes in graph

157 
5

158 
>>> G[1] # adjacency dictlike view keyed by neighbor to edge attributes

159 
AdjacencyView({2: {0: {'weight': 4}, 1: {'color': 'blue'}}})

160 

161 
Often the best way to traverse all edges of a graph is via the neighbors.

162 
The neighbors are reported as an adjacencydict `G.adj` or `G.adjacency()`.

163 

164 
>>> for n, nbrsdict in G.adjacency():

165 
... for nbr, keydict in nbrsdict.items():

166 
... for key, eattr in keydict.items():

167 
... if 'weight' in eattr:

168 
... # Do something useful with the edges

169 
... pass

170 

171 
But the edges() method is often more convenient:

172 

173 
>>> for u, v, keys, weight in G.edges(data='weight', keys=True):

174 
... if weight is not None:

175 
... # Do something useful with the edges

176 
... pass

177 

178 
**Reporting:**

179 

180 
Simple graph information is obtained using methods and objectattributes.

181 
Reporting usually provides views instead of containers to reduce memory

182 
usage. The views update as the graph is updated similarly to dictviews.

183 
The objects `nodes, `edges` and `adj` provide access to data attributes

184 
via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration

185 
(e.g. `nodes.items()`, `nodes.data('color')`,

186 
`nodes.data('color', default='blue')` and similarly for `edges`)

187 
Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.

188 

189 
For details on these and other miscellaneous methods, see below.

190 

191 
**Subclasses (Advanced):**

192 

193 
The MultiGraph class uses a dictofdictofdictofdict data structure.

194 
The outer dict (node_dict) holds adjacency information keyed by node.

195 
The next dict (adjlist_dict) represents the adjacency information and holds

196 
edge_key dicts keyed by neighbor. The edge_key dict holds each edge_attr

197 
dict keyed by edge key. The inner dict (edge_attr_dict) represents

198 
the edge data and holds edge attribute values keyed by attribute names.

199 

200 
Each of these four dicts in the dictofdictofdictofdict

201 
structure can be replaced by a user defined dictlike object.

202 
In general, the dictlike features should be maintained but

203 
extra features can be added. To replace one of the dicts create

204 
a new graph class by changing the class(!) variable holding the

205 
factory for that dictlike structure. The variable names are

206 
node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,

207 
adjlist_outer_dict_factory, edge_key_dict_factory, edge_attr_dict_factory

208 
and graph_attr_dict_factory.

209 

210 
node_dict_factory : function, (default: dict)

211 
Factory function to be used to create the dict containing node

212 
attributes, keyed by node id.

213 
It should require no arguments and return a dictlike object

214 

215 
node_attr_dict_factory: function, (default: dict)

216 
Factory function to be used to create the node attribute

217 
dict which holds attribute values keyed by attribute name.

218 
It should require no arguments and return a dictlike object

219 

220 
adjlist_outer_dict_factory : function, (default: dict)

221 
Factory function to be used to create the outermost dict

222 
in the data structure that holds adjacency info keyed by node.

223 
It should require no arguments and return a dictlike object.

224 

225 
adjlist_inner_dict_factory : function, (default: dict)

226 
Factory function to be used to create the adjacency list

227 
dict which holds multiedge key dicts keyed by neighbor.

228 
It should require no arguments and return a dictlike object.

229 

230 
edge_key_dict_factory : function, (default: dict)

231 
Factory function to be used to create the edge key dict

232 
which holds edge data keyed by edge key.

233 
It should require no arguments and return a dictlike object.

234 

235 
edge_attr_dict_factory : function, (default: dict)

236 
Factory function to be used to create the edge attribute

237 
dict which holds attribute values keyed by attribute name.

238 
It should require no arguments and return a dictlike object.

239 

240 
graph_attr_dict_factory : function, (default: dict)

241 
Factory function to be used to create the graph attribute

242 
dict which holds attribute values keyed by attribute name.

243 
It should require no arguments and return a dictlike object.

244 

245 
Typically, if your extension doesn't impact the data structure all

246 
methods will inherited without issue except: `to_directed/to_undirected`.

247 
By default these methods create a DiGraph/Graph class and you probably

248 
want them to create your extension of a DiGraph/Graph. To facilitate

249 
this we define two class variables that you can set in your subclass.

250 

251 
to_directed_class : callable, (default: DiGraph or MultiDiGraph)

252 
Class to create a new graph structure in the `to_directed` method.

253 
If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.

254 

255 
to_undirected_class : callable, (default: Graph or MultiGraph)

256 
Class to create a new graph structure in the `to_undirected` method.

257 
If `None`, a NetworkX class (Graph or MultiGraph) is used.

258 

259 
Examples

260 


261 

262 
Please see :mod:`~networkx.classes.ordered` for examples of

263 
creating graph subclasses by overwriting the base class `dict` with

264 
a dictionarylike object.

265 
"""

266 
# node_dict_factory = dict # already assigned in Graph

267 
# adjlist_outer_dict_factory = dict

268 
# adjlist_inner_dict_factory = dict

269 
edge_key_dict_factory = dict

270 
# edge_attr_dict_factory = dict

271  
272 
def to_directed_class(self): 
273 
"""Returns the class to use for empty directed copies.

274 

275 
If you subclass the base classes, use this to designate

276 
what directed class to use for `to_directed()` copies.

277 
"""

278 
return nx.MultiDiGraph

279  
280 
def to_undirected_class(self): 
281 
"""Returns the class to use for empty undirected copies.

282 

283 
If you subclass the base classes, use this to designate

284 
what directed class to use for `to_directed()` copies.

285 
"""

286 
return MultiGraph

287  
288 
def __init__(self, incoming_graph_data=None, **attr): 
289 
"""Initialize a graph with edges, name, or graph attributes.

290 

291 
Parameters

292 


293 
incoming_graph_data : input graph

294 
Data to initialize graph. If incoming_graph_data=None (default)

295 
an empty graph is created. The data can be an edge list, or any

296 
NetworkX graph object. If the corresponding optional Python

297 
packages are installed the data can also be a NumPy matrix

298 
or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.

299 

300 
attr : keyword arguments, optional (default= no attributes)

301 
Attributes to add to graph as key=value pairs.

302 

303 
See Also

304 


305 
convert

306 

307 
Examples

308 


309 
>>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc

310 
>>> G = nx.Graph(name='my graph')

311 
>>> e = [(1, 2), (2, 3), (3, 4)] # list of edges

312 
>>> G = nx.Graph(e)

313 

314 
Arbitrary graph attribute pairs (key=value) may be assigned

315 

316 
>>> G = nx.Graph(e, day="Friday")

317 
>>> G.graph

318 
{'day': 'Friday'}

319 

320 
"""

321 
self.edge_key_dict_factory = self.edge_key_dict_factory 
322 
Graph.__init__(self, incoming_graph_data, **attr)

323  
324 
@property

325 
def adj(self): 
326 
"""Graph adjacency object holding the neighbors of each node.

327 

328 
This object is a readonly dictlike structure with node keys

329 
and neighbordict values. The neighbordict is keyed by neighbor

330 
to the edgekeydatadict. So `G.adj[3][2][0]['color'] = 'blue'` sets

331 
the color of the edge `(3, 2, 0)` to `"blue"`.

332 

333 
Iterating over G.adj behaves like a dict. Useful idioms include

334 
`for nbr, nbrdict in G.adj[n].items():`.

335 

336 
The neighbor information is also provided by subscripting the graph.

337 
So `for nbr, foovalue in G[node].data('foo', default=1):` works.

338 

339 
For directed graphs, `G.adj` holds outgoing (successor) info.

340 
"""

341 
return MultiAdjacencyView(self._adj) 
342  
343 
def new_edge_key(self, u, v): 
344 
"""Returns an unused key for edges between nodes `u` and `v`.

345 

346 
The nodes `u` and `v` do not need to be already in the graph.

347 

348 
Notes

349 


350 
In the standard MultiGraph class the new key is the number of existing

351 
edges between `u` and `v` (increased if necessary to ensure unused).

352 
The first edge will have key 0, then 1, etc. If an edge is removed

353 
further new_edge_keys may not be in this order.

354 

355 
Parameters

356 


357 
u, v : nodes

358 

359 
Returns

360 


361 
key : int

362 
"""

363 
try:

364 
keydict = self._adj[u][v]

365 
except KeyError: 
366 
return 0 
367 
key = len(keydict)

368 
while key in keydict: 
369 
key += 1

370 
return key

371  
372 
def add_edge(self, u_for_edge, v_for_edge, key=None, **attr): 
373 
"""Add an edge between u and v.

374 

375 
The nodes u and v will be automatically added if they are

376 
not already in the graph.

377 

378 
Edge attributes can be specified with keywords or by directly

379 
accessing the edge's attribute dictionary. See examples below.

380 

381 
Parameters

382 


383 
u_for_edge, v_for_edge : nodes

384 
Nodes can be, for example, strings or numbers.

385 
Nodes must be hashable (and not None) Python objects.

386 
key : hashable identifier, optional (default=lowest unused integer)

387 
Used to distinguish multiedges between a pair of nodes.

388 
attr : keyword arguments, optional

389 
Edge data (or labels or objects) can be assigned using

390 
keyword arguments.

391 

392 
Returns

393 


394 
The edge key assigned to the edge.

395 

396 
See Also

397 


398 
add_edges_from : add a collection of edges

399 

400 
Notes

401 


402 
To replace/update edge data, use the optional key argument

403 
to identify a unique edge. Otherwise a new edge will be created.

404 

405 
NetworkX algorithms designed for weighted graphs cannot use

406 
multigraphs directly because it is not clear how to handle

407 
multiedge weights. Convert to Graph using edge attribute

408 
'weight' to enable weighted graph algorithms.

409 

410 
Default keys are generated using the method `new_edge_key()`.

411 
This method can be overridden by subclassing the base class and

412 
providing a custom `new_edge_key()` method.

413 

414 
Examples

415 


416 
The following all add the edge e=(1, 2) to graph G:

417 

418 
>>> G = nx.MultiGraph()

419 
>>> e = (1, 2)

420 
>>> ekey = G.add_edge(1, 2) # explicit twonode form

421 
>>> G.add_edge(*e) # single edge as tuple of two nodes

422 
1

423 
>>> G.add_edges_from( [(1, 2)] ) # add edges from iterable container

424 
[2]

425 

426 
Associate data to edges using keywords:

427 

428 
>>> ekey = G.add_edge(1, 2, weight=3)

429 
>>> ekey = G.add_edge(1, 2, key=0, weight=4) # update data for key=0

430 
>>> ekey = G.add_edge(1, 3, weight=7, capacity=15, length=342.7)

431 

432 
For nonstring attribute keys, use subscript notation.

433 

434 
>>> ekey = G.add_edge(1, 2)

435 
>>> G[1][2][0].update({0: 5})

436 
>>> G.edges[1, 2, 0].update({0: 5})

437 
"""

438 
u, v = u_for_edge, v_for_edge 
439 
# add nodes

440 
if u not in self._adj: 
441 
self._adj[u] = self.adjlist_inner_dict_factory() 
442 
self._node[u] = self.node_attr_dict_factory() 
443 
if v not in self._adj: 
444 
self._adj[v] = self.adjlist_inner_dict_factory() 
445 
self._node[v] = self.node_attr_dict_factory() 
446 
if key is None: 
447 
key = self.new_edge_key(u, v)

448 
if v in self._adj[u]: 
449 
keydict = self._adj[u][v]

450 
datadict = keydict.get(key, self.edge_attr_dict_factory())

451 
datadict.update(attr) 
452 
keydict[key] = datadict 
453 
else:

454 
# selfloops work this way without special treatment

455 
datadict = self.edge_attr_dict_factory()

456 
datadict.update(attr) 
457 
keydict = self.edge_key_dict_factory()

458 
keydict[key] = datadict 
459 
self._adj[u][v] = keydict

460 
self._adj[v][u] = keydict

461 
return key

462  
463 
def add_edges_from(self, ebunch_to_add, **attr): 
464 
"""Add all the edges in ebunch_to_add.

465 

466 
Parameters

467 


468 
ebunch_to_add : container of edges

469 
Each edge given in the container will be added to the

470 
graph. The edges can be:

471 

472 
 2tuples (u, v) or

473 
 3tuples (u, v, d) for an edge data dict d, or

474 
 3tuples (u, v, k) for not iterable key k, or

475 
 4tuples (u, v, k, d) for an edge with data and key k

476 

477 
attr : keyword arguments, optional

478 
Edge data (or labels or objects) can be assigned using

479 
keyword arguments.

480 

481 
Returns

482 


483 
A list of edge keys assigned to the edges in `ebunch`.

484 

485 
See Also

486 


487 
add_edge : add a single edge

488 
add_weighted_edges_from : convenient way to add weighted edges

489 

490 
Notes

491 


492 
Adding the same edge twice has no effect but any edge data

493 
will be updated when each duplicate edge is added.

494 

495 
Edge attributes specified in an ebunch take precedence over

496 
attributes specified via keyword arguments.

497 

498 
Default keys are generated using the method ``new_edge_key()``.

499 
This method can be overridden by subclassing the base class and

500 
providing a custom ``new_edge_key()`` method.

501 

502 
Examples

503 


504 
>>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc

505 
>>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples

506 
>>> e = zip(range(0, 3), range(1, 4))

507 
>>> G.add_edges_from(e) # Add the path graph 0123

508 

509 
Associate data to edges

510 

511 
>>> G.add_edges_from([(1, 2), (2, 3)], weight=3)

512 
>>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898')

513 
"""

514 
keylist = [] 
515 
for e in ebunch_to_add: 
516 
ne = len(e)

517 
if ne == 4: 
518 
u, v, key, dd = e 
519 
elif ne == 3: 
520 
u, v, dd = e 
521 
key = None

522 
elif ne == 2: 
523 
u, v = e 
524 
dd = {} 
525 
key = None

526 
else:

527 
msg = "Edge tuple {} must be a 2tuple, 3tuple or 4tuple."

528 
raise NetworkXError(msg.format(e))

529 
ddd = {} 
530 
ddd.update(attr) 
531 
try:

532 
ddd.update(dd) 
533 
except:

534 
if ne != 3: 
535 
raise

536 
key = dd 
537 
key = self.add_edge(u, v, key)

538 
self[u][v][key].update(ddd)

539 
keylist.append(key) 
540 
return keylist

541  
542 
def remove_edge(self, u, v, key=None): 
543 
"""Remove an edge between u and v.

544 

545 
Parameters

546 


547 
u, v : nodes

548 
Remove an edge between nodes u and v.

549 
key : hashable identifier, optional (default=None)

550 
Used to distinguish multiple edges between a pair of nodes.

551 
If None remove a single (arbitrary) edge between u and v.

552 

553 
Raises

554 


555 
NetworkXError

556 
If there is not an edge between u and v, or

557 
if there is no edge with the specified key.

558 

559 
See Also

560 


561 
remove_edges_from : remove a collection of edges

562 

563 
Examples

564 


565 
>>> G = nx.MultiGraph()

566 
>>> nx.add_path(G, [0, 1, 2, 3])

567 
>>> G.remove_edge(0, 1)

568 
>>> e = (1, 2)

569 
>>> G.remove_edge(*e) # unpacks e from an edge tuple

570 

571 
For multiple edges

572 

573 
>>> G = nx.MultiGraph() # or MultiDiGraph, etc

574 
>>> G.add_edges_from([(1, 2), (1, 2), (1, 2)]) # key_list returned

575 
[0, 1, 2]

576 
>>> G.remove_edge(1, 2) # remove a single (arbitrary) edge

577 

578 
For edges with keys

579 

580 
>>> G = nx.MultiGraph() # or MultiDiGraph, etc

581 
>>> G.add_edge(1, 2, key='first')

582 
'first'

583 
>>> G.add_edge(1, 2, key='second')

584 
'second'

585 
>>> G.remove_edge(1, 2, key='second')

586 

587 
"""

588 
try:

589 
d = self._adj[u][v]

590 
except KeyError: 
591 
raise NetworkXError(

592 
"The edge %s%s is not in the graph." % (u, v))

593 
# remove the edge with specified data

594 
if key is None: 
595 
d.popitem() 
596 
else:

597 
try:

598 
del d[key]

599 
except KeyError: 
600 
msg = "The edge %s%s with key %s is not in the graph."

601 
raise NetworkXError(msg % (u, v, key))

602 
if len(d) == 0: 
603 
# remove the key entries if last edge

604 
del self._adj[u][v] 
605 
if u != v: # check for selfloop 
606 
del self._adj[v][u] 
607  
608 
def remove_edges_from(self, ebunch): 
609 
"""Remove all edges specified in ebunch.

610 

611 
Parameters

612 


613 
ebunch: list or container of edge tuples

614 
Each edge given in the list or container will be removed

615 
from the graph. The edges can be:

616 

617 
 2tuples (u, v) All edges between u and v are removed.

618 
 3tuples (u, v, key) The edge identified by key is removed.

619 
 4tuples (u, v, key, data) where data is ignored.

620 

621 
See Also

622 


623 
remove_edge : remove a single edge

624 

625 
Notes

626 


627 
Will fail silently if an edge in ebunch is not in the graph.

628 

629 
Examples

630 


631 
>>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc

632 
>>> ebunch=[(1, 2), (2, 3)]

633 
>>> G.remove_edges_from(ebunch)

634 

635 
Removing multiple copies of edges

636 

637 
>>> G = nx.MultiGraph()

638 
>>> keys = G.add_edges_from([(1, 2), (1, 2), (1, 2)])

639 
>>> G.remove_edges_from([(1, 2), (1, 2)])

640 
>>> list(G.edges())

641 
[(1, 2)]

642 
>>> G.remove_edges_from([(1, 2), (1, 2)]) # silently ignore extra copy

643 
>>> list(G.edges) # now empty graph

644 
[]

645 
"""

646 
for e in ebunch: 
647 
try:

648 
self.remove_edge(*e[:3]) 
649 
except NetworkXError:

650 
pass

651  
652 
def has_edge(self, u, v, key=None): 
653 
"""Returns True if the graph has an edge between nodes u and v.

654 

655 
This is the same as `v in G[u] or key in G[u][v]`

656 
without KeyError exceptions.

657 

658 
Parameters

659 


660 
u, v : nodes

661 
Nodes can be, for example, strings or numbers.

662 

663 
key : hashable identifier, optional (default=None)

664 
If specified return True only if the edge with

665 
key is found.

666 

667 
Returns

668 


669 
edge_ind : bool

670 
True if edge is in the graph, False otherwise.

671 

672 
Examples

673 


674 
Can be called either using two nodes u, v, an edge tuple (u, v),

675 
or an edge tuple (u, v, key).

676 

677 
>>> G = nx.MultiGraph() # or MultiDiGraph

678 
>>> nx.add_path(G, [0, 1, 2, 3])

679 
>>> G.has_edge(0, 1) # using two nodes

680 
True

681 
>>> e = (0, 1)

682 
>>> G.has_edge(*e) # e is a 2tuple (u, v)

683 
True

684 
>>> G.add_edge(0, 1, key='a')

685 
'a'

686 
>>> G.has_edge(0, 1, key='a') # specify key

687 
True

688 
>>> e=(0, 1, 'a')

689 
>>> G.has_edge(*e) # e is a 3tuple (u, v, 'a')

690 
True

691 

692 
The following syntax are equivalent:

693 

694 
>>> G.has_edge(0, 1)

695 
True

696 
>>> 1 in G[0] # though this gives :exc:`KeyError` if 0 not in G

697 
True

698 

699 
"""

700 
try:

701 
if key is None: 
702 
return v in self._adj[u] 
703 
else:

704 
return key in self._adj[u][v] 
705 
except KeyError: 
706 
return False 
707  
708 
@property

709 
def edges(self): 
710 
"""Returns an iterator over the edges.

711 

712 
edges(self, nbunch=None, data=False, keys=False, default=None)

713 

714 
The EdgeView provides setlike operations on the edgetuples

715 
as well as edge attribute lookup. When called, it also provides

716 
an EdgeDataView object which allows control of access to edge

717 
attributes (but does not provide setlike operations).

718 
Hence, `G.edges[u, v]['color']` provides the value of the color

719 
attribute for edge `(u, v)` while

720 
`for (u, v, c) in G.edges(data='color', default='red'):`

721 
iterates through all the edges yielding the color attribute.

722 

723 
Edges are returned as tuples with optional data and keys

724 
in the order (node, neighbor, key, data).

725 

726 
Parameters

727 


728 
nbunch : single node, container, or all nodes (default= all nodes)

729 
The view will only report edges incident to these nodes.

730 
data : string or bool, optional (default=False)

731 
The edge attribute returned in 3tuple (u, v, ddict[data]).

732 
If True, return edge attribute dict in 3tuple (u, v, ddict).

733 
If False, return 2tuple (u, v).

734 
keys : bool, optional (default=False)

735 
If True, return edge keys with each edge.

736 
default : value, optional (default=None)

737 
Value used for edges that don't have the requested attribute.

738 
Only relevant if data is not True or False.

739 

740 
Returns

741 


742 
edges : MultiEdgeView

743 
A view of edge attributes, usually it iterates over (u, v)

744 
(u, v, k) or (u, v, k, d) tuples of edges, but can also be

745 
used for attribute lookup as `edges[u, v, k]['foo']`.

746 

747 
Notes

748 


749 
Nodes in nbunch that are not in the graph will be (quietly) ignored.

750 
For directed graphs this returns the outedges.

751 

752 
Examples

753 


754 
>>> G = nx.MultiGraph() # or MultiDiGraph

755 
>>> nx.add_path(G, [0, 1, 2])

756 
>>> key = G.add_edge(2, 3, weight=5)

757 
>>> [e for e in G.edges()]

758 
[(0, 1), (1, 2), (2, 3)]

759 
>>> G.edges.data() # default data is {} (empty dict)

760 
MultiEdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])

761 
>>> G.edges.data('weight', default=1)

762 
MultiEdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])

763 
>>> G.edges(keys=True) # default keys are integers

764 
MultiEdgeView([(0, 1, 0), (1, 2, 0), (2, 3, 0)])

765 
>>> G.edges.data(keys=True)

766 
MultiEdgeDataView([(0, 1, 0, {}), (1, 2, 0, {}), (2, 3, 0, {'weight': 5})])

767 
>>> G.edges.data('weight', default=1, keys=True)

768 
MultiEdgeDataView([(0, 1, 0, 1), (1, 2, 0, 1), (2, 3, 0, 5)])

769 
>>> G.edges([0, 3])

770 
MultiEdgeDataView([(0, 1), (3, 2)])

771 
>>> G.edges(0)

772 
MultiEdgeDataView([(0, 1)])

773 
"""

774 
return MultiEdgeView(self) 
775  
776 
def get_edge_data(self, u, v, key=None, default=None): 
777 
"""Returns the attribute dictionary associated with edge (u, v).

778 

779 
This is identical to `G[u][v][key]` except the default is returned

780 
instead of an exception is the edge doesn't exist.

781 

782 
Parameters

783 


784 
u, v : nodes

785 

786 
default : any Python object (default=None)

787 
Value to return if the edge (u, v) is not found.

788 

789 
key : hashable identifier, optional (default=None)

790 
Return data only for the edge with specified key.

791 

792 
Returns

793 


794 
edge_dict : dictionary

795 
The edge attribute dictionary.

796 

797 
Examples

798 


799 
>>> G = nx.MultiGraph() # or MultiDiGraph

800 
>>> key = G.add_edge(0, 1, key='a', weight=7)

801 
>>> G[0][1]['a'] # key='a'

802 
{'weight': 7}

803 
>>> G.edges[0, 1, 'a'] # key='a'

804 
{'weight': 7}

805 

806 
Warning: we protect the graph data structure by making

807 
`G.edges` and `G[1][2]` readonly dictlike structures.

808 
However, you can assign values to attributes in e.g.

809 
`G.edges[1, 2, 'a']` or `G[1][2]['a']` using an additional

810 
bracket as shown next. You need to specify all edge info

811 
to assign to the edge data associated with an edge.

812 

813 
>>> G[0][1]['a']['weight'] = 10

814 
>>> G.edges[0, 1, 'a']['weight'] = 10

815 
>>> G[0][1]['a']['weight']

816 
10

817 
>>> G.edges[1, 0, 'a']['weight']

818 
10

819 

820 
>>> G = nx.MultiGraph() # or MultiDiGraph

821 
>>> nx.add_path(G, [0, 1, 2, 3])

822 
>>> G.get_edge_data(0, 1)

823 
{0: {}}

824 
>>> e = (0, 1)

825 
>>> G.get_edge_data(*e) # tuple form

826 
{0: {}}

827 
>>> G.get_edge_data('a', 'b', default=0) # edge not in graph, return 0

828 
0

829 
"""

830 
try:

831 
if key is None: 
832 
return self._adj[u][v] 
833 
else:

834 
return self._adj[u][v][key] 
835 
except KeyError: 
836 
return default

837  
838 
@property

839 
def degree(self): 
840 
"""A DegreeView for the Graph as G.degree or G.degree().

841 

842 
The node degree is the number of edges adjacent to the node.

843 
The weighted node degree is the sum of the edge weights for

844 
edges incident to that node.

845 

846 
This object provides an iterator for (node, degree) as well as

847 
lookup for the degree for a single node.

848 

849 
Parameters

850 


851 
nbunch : single node, container, or all nodes (default= all nodes)

852 
The view will only report edges incident to these nodes.

853 

854 
weight : string or None, optional (default=None)

855 
The name of an edge attribute that holds the numerical value used

856 
as a weight. If None, then each edge has weight 1.

857 
The degree is the sum of the edge weights adjacent to the node.

858 

859 
Returns

860 


861 
If a single node is requested

862 
deg : int

863 
Degree of the node, if a single node is passed as argument.

864 

865 
OR if multiple nodes are requested

866 
nd_iter : iterator

867 
The iterator returns twotuples of (node, degree).

868 

869 
Examples

870 


871 
>>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc

872 
>>> nx.add_path(G, [0, 1, 2, 3])

873 
>>> G.degree(0) # node 0 with degree 1

874 
1

875 
>>> list(G.degree([0, 1]))

876 
[(0, 1), (1, 2)]

877 

878 
"""

879 
return MultiDegreeView(self) 
880  
881 
def is_multigraph(self): 
882 
"""Returns True if graph is a multigraph, False otherwise."""

883 
return True 
884  
885 
def is_directed(self): 
886 
"""Returns True if graph is directed, False otherwise."""

887 
return False 
888  
889 
def copy(self, as_view=False): 
890 
"""Returns a copy of the graph.

891 

892 
The copy method by default returns an independent shallow copy

893 
of the graph and attributes. That is, if an attribute is a

894 
container, that container is shared by the original an the copy.

895 
Use Python's `copy.deepcopy` for new containers.

896 

897 
If `as_view` is True then a view is returned instead of a copy.

898 

899 
Notes

900 


901 
All copies reproduce the graph structure, but data attributes

902 
may be handled in different ways. There are four types of copies

903 
of a graph that people might want.

904 

905 
Deepcopy  A "deepcopy" copies the graph structure as well as

906 
all data attributes and any objects they might contain.

907 
The entire graph object is new so that changes in the copy

908 
do not affect the original object. (see Python's copy.deepcopy)

909 

910 
Data Reference (Shallow)  For a shallow copy the graph structure

911 
is copied but the edge, node and graph attribute dicts are

912 
references to those in the original graph. This saves

913 
time and memory but could cause confusion if you change an attribute

914 
in one graph and it changes the attribute in the other.

915 
NetworkX does not provide this level of shallow copy.

916 

917 
Independent Shallow  This copy creates new independent attribute

918 
dicts and then does a shallow copy of the attributes. That is, any

919 
attributes that are containers are shared between the new graph

920 
and the original. This is exactly what `dict.copy()` provides.

921 
You can obtain this style copy using:

922 

923 
>>> G = nx.path_graph(5)

924 
>>> H = G.copy()

925 
>>> H = G.copy(as_view=False)

926 
>>> H = nx.Graph(G)

927 
>>> H = G.__class__(G)

928 

929 
Fresh Data  For fresh data, the graph structure is copied while

930 
new empty data attribute dicts are created. The resulting graph

931 
is independent of the original and it has no edge, node or graph

932 
attributes. Fresh copies are not enabled. Instead use:

933 

934 
>>> H = G.__class__()

935 
>>> H.add_nodes_from(G)

936 
>>> H.add_edges_from(G.edges)

937 

938 
View  Inspired by dictviews, graphviews act like readonly

939 
versions of the original graph, providing a copy of the original

940 
structure without requiring any memory for copying the information.

941 

942 
See the Python copy module for more information on shallow

943 
and deep copies, https://docs.python.org/2/library/copy.html.

944 

945 
Parameters

946 


947 
as_view : bool, optional (default=False)

948 
If True, the returned graphview provides a readonly view

949 
of the original graph without actually copying any data.

950 

951 
Returns

952 


953 
G : Graph

954 
A copy of the graph.

955 

956 
See Also

957 


958 
to_directed: return a directed copy of the graph.

959 

960 
Examples

961 


962 
>>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc

963 
>>> H = G.copy()

964 

965 
"""

966 
if as_view is True: 
967 
return nx.graphviews.generic_graph_view(self) 
968 
G = self.__class__()

969 
G.graph.update(self.graph)

970 
G.add_nodes_from((n, d.copy()) for n, d in self._node.items()) 
971 
G.add_edges_from((u, v, key, datadict.copy()) 
972 
for u, nbrs in self._adj.items() 
973 
for v, keydict in nbrs.items() 
974 
for key, datadict in keydict.items()) 
975 
return G

976  
977 
def to_directed(self, as_view=False): 
978 
"""Returns a directed representation of the graph.

979 

980 
Returns

981 


982 
G : MultiDiGraph

983 
A directed graph with the same name, same nodes, and with

984 
each edge (u, v, data) replaced by two directed edges

985 
(u, v, data) and (v, u, data).

986 

987 
Notes

988 


989 
This returns a "deepcopy" of the edge, node, and

990 
graph attributes which attempts to completely copy

991 
all of the data and references.

992 

993 
This is in contrast to the similar D=DiGraph(G) which returns a

994 
shallow copy of the data.

995 

996 
See the Python copy module for more information on shallow

997 
and deep copies, https://docs.python.org/2/library/copy.html.

998 

999 
Warning: If you have subclassed MultiGraph to use dictlike objects

1000 
in the data structure, those changes do not transfer to the

1001 
MultiDiGraph created by this method.

1002 

1003 
Examples

1004 


1005 
>>> G = nx.Graph() # or MultiGraph, etc

1006 
>>> G.add_edge(0, 1)

1007 
>>> H = G.to_directed()

1008 
>>> list(H.edges)

1009 
[(0, 1), (1, 0)]

1010 

1011 
If already directed, return a (deep) copy

1012 

1013 
>>> G = nx.DiGraph() # or MultiDiGraph, etc

1014 
>>> G.add_edge(0, 1)

1015 
>>> H = G.to_directed()

1016 
>>> list(H.edges)

1017 
[(0, 1)]

1018 
"""

1019 
graph_class = self.to_directed_class()

1020 
if as_view is True: 
1021 
return nx.graphviews.generic_graph_view(self, graph_class) 
1022 
# deepcopy when not a view

1023 
G = graph_class() 
1024 
G.graph.update(deepcopy(self.graph))

1025 
G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) 
1026 
G.add_edges_from((u, v, key, deepcopy(datadict)) 
1027 
for u, nbrs in self.adj.items() 
1028 
for v, keydict in nbrs.items() 
1029 
for key, datadict in keydict.items()) 
1030 
return G

1031  
1032 
def to_undirected(self, as_view=False): 
1033 
"""Returns an undirected copy of the graph.

1034 

1035 
Returns

1036 


1037 
G : Graph/MultiGraph

1038 
A deepcopy of the graph.

1039 

1040 
See Also

1041 


1042 
copy, add_edge, add_edges_from

1043 

1044 
Notes

1045 


1046 
This returns a "deepcopy" of the edge, node, and

1047 
graph attributes which attempts to completely copy

1048 
all of the data and references.

1049 

1050 
This is in contrast to the similar `G = nx.MultiGraph(D)`

1051 
which returns a shallow copy of the data.

1052 

1053 
See the Python copy module for more information on shallow

1054 
and deep copies, https://docs.python.org/2/library/copy.html.

1055 

1056 
Warning: If you have subclassed MultiiGraph to use dictlike

1057 
objects in the data structure, those changes do not transfer

1058 
to the MultiGraph created by this method.

1059 

1060 
Examples

1061 


1062 
>>> G = nx.path_graph(2) # or MultiGraph, etc

1063 
>>> H = G.to_directed()

1064 
>>> list(H.edges)

1065 
[(0, 1), (1, 0)]

1066 
>>> G2 = H.to_undirected()

1067 
>>> list(G2.edges)

1068 
[(0, 1)]

1069 
"""

1070 
graph_class = self.to_undirected_class()

1071 
if as_view is True: 
1072 
return nx.graphviews.generic_graph_view(self, graph_class) 
1073 
# deepcopy when not a view

1074 
G = graph_class() 
1075 
G.graph.update(deepcopy(self.graph))

1076 
G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) 
1077 
G.add_edges_from((u, v, key, deepcopy(datadict)) 
1078 
for u, nbrs in self._adj.items() 
1079 
for v, keydict in nbrs.items() 
1080 
for key, datadict in keydict.items()) 
1081 
return G

1082  
1083 
def number_of_edges(self, u=None, v=None): 
1084 
"""Returns the number of edges between two nodes.

1085 

1086 
Parameters

1087 


1088 
u, v : nodes, optional (Gefault=all edges)

1089 
If u and v are specified, return the number of edges between

1090 
u and v. Otherwise return the total number of all edges.

1091 

1092 
Returns

1093 


1094 
nedges : int

1095 
The number of edges in the graph. If nodes `u` and `v` are

1096 
specified return the number of edges between those nodes. If

1097 
the graph is directed, this only returns the number of edges

1098 
from `u` to `v`.

1099 

1100 
See Also

1101 


1102 
size

1103 

1104 
Examples

1105 


1106 
For undirected multigraphs, this method counts the total number

1107 
of edges in the graph::

1108 

1109 
>>> G = nx.MultiGraph()

1110 
>>> G.add_edges_from([(0, 1), (0, 1), (1, 2)])

1111 
[0, 1, 0]

1112 
>>> G.number_of_edges()

1113 
3

1114 

1115 
If you specify two nodes, this counts the total number of edges

1116 
joining the two nodes::

1117 

1118 
>>> G.number_of_edges(0, 1)

1119 
2

1120 

1121 
For directed multigraphs, this method can count the total number

1122 
of directed edges from `u` to `v`::

1123 

1124 
>>> G = nx.MultiDiGraph()

1125 
>>> G.add_edges_from([(0, 1), (0, 1), (1, 0)])

1126 
[0, 1, 0]

1127 
>>> G.number_of_edges(0, 1)

1128 
2

1129 
>>> G.number_of_edges(1, 0)

1130 
1

1131 

1132 
"""

1133 
if u is None: 
1134 
return self.size() 
1135 
try:

1136 
edgedata = self._adj[u][v]

1137 
except KeyError: 
1138 
return 0 # no such edge 
1139 
return len(edgedata) 