Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (33.2 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
#          Pieter Swart <swart@lanl.gov>
10
#          Dan Schult <dschult@colgate.edu>
11
"""Functional interface to graph methods and assorted utilities.
12
"""
13
from __future__ import division
14

    
15
from collections import Counter
16
from itertools import chain
17
try:
18
    from itertools import zip_longest
19
except ImportError:
20
    from itertools import izip_longest as zip_longest
21

    
22
import networkx as nx
23
from networkx.utils import pairwise, not_implemented_for
24

    
25
__all__ = ['nodes', 'edges', 'degree', 'degree_histogram', 'neighbors',
26
           'number_of_nodes', 'number_of_edges', 'density',
27
           'is_directed', 'info', 'freeze', 'is_frozen', 'subgraph',
28
           'induced_subgraph', 'edge_subgraph', 'restricted_view',
29
           'reverse_view', 'to_directed', 'to_undirected',
30
           'add_star', 'add_path', 'add_cycle',
31
           'create_empty_copy', 'set_node_attributes',
32
           'get_node_attributes', 'set_edge_attributes',
33
           'get_edge_attributes', 'all_neighbors', 'non_neighbors',
34
           'non_edges', 'common_neighbors', 'is_weighted',
35
           'is_negatively_weighted', 'is_empty',
36
           'selfloop_edges', 'nodes_with_selfloops', 'number_of_selfloops',
37
           ]
38

    
39

    
40
def nodes(G):
41
    """Returns an iterator over the graph nodes."""
42
    return G.nodes()
43

    
44

    
45
def edges(G, nbunch=None):
46
    """Returns an edge view of edges incident to nodes in nbunch.
47

48
    Return all edges if nbunch is unspecified or nbunch=None.
49

50
    For digraphs, edges=out_edges
51
    """
52
    return G.edges(nbunch)
53

    
54

    
55
def degree(G, nbunch=None, weight=None):
56
    """Returns a degree view of single node or of nbunch of nodes.
57
    If nbunch is omitted, then return degrees of *all* nodes.
58
    """
59
    return G.degree(nbunch, weight)
60

    
61

    
62
def neighbors(G, n):
63
    """Returns a list of nodes connected to node n. """
64
    return G.neighbors(n)
65

    
66

    
67
def number_of_nodes(G):
68
    """Returns the number of nodes in the graph."""
69
    return G.number_of_nodes()
70

    
71

    
72
def number_of_edges(G):
73
    """Returns the number of edges in the graph. """
74
    return G.number_of_edges()
75

    
76

    
77
def density(G):
78
    r"""Returns the density of a graph.
79

80
    The density for undirected graphs is
81

82
    .. math::
83

84
       d = \frac{2m}{n(n-1)},
85

86
    and for directed graphs is
87

88
    .. math::
89

90
       d = \frac{m}{n(n-1)},
91

92
    where `n` is the number of nodes and `m`  is the number of edges in `G`.
93

94
    Notes
95
    -----
96
    The density is 0 for a graph without edges and 1 for a complete graph.
97
    The density of multigraphs can be higher than 1.
98

99
    Self loops are counted in the total number of edges so graphs with self
100
    loops can have density higher than 1.
101
    """
102
    n = number_of_nodes(G)
103
    m = number_of_edges(G)
104
    if m == 0 or n <= 1:
105
        return 0
106
    d = m / (n * (n - 1))
107
    if not G.is_directed():
108
        d *= 2
109
    return d
110

    
111

    
112
def degree_histogram(G):
113
    """Returns a list of the frequency of each degree value.
114

115
    Parameters
116
    ----------
117
    G : Networkx graph
118
       A graph
119

120
    Returns
121
    -------
122
    hist : list
123
       A list of frequencies of degrees.
124
       The degree values are the index in the list.
125

126
    Notes
127
    -----
128
    Note: the bins are width one, hence len(list) can be large
129
    (Order(number_of_edges))
130
    """
131
    counts = Counter(d for n, d in G.degree())
132
    return [counts.get(i, 0) for i in range(max(counts) + 1)]
133

    
134

    
135
def is_directed(G):
136
    """ Return True if graph is directed."""
137
    return G.is_directed()
138

    
139

    
140
def frozen(*args, **kwargs):
141
    """Dummy method for raising errors when trying to modify frozen graphs"""
142
    raise nx.NetworkXError("Frozen graph can't be modified")
143

    
144

    
145
def freeze(G):
146
    """Modify graph to prevent further change by adding or removing
147
    nodes or edges.
148

149
    Node and edge data can still be modified.
150

151
    Parameters
152
    ----------
153
    G : graph
154
      A NetworkX graph
155

156
    Examples
157
    --------
158
    >>> G = nx.path_graph(4)
159
    >>> G = nx.freeze(G)
160
    >>> try:
161
    ...    G.add_edge(4, 5)
162
    ... except nx.NetworkXError as e:
163
    ...    print(str(e))
164
    Frozen graph can't be modified
165

166
    Notes
167
    -----
168
    To "unfreeze" a graph you must make a copy by creating a new graph object:
169

170
    >>> graph = nx.path_graph(4)
171
    >>> frozen_graph = nx.freeze(graph)
172
    >>> unfrozen_graph = nx.Graph(frozen_graph)
173
    >>> nx.is_frozen(unfrozen_graph)
174
    False
175

176
    See Also
177
    --------
178
    is_frozen
179
    """
180
    G.add_node = frozen
181
    G.add_nodes_from = frozen
182
    G.remove_node = frozen
183
    G.remove_nodes_from = frozen
184
    G.add_edge = frozen
185
    G.add_edges_from = frozen
186
    G.add_weighted_edges_from = frozen
187
    G.remove_edge = frozen
188
    G.remove_edges_from = frozen
189
    G.clear = frozen
190
    G.frozen = True
191
    return G
192

    
193

    
194
def is_frozen(G):
195
    """Returns True if graph is frozen.
196

197
    Parameters
198
    ----------
199
    G : graph
200
      A NetworkX graph
201

202
    See Also
203
    --------
204
    freeze
205
    """
206
    try:
207
        return G.frozen
208
    except AttributeError:
209
        return False
210

    
211

    
212
def add_star(G_to_add_to, nodes_for_star, **attr):
213
    """Add a star to Graph G_to_add_to.
214

215
    The first node in `nodes_for_star` is the middle of the star.
216
    It is connected to all other nodes.
217

218
    Parameters
219
    ----------
220
    G_to_add_to : graph
221
        A NetworkX graph
222
    nodes_for_star : iterable container
223
        A container of nodes.
224
    attr : keyword arguments, optional (default= no attributes)
225
        Attributes to add to every edge in star.
226

227
    See Also
228
    --------
229
    add_path, add_cycle
230

231
    Examples
232
    --------
233
    >>> G = nx.Graph()
234
    >>> nx.add_star(G, [0, 1, 2, 3])
235
    >>> nx.add_star(G, [10, 11, 12], weight=2)
236
    """
237
    nlist = iter(nodes_for_star)
238
    try:
239
        v = next(nlist)
240
    except StopIteration:
241
        return
242
    G_to_add_to.add_node(v)
243
    edges = ((v, n) for n in nlist)
244
    G_to_add_to.add_edges_from(edges, **attr)
245

    
246

    
247
def add_path(G_to_add_to, nodes_for_path, **attr):
248
    """Add a path to the Graph G_to_add_to.
249

250
    Parameters
251
    ----------
252
    G_to_add_to : graph
253
        A NetworkX graph
254
    nodes_for_path : iterable container
255
        A container of nodes.  A path will be constructed from
256
        the nodes (in order) and added to the graph.
257
    attr : keyword arguments, optional (default= no attributes)
258
        Attributes to add to every edge in path.
259

260
    See Also
261
    --------
262
    add_star, add_cycle
263

264
    Examples
265
    --------
266
    >>> G = nx.Graph()
267
    >>> nx.add_path(G, [0, 1, 2, 3])
268
    >>> nx.add_path(G, [10, 11, 12], weight=7)
269
    """
270
    nlist = iter(nodes_for_path)
271
    try:
272
        first_node = next(nlist)
273
    except StopIteration:
274
        return
275
    G_to_add_to.add_node(first_node)
276
    G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist)), **attr)
