Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (65.3 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
# Author:  Aric Hagberg (hagberg@lanl.gov),
9
#          Pieter Swart (swart@lanl.gov),
10
#          Dan Schult(dschult@colgate.edu)
11
"""Base class for undirected graphs.
12

13
The Graph class allows any hashable object as a node
14
and can associate key/value attribute pairs with each undirected edge.
15

16
Self-loops are allowed but multiple edges are not (see MultiGraph).
17

18
For directed graphs see DiGraph and MultiDiGraph.
19
"""
20
from __future__ import division
21
import warnings
22
from copy import deepcopy
23
from collections.abc import Mapping
24

    
25
import networkx as nx
26
from networkx.classes.coreviews import AtlasView, AdjacencyView
27
from networkx.classes.reportviews import NodeView, EdgeView, DegreeView
28
from networkx.exception import NetworkXError
29
import networkx.convert as convert
30
from networkx.utils import pairwise
31

    
32

    
33
class Graph(object):
34
    """
35
    Base class for undirected graphs.
36

37
    A Graph stores nodes and edges with optional data, or attributes.
38

39
    Graphs hold undirected edges.  Self loops are allowed but multiple
40
    (parallel) edges are not.
41

42
    Nodes can be arbitrary (hashable) Python objects with optional
43
    key/value attributes. By convention `None` is not used as a node.
44

45
    Edges are represented as links between nodes with optional
46
    key/value attributes.
47

48
    Parameters
49
    ----------
50
    incoming_graph_data : input graph (optional, default: None)
51
        Data to initialize graph. If None (default) an empty
52
        graph is created.  The data can be any format that is supported
53
        by the to_networkx_graph() function, currently including edge list,
54
        dict of dicts, dict of lists, NetworkX graph, NumPy matrix
55
        or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
56

57
    attr : keyword arguments, optional (default= no attributes)
58
        Attributes to add to graph as key=value pairs.
59

60
    See Also
61
    --------
62
    DiGraph
63
    MultiGraph
64
    MultiDiGraph
65
    OrderedGraph
66

67
    Examples
68
    --------
69
    Create an empty graph structure (a "null graph") with no nodes and
70
    no edges.
71

72
    >>> G = nx.Graph()
73

74
    G can be grown in several ways.
75

76
    **Nodes:**
77

78
    Add one node at a time:
79

80
    >>> G.add_node(1)
81

82
    Add the nodes from any container (a list, dict, set or
83
    even the lines from a file or the nodes from another graph).
84

85
    >>> G.add_nodes_from([2, 3])
86
    >>> G.add_nodes_from(range(100, 110))
87
    >>> H = nx.path_graph(10)
88
    >>> G.add_nodes_from(H)
89

90
    In addition to strings and integers any hashable Python object
91
    (except None) can represent a node, e.g. a customized node object,
92
    or even another Graph.
93

94
    >>> G.add_node(H)
95

96
    **Edges:**
97

98
    G can also be grown by adding edges.
99

100
    Add one edge,
101

102
    >>> G.add_edge(1, 2)
103

104
    a list of edges,
105

106
    >>> G.add_edges_from([(1, 2), (1, 3)])
107

108
    or a collection of edges,
109

110
    >>> G.add_edges_from(H.edges)
111

112
    If some edges connect nodes not yet in the graph, the nodes
113
    are added automatically.  There are no errors when adding
114
    nodes or edges that already exist.
115

116
    **Attributes:**
117

118
    Each graph, node, and edge can hold key/value attribute pairs
119
    in an associated attribute dictionary (the keys must be hashable).
120
    By default these are empty, but can be added or changed using
121
    add_edge, add_node or direct manipulation of the attribute
122
    dictionaries named graph, node and edge respectively.
123

124
    >>> G = nx.Graph(day="Friday")
125
    >>> G.graph
126
    {'day': 'Friday'}
127

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

130
    >>> G.add_node(1, time='5pm')
131
    >>> G.add_nodes_from([3], time='2pm')
132
    >>> G.nodes[1]
133
    {'time': '5pm'}
134
    >>> G.nodes[1]['room'] = 714  # node must exist already to use G.nodes
135
    >>> del G.nodes[1]['room']  # remove attribute
136
    >>> list(G.nodes(data=True))
137
    [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
138

139
    Add edge attributes using add_edge(), add_edges_from(), subscript
140
    notation, or G.edges.
141

142
    >>> G.add_edge(1, 2, weight=4.7 )
143
    >>> G.add_edges_from([(3, 4), (4, 5)], color='red')
144
    >>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
145
    >>> G[1][2]['weight'] = 4.7
146
    >>> G.edges[1, 2]['weight'] = 4
147

148
    Warning: we protect the graph data structure by making `G.edges` a
149
    read-only dict-like structure. However, you can assign to attributes
150
    in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change
151
    data attributes: `G.edges[1, 2]['weight'] = 4`
152
    (For multigraphs: `MG.edges[u, v, key][name] = value`).
153

154
    **Shortcuts:**
155

156
    Many common graph features allow python syntax to speed reporting.
157

158
    >>> 1 in G     # check if node in graph
159
    True
160
    >>> [n for n in G if n < 3]  # iterate through nodes
161
    [1, 2]
162
    >>> len(G)  # number of nodes in graph
163
    5
164

165
    Often the best way to traverse all edges of a graph is via the neighbors.
166
    The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`
167

168
    >>> for n, nbrsdict in G.adjacency():
169
    ...     for nbr, eattr in nbrsdict.items():
170
    ...        if 'weight' in eattr:
171
    ...            # Do something useful with the edges
172
    ...            pass
173

174
    But the edges() method is often more convenient:
175

176
    >>> for u, v, weight in G.edges.data('weight'):
177
    ...     if weight is not None:
178
    ...         # Do something useful with the edges
179
    ...         pass
180

181
    **Reporting:**
182

183
    Simple graph information is obtained using object-attributes and methods.
184
    Reporting typically provides views instead of containers to reduce memory
185
    usage. The views update as the graph is updated similarly to dict-views.
186
    The objects `nodes, `edges` and `adj` provide access to data attributes
187
    via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration
188
    (e.g. `nodes.items()`, `nodes.data('color')`,
189
    `nodes.data('color', default='blue')` and similarly for `edges`)
190
    Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
191

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

194
    **Subclasses (Advanced):**
195

196
    The Graph class uses a dict-of-dict-of-dict data structure.
197
    The outer dict (node_dict) holds adjacency information keyed by node.
198
    The next dict (adjlist_dict) represents the adjacency information and holds
199
    edge data keyed by neighbor.  The inner dict (edge_attr_dict) represents
200
    the edge data and holds edge attribute values keyed by attribute names.
201

202
    Each of these three dicts can be replaced in a subclass by a user defined
203
    dict-like object. In general, the dict-like features should be
204
    maintained but extra features can be added. To replace one of the
205
    dicts create a new graph class by changing the class(!) variable
206
    holding the factory for that dict-like structure. The variable names are
207
    node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
208
    adjlist_outer_dict_factory, edge_attr_dict_factory 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 edge data keyed by neighbor.
228
        It should require no arguments and return a dict-like object
229

230
    edge_attr_dict_factory : function, (default: dict)
231
        Factory function to be used to create the edge attribute
232
        dict which holds attribute values keyed by attribute name.
233
        It should require no arguments and return a dict-like object.
234

235
    graph_attr_dict_factory : function, (default: dict)
236
        Factory function to be used to create the graph 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
    Typically, if your extension doesn't impact the data structure all
241
    methods will inherit without issue except: `to_directed/to_undirected`.
242
    By default these methods create a DiGraph/Graph class and you probably
243
    want them to create your extension of a DiGraph/Graph. To facilitate
244
    this we define two class variables that you can set in your subclass.
245

246
    to_directed_class : callable, (default: DiGraph or MultiDiGraph)
247
        Class to create a new graph structure in the `to_directed` method.
248
        If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
249

250
    to_undirected_class : callable, (default: Graph or MultiGraph)
251
        Class to create a new graph structure in the `to_undirected` method.
252
        If `None`, a NetworkX class (Graph or MultiGraph) is used.
253

254
    Examples
255
    --------
256

257
    Create a low memory graph class that effectively disallows edge
258
    attributes by using a single attribute dict for all edges.
259
    This reduces the memory used, but you lose edge attributes.
260

261
    >>> class ThinGraph(nx.Graph):
262
    ...     all_edge_dict = {'weight': 1}
263
    ...     def single_edge_dict(self):
264
    ...         return self.all_edge_dict
265
    ...     edge_attr_dict_factory = single_edge_dict
266
    >>> G = ThinGraph()
267
    >>> G.add_edge(2, 1)
268
    >>> G[2][1]
269
    {'weight': 1}
270
    >>> G.add_edge(2, 2)
271
    >>> G[2][1] is G[2][2]
272
    True
273

274
    Please see :mod:`~networkx.classes.ordered` for more examples of
275
    creating graph subclasses by overwriting the base class `dict` with
276
    a dictionary-like object.
277
    """
278
    node_dict_factory = dict
279
    node_attr_dict_factory = dict
280
    adjlist_outer_dict_factory = dict
281
    adjlist_inner_dict_factory = dict
282
    edge_attr_dict_factory = dict
283
    graph_attr_dict_factory = dict
284

    
285
    def to_directed_class(self):
286
        """Returns the class to use for empty directed copies.
287

288
        If you subclass the base classes, use this to designate
289
        what directed class to use for `to_directed()` copies.
290
        """
291
        return nx.DiGraph
292

    
293
    def to_undirected_class(self):
294
        """Returns the class to use for empty undirected copies.
295

296
        If you subclass the base classes, use this to designate
297
        what directed class to use for `to_directed()` copies.
298
        """
299
        return Graph
300

    
301
    def __init__(self, incoming_graph_data=None, **attr):
302
        """Initialize a graph with edges, name, or graph attributes.
303

304
        Parameters
305
        ----------
306
        incoming_graph_data : input graph (optional, default: None)
307
            Data to initialize graph. If None (default) an empty
308
            graph is created.  The data can be an edge list, or any
309
            NetworkX graph object.  If the corresponding optional Python
310
            packages are installed the data can also be a NumPy matrix
311
            or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
312

313
        attr : keyword arguments, optional (default= no attributes)
314
            Attributes to add to graph as key=value pairs.
315

316
        See Also
317
        --------
318
        convert
319

320
        Examples
321
        --------
322
        >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
323
        >>> G = nx.Graph(name='my graph')
324
        >>> e = [(1, 2), (2, 3), (3, 4)]  # list of edges
325
        >>> G = nx.Graph(e)
326

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

329
        >>> G = nx.Graph(e, day="Friday")
330
        >>> G.graph
331
        {'day': 'Friday'}
332

333
        """
334
        self.graph_attr_dict_factory = self.graph_attr_dict_factory
335
        self.node_dict_factory = self.node_dict_factory
336
        self.node_attr_dict_factory = self.node_attr_dict_factory
337
        self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory
338
        self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory
339
        self.edge_attr_dict_factory = self.edge_attr_dict_factory
340

    
341
        self.graph = self.graph_attr_dict_factory()   # dictionary for graph attributes
342
        self._node = self.node_dict_factory()  # empty node attribute dict
343
        self._adj = self.adjlist_outer_dict_factory()  # empty adjacency dict
344
        # attempt to load graph with data
345
        if incoming_graph_data is not None:
346
            convert.to_networkx_graph(incoming_graph_data, create_using=self)
347
        # load graph attributes (must be after convert)
348
        self.graph.update(attr)
349

    
350
    @property
351
    def adj(self):
352
        """Graph adjacency object holding the neighbors of each node.
353

354
        This object is a read-only dict-like structure with node keys
355
        and neighbor-dict values.  The neighbor-dict is keyed by neighbor
356
        to the edge-data-dict.  So `G.adj[3][2]['color'] = 'blue'` sets
357
        the color of the edge `(3, 2)` to `"blue"`.
358

359
        Iterating over G.adj behaves like a dict. Useful idioms include
360
        `for nbr, datadict in G.adj[n].items():`.
361

362
        The neighbor information is also provided by subscripting the graph.
363
        So `for nbr, foovalue in G[node].data('foo', default=1):` works.
364

365
        For directed graphs, `G.adj` holds outgoing (successor) info.
366
        """
367
        return AdjacencyView(self._adj)
368

    
369
    @property
370
    def name(self):
371
        """String identifier of the graph.
372

373
        This graph attribute appears in the attribute dict G.graph
374
        keyed by the string `"name"`. as well as an attribute (technically
375
        a property) `G.name`. This is entirely user controlled.
376
        """
377
        return self.graph.get('name', '')
378

    
379
    @name.setter
380
    def name(self, s):
381
        self.graph['name'] = s
382

    
383
    def __str__(self):
384
        """Returns the graph name.
385

386
        Returns
387
        -------
388
        name : string
389
            The name of the graph.
390

391
        Examples
392
        --------
393
        >>> G = nx.Graph(name='foo')
394
        >>> str(G)
395
        'foo'
396
        """
397
        return self.name
398

    
399
    def __iter__(self):
400
        """Iterate over the nodes. Use: 'for n in G'.
401

402
        Returns
403
        -------
404
        niter : iterator
405
            An iterator over all nodes in the graph.
406

407
        Examples
408
        --------
409
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
410
        >>> [n for n in G]
411
        [0, 1, 2, 3]
412
        >>> list(G)
413
        [0, 1, 2, 3]
414
        """
415
        return iter(self._node)
416

    
417
    def __contains__(self, n):
418
        """Returns True if n is a node, False otherwise. Use: 'n in G'.
419

420
        Examples
421
        --------
422
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
423
        >>> 1 in G
424
        True
425
        """
426
        try:
427
            return n in self._node
428
        except TypeError:
429
            return False
430

    
431
    def __len__(self):
432
        """Returns the number of nodes. Use: 'len(G)'.
433

434
        Returns
435
        -------
436
        nnodes : int
437
            The number of nodes in the graph.
438

439
        Examples
440
        --------
441
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
442
        >>> len(G)
443
        4
444

445
        """
446
        return len(self._node)
447

    
448
    def __getitem__(self, n):
449
        """Returns a dict of neighbors of node n.  Use: 'G[n]'.
450

451
        Parameters
452
        ----------
453
        n : node
454
           A node in the graph.
455

456
        Returns
457
        -------
458
        adj_dict : dictionary
459
           The adjacency dictionary for nodes connected to n.
460

461
        Notes
462
        -----
463
        G[n] is the same as G.adj[n] and similar to G.neighbors(n)
464
        (which is an iterator over G.adj[n])
465

466
        Examples
467
        --------
468
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
469
        >>> G[0]
470
        AtlasView({1: {}})
471
        """
472
        return self.adj[n]
473

    
474
    def add_node(self, node_for_adding, **attr):
475
        """Add a single node `node_for_adding` and update node attributes.
476

477
        Parameters
478
        ----------
479
        node_for_adding : node
480
            A node can be any hashable Python object except None.
481
        attr : keyword arguments, optional
482
            Set or change node attributes using key=value.
483

484
        See Also
485
        --------
486
        add_nodes_from
487

488
        Examples
489
        --------
490
        >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
491
        >>> G.add_node(1)
492
        >>> G.add_node('Hello')
493
        >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
494
        >>> G.add_node(K3)
495
        >>> G.number_of_nodes()
496
        3
497

498
        Use keywords set/change node attributes:
499

500
        >>> G.add_node(1, size=10)
501
        >>> G.add_node(3, weight=0.4, UTM=('13S', 382871, 3972649))
502

503
        Notes
504
        -----
505
        A hashable object is one that can be used as a key in a Python
506
        dictionary. This includes strings, numbers, tuples of strings
507
        and numbers, etc.
508

509
        On many platforms hashable items also include mutables such as
510
        NetworkX Graphs, though one should be careful that the hash
511
        doesn't change on mutables.
512
        """
513
        if node_for_adding not in self._node:
514
            self._adj[node_for_adding] = self.adjlist_inner_dict_factory()
515
            attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
516
            attr_dict.update(attr)
517
        else:  # update attr even if node already exists
518
            self._node[node_for_adding].update(attr)
519

    
520
    def add_nodes_from(self, nodes_for_adding, **attr):
521
        """Add multiple nodes.
522

523
        Parameters
524
        ----------
525
        nodes_for_adding : iterable container
526
            A container of nodes (list, dict, set, etc.).
527
            OR
528
            A container of (node, attribute dict) tuples.
529
            Node attributes are updated using the attribute dict.
530
        attr : keyword arguments, optional (default= no attributes)
531
            Update attributes for all nodes in nodes.
532
            Node attributes specified in nodes as a tuple take
533
            precedence over attributes specified via keyword arguments.
534

535
        See Also
536
        --------
537
        add_node
538

539
        Examples
540
        --------
541
        >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
542
        >>> G.add_nodes_from('Hello')
543
        >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
544
        >>> G.add_nodes_from(K3)
545
        >>> sorted(G.nodes(), key=str)
546
        [0, 1, 2, 'H', 'e', 'l', 'o']
547

548
        Use keywords to update specific node attributes for every node.
549

550
        >>> G.add_nodes_from([1, 2], size=10)
551
        >>> G.add_nodes_from([3, 4], weight=0.4)
552

553
        Use (node, attrdict) tuples to update attributes for specific nodes.
554

555
        >>> G.add_nodes_from([(1, dict(size=11)), (2, {'color':'blue'})])
556
        >>> G.nodes[1]['size']
557
        11
558
        >>> H = nx.Graph()
559
        >>> H.add_nodes_from(G.nodes(data=True))
560
        >>> H.nodes[1]['size']
561
        11
562

563
        """
564
        for n in nodes_for_adding:
565
            # keep all this inside try/except because
566
            # CPython throws TypeError on n not in self._node,
567
            # while pre-2.7.5 ironpython throws on self._adj[n]
568
            try:
569
                if n not in self._node:
570
                    self._adj[n] = self.adjlist_inner_dict_factory()
571
                    attr_dict = self._node[n] = self.node_attr_dict_factory()
572
                    attr_dict.update(attr)
573
                else:
574
                    self._node[n].update(attr)
575
            except TypeError:
576
                nn, ndict = n
577
                if nn not in self._node:
578
                    self._adj[nn] = self.adjlist_inner_dict_factory()
579
                    newdict = attr.copy()
580
                    newdict.update(ndict)
581
                    attr_dict = self._node[nn] = self.node_attr_dict_factory()
582
                    attr_dict.update(newdict)
583
                else:
584
                    olddict = self._node[nn]
585
                    olddict.update(attr)
586
                    olddict.update(ndict)
587

    
588
    def remove_node(self, n):
589
        """Remove node n.
590

591
        Removes the node n and all adjacent edges.
592
        Attempting to remove a non-existent node will raise an exception.
593

594
        Parameters
595
        ----------
596
        n : node
597
           A node in the graph
598

599
        Raises
600
        -------
601
        NetworkXError
602
           If n is not in the graph.
603

604
        See Also
605
        --------
606
        remove_nodes_from
607

608
        Examples
609
        --------
610
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
611
        >>> list(G.edges)
612
        [(0, 1), (1, 2)]
613
        >>> G.remove_node(1)
614
        >>> list(G.edges)
615
        []
616

617
        """
618
        adj = self._adj
619
        try:
620
            nbrs = list(adj[n])  # list handles self-loops (allows mutation)
621
            del self._node[n]
622
        except KeyError:  # NetworkXError if n not in self
623
            raise NetworkXError("The node %s is not in the graph." % (n,))
624
        for u in nbrs:
625
            del adj[u][n]   # remove all edges n-u in graph
626
        del adj[n]          # now remove node
627

    
628
    def remove_nodes_from(self, nodes):
629
        """Remove multiple nodes.
630

631
        Parameters
632
        ----------
633
        nodes : iterable container
634
            A container of nodes (list, dict, set, etc.).  If a node
635
            in the container is not in the graph it is silently
636
            ignored.
637

638
        See Also
639
        --------
640
        remove_node
641

642
        Examples
643
        --------
644
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
645
        >>> e = list(G.nodes)
646
        >>> e
647
        [0, 1, 2]
648
        >>> G.remove_nodes_from(e)
649
        >>> list(G.nodes)
650
        []
651

652
        """
653
        adj = self._adj
654
        for n in nodes:
655
            try:
656
                del self._node[n]
657
                for u in list(adj[n]):   # list handles self-loops
658
                    del adj[u][n]  # (allows mutation of dict in loop)
659
                del adj[n]
660
            except KeyError:
661
                pass
662

    
663
    @property
664
    def nodes(self):
665
        """A NodeView of the Graph as G.nodes or G.nodes().
666

667
        Can be used as `G.nodes` for data lookup and for set-like operations.
668
        Can also be used as `G.nodes(data='color', default=None)` to return a
669
        NodeDataView which reports specific node data but no set operations.
670
        It presents a dict-like interface as well with `G.nodes.items()`
671
        iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']`
672
        providing the value of the `foo` attribute for node `3`. In addition,
673
        a view `G.nodes.data('foo')` provides a dict-like interface to the
674
        `foo` attribute of each node. `G.nodes.data('foo', default=1)`
675
        provides a default for nodes that do not have attribute `foo`.
676

677
        Parameters
678
        ----------
679
        data : string or bool, optional (default=False)
680
            The node attribute returned in 2-tuple (n, ddict[data]).
681
            If True, return entire node attribute dict as (n, ddict).
682
            If False, return just the nodes n.
683

684
        default : value, optional (default=None)
685
            Value used for nodes that don't have the requested attribute.
686
            Only relevant if data is not True or False.
687

688
        Returns
689
        -------
690
        NodeView
691
            Allows set-like operations over the nodes as well as node
692
            attribute dict lookup and calling to get a NodeDataView.
693
            A NodeDataView iterates over `(n, data)` and has no set operations.
694
            A NodeView iterates over `n` and includes set operations.
695

696
            When called, if data is False, an iterator over nodes.
697
            Otherwise an iterator of 2-tuples (node, attribute value)
698
            where the attribute is specified in `data`.
699
            If data is True then the attribute becomes the
700
            entire data dictionary.
701

702
        Notes
703
        -----
704
        If your node data is not needed, it is simpler and equivalent
705
        to use the expression ``for n in G``, or ``list(G)``.
706

707
        Examples
708
        --------
709
        There are two simple ways of getting a list of all nodes in the graph:
710

711
        >>> G = nx.path_graph(3)
712
        >>> list(G.nodes)
713
        [0, 1, 2]
714
        >>> list(G)
715
        [0, 1, 2]
716

717
        To get the node data along with the nodes:
718

719
        >>> G.add_node(1, time='5pm')
720
        >>> G.nodes[0]['foo'] = 'bar'
721
        >>> list(G.nodes(data=True))
722
        [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
723
        >>> list(G.nodes.data())
724
        [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
725

726
        >>> list(G.nodes(data='foo'))
727
        [(0, 'bar'), (1, None), (2, None)]
728
        >>> list(G.nodes.data('foo'))
729
        [(0, 'bar'), (1, None), (2, None)]
730

731
        >>> list(G.nodes(data='time'))
732
        [(0, None), (1, '5pm'), (2, None)]
733
        >>> list(G.nodes.data('time'))
734
        [(0, None), (1, '5pm'), (2, None)]
735

736
        >>> list(G.nodes(data='time', default='Not Available'))
737
        [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
738
        >>> list(G.nodes.data('time', default='Not Available'))
739
        [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
740

741
        If some of your nodes have an attribute and the rest are assumed
742
        to have a default attribute value you can create a dictionary
743
        from node/attribute pairs using the `default` keyword argument
744
        to guarantee the value is never None::
745

746
            >>> G = nx.Graph()
747
            >>> G.add_node(0)
748
            >>> G.add_node(1, weight=2)
749
            >>> G.add_node(2, weight=3)
750
            >>> dict(G.nodes(data='weight', default=1))
751
            {0: 1, 1: 2, 2: 3}
752

753
        """
754
        nodes = NodeView(self)
755
        # Lazy View creation: overload the (class) property on the instance
756
        # Then future G.nodes use the existing View
757
        # setattr doesn't work because attribute already exists
758
        self.__dict__['nodes'] = nodes
759
        return nodes
760

    
761
    # for backwards compatibility with 1.x, will be removed for 3.x
762
    node = nodes
763

    
764
    def add_path(self, nodes, **attr):
765
        msg = "add_path is deprecated. Use nx.add_path instead."
766
        warnings.warn(msg, DeprecationWarning)
767
        return nx.add_path(self, nodes, **attr)
768

    
769
    def add_cycle(self, nodes, **attr):
770
        msg = "add_cycle is deprecated. Use nx.add_cycle instead."
771
        warnings.warn(msg, DeprecationWarning)
772
        return nx.add_cycle(self, nodes, **attr)
773

    
774
    def add_star(self, nodes, **attr):
775
        msg = "add_star is deprecated. Use nx.add_star instead."
776
        warnings.warn(msg, DeprecationWarning)
777
        return nx.add_star(self, nodes, **attr)
778

    
779
    def nodes_with_selfloops(self):
780
        msg = "nodes_with_selfloops is deprecated." \
781
              "Use nx.nodes_with_selfloops instead."
782
        warnings.warn(msg, DeprecationWarning)
783
        return nx.nodes_with_selfloops(self)
784

    
785
    def number_of_selfloops(self):
786
        msg = "number_of_selfloops is deprecated." \
787
              "Use nx.number_of_selfloops instead."
788
        warnings.warn(msg, DeprecationWarning)
789
        return nx.number_of_selfloops(self)
790

    
791
    def selfloop_edges(self, data=False, keys=False, default=None):
792
        msg = "selfloop_edges is deprecated. Use nx.selfloop_edges instead."
793
        warnings.warn(msg, DeprecationWarning)
794
        return nx.selfloop_edges(self, data, keys, default)
795
    # Done with backward compatibility methods for 1.x
796

    
797
    def number_of_nodes(self):
798
        """Returns the number of nodes in the graph.
799

800
        Returns
801
        -------
802
        nnodes : int
803
            The number of nodes in the graph.
804

805
        See Also
806
        --------
807
        order, __len__  which are identical
808

809
        Examples
810
        --------
811
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
812
        >>> len(G)
813
        3
814
        """
815
        return len(self._node)
816

    
817
    def order(self):
818
        """Returns the number of nodes in the graph.
819

820
        Returns
821
        -------
822
        nnodes : int
823
            The number of nodes in the graph.
824

825
        See Also
826
        --------
827
        number_of_nodes, __len__  which are identical
828

829
        """
830
        return len(self._node)
831

    
832
    def has_node(self, n):
833
        """Returns True if the graph contains the node n.
834

835
        Identical to `n in G`
836

837
        Parameters
838
        ----------
839
        n : node
840

841
        Examples
842
        --------
843
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
844
        >>> G.has_node(0)
845
        True
846

847
        It is more readable and simpler to use
848

849
        >>> 0 in G
850
        True
851

852
        """
853
        try:
854
            return n in self._node
855
        except TypeError:
856
            return False
857

    
858
    def add_edge(self, u_of_edge, v_of_edge, **attr):
859
        """Add an edge between u and v.
860

861
        The nodes u and v will be automatically added if they are
862
        not already in the graph.
863

864
        Edge attributes can be specified with keywords or by directly
865
        accessing the edge's attribute dictionary. See examples below.
866

867
        Parameters
868
        ----------
869
        u, v : nodes
870
            Nodes can be, for example, strings or numbers.
871
            Nodes must be hashable (and not None) Python objects.
872
        attr : keyword arguments, optional
873
            Edge data (or labels or objects) can be assigned using
874
            keyword arguments.
875

876
        See Also
877
        --------
878
        add_edges_from : add a collection of edges
879

880
        Notes
881
        -----
882
        Adding an edge that already exists updates the edge data.
883

884
        Many NetworkX algorithms designed for weighted graphs use
885
        an edge attribute (by default `weight`) to hold a numerical value.
886

887
        Examples
888
        --------
889
        The following all add the edge e=(1, 2) to graph G:
890

891
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
892
        >>> e = (1, 2)
893
        >>> G.add_edge(1, 2)           # explicit two-node form
894
        >>> G.add_edge(*e)             # single edge as tuple of two nodes
895
        >>> G.add_edges_from([(1, 2)])  # add edges from iterable container
896

897
        Associate data to edges using keywords:
898

899
        >>> G.add_edge(1, 2, weight=3)
900
        >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
901

902
        For non-string attribute keys, use subscript notation.
903

904
        >>> G.add_edge(1, 2)
905
        >>> G[1][2].update({0: 5})
906
        >>> G.edges[1, 2].update({0: 5})
907
        """
908
        u, v = u_of_edge, v_of_edge
909
        # add nodes
910
        if u not in self._node:
911
            self._adj[u] = self.adjlist_inner_dict_factory()
912
            self._node[u] = self.node_attr_dict_factory()
913
        if v not in self._node:
914
            self._adj[v] = self.adjlist_inner_dict_factory()
915
            self._node[v] = self.node_attr_dict_factory()
916
        # add the edge
917
        datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
918
        datadict.update(attr)
919
        self._adj[u][v] = datadict
920
        self._adj[v][u] = datadict
921

    
922
    def add_edges_from(self, ebunch_to_add, **attr):
923
        """Add all the edges in ebunch_to_add.
924

925
        Parameters
926
        ----------
927
        ebunch_to_add : container of edges
928
            Each edge given in the container will be added to the
929
            graph. The edges must be given as as 2-tuples (u, v) or
930
            3-tuples (u, v, d) where d is a dictionary containing edge data.
931
        attr : keyword arguments, optional
932
            Edge data (or labels or objects) can be assigned using
933
            keyword arguments.
934

935
        See Also
936
        --------
937
        add_edge : add a single edge
938
        add_weighted_edges_from : convenient way to add weighted edges
939

940
        Notes
941
        -----
942
        Adding the same edge twice has no effect but any edge data
943
        will be updated when each duplicate edge is added.
944

945
        Edge attributes specified in an ebunch take precedence over
946
        attributes specified via keyword arguments.
947

948
        Examples
949
        --------
950
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
951
        >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
952
        >>> e = zip(range(0, 3), range(1, 4))
953
        >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
954

955
        Associate data to edges
956

957
        >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
958
        >>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898')
959
        """
960
        for e in ebunch_to_add:
961
            ne = len(e)
962
            if ne == 3:
963
                u, v, dd = e
964
            elif ne == 2:
965
                u, v = e
966
                dd = {}  # doesn't need edge_attr_dict_factory
967
            else:
968
                raise NetworkXError(
969
                    "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))
970
            if u not in self._node:
971
                self._adj[u] = self.adjlist_inner_dict_factory()
972
                self._node[u] = self.node_attr_dict_factory()
973
            if v not in self._node:
974
                self._adj[v] = self.adjlist_inner_dict_factory()
975
                self._node[v] = self.node_attr_dict_factory()
976
            datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
977
            datadict.update(attr)
978
            datadict.update(dd)
979
            self._adj[u][v] = datadict
980
            self._adj[v][u] = datadict
981

    
982
    def add_weighted_edges_from(self, ebunch_to_add, weight='weight', **attr):
983
        """Add weighted edges in `ebunch_to_add` with specified weight attr
984

985
        Parameters
986
        ----------
987
        ebunch_to_add : container of edges
988
            Each edge given in the list or container will be added
989
            to the graph. The edges must be given as 3-tuples (u, v, w)
990
            where w is a number.
991
        weight : string, optional (default= 'weight')
992
            The attribute name for the edge weights to be added.
993
        attr : keyword arguments, optional (default= no attributes)
994
            Edge attributes to add/update for all edges.
995

996
        See Also
997
        --------
998
        add_edge : add a single edge
999
        add_edges_from : add multiple edges
1000

1001
        Notes
1002
        -----
1003
        Adding the same edge twice for Graph/DiGraph simply updates
1004
        the edge data. For MultiGraph/MultiDiGraph, duplicate edges
1005
        are stored.
1006

1007
        Examples
1008
        --------
1009
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
1010
        >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
1011
        """
1012
        self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add),
1013
                            **attr)
