Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (37.5 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
"""
12
View Classes provide node, edge and degree "views" of a graph.
13

14
Views for nodes, edges and degree are provided for all base graph classes.
15
A view means a read-only object that is quick to create, automatically
16
updated when the graph changes, and provides basic access like `n in V`,
17
`for n in V`, `V[n]` and sometimes set operations.
18

19
The views are read-only iterable containers that are updated as the
20
graph is updated. As with dicts, the graph should not be updated
21
while iterating through the view. Views can be iterated multiple times.
22

23
Edge and Node views also allow data attribute lookup.
24
The resulting attribute dict is writable as `G.edges[3, 4]['color']='red'`
25
Degree views allow lookup of degree values for single nodes.
26
Weighted degree is supported with the `weight` argument.
27

28
NodeView
29
========
30

31
    `V = G.nodes` (or `V = G.nodes()`) allows `len(V)`, `n in V`, set
32
    operations e.g. "G.nodes & H.nodes", and `dd = G.nodes[n]`, where
33
    `dd` is the node data dict. Iteration is over the nodes by default.
34

35
NodeDataView
36
============
37

38
    To iterate over (node, data) pairs, use arguments to `G.nodes()`
39
    to create a DataView e.g. `DV = G.nodes(data='color', default='red')`.
40
    The DataView iterates as `for n, color in DV` and allows
41
    `(n, 'red') in DV`. Using `DV = G.nodes(data=True)`, the DataViews
42
    use the full datadict in writeable form also allowing contain testing as
43
    `(n, {'color': 'red'}) in VD`. DataViews allow set operations when
44
    data attributes are hashable.
45

46
DegreeView
47
==========
48

49
    `V = G.degree` allows iteration over (node, degree) pairs as well
50
    as lookup: `deg=V[n]`. There are many flavors of DegreeView
51
    for In/Out/Directed/Multi. For Directed Graphs, `G.degree`
52
    counts both in and out going edges. `G.out_degree` and
53
    `G.in_degree` count only specific directions.
54
    Weighted degree using edge data attributes is provide via
55
    `V = G.degree(weight='attr_name')` where any string with the
56
    attribute name can be used. `weight=None` is the default.
57
    No set operations are implemented for degrees, use NodeView.
58

59
    The argument `nbunch` restricts iteration to nodes in nbunch.
60
    The DegreeView can still lookup any node even if nbunch is specified.
61

62
EdgeView
63
========
64

65
    `V = G.edges` or `V = G.edges()` allows iteration over edges as well as
66
    `e in V`, set operations and edge data lookup `dd = G.edges[2, 3]`.
67
    Iteration is over 2-tuples `(u, v)` for Graph/DiGraph. For multigraphs
68
    edges 3-tuples `(u, v, key)` are the default but 2-tuples can be obtained
69
    via `V = G.edges(keys=False)`.
70

71
    Set operations for directed graphs treat the edges as a set of 2-tuples.
72
    For undirected graphs, 2-tuples are not a unique representation of edges.
73
    So long as the set being compared to contains unique representations
74
    of its edges, the set operations will act as expected. If the other
75
    set contains both `(0, 1)` and `(1, 0)` however, the result of set
76
    operations may contain both representations of the same edge.
77

78
EdgeDataView
79
============
80

81
    Edge data can be reported using an EdgeDataView typically created
82
    by calling an EdgeView: `DV = G.edges(data='weight', default=1)`.
83
    The EdgeDataView allows iteration over edge tuples, membership checking
84
    but no set operations.
85

86
    Iteration depends on `data` and `default` and for multigraph `keys`
87
    If `data is False` (the default) then iterate over 2-tuples `(u, v)`.
88
    If `data is True` iterate over 3-tuples `(u, v, datadict)`.
89
    Otherwise iterate over `(u, v, datadict.get(data, default))`.
90
    For Multigraphs, if `keys is True`, replace `u, v` with `u, v, key`
91
    to create 3-tuples and 4-tuples.
92

93
    The argument `nbunch` restricts edges to those incident to nodes in nbunch.
94
"""
95
from collections.abc import Mapping, Set, Iterable
96
import networkx as nx
97

    
98
__all__ = ['NodeView', 'NodeDataView',
99
           'EdgeView', 'OutEdgeView', 'InEdgeView',
100
           'EdgeDataView', 'OutEdgeDataView', 'InEdgeDataView',
101
           'MultiEdgeView', 'OutMultiEdgeView', 'InMultiEdgeView',
102
           'MultiEdgeDataView', 'OutMultiEdgeDataView', 'InMultiEdgeDataView',
103
           'DegreeView', 'DiDegreeView', 'InDegreeView', 'OutDegreeView',
104
           'MultiDegreeView', 'DiMultiDegreeView',
105
           'InMultiDegreeView', 'OutMultiDegreeView']
106

    
107

    
108
# NodeViews
109
class NodeView(Mapping, Set):
110
    """A NodeView class to act as G.nodes for a NetworkX Graph
111

112
    Set operations act on the nodes without considering data.
113
    Iteration is over nodes. Node data can be looked up like a dict.
114
    Use NodeDataView to iterate over node data or to specify a data
115
    attribute for lookup. NodeDataView is created by calling the NodeView.
116

117
    Parameters
118
    ----------
119
    graph : NetworkX graph-like class
120

121
    Examples
122
    --------
123
    >>> G = nx.path_graph(3)
124
    >>> NV = G.nodes()
125
    >>> 2 in NV
126
    True
127
    >>> for n in NV: print(n)
128
    0
129
    1
130
    2
131
    >>> assert(NV & {1, 2, 3} == {1, 2})
132

133
    >>> G.add_node(2, color='blue')
134
    >>> NV[2]
135
    {'color': 'blue'}
136
    >>> G.add_node(8, color='red')
137
    >>> NDV = G.nodes(data=True)
138
    >>> (2, NV[2]) in NDV
139
    True
140
    >>> for n, dd in NDV: print((n, dd.get('color', 'aqua')))
141
    (0, 'aqua')
142
    (1, 'aqua')
143
    (2, 'blue')
144
    (8, 'red')
145
    >>> NDV[2] == NV[2]
146
    True
147

148
    >>> NVdata = G.nodes(data='color', default='aqua')
149
    >>> (2, NVdata[2]) in NVdata
150
    True
151
    >>> for n, dd in NVdata: print((n, dd))
152
    (0, 'aqua')
153
    (1, 'aqua')
154
    (2, 'blue')
155
    (8, 'red')
156
    >>> NVdata[2] == NV[2]  # NVdata gets 'color', NV gets datadict
157
    False
158
    """
159
    __slots__ = '_nodes',
160

    
161
    def __getstate__(self):
162
        return {'_nodes': self._nodes}
163

    
164
    def __setstate__(self, state):
165
        self._nodes = state['_nodes']
166

    
167
    def __init__(self, graph):
168
        self._nodes = graph._node
169

    
170
    # Mapping methods
171
    def __len__(self):
172
        return len(self._nodes)
173

    
174
    def __iter__(self):
175
        return iter(self._nodes)
176

    
177
    def __getitem__(self, n):
178
        return self._nodes[n]
179

    
180
    # Set methods
181
    def __contains__(self, n):
182
        return n in self._nodes
183

    
184
    @classmethod
185
    def _from_iterable(cls, it):
186
        return set(it)
187

    
188
    # DataView method
189
    def __call__(self, data=False, default=None):
190
        if data is False:
191
            return self
192
        return NodeDataView(self._nodes, data, default)
193

    
194
    def data(self, data=True, default=None):
195
        if data is False:
196
            return self
197
        return NodeDataView(self._nodes, data, default)
198

    
199
    def __str__(self):
200
        return str(list(self))
201

    
202
    def __repr__(self):
203
        return '%s(%r)' % (self.__class__.__name__, tuple(self))
204

    
205

    
206
class NodeDataView(Set):
207
    """A DataView class for nodes of a NetworkX Graph
208

209
    The main use for this class is to iterate through node-data pairs.
210
    The data can be the entire data-dictionary for each node, or it
211
    can be a specific attribute (with default) for each node.
212
    Set operations are enabled with NodeDataView, but don't work in
213
    cases where the data is not hashable. Use with caution.
214
    Typically, set operations on nodes use NodeView, not NodeDataView.
215
    That is, they use `G.nodes` instead of `G.nodes(data='foo')`.
216

217
    Parameters
218
    ==========
219
    graph : NetworkX graph-like class
220
    data : bool or string (default=False)
221
    default : object (default=None)
222
    """
223
    __slots__ = ('_nodes', '_data', '_default')
224

    
225
    def __getstate__(self):
226
        return {'_nodes': self._nodes,
227
                '_data': self._data,
228
                '_default': self._default}
229

    
230
    def __setstate__(self, state):
231
        self._nodes = state['_nodes']
232
        self._data = state['_data']
233
        self._default = state['_default']
234

    
235
    def __init__(self, nodedict, data=False, default=None):
236
        self._nodes = nodedict
237
        self._data = data
238
        self._default = default
239

    
240
    @classmethod
241
    def _from_iterable(cls, it):
242
        try:
243
            return set(it)
244
        except TypeError as err:
245
            if "unhashable" in str(err):
246
                msg = " : Could be b/c data=True or your values are unhashable"
247
                raise TypeError(str(err) + msg)
248
            raise
249

    
250
    def __len__(self):
251
        return len(self._nodes)
252

    
253
    def __iter__(self):
254
        data = self._data
255
        if data is False:
256
            return iter(self._nodes)
257
        if data is True:
258
            return iter(self._nodes.items())
259
        return ((n, dd[data] if data in dd else self._default)
260
                for n, dd in self._nodes.items())
261

    
262
    def __contains__(self, n):
263
        try:
264
            node_in = n in self._nodes
265
        except TypeError:
266
            n, d = n
267
            return n in self._nodes and self[n] == d
268
        if node_in is True:
269
            return node_in
270
        try:
271
            n, d = n
272
        except (TypeError, ValueError):
273
            return False
274
        return n in self._nodes and self[n] == d
275

    
276
    def __getitem__(self, n):
277
        ddict = self._nodes[n]
278
        data = self._data
279
        if data is False or data is True:
280
            return ddict
281
        return ddict[data] if data in ddict else self._default
282

    
283
    def __str__(self):
284
        return str(list(self))
285

    
286
    def __repr__(self):
287
        if self._data is False:
288
            return '%s(%r)' % (self.__class__.__name__, tuple(self))
289
        if self._data is True:
290
            return '%s(%r)' % (self.__class__.__name__, dict(self))
291
        return '%s(%r, data=%r)' % \
292
               (self.__class__.__name__, dict(self), self._data)
293

    
294

    
295
# DegreeViews
296
class DiDegreeView(object):
297
    """A View class for degree of nodes in a NetworkX Graph
298

299
    The functionality is like dict.items() with (node, degree) pairs.
300
    Additional functionality includes read-only lookup of node degree,
301
    and calling with optional features nbunch (for only a subset of nodes)
302
    and weight (use edge weights to compute degree).
303

304
    Parameters
305
    ==========
306
    graph : NetworkX graph-like class
307
    nbunch : node, container of nodes, or None meaning all nodes (default=None)
308
    weight : bool or string (default=None)
309

310
    Notes
311
    -----
312
    DegreeView can still lookup any node even if nbunch is specified.
313

314
    Examples
315
    --------
316
    >>> G = nx.path_graph(3)
317
    >>> DV = G.degree()
318
    >>> assert(DV[2] == 1)
319
    >>> assert(sum(deg for n, deg in DV) == 4)
320

321
    >>> DVweight = G.degree(weight="span")
322
    >>> G.add_edge(1, 2, span=34)
323
    >>> DVweight[2]
324
    34
325
    >>> DVweight[0]  #  default edge weight is 1
326
    1
327
    >>> sum(span for n, span in DVweight)  # sum weighted degrees
328
    70
329

330
    >>> DVnbunch = G.degree(nbunch=(1, 2))
331
    >>> assert(len(list(DVnbunch)) == 2)  # iteration over nbunch only
332
    """
333

    
334
    def __init__(self, G, nbunch=None, weight=None):
335
        self._graph = G
336
        self._succ = G._succ if hasattr(G, "_succ") else G._adj
337
        self._pred = G._pred if hasattr(G, "_pred") else G._adj
338
        self._nodes = self._succ if nbunch is None \
339
            else list(G.nbunch_iter(nbunch))
340
        self._weight = weight
341

    
342
    def __call__(self, nbunch=None, weight=None):
343
        if nbunch is None:
344
            if weight == self._weight:
345
                return self
346
            return self.__class__(self._graph, None, weight)
347
        try:
348
            if nbunch in self._nodes:
349
                if weight == self._weight:
350
                    return self[nbunch]
351
                return self.__class__(self._graph, None, weight)[nbunch]
352
        except TypeError:
353
            pass
354
        return self.__class__(self._graph, nbunch, weight)
355

    
356
    def __getitem__(self, n):
357
        weight = self._weight
358
        succs = self._succ[n]
359
        preds = self._pred[n]
360
        if weight is None:
361
            return len(succs) + len(preds)
362
        return sum(dd.get(weight, 1) for dd in succs.values()) + \
363
            sum(dd.get(weight, 1) for dd in preds.values())
364

    
365
    def __iter__(self):
366
        weight = self._weight
367
        if weight is None:
368
            for n in self._nodes:
369
                succs = self._succ[n]
370
                preds = self._pred[n]
371
                yield (n, len(succs) + len(preds))
372
        else:
373
            for n in self._nodes:
374
                succs = self._succ[n]
375
                preds = self._pred[n]
376
                deg = sum(dd.get(weight, 1) for dd in succs.values()) \
377
                    + sum(dd.get(weight, 1) for dd in preds.values())
378
                yield (n, deg)
379

    
380
    def __len__(self):
381
        return len(self._nodes)
382

    
383
    def __str__(self):
384
        return str(list(self))
385

    
386
    def __repr__(self):
387
        return '%s(%r)' % (self.__class__.__name__, dict(self))
388

    
389

    
390
class DegreeView(DiDegreeView):
391
    """A DegreeView class to act as G.degree for a NetworkX Graph
392

393
    Typical usage focuses on iteration over `(node, degree)` pairs.
394
    The degree is by default the number of edges incident to the node.
395
    Optional argument `weight` enables weighted degree using the edge
396
    attribute named in the `weight` argument.  Reporting and iteration
397
    can also be restricted to a subset of nodes using `nbunch`.
398

399
    Additional functionality include node lookup so that `G.degree[n]`
400
    reported the (possibly weighted) degree of node `n`. Calling the
401
    view creates a view with different arguments `nbunch` or `weight`.
402

403
    Parameters
404
    ==========
405
    graph : NetworkX graph-like class
406
    nbunch : node, container of nodes, or None meaning all nodes (default=None)
407
    weight : string or None (default=None)
408

409
    Notes
410
    -----
411
    DegreeView can still lookup any node even if nbunch is specified.
412

413
    Examples
414
    --------
415
    >>> G = nx.path_graph(3)
416
    >>> DV = G.degree()
417
    >>> assert(DV[2] == 1)
418
    >>> assert(G.degree[2] == 1)
419
    >>> assert(sum(deg for n, deg in DV) == 4)
420

421
    >>> DVweight = G.degree(weight="span")
422
    >>> G.add_edge(1, 2, span=34)
423
    >>> DVweight[2]
424
    34
425
    >>> DVweight[0]  #  default edge weight is 1
426
    1
427
    >>> sum(span for n, span in DVweight)  # sum weighted degrees
428
    70
429

430
    >>> DVnbunch = G.degree(nbunch=(1, 2))
431
    >>> assert(len(list(DVnbunch)) == 2)  # iteration over nbunch only
432
    """
433

    
434
    def __getitem__(self, n):
435
        weight = self._weight
436
        nbrs = self._succ[n]
437
        if weight is None:
438
            return len(nbrs) + (n in nbrs)
439
        return sum(dd.get(weight, 1) for dd in nbrs.values()) + \
440
            (n in nbrs and nbrs[n].get(weight, 1))
441

    
442
    def __iter__(self):
443
        weight = self._weight
444
        if weight is None:
445
            for n in self._nodes:
446
                nbrs = self._succ[n]
447
                yield (n, len(nbrs) + (n in nbrs))
448
        else:
449
            for n in self._nodes:
450
                nbrs = self._succ[n]
451
                deg = sum(dd.get(weight, 1) for dd in nbrs.values()) + \
452
                    (n in nbrs and nbrs[n].get(weight, 1))
453
                yield (n, deg)
454

    
455

    
456
class OutDegreeView(DiDegreeView):
457
    """A DegreeView class to report out_degree for a DiGraph; See DegreeView"""
458

    
459
    def __getitem__(self, n):
460
        weight = self._weight
461
        nbrs = self._succ[n]
462
        if self._weight is None:
463
            return len(nbrs)
464
        return sum(dd.get(self._weight, 1) for dd in nbrs.values())
465

    
466
    def __iter__(self):
467
        weight = self._weight
468
        if weight is None:
469
            for n in self._nodes:
470
                succs = self._succ[n]
471
                yield (n, len(succs))
472
        else:
473
            for n in self._nodes:
474
                succs = self._succ[n]
475
                deg = sum(dd.get(weight, 1) for dd in succs.values())
476
                yield (n, deg)
477

    
478

    
479
class InDegreeView(DiDegreeView):
480
    """A DegreeView class to report in_degree for a DiGraph; See DegreeView"""
481

    
482
    def __getitem__(self, n):
483
        weight = self._weight
484
        nbrs = self._pred[n]
485
        if weight is None:
486
            return len(nbrs)
487
        return sum(dd.get(weight, 1) for dd in nbrs.values())
488

    
489
    def __iter__(self):
490
        weight = self._weight
491
        if weight is None:
492
            for n in self._nodes:
493
                preds = self._pred[n]
494
                yield (n, len(preds))
495
        else:
496
            for n in self._nodes:
497
                preds = self._pred[n]
498
                deg = sum(dd.get(weight, 1) for dd in preds.values())
499
                yield (n, deg)
500

    
501

    
502
class MultiDegreeView(DiDegreeView):
503
    """A DegreeView class for undirected multigraphs; See DegreeView"""
504

    
505
    def __getitem__(self, n):
506
        weight = self._weight
507
        nbrs = self._succ[n]
508
        if weight is None:
509
            return sum(len(keys) for keys in nbrs.values()) + \
510
                (n in nbrs and len(nbrs[n]))
511
        # edge weighted graph - degree is sum of nbr edge weights
512
        deg = sum(d.get(weight, 1) for key_dict in nbrs.values()
513
                  for d in key_dict.values())
514
        if n in nbrs:
515
            deg += sum(d.get(weight, 1) for d in nbrs[n].values())
516
        return deg
517

    
518
    def __iter__(self):
519
        weight = self._weight
520
        if weight is None:
521
            for n in self._nodes:
522
                nbrs = self._succ[n]
523
                deg = sum(len(keys) for keys in nbrs.values()) + \
524
                    (n in nbrs and len(nbrs[n]))
525
                yield (n, deg)
526
        else:
527
            for n in self._nodes:
528
                nbrs = self._succ[n]
529
                deg = sum(d.get(weight, 1) for key_dict in nbrs.values()
530
                          for d in key_dict.values())
531
                if n in nbrs:
532
                    deg += sum(d.get(weight, 1) for d in nbrs[n].values())
533
                yield (n, deg)
534

    
535

    
536
class DiMultiDegreeView(DiDegreeView):
537
    """A DegreeView class for MultiDiGraph; See DegreeView"""
538

    
539
    def __getitem__(self, n):
540
        weight = self._weight
541
        succs = self._succ[n]
542
        preds = self._pred[n]
543
        if weight is None:
544
            return sum(len(keys) for keys in succs.values()) + \
545
                sum(len(keys) for keys in preds.values())
546
        # edge weighted graph - degree is sum of nbr edge weights
547
        deg = sum(d.get(weight, 1) for key_dict in succs.values()
548
                  for d in key_dict.values()) + \
549
            sum(d.get(weight, 1) for key_dict in preds.values()
550
                for d in key_dict.values())
551
        return deg
552

    
553
    def __iter__(self):
554
        weight = self._weight
555
        if weight is None:
556
            for n in self._nodes:
557
                succs = self._succ[n]
558
                preds = self._pred[n]
559
                deg = sum(len(keys) for keys in succs.values()) + \
560
                    sum(len(keys) for keys in preds.values())
561
                yield (n, deg)
562
        else:
563
            for n in self._nodes:
564
                succs = self._succ[n]
565
                preds = self._pred[n]
566
                deg = sum(d.get(weight, 1) for key_dict in succs.values()
567
                          for d in key_dict.values()) + \
568
                    sum(d.get(weight, 1) for key_dict in preds.values()
569
                        for d in key_dict.values())
570
                yield (n, deg)
571

    
572

    
573
class InMultiDegreeView(DiDegreeView):
574
    """A DegreeView class for inward degree of MultiDiGraph; See DegreeView"""
575

    
576
    def __getitem__(self, n):
577
        weight = self._weight
578
        nbrs = self._pred[n]
579
        if weight is None:
580
            return sum(len(data) for data in nbrs.values())
581
        # edge weighted graph - degree is sum of nbr edge weights
582
        return sum(d.get(weight, 1) for key_dict in nbrs.values()
583
                   for d in key_dict.values())
584

    
585
    def __iter__(self):
586
        weight = self._weight
587
        if weight is None:
588
            for n in self._nodes:
589
                nbrs = self._pred[n]
590
                deg = sum(len(data) for data in nbrs.values())
591
                yield (n, deg)
592
        else:
593
            for n in self._nodes:
594
                nbrs = self._pred[n]
595
                deg = sum(d.get(weight, 1) for key_dict in nbrs.values()
596
                          for d in key_dict.values())
597
                yield (n, deg)
598

    
599

    
600
class OutMultiDegreeView(DiDegreeView):
601
    """A DegreeView class for outward degree of MultiDiGraph; See DegreeView"""
602

    
603
    def __getitem__(self, n):
604
        weight = self._weight
605
        nbrs = self._succ[n]
606
        if weight is None:
607
            return sum(len(data) for data in nbrs.values())
608
        # edge weighted graph - degree is sum of nbr edge weights
609
        return sum(d.get(weight, 1) for key_dict in nbrs.values()
610
                   for d in key_dict.values())
611

    
612
    def __iter__(self):
613
        weight = self._weight
614
        if weight is None:
615
            for n in self._nodes:
616
                nbrs = self._succ[n]
617
                deg = sum(len(data) for data in nbrs.values())
618
                yield (n, deg)
619
        else:
620
            for n in self._nodes:
621
                nbrs = self._succ[n]
622
                deg = sum(d.get(weight, 1) for key_dict in nbrs.values()
623
                          for d in key_dict.values())
624
                yield (n, deg)
625

    
626

    
627
# EdgeDataViews
628
class OutEdgeDataView(object):
629
    """EdgeDataView for outward edges of DiGraph; See EdgeDataView"""
630
    __slots__ = ('_viewer', '_nbunch', '_data', '_default',
631
                 '_adjdict', '_nodes_nbrs', '_report')
632

    
633
    def __getstate__(self):
634
        return {'viewer': self._viewer,
635
                'nbunch': self._nbunch,
636
                'data': self._data,
637
                'default': self._default}
638

    
639
    def __setstate__(self, state):
640
        self.__init__(**state)
641

    
642
    def __init__(self, viewer, nbunch=None, data=False, default=None):
643
        self._viewer = viewer
644
        self._adjdict = viewer._adjdict
645
        if nbunch is None:
646
            self._nodes_nbrs = self._adjdict.items
647
        else:
648
            nbunch = list(viewer._graph.nbunch_iter(nbunch))
649
            self._nodes_nbrs = lambda: [(n, self._adjdict[n]) for n in nbunch]
650
        self._nbunch = nbunch
651
        self._data = data
652
        self._default = default
653
        # Set _report based on data and default
654
        if data is True:
655
            self._report = lambda n, nbr, dd: (n, nbr, dd)
656
        elif data is False:
657
            self._report = lambda n, nbr, dd: (n, nbr)
658
        else:  # data is attribute name
659
            self._report = lambda n, nbr, dd: \
660
                (n, nbr, dd[data]) if data in dd else (n, nbr, default)
661

    
662
    def __len__(self):
663
        return sum(len(nbrs) for n, nbrs in self._nodes_nbrs())
664

    
665
    def __iter__(self):
666
        return (self._report(n, nbr, dd) for n, nbrs in self._nodes_nbrs()
667
                for nbr, dd in nbrs.items())
668

    
669
    def __contains__(self, e):
670
        try:
671
            u, v = e[:2]
672
            ddict = self._adjdict[u][v]
673
        except KeyError:
674
            return False
675
        return e == self._report(u, v, ddict)
676

    
677
    def __str__(self):
678
        return str(list(self))
679

    
680
    def __repr__(self):
681
        return '%s(%r)' % (self.__class__.__name__, list(self))
682

    
683

    
684
class EdgeDataView(OutEdgeDataView):
685
    """A EdgeDataView class for edges of Graph
686

687
    This view is primarily used to iterate over the edges reporting
688
    edges as node-tuples with edge data optionally reported. The
689
    argument `nbunch` allows restriction to edges incident to nodes
690
    in that container/singleton. The default (nbunch=None)
691
    reports all edges. The arguments `data` and `default` control
692
    what edge data is reported. The default `data is False` reports
693
    only node-tuples for each edge. If `data is True` the entire edge
694
    data dict is returned. Otherwise `data` is assumed to hold the name
695
    of the edge attribute to report with default `default` if  that
696
    edge attribute is not present.
697

698
    Parameters
699
    ----------
700
    nbunch : container of nodes, node or None (default None)
701
    data : False, True or string (default False)
702
    default : default value (default None)
703

704
    Examples
705
    --------
706
    >>> G = nx.path_graph(3)
707
    >>> G.add_edge(1, 2, foo='bar')
708
    >>> list(G.edges(data='foo', default='biz'))
709
    [(0, 1, 'biz'), (1, 2, 'bar')]
710
    >>> assert((0, 1, 'biz') in G.edges(data='foo', default='biz'))
711
    """
712
    __slots__ = ()
713

    
714
    def __len__(self):
715
        return sum(1 for e in self)
716

    
717
    def __iter__(self):
718
        seen = {}
719
        for n, nbrs in self._nodes_nbrs():
720
            for nbr, dd in nbrs.items():
721
                if nbr not in seen:
722
                    yield self._report(n, nbr, dd)
723
            seen[n] = 1
724
        del seen
725

    
726
    def __contains__(self, e):
727
        try:
728
            u, v = e[:2]
729
            ddict = self._adjdict[u][v]
730
        except KeyError:
731
            try:
732
                ddict = self._adjdict[v][u]
733
            except KeyError:
734
                return False
735
        return e == self._report(u, v, ddict)
736

    
737

    
738
class InEdgeDataView(OutEdgeDataView):
739
    """An EdgeDataView class for outward edges of DiGraph; See EdgeDataView"""
740
    __slots__ = ()
741

    
742
    def __iter__(self):
743
        return (self._report(nbr, n, dd) for n, nbrs in self._nodes_nbrs()
744
                for nbr, dd in nbrs.items())
745

    
746
    def __contains__(self, e):
747
        try:
748
            u, v = e[:2]
749
            ddict = self._adjdict[v][u]
750
        except KeyError:
751
            return False
752
        return e == self._report(u, v, ddict)
753

    
754

    
755
class OutMultiEdgeDataView(OutEdgeDataView):
756
    """An EdgeDataView for outward edges of MultiDiGraph; See EdgeDataView"""
757
    __slots__ = ('keys',)
758

    
759
    def __getstate__(self):
760
        return {'viewer': self._viewer,
761
                'nbunch': self._nbunch,
762
                'keys': self.keys,
763
                'data': self._data,
764
                'default': self._default}
765

    
766
    def __setstate__(self, state):
767
        self.__init__(**state)
768

    
769
    def __init__(self, viewer, nbunch=None,
770
                 data=False, keys=False, default=None):
771
        self._viewer = viewer
772
        self._adjdict = viewer._adjdict
773
        self.keys = keys
774
        if nbunch is None:
775
            self._nodes_nbrs = self._adjdict.items
776
        else:
777
            nbunch = list(viewer._graph.nbunch_iter(nbunch))
778
            self._nodes_nbrs = lambda: [(n, self._adjdict[n]) for n in nbunch]
779
        self._nbunch = nbunch
780
        self._data = data
781
        self._default = default
782
        # Set _report based on data and default
783
        if data is True:
784
            if keys is True:
785
                self._report = lambda n, nbr, k, dd: (n, nbr, k, dd)
786
            else:
787
                self._report = lambda n, nbr, k, dd: (n, nbr, dd)
788
        elif data is False:
789
            if keys is True:
790
                self._report = lambda n, nbr, k, dd: (n, nbr, k)
791
            else:
792
                self._report = lambda n, nbr, k, dd: (n, nbr)
793
        else:  # data is attribute name
794
            if keys is True:
795
                self._report = lambda n, nbr, k, dd: (n, nbr, k, dd[data]) \
796
                    if data in dd else (n, nbr, k, default)
797
            else:
798
                self._report = lambda n, nbr, k, dd: (n, nbr, dd[data]) \
799
                    if data in dd else (n, nbr, default)
800

    
801
    def __len__(self):
802
        return sum(1 for e in self)
803

    
804
    def __iter__(self):
805
        return (self._report(n, nbr, k, dd) for n, nbrs in self._nodes_nbrs()
806
                for nbr, kd in nbrs.items() for k, dd in kd.items())
807

    
808
    def __contains__(self, e):
809
        u, v = e[:2]
810
        try:
811
            kdict = self._adjdict[u][v]
812
        except KeyError:
813
            return False
814
        if self.keys is True:
815
            k = e[2]
816
            try:
817
                dd = kdict[k]
818
            except KeyError:
819
                return False
820
            return e == self._report(u, v, k, dd)
821
        for k, dd in kdict.items():
822
            if e == self._report(u, v, k, dd):
823
                return True
824
        return False
825

    
826

    
827
class MultiEdgeDataView(OutMultiEdgeDataView):
828
    """An EdgeDataView class for edges of MultiGraph; See EdgeDataView"""
829
    __slots__ = ()
830

    
831
    def __iter__(self):
832
        seen = {}
833
        for n, nbrs in self._nodes_nbrs():
834
            for nbr, kd in nbrs.items():
835
                if nbr not in seen:
836
                    for k, dd in kd.items():
837
                        yield self._report(n, nbr, k, dd)
838
            seen[n] = 1
839
        del seen
840

    
841
    def __contains__(self, e):
842
        u, v = e[:2]
843
        try:
844
            kdict = self._adjdict[u][v]
845
        except KeyError:
846
            try:
847
                kdict = self._adjdict[v][u]
848
            except KeyError:
849
                return False
850
        if self.keys is True:
851
            k = e[2]
852
            try:
853
                dd = kdict[k]
854
            except KeyError:
855
                return False
856
            return e == self._report(u, v, k, dd)
857
        for k, dd in kdict.items():
858
            if e == self._report(u, v, k, dd):
859
                return True
860
        return False
861

    
862

    
863
class InMultiEdgeDataView(OutMultiEdgeDataView):
864
    """An EdgeDataView for inward edges of MultiDiGraph; See EdgeDataView"""
865
    __slots__ = ()
866

    
867
    def __iter__(self):
868
        return (self._report(nbr, n, k, dd) for n, nbrs in self._nodes_nbrs()
869
                for nbr, kd in nbrs.items() for k, dd in kd.items())
870

    
871
    def __contains__(self, e):
872
        u, v = e[:2]
873
        try:
874
            kdict = self._adjdict[v][u]
875
        except KeyError:
876
            return False
877
        if self.keys is True:
878
            k = e[2]
879
            dd = kdict[k]
880
            return e == self._report(u, v, k, dd)
881
        for k, dd in kdict.items():
882
            if e == self._report(u, v, k, dd):
883
                return True
884
        return False
885

    
886

    
887
# EdgeViews    have set operations and no data reported
888
class OutEdgeView(Set, Mapping):
889
    """A EdgeView class for outward edges of a DiGraph"""
890
    __slots__ = ('_adjdict', '_graph', '_nodes_nbrs')
891

    
892
    def __getstate__(self):
893
        return {'_graph': self._graph}
894

    
895
    def __setstate__(self, state):
896
        self._graph = G = state['_graph']
897
        self._adjdict = G._succ if hasattr(G, "succ") else G._adj
898
        self._nodes_nbrs = self._adjdict.items
899

    
900
    @classmethod
901
    def _from_iterable(cls, it):
902
        return set(it)
903

    
904
    dataview = OutEdgeDataView
905

    
906
    def __init__(self, G):
907
        self._graph = G
908
        self._adjdict = G._succ if hasattr(G, "succ") else G._adj
909
        self._nodes_nbrs = self._adjdict.items
910

    
911
    # Set methods
912
    def __len__(self):
913
        return sum(len(nbrs) for n, nbrs in self._nodes_nbrs())
914

    
915
    def __iter__(self):
916
        for n, nbrs in self._nodes_nbrs():
917
            for nbr in nbrs:
918
                yield (n, nbr)
919

    
920
    def __contains__(self, e):
921
        try:
922
            u, v = e
923
            return v in self._adjdict[u]
924
        except KeyError:
925
            return False
926

    
927
    # Mapping Methods
928
    def __getitem__(self, e):
929
        u, v = e
930
        return self._adjdict[u][v]
931

    
932
    # EdgeDataView methods
933
    def __call__(self, nbunch=None, data=False, default=None):
934
        if nbunch is None and data is False:
935
            return self
936
        return self.dataview(self, nbunch, data, default)
937

    
938
    def data(self, data=True, default=None, nbunch=None):
939
        if nbunch is None and data is False:
940
            return self
941
        return self.dataview(self, nbunch, data, default)
942

    
943
    # String Methods
944
    def __str__(self):
945
        return str(list(self))
946

    
947
    def __repr__(self):
948
        return "{0.__class__.__name__}({1!r})".format(self, list(self))
949

    
950

    
951
class EdgeView(OutEdgeView):
952
    """A EdgeView class for edges of a Graph
953

954
    This densely packed View allows iteration over edges, data lookup
955
    like a dict and set operations on edges represented by node-tuples.
956
    In addition, edge data can be controlled by calling this object
957
    possibly creating an EdgeDataView. Typically edges are iterated over
958
    and reported as `(u, v)` node tuples or `(u, v, key)` node/key tuples
959
    for multigraphs. Those edge representations can also be using to
960
    lookup the data dict for any edge. Set operations also are available
961
    where those tuples are the elements of the set.
962
    Calling this object with optional arguments `data`, `default` and `keys`
963
    controls the form of the tuple (see EdgeDataView). Optional argument
964
    `nbunch` allows restriction to edges only involving certain nodes.
965

966
    If `data is False` (the default) then iterate over 2-tuples `(u, v)`.
967
    If `data is True` iterate over 3-tuples `(u, v, datadict)`.
968
    Otherwise iterate over `(u, v, datadict.get(data, default))`.
969
    For Multigraphs, if `keys is True`, replace `u, v` with `u, v, key` above.
970

971
    Parameters
972
    ==========
973
    graph : NetworkX graph-like class
974
    nbunch : (default= all nodes in graph) only report edges with these nodes
975
    keys : (only for MultiGraph. default=False) report edge key in tuple
976
    data : bool or string (default=False) see above
977
    default : object (default=None)
978

979
    Examples
980
    ========
981
    >>> G = nx.path_graph(4)
982
    >>> EV = G.edges()
983
    >>> (2, 3) in EV
984
    True
985
    >>> for u, v in EV: print((u, v))
986
    (0, 1)
987
    (1, 2)
988
    (2, 3)
989
    >>> assert(EV & {(1, 2), (3, 4)} == {(1, 2)})
990

991
    >>> EVdata = G.edges(data='color', default='aqua')
992
    >>> G.add_edge(2, 3, color='blue')
993
    >>> assert((2, 3, 'blue') in EVdata)
994
    >>> for u, v, c in EVdata: print("({}, {}) has color: {}".format(u, v, c))
995
    (0, 1) has color: aqua
996
    (1, 2) has color: aqua
997
    (2, 3) has color: blue
998

999
    >>> EVnbunch = G.edges(nbunch=2)
1000
    >>> assert((2, 3) in EVnbunch)
1001
    >>> assert((0, 1) in EVnbunch)   #  nbunch is ignored in __contains__
1002
    >>> for u, v in EVnbunch: assert(u == 2 or v == 2)
1003

1004
    >>> MG = nx.path_graph(4, create_using=nx.MultiGraph)
1005
    >>> EVmulti = MG.edges(keys=True)
1006
    >>> (2, 3, 0) in EVmulti
1007
    True
1008
    >>> (2, 3) in EVmulti   # 2-tuples work even when keys is True
1009
    True
1010
    >>> key = MG.add_edge(2, 3)
1011
    >>> for u, v, k in EVmulti: print((u, v, k))
1012
    (0, 1, 0)
1013
    (1, 2, 0)
1014
    (2, 3, 0)
1015
    (2, 3, 1)
1016
    """
1017
    __slots__ = ()
1018

    
1019
    dataview = EdgeDataView
1020

    
1021
    def __len__(self):
1022
        num_nbrs = (len(nbrs) + (n in nbrs) for n, nbrs in self._nodes_nbrs())
1023
        return sum(num_nbrs) // 2
1024

    
1025
    def __iter__(self):
1026
        seen = {}
1027
        for n, nbrs in self._nodes_nbrs():
1028
            for nbr in nbrs:
1029
                if nbr not in seen:
1030
                    yield (n, nbr)
1031
            seen[n] = 1
1032
        del seen
1033

    
1034
    def __contains__(self, e):
1035
        try:
1036
            u, v = e[:2]
1037
            return v in self._adjdict[u] or u in self._adjdict[v]
1038
        except (KeyError, ValueError):
1039
            return False
1040

    
1041

    
1042
class InEdgeView(OutEdgeView):
1043
    """A EdgeView class for inward edges of a DiGraph"""
1044
    __slots__ = ()
1045

    
1046
    def __setstate__(self, state):
1047
        self._graph = G = state['_graph']
1048
        self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1049
        self._nodes_nbrs = self._adjdict.items
1050

    
1051
    dataview = InEdgeDataView
1052

    
1053
    def __init__(self, G):
1054
        self._graph = G
1055
        self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1056
        self._nodes_nbrs = self._adjdict.items
1057

    
1058
    def __iter__(self):
1059
        for n, nbrs in self._nodes_nbrs():
1060
            for nbr in nbrs:
1061
                yield (nbr, n)
1062

    
1063
    def __contains__(self, e):
1064
        try:
1065
            u, v = e
1066
            return u in self._adjdict[v]
1067
        except KeyError:
1068
            return False
1069

    
1070
    def __getitem__(self, e):
1071
        u, v = e
1072
        return self._adjdict[v][u]
1073

    
1074

    
1075
class OutMultiEdgeView(OutEdgeView):
1076
    """A EdgeView class for outward edges of a MultiDiGraph"""
1077
    __slots__ = ()
1078

    
1079
    dataview = OutMultiEdgeDataView
1080

    
1081
    def __len__(self):
1082
        return sum(len(kdict) for n, nbrs in self._nodes_nbrs()
1083
                   for nbr, kdict in nbrs.items())
1084

    
1085
    def __iter__(self):
1086
        for n, nbrs in self._nodes_nbrs():
1087
            for nbr, kdict in nbrs.items():
1088
                for key in kdict:
1089
                    yield (n, nbr, key)
1090

    
1091
    def __contains__(self, e):
1092
        N = len(e)
1093
        if N == 3:
1094
            u, v, k = e
1095
        elif N == 2:
1096
            u, v = e
1097
            k = 0
1098
        else:
1099
            raise ValueError("MultiEdge must have length 2 or 3")
1100
        try:
1101
            return k in self._adjdict[u][v]
1102
        except KeyError:
1103
            return False
1104

    
1105
    def __getitem__(self, e):
1106
        u, v, k = e
1107
        return self._adjdict[u][v][k]
1108

    
1109
    def __call__(self, nbunch=None, data=False, keys=False, default=None):
1110
        if nbunch is None and data is False and keys is True:
1111
            return self
1112
        return self.dataview(self, nbunch, data, keys, default)
1113

    
1114
    def data(self, data=True, keys=False, default=None, nbunch=None):
1115
        if nbunch is None and data is False and keys is True:
1116
            return self
1117
        return self.dataview(self, nbunch, data, keys, default)
1118

    
1119

    
1120
class MultiEdgeView(OutMultiEdgeView):
1121
    """A EdgeView class for edges of a MultiGraph"""
1122
    __slots__ = ()
1123

    
1124
    dataview = MultiEdgeDataView
1125

    
1126
    def __len__(self):
1127
        return sum(1 for e in self)
1128

    
1129
    def __iter__(self):
1130
        seen = {}
1131
        for n, nbrs in self._nodes_nbrs():
1132
            for nbr, kd in nbrs.items():
1133
                if nbr not in seen:
1134
                    for k, dd in kd.items():
1135
                        yield (n, nbr, k)
1136
            seen[n] = 1
1137
        del seen
1138

    
1139

    
1140
class InMultiEdgeView(OutMultiEdgeView):
1141
    """A EdgeView class for inward edges of a MultiDiGraph"""
1142
    __slots__ = ()
1143

    
1144
    def __setstate__(self, state):
1145
        self._graph = G = state['_graph']
1146
        self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1147
        self._nodes_nbrs = self._adjdict.items
1148

    
1149
    dataview = InMultiEdgeDataView
1150

    
1151
    def __init__(self, G):
1152
        self._graph = G
1153
        self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1154
        self._nodes_nbrs = self._adjdict.items
1155

    
1156
    def __iter__(self):
1157
        for n, nbrs in self._nodes_nbrs():
1158
            for nbr, kdict in nbrs.items():
1159
                for key in kdict:
1160
                    yield (nbr, n, key)
1161

    
1162
    def __contains__(self, e):
1163
        N = len(e)
1164
        if N == 3:
1165
            u, v, k = e
1166
        elif N == 2:
1167
            u, v = e
1168
            k = 0
1169
        else:
1170
            raise ValueError("MultiEdge must have length 2 or 3")
1171
        try:
1172
            return k in self._adjdict[v][u]
1173
        except KeyError:
1174
            return False
1175

    
1176
    def __getitem__(self, e):
1177
        u, v, k = e
1178
        return self._adjdict[v][u][k]