277

    
278

    
279
def add_cycle(G_to_add_to, nodes_for_cycle, **attr):
280
    """Add a cycle to the Graph G_to_add_to.
281

282
    Parameters
283
    ----------
284
    G_to_add_to : graph
285
        A NetworkX graph
286
    nodes_for_cycle: iterable container
287
        A container of nodes.  A cycle will be constructed from
288
        the nodes (in order) and added to the graph.
289
    attr : keyword arguments, optional (default= no attributes)
290
        Attributes to add to every edge in cycle.
291

292
    See Also
293
    --------
294
    add_path, add_star
295

296
    Examples
297
    --------
298
    >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
299
    >>> nx.add_cycle(G, [0, 1, 2, 3])
300
    >>> nx.add_cycle(G, [10, 11, 12], weight=7)
301
    """
302
    nlist = iter(nodes_for_cycle)
303
    try:
304
        first_node = next(nlist)
305
    except StopIteration:
306
        return
307
    G_to_add_to.add_node(first_node)
308
    G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist), cyclic=True), **attr)
309

    
310

    
311
def subgraph(G, nbunch):
312
    """Returns the subgraph induced on nodes in nbunch.
313

314
    Parameters
315
    ----------
316
    G : graph
317
       A NetworkX graph
318

319
    nbunch : list, iterable
320
       A container of nodes that will be iterated through once (thus
321
       it should be an iterator or be iterable).  Each element of the
322
       container should be a valid node type: any hashable type except
323
       None.  If nbunch is None, return all edges data in the graph.
324
       Nodes in nbunch that are not in the graph will be (quietly)
325
       ignored.
326

327
    Notes
328
    -----
329
    subgraph(G) calls G.subgraph()
330
    """