1014

    
1015
    def remove_edge(self, u, v):
1016
        """Remove the edge between u and v.
1017

1018
        Parameters
1019
        ----------
1020
        u, v : nodes
1021
            Remove the edge between nodes u and v.
1022

1023
        Raises
1024
        ------
1025
        NetworkXError
1026
            If there is not an edge between u and v.
1027

1028
        See Also
1029
        --------
1030
        remove_edges_from : remove a collection of edges
1031

1032
        Examples
1033
        --------
1034
        >>> G = nx.path_graph(4)  # or DiGraph, etc
1035
        >>> G.remove_edge(0, 1)
1036
        >>> e = (1, 2)
1037
        >>> G.remove_edge(*e) # unpacks e from an edge tuple
1038
        >>> e = (2, 3, {'weight':7}) # an edge with attribute data
1039
        >>> G.remove_edge(*e[:2]) # select first part of edge tuple
1040
        """
1041
        try:
1042
            del self._adj[u][v]
1043
            if u != v:  # self-loop needs only one entry removed
1044
                del self._adj[v][u]
1045
        except KeyError:
1046
            raise NetworkXError("The edge %s-%s is not in the graph" % (u, v))
1047

    
1048
    def remove_edges_from(self, ebunch):
1049
        """Remove all edges specified in ebunch.
1050

1051
        Parameters
1052
        ----------
1053
        ebunch: list or container of edge tuples
1054
            Each edge given in the list or container will be removed
1055
            from the graph. The edges can be:
1056

1057
                - 2-tuples (u, v) edge between u and v.
1058
                - 3-tuples (u, v, k) where k is ignored.
1059

1060
        See Also
1061
        --------
1062
        remove_edge : remove a single edge
1063

1064
        Notes
1065
        -----
1066
        Will fail silently if an edge in ebunch is not in the graph.
1067

1068
        Examples
1069
        --------
1070
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1071
        >>> ebunch=[(1, 2), (2, 3)]
1072
        >>> G.remove_edges_from(ebunch)
1073
        """
