File size: 6,568 Bytes
4cef980 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
"""View of Graphs as SubGraph, Reverse, Directed, Undirected.
In some algorithms it is convenient to temporarily morph
a graph to exclude some nodes or edges. It should be better
to do that via a view than to remove and then re-add.
In other algorithms it is convenient to temporarily morph
a graph to reverse directed edges, or treat a directed graph
as undirected, etc. This module provides those graph views.
The resulting views are essentially read-only graphs that
report data from the original graph object. We provide an
attribute G._graph which points to the underlying graph object.
Note: Since graphviews look like graphs, one can end up with
view-of-view-of-view chains. Be careful with chains because
they become very slow with about 15 nested views.
For the common simple case of node induced subgraphs created
from the graph class, we short-cut the chain by returning a
subgraph of the original graph directly rather than a subgraph
of a subgraph. We are careful not to disrupt any edge filter in
the middle subgraph. In general, determining how to short-cut
the chain is tricky and much harder with restricted_views than
with induced subgraphs.
Often it is easiest to use .copy() to avoid chains.
"""
import networkx as nx
from networkx.classes.coreviews import (
FilterAdjacency,
FilterAtlas,
FilterMultiAdjacency,
UnionAdjacency,
UnionMultiAdjacency,
)
from networkx.classes.filters import no_filter
from networkx.exception import NetworkXError
from networkx.utils import not_implemented_for
__all__ = ["generic_graph_view", "subgraph_view", "reverse_view"]
def generic_graph_view(G, create_using=None):
if create_using is None:
newG = G.__class__()
else:
newG = nx.empty_graph(0, create_using)
if G.is_multigraph() != newG.is_multigraph():
raise NetworkXError("Multigraph for G must agree with create_using")
newG = nx.freeze(newG)
# create view by assigning attributes from G
newG._graph = G
newG.graph = G.graph
newG._node = G._node
if newG.is_directed():
if G.is_directed():
newG._succ = G._succ
newG._pred = G._pred
# newG._adj is synced with _succ
else:
newG._succ = G._adj
newG._pred = G._adj
# newG._adj is synced with _succ
elif G.is_directed():
if G.is_multigraph():
newG._adj = UnionMultiAdjacency(G._succ, G._pred)
else:
newG._adj = UnionAdjacency(G._succ, G._pred)
else:
newG._adj = G._adj
return newG
def subgraph_view(G, filter_node=no_filter, filter_edge=no_filter):
"""View of `G` applying a filter on nodes and edges.
`subgraph_view` provides a read-only view of the input graph that excludes
nodes and edges based on the outcome of two filter functions `filter_node`
and `filter_edge`.
The `filter_node` function takes one argument --- the node --- and returns
`True` if the node should be included in the subgraph, and `False` if it
should not be included.
The `filter_edge` function takes two (or three arguments if `G` is a
multi-graph) --- the nodes describing an edge, plus the edge-key if
parallel edges are possible --- and returns `True` if the edge should be
included in the subgraph, and `False` if it should not be included.
Both node and edge filter functions are called on graph elements as they
are queried, meaning there is no up-front cost to creating the view.
Parameters
----------
G : networkx.Graph
A directed/undirected graph/multigraph
filter_node : callable, optional
A function taking a node as input, which returns `True` if the node
should appear in the view.
filter_edge : callable, optional
A function taking as input the two nodes describing an edge (plus the
edge-key if `G` is a multi-graph), which returns `True` if the edge
should appear in the view.
Returns
-------
graph : networkx.Graph
A read-only graph view of the input graph.
Examples
--------
>>> G = nx.path_graph(6)
Filter functions operate on the node, and return `True` if the node should
appear in the view:
>>> def filter_node(n1):
... return n1 != 5
...
>>> view = nx.subgraph_view(G, filter_node=filter_node)
>>> view.nodes()
NodeView((0, 1, 2, 3, 4))
We can use a closure pattern to filter graph elements based on additional
data --- for example, filtering on edge data attached to the graph:
>>> G[3][4]["cross_me"] = False
>>> def filter_edge(n1, n2):
... return G[n1][n2].get("cross_me", True)
...
>>> view = nx.subgraph_view(G, filter_edge=filter_edge)
>>> view.edges()
EdgeView([(0, 1), (1, 2), (2, 3), (4, 5)])
>>> view = nx.subgraph_view(G, filter_node=filter_node, filter_edge=filter_edge,)
>>> view.nodes()
NodeView((0, 1, 2, 3, 4))
>>> view.edges()
EdgeView([(0, 1), (1, 2), (2, 3)])
"""
newG = nx.freeze(G.__class__())
newG._NODE_OK = filter_node
newG._EDGE_OK = filter_edge
# create view by assigning attributes from G
newG._graph = G
newG.graph = G.graph
newG._node = FilterAtlas(G._node, filter_node)
if G.is_multigraph():
Adj = FilterMultiAdjacency
def reverse_edge(u, v, k=None):
return filter_edge(v, u, k)
else:
Adj = FilterAdjacency
def reverse_edge(u, v, k=None):
return filter_edge(v, u)
if G.is_directed():
newG._succ = Adj(G._succ, filter_node, filter_edge)
newG._pred = Adj(G._pred, filter_node, reverse_edge)
# newG._adj is synced with _succ
else:
newG._adj = Adj(G._adj, filter_node, filter_edge)
return newG
@not_implemented_for("undirected")
def reverse_view(G):
"""View of `G` with edge directions reversed
`reverse_view` returns a read-only view of the input graph where
edge directions are reversed.
Identical to digraph.reverse(copy=False)
Parameters
----------
G : networkx.DiGraph
Returns
-------
graph : networkx.DiGraph
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edge(1, 2)
>>> G.add_edge(2, 3)
>>> G.edges()
OutEdgeView([(1, 2), (2, 3)])
>>> view = nx.reverse_view(G)
>>> view.edges()
OutEdgeView([(2, 1), (3, 2)])
"""
newG = generic_graph_view(G)
newG._succ, newG._pred = G._pred, G._succ
# newG._adj is synced with _succ
return newG
|