331
    return G.subgraph(nbunch)
332

    
333

    
334
def induced_subgraph(G, nbunch):
335
    """Returns a SubGraph view of `G` showing only nodes in nbunch.
336

337
    The induced subgraph of a graph on a set of nodes N is the
338
    graph with nodes N and edges from G which have both ends in N.
339

340
    Parameters
341
    ----------
342
    G : NetworkX Graph
343
    nbunch : node, container of nodes or None (for all nodes)
344

345
    Returns
346
    -------
347
    subgraph : SubGraph View
348
        A read-only view of the subgraph in `G` induced by the nodes.
349
        Changes to the graph `G` will be reflected in the view.
350

351
    Notes
352
    -----
353
    To create a mutable subgraph with its own copies of nodes
354
    edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
355

356
    For an inplace reduction of a graph to a subgraph you can remove nodes:
357
    `G.remove_nodes_from(n in G if n not in set(nbunch))`
358

359
    If you are going to compute subgraphs of your subgraphs you could
360
    end up with a chain of views that can be very slow once the chain
361
    has about 15 views in it. If they are all induced subgraphs, you
362
    can short-cut the chain by making them all subgraphs of the original
363
    graph. The graph class method `G.subgraph` does this when `G` is
364
    a subgraph. In contrast, this function allows you to choose to build
365
    chains or not, as you wish. The returned subgraph is a view on `G`.
366

367
    Examples
368
    --------
369
    >>> import networkx as nx
370
    >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
371
    >>> H = G.subgraph([0, 1, 2])
372
    >>> list(H.edges)
373
    [(0, 1), (1, 2)]
374
    """
375
    induced_nodes = nx.filters.show_nodes(G.nbunch_iter(nbunch))
376
    return nx.graphviews.subgraph_view(G, induced_nodes)
377

    
378

    
379
def edge_subgraph(G, edges):
380
    """Returns a view of the subgraph induced by the specified edges.
381

382
    The induced subgraph contains each edge in `edges` and each
383
    node incident to any of those edges.
384

385
    Parameters
386
    ----------
387
    G : NetworkX Graph
388
    edges : iterable
389
        An iterable of edges. Edges not present in `G` are ignored.
390

391
    Returns
392
    -------
393
    subgraph : SubGraph View
394
        A read-only edge-induced subgraph of `G`.
395
        Changes to `G` are reflected in the view.
396

397
    Notes
398
    -----
399
    To create a mutable subgraph with its own copies of nodes
400
    edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
401

402
    If you create a subgraph of a subgraph recursively you can end up
403
    with a chain of subgraphs that becomes very slow with about 15
404
    nested subgraph views. Luckily the edge_subgraph filter nests
405
    nicely so you can use the original graph as G in this function
406
    to avoid chains. We do not rule out chains programmatically so
407
    that odd cases like an `edge_subgraph` of a `restricted_view`
408
    can be created.
409

410
    Examples
411
    --------
412
    >>> import networkx as nx
413
    >>> G = nx.path_graph(5)
414
    >>> H = G.edge_subgraph([(0, 1), (3, 4)])
415
    >>> list(H.nodes)
416
    [0, 1, 3, 4]
417
    >>> list(H.edges)
418
    [(0, 1), (3, 4)]
419
    """
420
    nxf = nx.filters
421
    edges = set(edges)
422
    nodes = set()
423
    for e in edges:
424
        nodes.update(e[:2])
425
    induced_nodes = nxf.show_nodes(nodes)
426
    if G.is_multigraph():
427
        if G.is_directed():
428
            induced_edges = nxf.show_multidiedges(edges)
429
        else:
430
            induced_edges = nxf.show_multiedges(edges)
431
    else:
432
        if G.is_directed():
433
            induced_edges = nxf.show_diedges(edges)
434
        else:
435
            induced_edges = nxf.show_edges(edges)
436
    return nx.graphviews.subgraph_view(G, induced_nodes, induced_edges)
437

    
438

    
439
def restricted_view(G, nodes, edges):
440
    """Returns a view of `G` with hidden nodes and edges.
441

442
    The resulting subgraph filters out node `nodes` and edges `edges`.
443
    Filtered out nodes also filter out any of their edges.
444

445
    Parameters
446
    ----------
447
    G : NetworkX Graph
448
    nodes : iterable
449
        An iterable of nodes. Nodes not present in `G` are ignored.
450
    edges : iterable
451
        An iterable of edges. Edges not present in `G` are ignored.
452

453
    Returns
454
    -------
455
    subgraph : SubGraph View
456
        A read-only restricted view of `G` filtering out nodes and edges.
457
        Changes to `G` are reflected in the view.
458

459
    Notes
460
    -----
461
    To create a mutable subgraph with its own copies of nodes
462
    edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
463

464
    If you create a subgraph of a subgraph recursively you may end up
465
    with a chain of subgraph views. Such chains can get quite slow
466
    for lengths near 15. To avoid long chains, try to make your subgraph
467
    based on the original graph.  We do not rule out chains programmatically
468
    so that odd cases like an `edge_subgraph` of a `restricted_view`
469
    can be created.
470

471
    Examples
472
    --------
473
    >>> import networkx as nx
474
    >>> G = nx.path_graph(5)
475
    >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)])
476
    >>> list(H.nodes)
477
    [1, 2, 3, 4]
478
    >>> list(H.edges)
479
    [(2, 3)]
480
    """