1074
        adj = self._adj
1075
        for e in ebunch:
1076
            u, v = e[:2]  # ignore edge data if present
1077
            if u in adj and v in adj[u]:
1078
                del adj[u][v]
1079
                if u != v:  # self loop needs only one entry removed
1080
                    del adj[v][u]
1081

    
1082
    def update(self, edges=None, nodes=None):
1083
        """Update the graph using nodes/edges/graphs as input.
1084

1085
        Like dict.update, this method takes a graph as input, adding the
1086
        graph's nodes and edges to this graph. It can also take two inputs:
1087
        edges and nodes. Finally it can take either edges or nodes.
1088
        To specify only nodes the keyword `nodes` must be used.
1089

1090
        The collections of edges and nodes are treated similarly to
1091
        the add_edges_from/add_nodes_from methods. When iterated, they
1092
        should yield 2-tuples (u, v) or 3-tuples (u, v, datadict).
1093

1094
        Parameters
1095
        ----------
1096
        edges : Graph object, collection of edges, or None
1097
            The first parameter can be a graph or some edges. If it has
1098
            attributes `nodes` and `edges`, then it is taken to be a
1099
            Graph-like object and those attributes are used as collections
1100
            of nodes and edges to be added to the graph.
1101
            If the first parameter does not have those attributes, it is
1102
            treated as a collection of edges and added to the graph.
1103
            If the first argument is None, no edges are added.
1104
        nodes : collection of nodes, or None
1105
            The second parameter is treated as a collection of nodes
1106
            to be added to the graph unless it is None.
1107
            If `edges is None` and `nodes is None` an exception is raised.
1108
            If the first parameter is a Graph, then `nodes` is ignored.
1109

1110
        Examples
1111
        --------
1112
        >>> G = nx.path_graph(5)
1113
        >>> G.update(nx.complete_graph(range(4,10)))
1114
        >>> from itertools import combinations
1115
        >>> edges = ((u, v, {'power': u * v})
1116
        ...          for u, v in combinations(range(10, 20), 2)
1117
        ...          if u * v < 225)
1118
        >>> nodes = [1000]  # for singleton, use a container
1119
        >>> G.update(edges, nodes)
1120

1121
        Notes
1122
        -----
1123
        It you want to update the graph using an adjacency structure
1124
        it is straightforward to obtain the edges/nodes from adjacency.
1125
        The following examples provide common cases, your adjacency may
1126
        be slightly different and require tweaks of these examples.
1127

1128
        >>> # dict-of-set/list/tuple
1129
        >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}}
1130
        >>> e = [(u, v) for u, nbrs in adj.items() for v in  nbrs]
1131
        >>> G.update(edges=e, nodes=adj)
1132

1133
        >>> DG = nx.DiGraph()
1134
        >>> # dict-of-dict-of-attribute
1135
        >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}}
1136
        >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items()
1137
        ...      for v, d in nbrs.items()]
1138
        >>> DG.update(edges=e, nodes=adj)
1139

1140
        >>> # dict-of-dict-of-dict
1141
        >>> adj = {1: {2: {'weight': 1.3}, 3: {'color': 0.7, 'weight':1.2}}}
1142
        >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items()
1143
        ...      for v, d in nbrs.items()]
1144
        >>> DG.update(edges=e, nodes=adj)
1145

1146
        >>> # predecessor adjacency (dict-of-set)
1147
        >>> pred = {1: {2, 3}, 2: {3}, 3: {3}}
1148
        >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs]
1149

1150
        >>> # MultiGraph dict-of-dict-of-dict-of-attribute
1151
        >>> MDG = nx.MultiDiGraph()
1152
        >>> adj = {1: {2: {0: {'weight': 1.3}, 1: {'weight': 1.2}}},
1153
        ...        3: {2: {0: {'weight': 0.7}}}}
1154
        >>> e = [(u, v, ekey, d) for u, nbrs in adj.items()
1155
        ...      for v, keydict in nbrs.items()
1156
        ...      for ekey, d in keydict.items()]
1157
        >>> MDG.update(edges=e)
1158

1159
        See Also
1160
        --------
1161
        add_edges_from: add multiple edges to a graph
1162
        add_nodes_from: add multiple nodes to a graph
1163
        """
