Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.81 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Author:  Aric Hagberg (hagberg@lanl.gov),
9
#          Pieter Swart (swart@lanl.gov),
10
#          Dan Schult(dschult@colgate.edu)
11
"""View of Graphs as SubGraph, Reverse, Directed, Undirected.
12

13
In some algorithms it is convenient to temporarily morph
14
a graph to exclude some nodes or edges. It should be better
15
to do that via a view than to remove and then re-add.
16
In other algorithms it is convenient to temporarily morph
17
a graph to reverse directed edges, or treat a directed graph
18
as undirected, etc. This module provides those graph views.
19

20
The resulting views are essentially read-only graphs that
21
report data from the orignal graph object. We provide an
22
attribute G._graph which points to the underlying graph object.
23

24
Note: Since graphviews look like graphs, one can end up with
25
view-of-view-of-view chains. Be careful with chains because
26
they become very slow with about 15 nested views.
27
For the common simple case of node induced subgraphs created
28
from the graph class, we short-cut the chain by returning a
29
subgraph of the original graph directly rather than a subgraph
30
of a subgraph. We are careful not to disrupt any edge filter in
31
the middle subgraph. In general, determining how to short-cut
32
the chain is tricky and much harder with restricted_views than
33
with induced subgraphs.
34
Often it is easiest to use .copy() to avoid chains.
35
"""
36
from networkx.classes.coreviews import UnionAdjacency, UnionMultiAdjacency, \
37
    FilterAtlas, FilterAdjacency, FilterMultiAdjacency
38
from networkx.classes.filters import no_filter
39
from networkx.exception import NetworkXError, NetworkXNotImplemented
40
# remove the graph class import when deprecated GraphView removed
41
from networkx.classes import Graph, DiGraph, MultiGraph, MultiDiGraph
42

    
43
import networkx as nx
44

    
45
__all__ = ['generic_graph_view', 'subgraph_view', 'reverse_view',
46
           'SubGraph', 'SubDiGraph', 'SubMultiGraph', 'SubMultiDiGraph',
47
           'ReverseView', 'MultiReverseView',
48
           'DiGraphView', 'MultiDiGraphView',
49
           'GraphView', 'MultiGraphView',
50
           ]
51

    
52

    
53
def generic_graph_view(G, create_using=None):
54
    if create_using is None:
55
        newG = G.__class__()
56
    else:
57
        newG = nx.empty_graph(0, create_using)
58
    if G.is_multigraph() != newG.is_multigraph():
59
        raise NetworkXError("Multigraph for G must agree with create_using")
60
    newG = nx.freeze(newG)
61

    
62
    # create view by assigning attributes from G
63
    newG._graph = G
64
    newG.graph = G.graph
65

    
66
    newG._node = G._node
67
    if newG.is_directed():
68
        if G.is_directed():
69
            newG._succ = G._succ
70
            newG._pred = G._pred
71
            newG._adj = G._succ
72
        else:
73
            newG._succ = G._adj
74
            newG._pred = G._adj
75
            newG._adj = G._adj
76
    elif G.is_directed():
77
        if G.is_multigraph():
78
            newG._adj = UnionMultiAdjacency(G._succ, G._pred)
79
        else:
80
            newG._adj = UnionAdjacency(G._succ, G._pred)
81
    else:
82
        newG._adj = G._adj
83
    return newG
84

    
85

    
86
def subgraph_view(G, filter_node=no_filter, filter_edge=no_filter):
87
    newG = nx.freeze(G.__class__())
88
    newG._NODE_OK = filter_node
89
    newG._EDGE_OK = filter_edge
90

    
91
    # create view by assigning attributes from G
92
    newG._graph = G
93
    newG.graph = G.graph
94

    
95
    newG._node = FilterAtlas(G._node, filter_node)
96
    if G.is_multigraph():
97
        Adj = FilterMultiAdjacency
98

    
99
        def reverse_edge(u, v, k): return filter_edge(v, u, k)
100
    else:
101
        Adj = FilterAdjacency
102

    
103
        def reverse_edge(u, v): return filter_edge(v, u)
104
    if G.is_directed():
105
        newG._succ = Adj(G._succ, filter_node, filter_edge)
106
        newG._pred = Adj(G._pred, filter_node, reverse_edge)
107
        newG._adj = newG._succ
108
    else:
109
        newG._adj = Adj(G._adj, filter_node, filter_edge)
110
    return newG
111

    
112

    
113
def reverse_view(G):
114
    if not G.is_directed():
115
        msg = "not implemented for undirected type"
116
        raise NetworkXNotImplemented(msg)
117
    newG = generic_graph_view(G)
118
    newG._succ, newG._pred = G._pred, G._succ
119
    newG._adj = newG._succ
120
    return newG
121

    
122

    
123
# The remaining definitions are for backward compatibility with v2.0 and 2.1
124
def ReverseView(G):
125
    # remove by v3 if not before
126
    import warnings
127
    msg = 'ReverseView is deprecated. Use reverse_view instead'
128
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
129
    return reverse_view(G)
130

    
131

    
132
def SubGraph(G, filter_node=no_filter, filter_edge=no_filter):
133
    # remove by v3 if not before
134
    import warnings
135
    msg = 'SubGraph is deprecated. Use subgraph_view instead'
136
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
137
    return subgraph_view(G, filter_node, filter_edge)
138

    
139

    
140
def GraphView(G):
141
    # remove by v3 if not before
142
    import warnings
143
    msg = 'GraphView is deprecated. Use generic_graph_view instead'
144
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
145
    return generic_graph_view(G, Graph)
146

    
147

    
148
def DiGraphView(G):
149
    # remove by v3 if not before
150
    import warnings
151
    msg = 'GraphView is deprecated. Use generic_graph_view instead'
152
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
153
    return generic_graph_view(G, DiGraph)
154

    
155

    
156
def MultiGraphView(G):
157
    # remove by v3 if not before
158
    import warnings
159
    msg = 'GraphView is deprecated. Use generic_graph_view instead'
160
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
161
    return generic_graph_view(G, MultiGraph)
162

    
163

    
164
def MultiDiGraphView(G):
165
    # remove by v3 if not before
166
    import warnings
167
    msg = 'GraphView is deprecated. Use generic_graph_view instead'
168
    warnings.warn(msg, category=DeprecationWarning, stacklevel=2)
169
    return generic_graph_view(G, MultiDiGraph)
170

    
171

    
172
MultiReverseView = ReverseView
173
SubMultiGraph = SubMultiDiGraph = SubDiGraph = SubGraph