481
    nxf = nx.filters
482
    hide_nodes = nxf.hide_nodes(nodes)
483
    if G.is_multigraph():
484
        if G.is_directed():
485
            hide_edges = nxf.hide_multidiedges(edges)
486
        else:
487
            hide_edges = nxf.hide_multiedges(edges)
488
    else:
489
        if G.is_directed():
490
            hide_edges = nxf.hide_diedges(edges)
491
        else:
492
            hide_edges = nxf.hide_edges(edges)
493
    return nx.graphviews.subgraph_view(G, hide_nodes, hide_edges)
494

    
495

    
496
@not_implemented_for('undirected')
497
def reverse_view(digraph):
498
    """Provide a reverse view of the digraph with edges reversed.
499

500
    Identical to digraph.reverse(copy=False)
501
    """
502
    return nx.graphviews.reverse_view(digraph)
503

    
504

    
505
def to_directed(graph):
506
    """Returns a directed view of the graph `graph`.
507

508
    Identical to graph.to_directed(as_view=True)
509
    Note that graph.to_directed defaults to `as_view=False`
510
    while this function always provides a view.
511
    """
512
    return graph.to_directed()
513

    
514

    
515
def to_undirected(graph):
516
    """Returns an undirected view of the graph `graph`.
517

518
    Identical to graph.to_undirected(as_view=True)
519
    Note that graph.to_undirected defaults to `as_view=False`
520
    while this function always provides a view.
521
    """
522
    return graph.to_undirected(as_view=True)
523

    
524

    
525
def create_empty_copy(G, with_data=True):
526
    """Returns a copy of the graph G with all of the edges removed.
527

528
    Parameters
529
    ----------
530
    G : graph
531
       A NetworkX graph
532

533
    with_data :  bool (default=True)
534
       Propagate Graph and Nodes data to the new graph.
535

536
    See Also
537
    -----
538
    empty_graph
539

540
    """
541
    H = G.__class__()
542
    H.add_nodes_from(G.nodes(data=with_data))
543
    if with_data:
544
        H.graph.update(G.graph)
545
    return H
546

    
547

    
548
def info(G, n=None):
549
    """Print short summary of information for the graph G or the node n.
550

551
    Parameters
552
    ----------
553
    G : Networkx graph
554
       A graph
555
    n : node (any hashable)
556
       A node in the graph G
557
    """
558
    info = ''  # append this all to a string
559
    if n is None:
560
        info += "Name: %s\n" % G.name
561
        type_name = [type(G).__name__]
562
        info += "Type: %s\n" % ",".join(type_name)
563
        info += "Number of nodes: %d\n" % G.number_of_nodes()
564
        info += "Number of edges: %d\n" % G.number_of_edges()
565
        nnodes = G.number_of_nodes()
566
        if len(G) > 0:
567
            if G.is_directed():
568
                deg = sum(d for n, d in G.in_degree()) / float(nnodes)
569
                info += "Average in degree: %8.4f\n" % deg
570
                deg = sum(d for n, d in G.out_degree()) / float(nnodes)
571
                info += "Average out degree: %8.4f" % deg
572
            else:
573
                s = sum(dict(G.degree()).values())
574
                info += "Average degree: %8.4f" % (float(s) / float(nnodes))
575

    
576
    else:
577
        if n not in G:
578
            raise nx.NetworkXError("node %s not in graph" % (n,))
579
        info += "Node % s has the following properties:\n" % n
580
        info += "Degree: %d\n" % G.degree(n)
581
        info += "Neighbors: "
582
        info += ' '.join(str(nbr) for nbr in G.neighbors(n))
583
    return info