1164
        if edges is not None:
1165
            if nodes is not None:
1166
                self.add_nodes_from(nodes)
1167
                self.add_edges_from(edges)
1168
            else:
1169
                # check if edges is a Graph object
1170
                try:
1171
                    graph_nodes = edges.nodes
1172
                    graph_edges = edges.edges
1173
                except AttributeError:
1174
                    # edge not Graph-like
1175
                    self.add_edges_from(edges)
1176
                else:  # edges is Graph-like
1177
                    self.add_nodes_from(graph_nodes.data())
1178
                    self.add_edges_from(graph_edges.data())
1179
                    self.graph.update(edges.graph)
1180
        elif nodes is not None:
1181
            self.add_nodes_from(nodes)
1182
        else:
1183
            raise NetworkXError("update needs nodes or edges input")
1184

    
1185
    def has_edge(self, u, v):
1186
        """Returns True if the edge (u, v) is in the graph.
1187

1188
        This is the same as `v in G[u]` without KeyError exceptions.
1189

1190
        Parameters
1191
        ----------
1192
        u, v : nodes
1193
            Nodes can be, for example, strings or numbers.
1194
            Nodes must be hashable (and not None) Python objects.
1195

1196
        Returns
1197
        -------
1198
        edge_ind : bool
1199
            True if edge is in the graph, False otherwise.
1200

1201
        Examples
1202
        --------
1203
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1204
        >>> G.has_edge(0, 1)  # using two nodes
1205
        True
1206
        >>> e = (0, 1)
1207
        >>> G.has_edge(*e)  #  e is a 2-tuple (u, v)
1208
        True
1209
        >>> e = (0, 1, {'weight':7})
1210
        >>> G.has_edge(*e[:2])  # e is a 3-tuple (u, v, data_dictionary)
1211
        True
1212

1213
        The following syntax are equivalent:
1214

1215
        >>> G.has_edge(0, 1)
1216
        True
1217
        >>> 1 in G[0]  # though this gives KeyError if 0 not in G
1218
        True
1219

1220
        """
