Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / classes / multigraph.py @ 5cef0f13

History | View | Annotate | Download (39.7 KB)

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)