584

    
585

    
586
def set_node_attributes(G, values, name=None):
587
    """Sets node attributes from a given value or dictionary of values.
588

589
    .. Warning:: The call order of arguments `values` and `name`
590
        switched between v1.x & v2.x.
591

592
    Parameters
593
    ----------
594
    G : NetworkX Graph
595

596
    values : scalar value, dict-like
597
        What the node attribute should be set to.  If `values` is
598
        not a dictionary, then it is treated as a single attribute value
599
        that is then applied to every node in `G`.  This means that if
600
        you provide a mutable object, like a list, updates to that object
601
        will be reflected in the node attribute for every node.
602
        The attribute name will be `name`.
603

604
        If `values` is a dict or a dict of dict, it should be keyed
605
        by node to either an attribute value or a dict of attribute key/value
606
        pairs used to update the node's attributes.
607

608
    name : string (optional, default=None)
609
        Name of the node attribute to set if values is a scalar.
610

611
    Examples
612
    --------
613
    After computing some property of the nodes of a graph, you may want
614
    to assign a node attribute to store the value of that property for
615
    each node::
616

617
        >>> G = nx.path_graph(3)
618
        >>> bb = nx.betweenness_centrality(G)
619
        >>> isinstance(bb, dict)
620
        True
621
        >>> nx.set_node_attributes(G, bb, 'betweenness')
622
        >>> G.nodes[1]['betweenness']
623
        1.0
624

625
    If you provide a list as the second argument, updates to the list
626
    will be reflected in the node attribute for each node::
627

628
        >>> G = nx.path_graph(3)
629
        >>> labels = []
630
        >>> nx.set_node_attributes(G, labels, 'labels')
631
        >>> labels.append('foo')
632
        >>> G.nodes[0]['labels']
633
        ['foo']
634
        >>> G.nodes[1]['labels']
635
        ['foo']
636
        >>> G.nodes[2]['labels']
637
        ['foo']
638

639
    If you provide a dictionary of dictionaries as the second argument,
640
    the outer dictionary is assumed to be keyed by node to an inner
641
    dictionary of node attributes for that node::
642

643
        >>> G = nx.path_graph(3)
644
        >>> attrs = {0: {'attr1': 20, 'attr2': 'nothing'}, 1: {'attr2': 3}}
645
        >>> nx.set_node_attributes(G, attrs)
646
        >>> G.nodes[0]['attr1']
647
        20
648
        >>> G.nodes[0]['attr2']
649
        'nothing'
650
        >>> G.nodes[1]['attr2']
651
        3
652
        >>> G.nodes[2]
653
        {}
654

655
    """
656
    # Set node attributes based on type of `values`
657
    if name is not None:  # `values` must not be a dict of dict
658
        try:  # `values` is a dict
659
            for n, v in values.items():
660
                try:
661
                    G.nodes[n][name] = values[n]
662
                except KeyError:
663
                    pass
664
        except AttributeError:  # `values` is a constant
665
            for n in G:
666
                G.nodes[n][name] = values
667
    else:  # `values` must be dict of dict
668
        for n, d in values.items():
669
            try:
670
                G.nodes[n].update(d)
671
            except KeyError:
672
                pass
673

    
674

    
675
def get_node_attributes(G, name):
676
    """Get node attributes from graph
677

678
    Parameters
679
    ----------
680
    G : NetworkX Graph
681

682
    name : string
683
       Attribute name
684

685
    Returns
686
    -------
687
    Dictionary of attributes keyed by node.
688

689
    Examples
690
    --------
691
    >>> G = nx.Graph()
692
    >>> G.add_nodes_from([1, 2, 3], color='red')
693
    >>> color = nx.get_node_attributes(G, 'color')
694
    >>> color[1]
695
    'red'
696
    """
697
    return {n: d[name] for n, d in G.nodes.items() if name in d}
698

    
699

    
700
def set_edge_attributes(G, values, name=None):
701
    """Sets edge attributes from a given value or dictionary of values.
702

703
    .. Warning:: The call order of arguments `values` and `name`
704
        switched between v1.x & v2.x.
705

706
    Parameters
707
    ----------
708
    G : NetworkX Graph
709

710
    values : scalar value, dict-like
711
        What the edge attribute should be set to.  If `values` is
712
        not a dictionary, then it is treated as a single attribute value
713
        that is then applied to every edge in `G`.  This means that if
714
        you provide a mutable object, like a list, updates to that object
715
        will be reflected in the edge attribute for each edge.  The attribute
716
        name will be `name`.
717

718
        If `values` is a dict or a dict of dict, it should be keyed
719
        by edge tuple to either an attribute value or a dict of attribute
720
        key/value pairs used to update the edge's attributes.
721
        For multigraphs, the edge tuples must be of the form ``(u, v, key)``,
722
        where `u` and `v` are nodes and `key` is the edge key.
723
        For non-multigraphs, the keys must be tuples of the form ``(u, v)``.
724

725
    name : string (optional, default=None)
726
        Name of the edge attribute to set if values is a scalar.
727

728
    Examples
729
    --------
730
    After computing some property of the edges of a graph, you may want
731
    to assign a edge attribute to store the value of that property for
732
    each edge::
733

734
        >>> G = nx.path_graph(3)
735
        >>> bb = nx.edge_betweenness_centrality(G, normalized=False)
736
        >>> nx.set_edge_attributes(G, bb, 'betweenness')
737
        >>> G.edges[1, 2]['betweenness']
738
        2.0
739

740
    If you provide a list as the second argument, updates to the list
741
    will be reflected in the edge attribute for each edge::
742

743
        >>> labels = []
744
        >>> nx.set_edge_attributes(G, labels, 'labels')
745
        >>> labels.append('foo')
746
        >>> G.edges[0, 1]['labels']
747
        ['foo']
748
        >>> G.edges[1, 2]['labels']
749
        ['foo']
750

751
    If you provide a dictionary of dictionaries as the second argument,
752
    the entire dictionary will be used to update edge attributes::
753

754
        >>> G = nx.path_graph(3)
755
        >>> attrs = {(0, 1): {'attr1': 20, 'attr2': 'nothing'},
756
        ...          (1, 2): {'attr2': 3}}
757
        >>> nx.set_edge_attributes(G, attrs)
758
        >>> G[0][1]['attr1']
759
        20
760
        >>> G[0][1]['attr2']
761
        'nothing'
762
        >>> G[1][2]['attr2']
763
        3
764

765
    """