1221
        try:
1222
            return v in self._adj[u]
1223
        except KeyError:
1224
            return False
1225

    
1226
    def neighbors(self, n):
1227
        """Returns an iterator over all neighbors of node n.
1228

1229
        This is identical to `iter(G[n])`
1230

1231
        Parameters
1232
        ----------
1233
        n : node
1234
           A node in the graph
1235

1236
        Returns
1237
        -------
1238
        neighbors : iterator
1239
            An iterator over all neighbors of node n
1240

1241
        Raises
1242
        ------
1243
        NetworkXError
1244
            If the node n is not in the graph.
1245

1246
        Examples
1247
        --------
1248
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1249
        >>> [n for n in G.neighbors(0)]
1250
        [1]
1251

1252
        Notes
1253
        -----
1254
        It is usually more convenient (and faster) to access the
1255
        adjacency dictionary as ``G[n]``:
1256

1257
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
1258
        >>> G.add_edge('a', 'b', weight=7)
1259
        >>> G['a']
1260
        AtlasView({'b': {'weight': 7}})
1261
        >>> G = nx.path_graph(4)
1262
        >>> [n for n in G[0]]
1263
        [1]
1264
        """
1265
        try:
1266
            return iter(self._adj[n])
1267
        except KeyError:
1268
            raise NetworkXError("The node %s is not in the graph." % (n,))
