Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/classes/multigraph.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
1 # Copyright (C) 2004-2019 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 read-only dict-like 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 dict-like 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 adjacency-dict `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 object-attributes.
181 Reporting usually provides views instead of containers to reduce memory
182 usage. The views update as the graph is updated similarly to dict-views.
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 dict-of-dict-of-dict-of-dict 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 dict-of-dict-of-dict-of-dict
201 structure can be replaced by a user defined dict-like object.
202 In general, the dict-like 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 dict-like 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 dict-like 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 dict-like object
219
220 adjlist_outer_dict_factory : function, (default: dict)
221 Factory function to be used to create the outer-most dict
222 in the data structure that holds adjacency info keyed by node.
223 It should require no arguments and return a dict-like 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 dict-like 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 dict-like 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 dict-like 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 dict-like 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 dictionary-like 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 read-only dict-like structure with node keys
329 and neighbor-dict values. The neighbor-dict is keyed by neighbor
330 to the edgekey-data-dict. 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 two-node 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 non-string 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 - 2-tuples (u, v) or
473 - 3-tuples (u, v, d) for an edge data dict d, or
474 - 3-tuples (u, v, k) for not iterable key k, or
475 - 4-tuples (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 0-1-2-3
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 2-tuple, 3-tuple or 4-tuple."
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 - 2-tuples (u, v) All edges between u and v are removed.
618 - 3-tuples (u, v, key) The edge identified by key is removed.
619 - 4-tuples (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 2-tuple (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 3-tuple (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 set-like operations on the edge-tuples
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 set-like 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 3-tuple (u, v, ddict[data]).
732 If True, return edge attribute dict in 3-tuple (u, v, ddict).
733 If False, return 2-tuple (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 out-edges.
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]` read-only dict-like 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 two-tuples 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 dict-views, graph-views act like read-only
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 graph-view provides a read-only 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 dict-like 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 dict-like
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)