766
    if name is not None:
767
        # `values` does not contain attribute names
768
        try:
769
            # if `values` is a dict using `.items()` => {edge: value}
770
            if G.is_multigraph():
771
                for (u, v, key), value in values.items():
772
                    try:
773
                        G[u][v][key][name] = value
774
                    except KeyError:
775
                        pass
776
            else:
777
                for (u, v), value in values.items():
778
                    try:
779
                        G[u][v][name] = value
780
                    except KeyError:
781
                        pass
782
        except AttributeError:
783
            # treat `values` as a constant
784
            for u, v, data in G.edges(data=True):
785
                data[name] = values
786
    else:
787
        # `values` consists of doct-of-dict {edge: {attr: value}} shape
788
        if G.is_multigraph():
789
            for (u, v, key), d in values.items():
790
                try:
791
                    G[u][v][key].update(d)
792
                except KeyError:
793
                    pass
794
        else:
795
            for (u, v), d in values.items():
796
                try:
797
                    G[u][v].update(d)
798
                except KeyError:
799
                    pass
800

    
801

    
802
def get_edge_attributes(G, name):
803
    """Get edge attributes from graph
804

805
    Parameters
806
    ----------
807
    G : NetworkX Graph
808

809
    name : string
810
       Attribute name
811

812
    Returns
813
    -------
814
    Dictionary of attributes keyed by edge. For (di)graphs, the keys are
815
    2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of
816
    the form: (u, v, key).
817

818
    Examples
819
    --------
820
    >>> G = nx.Graph()
821
    >>> nx.add_path(G, [1, 2, 3], color='red')
822
    >>> color = nx.get_edge_attributes(G, 'color')
823
    >>> color[(1, 2)]
824
    'red'
825
    """
826
    if G.is_multigraph():
827
        edges = G.edges(keys=True, data=True)
828
    else:
829
        edges = G.edges(data=True)
830
    return {x[:-1]: x[-1][name] for x in edges if name in x[-1]}
831

    
832

    
833
def all_neighbors(graph, node):
834
    """Returns all of the neighbors of a node in the graph.
835

836
    If the graph is directed returns predecessors as well as successors.
837

838
    Parameters
839
    ----------
840
    graph : NetworkX graph
841
        Graph to find neighbors.
842

843
    node : node
844
        The node whose neighbors will be returned.
845

846
    Returns
847
    -------
848
    neighbors : iterator
849
        Iterator of neighbors
850
    """
851
    if graph.is_directed():
852
        values = chain(graph.predecessors(node), graph.successors(node))
853
    else:
854
        values = graph.neighbors(node)
855
    return values
856

    
857

    
858
def non_neighbors(graph, node):
859
    """Returns the non-neighbors of the node in the graph.
860

861
    Parameters
862
    ----------
863
    graph : NetworkX graph
864
        Graph to find neighbors.
865

866
    node : node
867
        The node whose neighbors will be returned.
868

869
    Returns
870
    -------
871
    non_neighbors : iterator
872
        Iterator of nodes in the graph that are not neighbors of the node.
873
    """
874
    nbors = set(neighbors(graph, node)) | {node}
875
    return (nnode for nnode in graph if nnode not in nbors)
876

    
877

    
878
def non_edges(graph):
879
    """Returns the non-existent edges in the graph.
880

881
    Parameters
882
    ----------
883
    graph : NetworkX graph.
884
        Graph to find non-existent edges.
885

886
    Returns
887
    -------
888
    non_edges : iterator
889
        Iterator of edges that are not in the graph.
890
    """
891
    if graph.is_directed():
892
        for u in graph:
893
            for v in non_neighbors(graph, u):
894
                yield (u, v)
895
    else:
896
        nodes = set(graph)
897
        while nodes:
898
            u = nodes.pop()
899
            for v in nodes - set(graph[u]):
900
                yield (u, v)