1269

    
1270
    @property
1271
    def edges(self):
1272
        """An EdgeView of the Graph as G.edges or G.edges().
1273

1274
        edges(self, nbunch=None, data=False, default=None)
1275

1276
        The EdgeView provides set-like operations on the edge-tuples
1277
        as well as edge attribute lookup. When called, it also provides
1278
        an EdgeDataView object which allows control of access to edge
1279
        attributes (but does not provide set-like operations).
1280
        Hence, `G.edges[u, v]['color']` provides the value of the color
1281
        attribute for edge `(u, v)` while
1282
        `for (u, v, c) in G.edges.data('color', default='red'):`
1283
        iterates through all the edges yielding the color attribute
1284
        with default `'red'` if no color attribute exists.
1285

1286
        Parameters
1287
        ----------
1288
        nbunch : single node, container, or all nodes (default= all nodes)
1289
            The view will only report edges incident to these nodes.
1290
        data : string or bool, optional (default=False)
1291
            The edge attribute returned in 3-tuple (u, v, ddict[data]).
1292
            If True, return edge attribute dict in 3-tuple (u, v, ddict).
1293
            If False, return 2-tuple (u, v).
1294
        default : value, optional (default=None)
1295
            Value used for edges that don't have the requested attribute.
1296
            Only relevant if data is not True or False.
1297

1298
        Returns
1299
        -------
1300
        edges : EdgeView
1301
            A view of edge attributes, usually it iterates over (u, v)
1302
            or (u, v, d) tuples of edges, but can also be used for
1303
            attribute lookup as `edges[u, v]['foo']`.
1304

1305
        Notes
1306
        -----
1307
        Nodes in nbunch that are not in the graph will be (quietly) ignored.
1308
        For directed graphs this returns the out-edges.
1309

1310
        Examples
1311
        --------
1312
        >>> G = nx.path_graph(3)   # or MultiGraph, etc
1313
        >>> G.add_edge(2, 3, weight=5)
1314
        >>> [e for e in G.edges]
1315
        [(0, 1), (1, 2), (2, 3)]
1316
        >>> G.edges.data()  # default data is {} (empty dict)
1317
        EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
1318
        >>> G.edges.data('weight', default=1)
1319
        EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
1320
        >>> G.edges([0, 3])  # only edges incident to these nodes
1321
        EdgeDataView([(0, 1), (3, 2)])
1322
        >>> G.edges(0)  # only edges incident to a single node (use G.adj[0]?)
1323
        EdgeDataView([(0, 1)])
1324
        """
1325
        return EdgeView(self)
1326

    
1327
    def get_edge_data(self, u, v, default=None):
1328
        """Returns the attribute dictionary associated with edge (u, v).
1329

1330
        This is identical to `G[u][v]` except the default is returned
1331
        instead of an exception is the edge doesn't exist.
1332

1333
        Parameters
1334
        ----------
1335
        u, v : nodes
1336
        default:  any Python object (default=None)
1337
            Value to return if the edge (u, v) is not found.
1338

1339
        Returns
1340
        -------
1341
        edge_dict : dictionary
1342
            The edge attribute dictionary.
1343

1344
        Examples
1345
        --------
1346
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1347
        >>> G[0][1]
1348
        {}
1349

1350
        Warning: Assigning to `G[u][v]` is not permitted.
1351
        But it is safe to assign attributes `G[u][v]['foo']`
1352

1353
        >>> G[0][1]['weight'] = 7
1354
        >>> G[0][1]['weight']
1355
        7
1356
        >>> G[1][0]['weight']
1357
        7
1358

1359
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1360
        >>> G.get_edge_data(0, 1)  # default edge data is {}
1361
        {}
1362
        >>> e = (0, 1)
1363
        >>> G.get_edge_data(*e)  # tuple form
1364
        {}
1365
        >>> G.get_edge_data('a', 'b', default=0)  # edge not in graph, return 0
1366
        0
1367
        """
1368
        try:
1369
            return self._adj[u][v]
1370
        except KeyError:
1371
            return default
1372

    
1373
    def adjacency(self):
1374
        """Returns an iterator over (node, adjacency dict) tuples for all nodes.
1375

1376
        For directed graphs, only outgoing neighbors/adjacencies are included.
1377

1378
        Returns
1379
        -------
1380
        adj_iter : iterator
1381
           An iterator over (node, adjacency dictionary) for all nodes in
1382
           the graph.
1383

1384
        Examples
1385
        --------
1386
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1387
        >>> [(n, nbrdict) for n, nbrdict in G.adjacency()]
1388
        [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]
1389

1390
        """
1391
        return iter(self._adj.items())
1392

    
1393
    @property
1394
    def degree(self):
1395
        """A DegreeView for the Graph as G.degree or G.degree().
1396

1397
        The node degree is the number of edges adjacent to the node.
1398
        The weighted node degree is the sum of the edge weights for
1399
        edges incident to that node.
1400

1401
        This object provides an iterator for (node, degree) as well as
1402
        lookup for the degree for a single node.
1403

1404
        Parameters
1405
        ----------
1406
        nbunch : single node, container, or all nodes (default= all nodes)
1407
            The view will only report edges incident to these nodes.
1408

1409
        weight : string or None, optional (default=None)
1410
           The name of an edge attribute that holds the numerical value used
1411
           as a weight.  If None, then each edge has weight 1.
1412
           The degree is the sum of the edge weights adjacent to the node.
1413

1414
        Returns
1415
        -------
1416
        If a single node is requested
1417
        deg : int
1418
            Degree of the node
1419

1420
        OR if multiple nodes are requested
1421
        nd_view : A DegreeView object capable of iterating (node, degree) pairs
1422

1423
        Examples
1424
        --------
1425
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1426
        >>> G.degree[0]  # node 0 has degree 1
1427
        1
1428
        >>> list(G.degree([0, 1, 2]))
1429
        [(0, 1), (1, 2), (2, 2)]
1430
        """
1431
        return DegreeView(self)
1432

    
1433
    def clear(self):
1434
        """Remove all nodes and edges from the graph.
1435

1436
        This also removes the name, and all graph, node, and edge attributes.
1437

1438
        Examples
1439
        --------
1440
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1441
        >>> G.clear()
1442
        >>> list(G.nodes)
1443
        []
1444
        >>> list(G.edges)
1445
        []
1446

1447
        """
1448
        self._adj.clear()
1449
        self._node.clear()
1450
        self.graph.clear()
1451

    
1452
    def is_multigraph(self):
1453
        """Returns True if graph is a multigraph, False otherwise."""
1454
        return False
1455

    
1456
    def is_directed(self):
1457
        """Returns True if graph is directed, False otherwise."""
1458
        return False
1459

    
1460
    def fresh_copy(self):
1461
        # remove by v3 if not before
1462
        msg = 'G.fresh_copy is deprecated. Use G.__class__ instead'
1463
        warnings.warn(msg, DeprecationWarning, stacklevel=2)
1464
        return self.__class__()
1465

    
1466
    def copy(self, as_view=False):
