Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (41.6 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 directed graphs."""
12
from copy import deepcopy
13

    
14
import networkx as nx
15
from networkx.classes.graph import Graph
16
from networkx.classes.coreviews import AdjacencyView
17
from networkx.classes.reportviews import OutEdgeView, InEdgeView, \
18
    DiDegreeView, InDegreeView, OutDegreeView
19
from networkx.exception import NetworkXError
20
import networkx.convert as convert
21

    
22

    
23
class DiGraph(Graph):
24
    """
25
    Base class for directed graphs.
26

27
    A DiGraph stores nodes and edges with optional data, or attributes.
28

29
    DiGraphs hold directed edges.  Self loops are allowed but multiple
30
    (parallel) edges are not.
31

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

35
    Edges are represented as links between nodes with optional
36
    key/value attributes.
37

38
    Parameters
39
    ----------
40
    incoming_graph_data : input graph (optional, default: None)
41
        Data to initialize graph. If None (default) an empty
42
        graph is created.  The data can be any format that is supported
43
        by the to_networkx_graph() function, currently including edge list,
44
        dict of dicts, dict of lists, NetworkX graph, NumPy matrix
45
        or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
46

47
    attr : keyword arguments, optional (default= no attributes)
48
        Attributes to add to graph as key=value pairs.
49

50
    See Also
51
    --------
52
    Graph
53
    MultiGraph
54
    MultiDiGraph
55
    OrderedDiGraph
56

57
    Examples
58
    --------
59
    Create an empty graph structure (a "null graph") with no nodes and
60
    no edges.
61

62
    >>> G = nx.DiGraph()
63

64
    G can be grown in several ways.
65

66
    **Nodes:**
67

68
    Add one node at a time:
69

70
    >>> G.add_node(1)
71

72
    Add the nodes from any container (a list, dict, set or
73
    even the lines from a file or the nodes from another graph).
74

75
    >>> G.add_nodes_from([2, 3])
76
    >>> G.add_nodes_from(range(100, 110))
77
    >>> H = nx.path_graph(10)
78
    >>> G.add_nodes_from(H)
79

80
    In addition to strings and integers any hashable Python object
81
    (except None) can represent a node, e.g. a customized node object,
82
    or even another Graph.
83

84
    >>> G.add_node(H)
85

86
    **Edges:**
87

88
    G can also be grown by adding edges.
89

90
    Add one edge,
91

92
    >>> G.add_edge(1, 2)
93

94
    a list of edges,
95

96
    >>> G.add_edges_from([(1, 2), (1, 3)])
97

98
    or a collection of edges,
99

100
    >>> G.add_edges_from(H.edges)
101

102
    If some edges connect nodes not yet in the graph, the nodes
103
    are added automatically.  There are no errors when adding
104
    nodes or edges that already exist.
105

106
    **Attributes:**
107

108
    Each graph, node, and edge can hold key/value attribute pairs
109
    in an associated attribute dictionary (the keys must be hashable).
110
    By default these are empty, but can be added or changed using
111
    add_edge, add_node or direct manipulation of the attribute
112
    dictionaries named graph, node and edge respectively.
113

114
    >>> G = nx.DiGraph(day="Friday")
115
    >>> G.graph
116
    {'day': 'Friday'}
117

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

120
    >>> G.add_node(1, time='5pm')
121
    >>> G.add_nodes_from([3], time='2pm')
122
    >>> G.nodes[1]
123
    {'time': '5pm'}
124
    >>> G.nodes[1]['room'] = 714
125
    >>> del G.nodes[1]['room'] # remove attribute
126
    >>> list(G.nodes(data=True))
127
    [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
128

129
    Add edge attributes using add_edge(), add_edges_from(), subscript
130
    notation, or G.edges.
131

132
    >>> G.add_edge(1, 2, weight=4.7 )
133
    >>> G.add_edges_from([(3, 4), (4, 5)], color='red')
134
    >>> G.add_edges_from([(1, 2, {'color':'blue'}), (2, 3, {'weight':8})])
135
    >>> G[1][2]['weight'] = 4.7
136
    >>> G.edges[1, 2]['weight'] = 4
137

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

144
    **Shortcuts:**
145

146
    Many common graph features allow python syntax to speed reporting.
147

148
    >>> 1 in G     # check if node in graph
149
    True
150
    >>> [n for n in G if n < 3]  # iterate through nodes
151
    [1, 2]
152
    >>> len(G)  # number of nodes in graph
153
    5
154

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

158
    >>> for n, nbrsdict in G.adjacency():
159
    ...     for nbr, eattr in nbrsdict.items():
160
    ...        if 'weight' in eattr:
161
    ...            # Do something useful with the edges
162
    ...            pass
163

164
    But the edges reporting object is often more convenient:
165

166
    >>> for u, v, weight in G.edges(data='weight'):
167
    ...     if weight is not None:
168
    ...         # Do something useful with the edges
169
    ...         pass
170

171
    **Reporting:**
172

173
    Simple graph information is obtained using object-attributes and methods.
174
    Reporting usually provides views instead of containers to reduce memory
175
    usage. The views update as the graph is updated similarly to dict-views.
176
    The objects `nodes, `edges` and `adj` provide access to data attributes
177
    via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration
178
    (e.g. `nodes.items()`, `nodes.data('color')`,
179
    `nodes.data('color', default='blue')` and similarly for `edges`)
180
    Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
181

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

184
    **Subclasses (Advanced):**
185

186
    The Graph class uses a dict-of-dict-of-dict data structure.
187
    The outer dict (node_dict) holds adjacency information keyed by node.
188
    The next dict (adjlist_dict) represents the adjacency information and holds
189
    edge data keyed by neighbor.  The inner dict (edge_attr_dict) represents
190
    the edge data and holds edge attribute values keyed by attribute names.
191

192
    Each of these three dicts can be replaced in a subclass by a user defined
193
    dict-like object. In general, the dict-like features should be
194
    maintained but extra features can be added. To replace one of the
195
    dicts create a new graph class by changing the class(!) variable
196
    holding the factory for that dict-like structure. The variable names are
197
    node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
198
    adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory.
199

200
    node_dict_factory : function, (default: dict)
201
        Factory function to be used to create the dict containing node
202
        attributes, keyed by node id.
203
        It should require no arguments and return a dict-like object
204

205
    node_attr_dict_factory: function, (default: dict)
206
        Factory function to be used to create the node attribute
207
        dict which holds attribute values keyed by attribute name.
208
        It should require no arguments and return a dict-like object
209

210
    adjlist_outer_dict_factory : function, (default: dict)
211
        Factory function to be used to create the outer-most dict
212
        in the data structure that holds adjacency info keyed by node.
213
        It should require no arguments and return a dict-like object.
214

215
    adjlist_inner_dict_factory : function, optional (default: dict)
216
        Factory function to be used to create the adjacency list
217
        dict which holds edge data keyed by neighbor.
218
        It should require no arguments and return a dict-like object
219

220
    edge_attr_dict_factory : function, optional (default: dict)
221
        Factory function to be used to create the edge attribute
222
        dict which holds attribute values keyed by attribute name.
223
        It should require no arguments and return a dict-like object.
224

225
    graph_attr_dict_factory : function, (default: dict)
226
        Factory function to be used to create the graph attribute
227
        dict which holds attribute values keyed by attribute name.
228
        It should require no arguments and return a dict-like object.
229

230
    Typically, if your extension doesn't impact the data structure all
231
    methods will inherited without issue except: `to_directed/to_undirected`.
232
    By default these methods create a DiGraph/Graph class and you probably
233
    want them to create your extension of a DiGraph/Graph. To facilitate
234
    this we define two class variables that you can set in your subclass.
235

236
    to_directed_class : callable, (default: DiGraph or MultiDiGraph)
237
        Class to create a new graph structure in the `to_directed` method.
238
        If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
239

240
    to_undirected_class : callable, (default: Graph or MultiGraph)
241
        Class to create a new graph structure in the `to_undirected` method.
242
        If `None`, a NetworkX class (Graph or MultiGraph) is used.
243

244
    Examples
245
    --------
246

247
    Create a low memory graph class that effectively disallows edge
248
    attributes by using a single attribute dict for all edges.
249
    This reduces the memory used, but you lose edge attributes.
250

251
    >>> class ThinGraph(nx.Graph):
252
    ...     all_edge_dict = {'weight': 1}
253
    ...     def single_edge_dict(self):
254
    ...         return self.all_edge_dict
255
    ...     edge_attr_dict_factory = single_edge_dict
256
    >>> G = ThinGraph()
257
    >>> G.add_edge(2, 1)
258
    >>> G[2][1]
259
    {'weight': 1}
260
    >>> G.add_edge(2, 2)
261
    >>> G[2][1] is G[2][2]
262
    True
263

264

265
    Please see :mod:`~networkx.classes.ordered` for more examples of
266
    creating graph subclasses by overwriting the base class `dict` with
267
    a dictionary-like object.
268
    """
269

    
270
    def __init__(self, incoming_graph_data=None, **attr):
271
        """Initialize a graph with edges, name, or graph attributes.
272

273
        Parameters
274
        ----------
275
        incoming_graph_data : input graph (optional, default: None)
276
            Data to initialize graph.  If None (default) an empty
277
            graph is created.  The data can be an edge list, or any
278
            NetworkX graph object.  If the corresponding optional Python
279
            packages are installed the data can also be a NumPy matrix
280
            or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
281

282
        attr : keyword arguments, optional (default= no attributes)
283
            Attributes to add to graph as key=value pairs.
284

285
        See Also
286
        --------
287
        convert
288

289
        Examples
290
        --------
291
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
292
        >>> G = nx.Graph(name='my graph')
293
        >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
294
        >>> G = nx.Graph(e)
295

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

298
        >>> G = nx.Graph(e, day="Friday")
299
        >>> G.graph
300
        {'day': 'Friday'}
301

302
        """
303
        self.graph_attr_dict_factory = self.graph_attr_dict_factory
304
        self.node_dict_factory = self.node_dict_factory
305
        self.node_attr_dict_factory = self.node_attr_dict_factory
306
        self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory
307
        self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory
308
        self.edge_attr_dict_factory = self.edge_attr_dict_factory
309

    
310
        self.graph = self.graph_attr_dict_factory()  # dictionary for graph attributes
311
        self._node = self.node_dict_factory()  # dictionary for node attr
312
        # We store two adjacency lists:
313
        # the  predecessors of node n are stored in the dict self._pred
314
        # the successors of node n are stored in the dict self._succ=self._adj
315
        self._adj = self.adjlist_outer_dict_factory()  # empty adjacency dict
316
        self._pred = self.adjlist_outer_dict_factory()  # predecessor
317
        self._succ = self._adj  # successor
318

    
319
        # attempt to load graph with data
320
        if incoming_graph_data is not None:
321
            convert.to_networkx_graph(incoming_graph_data, create_using=self)
322
        # load graph attributes (must be after convert)
323
        self.graph.update(attr)
324

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

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

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

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

340
        For directed graphs, `G.adj` holds outgoing (successor) info.
341
        """
342
        return AdjacencyView(self._succ)
343

    
344
    @property
345
    def succ(self):
346
        """Graph adjacency object holding the successors of each node.
347

348
        This object is a read-only dict-like structure with node keys
349
        and neighbor-dict values.  The neighbor-dict is keyed by neighbor
350
        to the edge-data-dict.  So `G.succ[3][2]['color'] = 'blue'` sets
351
        the color of the edge `(3, 2)` to `"blue"`.
352

353
        Iterating over G.succ behaves like a dict. Useful idioms include
354
        `for nbr, datadict in G.succ[n].items():`.  A data-view not provided
355
        by dicts also exists: `for nbr, foovalue in G.succ[node].data('foo'):`
356
        and a default can be set via a `default` argument to the `data` method.
357

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

361
        For directed graphs, `G.adj` is identical to `G.succ`.
362
        """
363
        return AdjacencyView(self._succ)
364

    
365
    @property
366
    def pred(self):
367
        """Graph adjacency object holding the predecessors of each node.
368

369
        This object is a read-only dict-like structure with node keys
370
        and neighbor-dict values.  The neighbor-dict is keyed by neighbor
371
        to the edge-data-dict.  So `G.pred[2][3]['color'] = 'blue'` sets
372
        the color of the edge `(3, 2)` to `"blue"`.
373

374
        Iterating over G.pred behaves like a dict. Useful idioms include
375
        `for nbr, datadict in G.pred[n].items():`.  A data-view not provided
376
        by dicts also exists: `for nbr, foovalue in G.pred[node].data('foo'):`
377
        A default can be set via a `default` argument to the `data` method.
378
        """
379
        return AdjacencyView(self._pred)
380

    
381
    def add_node(self, node_for_adding, **attr):
382
        """Add a single node `node_for_adding` and update node attributes.
383

384
        Parameters
385
        ----------
386
        node_for_adding : node
387
            A node can be any hashable Python object except None.
388
        attr : keyword arguments, optional
389
            Set or change node attributes using key=value.
390

391
        See Also
392
        --------
393
        add_nodes_from
394

395
        Examples
396
        --------
397
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
398
        >>> G.add_node(1)
399
        >>> G.add_node('Hello')
400
        >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
401
        >>> G.add_node(K3)
402
        >>> G.number_of_nodes()
403
        3
404

405
        Use keywords set/change node attributes:
406

407
        >>> G.add_node(1, size=10)
408
        >>> G.add_node(3, weight=0.4, UTM=('13S', 382871, 3972649))
409

410
        Notes
411
        -----
412
        A hashable object is one that can be used as a key in a Python
413
        dictionary. This includes strings, numbers, tuples of strings
414
        and numbers, etc.
415

416
        On many platforms hashable items also include mutables such as
417
        NetworkX Graphs, though one should be careful that the hash
418
        doesn't change on mutables.
419
        """
420
        if node_for_adding not in self._succ:
421
            self._succ[node_for_adding] = self.adjlist_inner_dict_factory()
422
            self._pred[node_for_adding] = self.adjlist_inner_dict_factory()
423
            attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
424
            attr_dict.update(attr)
425
        else:  # update attr even if node already exists
426
            self._node[node_for_adding].update(attr)
427

    
428
    def add_nodes_from(self, nodes_for_adding, **attr):
429
        """Add multiple nodes.
430

431
        Parameters
432
        ----------
433
        nodes_for_adding : iterable container
434
            A container of nodes (list, dict, set, etc.).
435
            OR
436
            A container of (node, attribute dict) tuples.
437
            Node attributes are updated using the attribute dict.
438
        attr : keyword arguments, optional (default= no attributes)
439
            Update attributes for all nodes in nodes.
440
            Node attributes specified in nodes as a tuple take
441
            precedence over attributes specified via keyword arguments.
442

443
        See Also
444
        --------
445
        add_node
446

447
        Examples
448
        --------
449
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
450
        >>> G.add_nodes_from('Hello')
451
        >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
452
        >>> G.add_nodes_from(K3)
453
        >>> sorted(G.nodes(), key=str)
454
        [0, 1, 2, 'H', 'e', 'l', 'o']
455

456
        Use keywords to update specific node attributes for every node.
457

458
        >>> G.add_nodes_from([1, 2], size=10)
459
        >>> G.add_nodes_from([3, 4], weight=0.4)
460

461
        Use (node, attrdict) tuples to update attributes for specific nodes.
462

463
        >>> G.add_nodes_from([(1, dict(size=11)), (2, {'color':'blue'})])
464
        >>> G.nodes[1]['size']
465
        11
466
        >>> H = nx.Graph()
467
        >>> H.add_nodes_from(G.nodes(data=True))
468
        >>> H.nodes[1]['size']
469
        11
470

471
        """
472
        for n in nodes_for_adding:
473
            # keep all this inside try/except because
474
            # CPython throws TypeError on n not in self._succ,
475
            # while pre-2.7.5 ironpython throws on self._succ[n]
476
            try:
477
                if n not in self._succ:
478
                    self._succ[n] = self.adjlist_inner_dict_factory()
479
                    self._pred[n] = self.adjlist_inner_dict_factory()
480
                    attr_dict = self._node[n] = self.node_attr_dict_factory()
481
                    attr_dict.update(attr)
482
                else:
483
                    self._node[n].update(attr)
484
            except TypeError:
485
                nn, ndict = n
486
                if nn not in self._succ:
487
                    self._succ[nn] = self.adjlist_inner_dict_factory()
488
                    self._pred[nn] = self.adjlist_inner_dict_factory()
489
                    newdict = attr.copy()
490
                    newdict.update(ndict)
491
                    attr_dict = self._node[nn] = self.node_attr_dict_factory()
492
                    attr_dict.update(newdict)
493
                else:
494
                    olddict = self._node[nn]
495
                    olddict.update(attr)
496
                    olddict.update(ndict)
497

    
498
    def remove_node(self, n):
499
        """Remove node n.
500

501
        Removes the node n and all adjacent edges.
502
        Attempting to remove a non-existent node will raise an exception.
503

504
        Parameters
505
        ----------
506
        n : node
507
           A node in the graph
508

509
        Raises
510
        -------
511
        NetworkXError
512
           If n is not in the graph.
513

514
        See Also
515
        --------
516
        remove_nodes_from
517

518
        Examples
519
        --------
520
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
521
        >>> list(G.edges)
522
        [(0, 1), (1, 2)]
523
        >>> G.remove_node(1)
524
        >>> list(G.edges)
525
        []
526

527
        """
528
        try:
529
            nbrs = self._succ[n]
530
            del self._node[n]
531
        except KeyError:  # NetworkXError if n not in self
532
            raise NetworkXError("The node %s is not in the digraph." % (n,))
533
        for u in nbrs:
534
            del self._pred[u][n]   # remove all edges n-u in digraph
535
        del self._succ[n]          # remove node from succ
536
        for u in self._pred[n]:
537
            del self._succ[u][n]   # remove all edges n-u in digraph
538
        del self._pred[n]          # remove node from pred
539

    
540
    def remove_nodes_from(self, nodes):
541
        """Remove multiple nodes.
542

543
        Parameters
544
        ----------
545
        nodes : iterable container
546
            A container of nodes (list, dict, set, etc.).  If a node
547
            in the container is not in the graph it is silently ignored.
548

549
        See Also
550
        --------
551
        remove_node
552

553
        Examples
554
        --------
555
        >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
556
        >>> e = list(G.nodes)
557
        >>> e
558
        [0, 1, 2]
559
        >>> G.remove_nodes_from(e)
560
        >>> list(G.nodes)
561
        []
562

563
        """
564
        for n in nodes:
565
            try:
566
                succs = self._succ[n]
567
                del self._node[n]
568
                for u in succs:
569
                    del self._pred[u][n]   # remove all edges n-u in digraph
570
                del self._succ[n]          # now remove node
571
                for u in self._pred[n]:
572
                    del self._succ[u][n]   # remove all edges n-u in digraph
573
                del self._pred[n]          # now remove node
574
            except KeyError:
575
                pass  # silent failure on remove
576

    
577
    def add_edge(self, u_of_edge, v_of_edge, **attr):
578
        """Add an edge between u and v.
579

580
        The nodes u and v will be automatically added if they are
581
        not already in the graph.
582

583
        Edge attributes can be specified with keywords or by directly
584
        accessing the edge's attribute dictionary. See examples below.
585

586
        Parameters
587
        ----------
588
        u, v : nodes
589
            Nodes can be, for example, strings or numbers.
590
            Nodes must be hashable (and not None) Python objects.
591
        attr : keyword arguments, optional
592
            Edge data (or labels or objects) can be assigned using
593
            keyword arguments.
594

595
        See Also
596
        --------
597
        add_edges_from : add a collection of edges
598

599
        Notes
600
        -----
601
        Adding an edge that already exists updates the edge data.
602

603
        Many NetworkX algorithms designed for weighted graphs use
604
        an edge attribute (by default `weight`) to hold a numerical value.
605

606
        Examples
607
        --------
608
        The following all add the edge e=(1, 2) to graph G:
609

610
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
611
        >>> e = (1, 2)
612
        >>> G.add_edge(1, 2)           # explicit two-node form
613
        >>> G.add_edge(*e)             # single edge as tuple of two nodes
614
        >>> G.add_edges_from( [(1, 2)] ) # add edges from iterable container
615

616
        Associate data to edges using keywords:
617

618
        >>> G.add_edge(1, 2, weight=3)
619
        >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
620

621
        For non-string attribute keys, use subscript notation.
622

623
        >>> G.add_edge(1, 2)
624
        >>> G[1][2].update({0: 5})
625
        >>> G.edges[1, 2].update({0: 5})
626
        """
627
        u, v = u_of_edge, v_of_edge
628
        # add nodes
629
        if u not in self._succ:
630
            self._succ[u] = self.adjlist_inner_dict_factory()
631
            self._pred[u] = self.adjlist_inner_dict_factory()
632
            self._node[u] = self.node_attr_dict_factory()
633
        if v not in self._succ:
634
            self._succ[v] = self.adjlist_inner_dict_factory()
635
            self._pred[v] = self.adjlist_inner_dict_factory()
636
            self._node[v] = self.node_attr_dict_factory()
637
        # add the edge
638
        datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
639
        datadict.update(attr)
640
        self._succ[u][v] = datadict
641
        self._pred[v][u] = datadict
642

    
643
    def add_edges_from(self, ebunch_to_add, **attr):
644
        """Add all the edges in ebunch_to_add.
645

646
        Parameters
647
        ----------
648
        ebunch_to_add : container of edges
649
            Each edge given in the container will be added to the
650
            graph. The edges must be given as 2-tuples (u, v) or
651
            3-tuples (u, v, d) where d is a dictionary containing edge data.
652
        attr : keyword arguments, optional
653
            Edge data (or labels or objects) can be assigned using
654
            keyword arguments.
655

656
        See Also
657
        --------
658
        add_edge : add a single edge
659
        add_weighted_edges_from : convenient way to add weighted edges
660

661
        Notes
662
        -----
663
        Adding the same edge twice has no effect but any edge data
664
        will be updated when each duplicate edge is added.
665

666
        Edge attributes specified in an ebunch take precedence over
667
        attributes specified via keyword arguments.
668

669
        Examples
670
        --------
671
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
672
        >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
673
        >>> e = zip(range(0, 3), range(1, 4))
674
        >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
675

676
        Associate data to edges
677

678
        >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
679
        >>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898')
680
        """
681
        for e in ebunch_to_add:
682
            ne = len(e)
683
            if ne == 3:
684
                u, v, dd = e
685
            elif ne == 2:
686
                u, v = e
687
                dd = {}
688
            else:
689
                raise NetworkXError(
690
                    "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))
691
            if u not in self._succ:
692
                self._succ[u] = self.adjlist_inner_dict_factory()
693
                self._pred[u] = self.adjlist_inner_dict_factory()
694
                self._node[u] = self.node_attr_dict_factory()
695
            if v not in self._succ:
696
                self._succ[v] = self.adjlist_inner_dict_factory()
697
                self._pred[v] = self.adjlist_inner_dict_factory()
698
                self._node[v] = self.node_attr_dict_factory()
699
            datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
700
            datadict.update(attr)
701
            datadict.update(dd)
702
            self._succ[u][v] = datadict
703
            self._pred[v][u] = datadict
704

    
705
    def remove_edge(self, u, v):
706
        """Remove the edge between u and v.
707

708
        Parameters
709
        ----------
710
        u, v : nodes
711
            Remove the edge between nodes u and v.
712

713
        Raises
714
        ------
715
        NetworkXError
716
            If there is not an edge between u and v.
717

718
        See Also
719
        --------
720
        remove_edges_from : remove a collection of edges
721

722
        Examples
723
        --------
724
        >>> G = nx.Graph()   # or DiGraph, etc
725
        >>> nx.add_path(G, [0, 1, 2, 3])
726
        >>> G.remove_edge(0, 1)
727
        >>> e = (1, 2)
728
        >>> G.remove_edge(*e) # unpacks e from an edge tuple
729
        >>> e = (2, 3, {'weight':7}) # an edge with attribute data
730
        >>> G.remove_edge(*e[:2]) # select first part of edge tuple
731
        """
732
        try:
733
            del self._succ[u][v]
734
            del self._pred[v][u]
735
        except KeyError:
736
            raise NetworkXError("The edge %s-%s not in graph." % (u, v))
737

    
738
    def remove_edges_from(self, ebunch):
739
        """Remove all edges specified in ebunch.
740

741
        Parameters
742
        ----------
743
        ebunch: list or container of edge tuples
744
            Each edge given in the list or container will be removed
745
            from the graph. The edges can be:
746

747
                - 2-tuples (u, v) edge between u and v.
748
                - 3-tuples (u, v, k) where k is ignored.
749

750
        See Also
751
        --------
752
        remove_edge : remove a single edge
753

754
        Notes
755
        -----
756
        Will fail silently if an edge in ebunch is not in the graph.
757

758
        Examples
759
        --------
760
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
761
        >>> ebunch = [(1, 2), (2, 3)]
762
        >>> G.remove_edges_from(ebunch)
763
        """
764
        for e in ebunch:
765
            u, v = e[:2]  # ignore edge data
766
            if u in self._succ and v in self._succ[u]:
767
                del self._succ[u][v]
768
                del self._pred[v][u]
769

    
770
    def has_successor(self, u, v):
771
        """Returns True if node u has successor v.
772

773
        This is true if graph has the edge u->v.
774
        """
775
        return (u in self._succ and v in self._succ[u])
776

    
777
    def has_predecessor(self, u, v):
778
        """Returns True if node u has predecessor v.
779

780
        This is true if graph has the edge u<-v.
781
        """
782
        return (u in self._pred and v in self._pred[u])
783

    
784
    def successors(self, n):
785
        """Returns an iterator over successor nodes of n.
786

787
        A successor of n is a node m such that there exists a directed
788
        edge from n to m.
789

790
        Parameters
791
        ----------
792
        n : node
793
           A node in the graph
794

795
        Raises
796
        -------
797
        NetworkXError
798
           If n is not in the graph.
799

800
        See Also
801
        --------
802
        predecessors
803

804
        Notes
805
        -----
806
        neighbors() and successors() are the same.
807
        """
808
        try:
809
            return iter(self._succ[n])
810
        except KeyError:
811
            raise NetworkXError("The node %s is not in the digraph." % (n,))
812

    
813
    # digraph definitions
814
    neighbors = successors
815

    
816
    def predecessors(self, n):
817
        """Returns an iterator over predecessor nodes of n.
818

819
        A predecessor of n is a node m such that there exists a directed
820
        edge from m to n.
821

822
        Parameters
823
        ----------
824
        n : node
825
           A node in the graph
826

827
        Raises
828
        -------
829
        NetworkXError
830
           If n is not in the graph.
831

832
        See Also
833
        --------
834
        successors
835
        """
836
        try:
837
            return iter(self._pred[n])
838
        except KeyError:
839
            raise NetworkXError("The node %s is not in the digraph." % (n,))
840

    
841
    @property
842
    def edges(self):
843
        """An OutEdgeView of the DiGraph as G.edges or G.edges().
844

845
        edges(self, nbunch=None, data=False, default=None)
846

847
        The OutEdgeView provides set-like operations on the edge-tuples
848
        as well as edge attribute lookup. When called, it also provides
849
        an EdgeDataView object which allows control of access to edge
850
        attributes (but does not provide set-like operations).
851
        Hence, `G.edges[u, v]['color']` provides the value of the color
852
        attribute for edge `(u, v)` while
853
        `for (u, v, c) in G.edges.data('color', default='red'):`
854
        iterates through all the edges yielding the color attribute
855
        with default `'red'` if no color attribute exists.
856

857
        Parameters
858
        ----------
859
        nbunch : single node, container, or all nodes (default= all nodes)
860
            The view will only report edges incident to these nodes.
861
        data : string or bool, optional (default=False)
862
            The edge attribute returned in 3-tuple (u, v, ddict[data]).
863
            If True, return edge attribute dict in 3-tuple (u, v, ddict).
864
            If False, return 2-tuple (u, v).
865
        default : value, optional (default=None)
866
            Value used for edges that don't have the requested attribute.
867
            Only relevant if data is not True or False.
868

869
        Returns
870
        -------
871
        edges : OutEdgeView
872
            A view of edge attributes, usually it iterates over (u, v)
873
            or (u, v, d) tuples of edges, but can also be used for
874
            attribute lookup as `edges[u, v]['foo']`.
875

876
        See Also
877
        --------
878
        in_edges, out_edges
879

880
        Notes
881
        -----
882
        Nodes in nbunch that are not in the graph will be (quietly) ignored.
883
        For directed graphs this returns the out-edges.
884

885
        Examples
886
        --------
887
        >>> G = nx.DiGraph()   # or MultiDiGraph, etc
888
        >>> nx.add_path(G, [0, 1, 2])
889
        >>> G.add_edge(2, 3, weight=5)
890
        >>> [e for e in G.edges]
891
        [(0, 1), (1, 2), (2, 3)]
892
        >>> G.edges.data()  # default data is {} (empty dict)
893
        OutEdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
894
        >>> G.edges.data('weight', default=1)
895
        OutEdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
896
        >>> G.edges([0, 2])  # only edges incident to these nodes
897
        OutEdgeDataView([(0, 1), (2, 3)])
898
        >>> G.edges(0)  # only edges incident to a single node (use G.adj[0]?)
899
        OutEdgeDataView([(0, 1)])
900

901
        """
902
        return OutEdgeView(self)
903

    
904
    # alias out_edges to edges
905
    out_edges = edges
906

    
907
    @property
908
    def in_edges(self):
909
        """An InEdgeView of the Graph as G.in_edges or G.in_edges().
910

911
        in_edges(self, nbunch=None, data=False, default=None):
912

913
        Parameters
914
        ----------
915
        nbunch : single node, container, or all nodes (default= all nodes)
916
            The view will only report edges incident to these nodes.
917
        data : string or bool, optional (default=False)
918
            The edge attribute returned in 3-tuple (u, v, ddict[data]).
919
            If True, return edge attribute dict in 3-tuple (u, v, ddict).
920
            If False, return 2-tuple (u, v).
921
        default : value, optional (default=None)
922
            Value used for edges that don't have the requested attribute.
923
            Only relevant if data is not True or False.
924

925
        Returns
926
        -------
927
        in_edges : InEdgeView
928
            A view of edge attributes, usually it iterates over (u, v)
929
            or (u, v, d) tuples of edges, but can also be used for
930
            attribute lookup as `edges[u, v]['foo']`.
931

932
        See Also
933
        --------
934
        edges
935
        """
936
        return InEdgeView(self)
937

    
938
    @property
939
    def degree(self):
940
        """A DegreeView for the Graph as G.degree or G.degree().
941

942
        The node degree is the number of edges adjacent to the node.
943
        The weighted node degree is the sum of the edge weights for
944
        edges incident to that node.
945

946
        This object provides an iterator for (node, degree) as well as
947
        lookup for the degree for a single node.
948

949
        Parameters
950
        ----------
951
        nbunch : single node, container, or all nodes (default= all nodes)
952
            The view will only report edges incident to these nodes.
953

954
        weight : string or None, optional (default=None)
955
           The name of an edge attribute that holds the numerical value used
956
           as a weight.  If None, then each edge has weight 1.
957
           The degree is the sum of the edge weights adjacent to the node.
958

959
        Returns
960
        -------
961
        If a single node is requested
962
        deg : int
963
            Degree of the node
964

965
        OR if multiple nodes are requested
966
        nd_iter : iterator
967
            The iterator returns two-tuples of (node, degree).
968

969
        See Also
970
        --------
971
        in_degree, out_degree
972

973
        Examples
974
        --------
975
        >>> G = nx.DiGraph()   # or MultiDiGraph
976
        >>> nx.add_path(G, [0, 1, 2, 3])
977
        >>> G.degree(0) # node 0 with degree 1
978
        1
979
        >>> list(G.degree([0, 1, 2]))
980
        [(0, 1), (1, 2), (2, 2)]
981

982
        """
983
        return DiDegreeView(self)
984

    
985
    @property
986
    def in_degree(self):
987
        """An InDegreeView for (node, in_degree) or in_degree for single node.
988

989
        The node in_degree is the number of edges pointing to the node.
990
        The weighted node degree is the sum of the edge weights for
991
        edges incident to that node.
992

993
        This object provides an iteration over (node, in_degree) as well as
994
        lookup for the degree for a single node.
995

996
        Parameters
997
        ----------
998
        nbunch : single node, container, or all nodes (default= all nodes)
999
            The view will only report edges incident to these nodes.
1000

1001
        weight : string or None, optional (default=None)
1002
           The name of an edge attribute that holds the numerical value used
1003
           as a weight.  If None, then each edge has weight 1.
1004
           The degree is the sum of the edge weights adjacent to the node.
1005

1006
        Returns
1007
        -------
1008
        If a single node is requested
1009
        deg : int
1010
            In-degree of the node
1011

1012
        OR if multiple nodes are requested
1013
        nd_iter : iterator
1014
            The iterator returns two-tuples of (node, in-degree).
1015

1016
        See Also
1017
        --------
1018
        degree, out_degree
1019

1020
        Examples
1021
        --------
1022
        >>> G = nx.DiGraph()
1023
        >>> nx.add_path(G, [0, 1, 2, 3])
1024
        >>> G.in_degree(0) # node 0 with degree 0
1025
        0
1026
        >>> list(G.in_degree([0, 1, 2]))
1027
        [(0, 0), (1, 1), (2, 1)]
1028

1029
        """
1030
        return InDegreeView(self)
1031

    
1032
    @property
1033
    def out_degree(self):
1034
        """An OutDegreeView for (node, out_degree)
1035

1036
        The node out_degree is the number of edges pointing out of the node.
1037
        The weighted node degree is the sum of the edge weights for
1038
        edges incident to that node.
1039

1040
        This object provides an iterator over (node, out_degree) as well as
1041
        lookup for the degree for a single node.
1042

1043
        Parameters
1044
        ----------
1045
        nbunch : single node, container, or all nodes (default= all nodes)
1046
            The view will only report edges incident to these nodes.
1047

1048
        weight : string or None, optional (default=None)
1049
           The name of an edge attribute that holds the numerical value used
1050
           as a weight.  If None, then each edge has weight 1.
1051
           The degree is the sum of the edge weights adjacent to the node.
1052

1053
        Returns
1054
        -------
1055
        If a single node is requested
1056
        deg : int
1057
            Out-degree of the node
1058

1059
        OR if multiple nodes are requested
1060
        nd_iter : iterator
1061
            The iterator returns two-tuples of (node, out-degree).
1062

1063
        See Also
1064
        --------
1065
        degree, in_degree
1066

1067
        Examples
1068
        --------
1069
        >>> G = nx.DiGraph()
1070
        >>> nx.add_path(G, [0, 1, 2, 3])
1071
        >>> G.out_degree(0) # node 0 with degree 1
1072
        1
1073
        >>> list(G.out_degree([0, 1, 2]))
1074
        [(0, 1), (1, 1), (2, 1)]
1075

1076
        """
1077
        return OutDegreeView(self)
1078

    
1079
    def clear(self):
1080
        """Remove all nodes and edges from the graph.
1081

1082
        This also removes the name, and all graph, node, and edge attributes.
1083

1084
        Examples
1085
        --------
1086
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
1087
        >>> G.clear()
1088
        >>> list(G.nodes)
1089
        []
1090
        >>> list(G.edges)
1091
        []
1092
        """
1093
        self._succ.clear()
1094
        self._pred.clear()
1095
        self._node.clear()
1096
        self.graph.clear()
1097

    
1098
    def is_multigraph(self):
1099
        """Returns True if graph is a multigraph, False otherwise."""
1100
        return False
1101

    
1102
    def is_directed(self):
1103
        """Returns True if graph is directed, False otherwise."""
1104
        return True
1105

    
1106
    def to_undirected(self, reciprocal=False, as_view=False):
1107
        """Returns an undirected representation of the digraph.
1108

1109
        Parameters
1110
        ----------
1111
        reciprocal : bool (optional)
1112
          If True only keep edges that appear in both directions
1113
          in the original digraph.
1114
        as_view : bool (optional, default=False)
1115
          If True return an undirected view of the original directed graph.
1116

1117
        Returns
1118
        -------
1119
        G : Graph
1120
            An undirected graph with the same name and nodes and
1121
            with edge (u, v, data) if either (u, v, data) or (v, u, data)
1122
            is in the digraph.  If both edges exist in digraph and
1123
            their edge data is different, only one edge is created
1124
            with an arbitrary choice of which edge data to use.
1125
            You must check and correct for this manually if desired.
1126

1127
        See Also
1128
        --------
1129
        Graph, copy, add_edge, add_edges_from
1130

1131
        Notes
1132
        -----
1133
        If edges in both directions (u, v) and (v, u) exist in the
1134
        graph, attributes for the new undirected edge will be a combination of
1135
        the attributes of the directed edges.  The edge data is updated
1136
        in the (arbitrary) order that the edges are encountered.  For
1137
        more customized control of the edge attributes use add_edge().
1138

1139
        This returns a "deepcopy" of the edge, node, and
1140
        graph attributes which attempts to completely copy
1141
        all of the data and references.
1142

1143
        This is in contrast to the similar G=DiGraph(D) which returns a
1144
        shallow copy of the data.
1145

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

1149
        Warning: If you have subclassed DiGraph to use dict-like objects
1150
        in the data structure, those changes do not transfer to the
1151
        Graph created by this method.
1152

1153
        Examples
1154
        --------
1155
        >>> G = nx.path_graph(2)   # or MultiGraph, etc
1156
        >>> H = G.to_directed()
1157
        >>> list(H.edges)
1158
        [(0, 1), (1, 0)]
1159
        >>> G2 = H.to_undirected()
1160
        >>> list(G2.edges)
1161
        [(0, 1)]
1162
        """
1163
        graph_class = self.to_undirected_class()
1164
        if as_view is True:
1165
            return nx.graphviews.generic_graph_view(self, Graph)
1166
        # deepcopy when not a view
1167
        G = Graph()
1168
        G.graph.update(deepcopy(self.graph))
1169
        G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1170
        if reciprocal is True:
1171
            G.add_edges_from((u, v, deepcopy(d))
1172
                             for u, nbrs in self._adj.items()
1173
                             for v, d in nbrs.items()
1174
                             if v in self._pred[u])
1175
        else:
1176
            G.add_edges_from((u, v, deepcopy(d))
1177
                             for u, nbrs in self._adj.items()
1178
                             for v, d in nbrs.items())
1179
        return G
1180

    
1181
    def reverse(self, copy=True):
1182
        """Returns the reverse of the graph.
1183

1184
        The reverse is a graph with the same nodes and edges
1185
        but with the directions of the edges reversed.
1186

1187
        Parameters
1188
        ----------
1189
        copy : bool optional (default=True)
1190
            If True, return a new DiGraph holding the reversed edges.
1191
            If False, the reverse graph is created using a view of
1192
            the original graph.
1193
        """
1194
        if copy:
1195
            H = self.__class__()
1196
            H.graph.update(deepcopy(self.graph))
1197
            H.add_nodes_from((n, deepcopy(d)) for n, d in self.node.items())
1198
            H.add_edges_from((v, u, deepcopy(d)) for u, v, d
1199
                             in self.edges(data=True))
1200
            return H
1201
        return nx.graphviews.reverse_view(self)