901

    
902

    
903
@not_implemented_for('directed')
904
def common_neighbors(G, u, v):
905
    """Returns the common neighbors of two nodes in a graph.
906

907
    Parameters
908
    ----------
909
    G : graph
910
        A NetworkX undirected graph.
911

912
    u, v : nodes
913
        Nodes in the graph.
914

915
    Returns
916
    -------
917
    cnbors : iterator
918
        Iterator of common neighbors of u and v in the graph.
919

920
    Raises
921
    ------
922
    NetworkXError
923
        If u or v is not a node in the graph.
924

925
    Examples
926
    --------
927
    >>> G = nx.complete_graph(5)
928
    >>> sorted(nx.common_neighbors(G, 0, 1))
929
    [2, 3, 4]
930
    """
931
    if u not in G:
932
        raise nx.NetworkXError('u is not in the graph.')
933
    if v not in G:
934
        raise nx.NetworkXError('v is not in the graph.')
935

    
936
    # Return a generator explicitly instead of yielding so that the above
937
    # checks are executed eagerly.
938
    return (w for w in G[u] if w in G[v] and w not in (u, v))
939

    
940

    
941
def is_weighted(G, edge=None, weight='weight'):
942
    """Returns True if `G` has weighted edges.
943

944
    Parameters
945
    ----------
946
    G : graph
947
        A NetworkX graph.
948

949
    edge : tuple, optional
950
        A 2-tuple specifying the only edge in `G` that will be tested. If
951
        None, then every edge in `G` is tested.
952

953
    weight: string, optional
954
        The attribute name used to query for edge weights.
955

956
    Returns
957
    -------
958
    bool
959
        A boolean signifying if `G`, or the specified edge, is weighted.
960

961
    Raises
962
    ------
963
    NetworkXError
964
        If the specified edge does not exist.
965

966
    Examples
967
    --------
968
    >>> G = nx.path_graph(4)
969
    >>> nx.is_weighted(G)
970
    False
971
    >>> nx.is_weighted(G, (2, 3))
972
    False
973

974
    >>> G = nx.DiGraph()
975
    >>> G.add_edge(1, 2, weight=1)
976
    >>> nx.is_weighted(G)
977
    True
978

979
    """
980
    if edge is not None:
981
        data = G.get_edge_data(*edge)
982
        if data is None:
983
            msg = 'Edge {!r} does not exist.'.format(edge)
984
            raise nx.NetworkXError(msg)
985
        return weight in data
986

    
987
    if is_empty(G):
988
        # Special handling required since: all([]) == True
989
        return False
990

    
991
    return all(weight in data for u, v, data in G.edges(data=True))
992

    
993

    
994
def is_negatively_weighted(G, edge=None, weight='weight'):
995
    """Returns True if `G` has negatively weighted edges.
996

997
    Parameters
998
    ----------
999
    G : graph
1000
        A NetworkX graph.
1001

1002
    edge : tuple, optional
1003
        A 2-tuple specifying the only edge in `G` that will be tested. If
1004
        None, then every edge in `G` is tested.
1005

1006
    weight: string, optional
1007
        The attribute name used to query for edge weights.
1008

1009
    Returns
1010
    -------
1011
    bool
1012
        A boolean signifying if `G`, or the specified edge, is negatively
1013
        weighted.
1014

1015
    Raises
1016
    ------
1017
    NetworkXError
1018
        If the specified edge does not exist.
1019

1020
    Examples
1021
    --------
1022
    >>> G = nx.Graph()
1023
    >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)])
1024
    >>> G.add_edge(1, 2, weight=4)
1025
    >>> nx.is_negatively_weighted(G, (1, 2))
1026
    False
1027
    >>> G[2][4]['weight'] = -2
1028
    >>> nx.is_negatively_weighted(G)
1029
    True
1030
    >>> G = nx.DiGraph()
1031
    >>> edges = [('0', '3', 3), ('0', '1', -5), ('1', '0', -2)]
1032
    >>> G.add_weighted_edges_from(edges)
1033
    >>> nx.is_negatively_weighted(G)
1034
    True
1035

1036
    """
1037
    if edge is not None:
1038
        data = G.get_edge_data(*edge)
1039
        if data is None:
1040
            msg = 'Edge {!r} does not exist.'.format(edge)
1041
            raise nx.NetworkXError(msg)
1042
        return weight in data and data[weight] < 0
1043

    
1044
    return any(weight in data and data[weight] < 0
1045
               for u, v, data in G.edges(data=True))
1046

    
1047

    
1048
def is_empty(G):
1049
    """Returns True if `G` has no edges.
1050

1051
    Parameters
1052
    ----------
1053
    G : graph
1054
        A NetworkX graph.
1055

1056
    Returns
1057
    -------
1058
    bool
1059
        True if `G` has no edges, and False otherwise.
1060

1061
    Notes
1062
    -----
1063
    An empty graph can have nodes but not edges. The empty graph with zero
1064
    nodes is known as the null graph. This is an $O(n)$ operation where n
1065
    is the number of nodes in the graph.
1066

1067
    """