1467
        """Returns a copy of the graph.
1468

1469
        The copy method by default returns an independent shallow copy
1470
        of the graph and attributes. That is, if an attribute is a
1471
        container, that container is shared by the original an the copy.
1472
        Use Python's `copy.deepcopy` for new containers.
1473

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

1476
        Notes
1477
        -----
1478
        All copies reproduce the graph structure, but data attributes
1479
        may be handled in different ways. There are four types of copies
1480
        of a graph that people might want.
1481

1482
        Deepcopy -- A "deepcopy" copies the graph structure as well as
1483
        all data attributes and any objects they might contain.
1484
        The entire graph object is new so that changes in the copy
1485
        do not affect the original object. (see Python's copy.deepcopy)
1486

1487
        Data Reference (Shallow) -- For a shallow copy the graph structure
1488
        is copied but the edge, node and graph attribute dicts are
1489
        references to those in the original graph. This saves
1490
        time and memory but could cause confusion if you change an attribute
1491
        in one graph and it changes the attribute in the other.
1492
        NetworkX does not provide this level of shallow copy.
1493

1494
        Independent Shallow -- This copy creates new independent attribute
1495
        dicts and then does a shallow copy of the attributes. That is, any
1496
        attributes that are containers are shared between the new graph
1497
        and the original. This is exactly what `dict.copy()` provides.
1498
        You can obtain this style copy using:
1499

1500
            >>> G = nx.path_graph(5)
1501
            >>> H = G.copy()
1502
            >>> H = G.copy(as_view=False)
1503
            >>> H = nx.Graph(G)
1504
            >>> H = G.__class__(G)
1505

1506
        Fresh Data -- For fresh data, the graph structure is copied while
1507
        new empty data attribute dicts are created. The resulting graph
1508
        is independent of the original and it has no edge, node or graph
1509
        attributes. Fresh copies are not enabled. Instead use:
1510

1511
            >>> H = G.__class__()
1512
            >>> H.add_nodes_from(G)
1513
            >>> H.add_edges_from(G.edges)
1514

1515
        View -- Inspired by dict-views, graph-views act like read-only
1516
        versions of the original graph, providing a copy of the original
1517
        structure without requiring any memory for copying the information.
1518

1519
        See the Python copy module for more information on shallow
1520
        and deep copies, https://docs.python.org/2/library/copy.html.
1521

1522
        Parameters
1523
        ----------
1524
        as_view : bool, optional (default=False)
1525
            If True, the returned graph-view provides a read-only view
1526
            of the original graph without actually copying any data.
1527

1528
        Returns
1529
        -------
1530
        G : Graph
1531
            A copy of the graph.
1532

1533
        See Also
1534
        --------
1535
        to_directed: return a directed copy of the graph.
1536

1537
        Examples
1538
        --------
1539
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1540
        >>> H = G.copy()
1541

1542
        """
1543
        if as_view is True:
1544
            return nx.graphviews.generic_graph_view(self)
1545
        G = self.__class__()
1546
        G.graph.update(self.graph)
1547
        G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1548
        G.add_edges_from((u, v, datadict.copy())
1549
                         for u, nbrs in self._adj.items()
1550
                         for v, datadict in nbrs.items())
1551
        return G
1552

    
1553
    def to_directed(self, as_view=False):
1554
        """Returns a directed representation of the graph.
1555

1556
        Returns
1557
        -------
1558
        G : DiGraph
1559
            A directed graph with the same name, same nodes, and with
1560
            each edge (u, v, data) replaced by two directed edges
1561
            (u, v, data) and (v, u, data).
1562

1563
        Notes
1564
        -----
1565
        This returns a "deepcopy" of the edge, node, and
1566
        graph attributes which attempts to completely copy
1567
        all of the data and references.
1568

1569
        This is in contrast to the similar D=DiGraph(G) which returns a
1570
        shallow copy of the data.
1571

1572
        See the Python copy module for more information on shallow
1573
        and deep copies, https://docs.python.org/2/library/copy.html.
1574

1575
        Warning: If you have subclassed Graph to use dict-like objects
1576
        in the data structure, those changes do not transfer to the
1577
        DiGraph created by this method.
1578

1579
        Examples
1580
        --------
1581
        >>> G = nx.Graph()  # or MultiGraph, etc
1582
        >>> G.add_edge(0, 1)
1583
        >>> H = G.to_directed()
1584
        >>> list(H.edges)
1585
        [(0, 1), (1, 0)]
1586

1587
        If already directed, return a (deep) copy
1588

1589
        >>> G = nx.DiGraph()  # or MultiDiGraph, etc
1590
        >>> G.add_edge(0, 1)
1591
        >>> H = G.to_directed()
1592
        >>> list(H.edges)
1593
        [(0, 1)]
1594
        """
1595
        graph_class = self.to_directed_class()
1596
        if as_view is True:
1597
            return nx.graphviews.generic_graph_view(self, graph_class)
1598
        # deepcopy when not a view
1599
        G = graph_class()
1600
        G.graph.update(deepcopy(self.graph))
1601
        G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1602
        G.add_edges_from((u, v, deepcopy(data))
1603
                         for u, nbrs in self._adj.items()
1604
                         for v, data in nbrs.items())
1605
        return G
1606

    
1607
    def to_undirected(self, as_view=False):
1608
        """Returns an undirected copy of the graph.
1609

1610
        Parameters
1611
        ----------
1612
        as_view : bool (optional, default=False)
1613
          If True return a view of the original undirected graph.
1614

1615
        Returns
1616
        -------
1617
        G : Graph/MultiGraph
1618
            A deepcopy of the graph.
1619

1620
        See Also
1621
        --------
1622
        Graph, copy, add_edge, add_edges_from
1623

1624
        Notes
1625
        -----
1626
        This returns a "deepcopy" of the edge, node, and
1627
        graph attributes which attempts to completely copy
1628
        all of the data and references.
1629

1630
        This is in contrast to the similar `G = nx.DiGraph(D)` which returns a
1631
        shallow copy of the data.
1632

1633
        See the Python copy module for more information on shallow
1634
        and deep copies, https://docs.python.org/2/library/copy.html.
1635

1636
        Warning: If you have subclassed DiGraph to use dict-like objects
1637
        in the data structure, those changes do not transfer to the
1638
        Graph created by this method.
1639

1640
        Examples
1641
        --------
1642
        >>> G = nx.path_graph(2)   # or MultiGraph, etc
1643
        >>> H = G.to_directed()
1644
        >>> list(H.edges)
1645
        [(0, 1), (1, 0)]
1646
        >>> G2 = H.to_undirected()
1647
        >>> list(G2.edges)
1648
        [(0, 1)]
1649
        """
1650
        graph_class = self.to_undirected_class()
1651
        if as_view is True:
1652
            return nx.graphviews.generic_graph_view(self, graph_class)
1653
        # deepcopy when not a view
1654
        G = graph_class()
1655
        G.graph.update(deepcopy(self.graph))
1656
        G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1657
        G.add_edges_from((u, v, deepcopy(d))
1658
                         for u, nbrs in self._adj.items()
1659
                         for v, d in nbrs.items())
1660
        return G
1661

    
1662
    def subgraph(self, nodes):