1068
    return not any(G.adj.values())
1069

    
1070

    
1071
def nodes_with_selfloops(G):
1072
    """Returns an iterator over nodes with self loops.
1073

1074
    A node with a self loop has an edge with both ends adjacent
1075
    to that node.
1076

1077
    Returns
1078
    -------
1079
    nodelist : iterator
1080
        A iterator over nodes with self loops.
1081

1082
    See Also
1083
    --------
1084
    selfloop_edges, number_of_selfloops
1085

1086
    Examples
1087
    --------
1088
    >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
1089
    >>> G.add_edge(1, 1)
1090
    >>> G.add_edge(1, 2)
1091
    >>> list(nx.nodes_with_selfloops(G))
1092
    [1]
1093

1094
    """
1095
    return (n for n, nbrs in G.adj.items() if n in nbrs)
1096

    
1097

    
1098
def selfloop_edges(G, data=False, keys=False, default=None):
1099
    """Returns an iterator over selfloop edges.
1100

1101
    A selfloop edge has the same node at both ends.
1102

1103
    Parameters
1104
    ----------
1105
    data : string or bool, optional (default=False)
1106
        Return selfloop edges as two tuples (u, v) (data=False)
1107
        or three-tuples (u, v, datadict) (data=True)
1108
        or three-tuples (u, v, datavalue) (data='attrname')
1109
    keys : bool, optional (default=False)
1110
        If True, return edge keys with each edge.
1111
    default : value, optional (default=None)
1112
        Value used for edges that don't have the requested attribute.
1113
        Only relevant if data is not True or False.
1114

1115
    Returns
1116
    -------
1117
    edgeiter : iterator over edge tuples
1118
        An iterator over all selfloop edges.
1119

1120
    See Also
1121
    --------
1122
    nodes_with_selfloops, number_of_selfloops
1123

1124
    Examples
1125
    --------
1126
    >>> G = nx.MultiGraph()   # or Graph, DiGraph, MultiDiGraph, etc
1127
    >>> ekey = G.add_edge(1, 1)
1128
    >>> ekey = G.add_edge(1, 2)
1129
    >>> list(nx.selfloop_edges(G))
1130
    [(1, 1)]
1131
    >>> list(nx.selfloop_edges(G, data=True))
1132
    [(1, 1, {})]
1133
    >>> list(nx.selfloop_edges(G, keys=True))
1134
    [(1, 1, 0)]
1135
    >>> list(nx.selfloop_edges(G, keys=True, data=True))
1136
    [(1, 1, 0, {})]
1137
    """
1138
    if data is True:
1139
        if G.is_multigraph():
1140
            if keys is True:
1141
                return ((n, n, k, d)
1142
                        for n, nbrs in G.adj.items()
1143
                        if n in nbrs for k, d in nbrs[n].items())
1144
            else:
1145
                return ((n, n, d)
1146
                        for n, nbrs in G.adj.items()
1147
                        if n in nbrs for d in nbrs[n].values())
1148
        else:
1149
            return ((n, n, nbrs[n]) for n, nbrs in G.adj.items() if n in nbrs)
1150
    elif data is not False:
1151
        if G.is_multigraph():
1152
            if keys is True:
1153
                return ((n, n, k, d.get(data, default))
1154
                        for n, nbrs in G.adj.items()
1155
                        if n in nbrs for k, d in nbrs[n].items())
1156
            else:
1157
                return ((n, n, d.get(data, default))
1158
                        for n, nbrs in G.adj.items()
1159
                        if n in nbrs for d in nbrs[n].values())
1160
        else:
1161
            return ((n, n, nbrs[n].get(data, default))
1162
                    for n, nbrs in G.adj.items() if n in nbrs)
1163
    else:
1164
        if G.is_multigraph():
1165
            if keys is True:
1166
                return ((n, n, k)
1167
                        for n, nbrs in G.adj.items()
1168
                        if n in nbrs for k in nbrs[n])
1169
            else:
1170
                return ((n, n)
1171
                        for n, nbrs in G.adj.items()
1172
                        if n in nbrs for d in nbrs[n].values())
1173
        else:
1174
            return ((n, n) for n, nbrs in G.adj.items() if n in nbrs)
1175

    
1176

    
1177
def number_of_selfloops(G):
1178
    """Returns the number of selfloop edges.
1179

1180
    A selfloop edge has the same node at both ends.
1181

1182
    Returns
1183
    -------
1184
    nloops : int
1185
        The number of selfloops.
1186

1187
    See Also
1188
    --------
1189
    nodes_with_selfloops, selfloop_edges
1190

1191
    Examples
1192
    --------
1193
    >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
1194
    >>> G.add_edge(1, 1)
1195
    >>> G.add_edge(1, 2)
1196
    >>> nx.number_of_selfloops(G)
1197
    1
1198
    """
1199
    return sum(1 for _ in nx.selfloop_edges(G))