1663
        """Returns a SubGraph view of the subgraph induced on `nodes`.
1664

1665
        The induced subgraph of the graph contains the nodes in `nodes`
1666
        and the edges between those nodes.
1667

1668
        Parameters
1669
        ----------
1670
        nodes : list, iterable
1671
            A container of nodes which will be iterated through once.
1672

1673
        Returns
1674
        -------
1675
        G : SubGraph View
1676
            A subgraph view of the graph. The graph structure cannot be
1677
            changed but node/edge attributes can and are shared with the
1678
            original graph.
1679

1680
        Notes
1681
        -----
1682
        The graph, edge and node attributes are shared with the original graph.
1683
        Changes to the graph structure is ruled out by the view, but changes
1684
        to attributes are reflected in the original graph.
1685

1686
        To create a subgraph with its own copy of the edge/node attributes use:
1687
        G.subgraph(nodes).copy()
1688

1689
        For an inplace reduction of a graph to a subgraph you can remove nodes:
1690
        G.remove_nodes_from([n for n in G if n not in set(nodes)])
1691

1692
        Subgraph views are sometimes NOT what you want. In most cases where
1693
        you want to do more than simply look at the induced edges, it makes
1694
        more sense to just create the subgraph as its own graph with code like:
1695

1696
        ::
1697

1698
            # Create a subgraph SG based on a (possibly multigraph) G
1699
            SG = G.__class__()
1700
            SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
1701
            if SG.is_multigraph:
1702
                SG.add_edges_from((n, nbr, key, d)
1703
                    for n, nbrs in G.adj.items() if n in largest_wcc
1704
                    for nbr, keydict in nbrs.items() if nbr in largest_wcc
1705
                    for key, d in keydict.items())
1706
            else:
1707
                SG.add_edges_from((n, nbr, d)
1708
                    for n, nbrs in G.adj.items() if n in largest_wcc
1709
                    for nbr, d in nbrs.items() if nbr in largest_wcc)
1710
            SG.graph.update(G.graph)
1711

1712
        Examples
1713
        --------
1714
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1715
        >>> H = G.subgraph([0, 1, 2])
1716
        >>> list(H.edges)
1717
        [(0, 1), (1, 2)]
1718
        """
1719
        induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes))
1720
        # if already a subgraph, don't make a chain
1721
        subgraph = nx.graphviews.subgraph_view
1722
        if hasattr(self, '_NODE_OK'):
1723
            return subgraph(self._graph, induced_nodes, self._EDGE_OK)
1724
        return subgraph(self, induced_nodes)
1725

    
1726
    def edge_subgraph(self, edges):
1727
        """Returns the subgraph induced by the specified edges.
1728

1729
        The induced subgraph contains each edge in `edges` and each
1730
        node incident to any one of those edges.
1731

1732
        Parameters
1733
        ----------
1734
        edges : iterable
1735
            An iterable of edges in this graph.
1736

1737
        Returns
1738
        -------
1739
        G : Graph
1740
            An edge-induced subgraph of this graph with the same edge
1741
            attributes.
1742

1743
        Notes
1744
        -----
1745
        The graph, edge, and node attributes in the returned subgraph
1746
        view are references to the corresponding attributes in the original
1747
        graph. The view is read-only.
1748

1749
        To create a full graph version of the subgraph with its own copy
1750
        of the edge or node attributes, use::
1751

1752
            >>> G.edge_subgraph(edges).copy()  # doctest: +SKIP
1753

1754
        Examples
1755
        --------
1756
        >>> G = nx.path_graph(5)
1757
        >>> H = G.edge_subgraph([(0, 1), (3, 4)])
1758
        >>> list(H.nodes)
1759
        [0, 1, 3, 4]
1760
        >>> list(H.edges)
1761
        [(0, 1), (3, 4)]
1762

1763
        """
1764
        return nx.edge_subgraph(self, edges)
1765

    
1766
    def size(self, weight=None):
1767
        """Returns the number of edges or total of all edge weights.
1768

1769
        Parameters
1770
        ----------
1771
        weight : string or None, optional (default=None)
1772
            The edge attribute that holds the numerical value used
1773
            as a weight. If None, then each edge has weight 1.
1774

1775
        Returns
1776
        -------
1777
        size : numeric
1778
            The number of edges or
1779
            (if weight keyword is provided) the total weight sum.
1780

1781
            If weight is None, returns an int. Otherwise a float
1782
            (or more general numeric if the weights are more general).
1783

1784
        See Also
1785
        --------
1786
        number_of_edges
1787

1788
        Examples
1789
        --------
1790
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1791
        >>> G.size()
1792
        3
1793

1794
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
1795
        >>> G.add_edge('a', 'b', weight=2)
1796
        >>> G.add_edge('b', 'c', weight=4)
1797
        >>> G.size()
1798
        2
1799
        >>> G.size(weight='weight')
1800
        6.0
1801
        """
1802
        s = sum(d for v, d in self.degree(weight=weight))
1803
        # If `weight` is None, the sum of the degrees is guaranteed to be
1804
        # even, so we can perform integer division and hence return an
1805
        # integer. Otherwise, the sum of the weighted degrees is not
1806
        # guaranteed to be an integer, so we perform "real" division.
1807
        return s // 2 if weight is None else s / 2
1808

    
1809
    def number_of_edges(self, u=None, v=None):
1810
        """Returns the number of edges between two nodes.
1811

1812
        Parameters
1813
        ----------
1814
        u, v : nodes, optional (default=all edges)
1815
            If u and v are specified, return the number of edges between
1816
            u and v. Otherwise return the total number of all edges.
1817

1818
        Returns
1819
        -------
1820
        nedges : int
1821
            The number of edges in the graph.  If nodes `u` and `v` are
1822
            specified return the number of edges between those nodes. If
1823
            the graph is directed, this only returns the number of edges
1824
            from `u` to `v`.
1825

1826
        See Also
1827
        --------
1828
        size
1829

1830
        Examples
1831
        --------
1832
        For undirected graphs, this method counts the total number of
1833
        edges in the graph:
1834

1835
        >>> G = nx.path_graph(4)
1836
        >>> G.number_of_edges()
1837
        3
1838

1839
        If you specify two nodes, this counts the total number of edges
1840
        joining the two nodes:
1841

1842
        >>> G.number_of_edges(0, 1)
1843
        1
1844

1845
        For directed graphs, this method can count the total number of
1846
        directed edges from `u` to `v`:
1847

1848
        >>> G = nx.DiGraph()
1849
        >>> G.add_edge(0, 1)
1850
        >>> G.add_edge(1, 0)
1851
        >>> G.number_of_edges(0, 1)
1852
        1
1853

1854
        """
1855
        if u is None:
1856
            return int(self.size())
1857
        if v in self._adj[u]:
1858
            return 1
1859
        return 0
1860

    
1861
    def nbunch_iter(self, nbunch=None):
1862
        """Returns an iterator over nodes contained in nbunch that are
1863
        also in the graph.
1864

1865
        The nodes in nbunch are checked for membership in the graph
1866
        and if not are silently ignored.
1867

1868
        Parameters
1869
        ----------
1870
        nbunch : single node, container, or all nodes (default= all nodes)
1871
            The view will only report edges incident to these nodes.
1872

1873
        Returns
1874
        -------
1875
        niter : iterator
1876
            An iterator over nodes in nbunch that are also in the graph.
1877
            If nbunch is None, iterate over all nodes in the graph.
1878

1879
        Raises
1880
        ------
1881
        NetworkXError
1882
            If nbunch is not a node or or sequence of nodes.
1883
            If a node in nbunch is not hashable.
1884

1885
        See Also
1886
        --------
1887
        Graph.__iter__
1888

1889
        Notes
1890
        -----
1891
        When nbunch is an iterator, the returned iterator yields values
1892
        directly from nbunch, becoming exhausted when nbunch is exhausted.
1893

1894
        To test whether nbunch is a single node, one can use
1895
        "if nbunch in self:", even after processing with this routine.
1896

1897
        If nbunch is not a node or a (possibly empty) sequence/iterator
1898
        or None, a :exc:`NetworkXError` is raised.  Also, if any object in
1899
        nbunch is not hashable, a :exc:`NetworkXError` is raised.
1900
        """
1901
        if nbunch is None:   # include all nodes via iterator
1902
            bunch = iter(self._adj)
1903
        elif nbunch in self:  # if nbunch is a single node
1904
            bunch = iter([nbunch])
1905
        else:                # if nbunch is a sequence of nodes
1906
            def bunch_iter(nlist, adj):
1907
                try:
1908
                    for n in nlist:
1909
                        if n in adj:
1910
                            yield n
1911
                except TypeError as e:
1912
                    message = e.args[0]
1913
                    # capture error for non-sequence/iterator nbunch.
1914
                    if 'iter' in message:
1915
                        msg = "nbunch is not a node or a sequence of nodes."
1916
                        raise NetworkXError(msg)
1917
                    # capture error for unhashable node.
1918
                    elif 'hashable' in message:
1919
                        msg = "Node {} in sequence nbunch is not a valid node."
1920
                        raise NetworkXError(msg.format(n))
1921
                    else:
1922
                        raise
1923
            bunch = bunch_iter(nbunch, self._adj)
1924
        return bunch