# Copyright (C) 2004-2017 by # Aric Hagberg # Dan Schult # Pieter Swart # All rights reserved. # BSD license. # # Author: Aric Hagberg (hagberg@lanl.gov), # Pieter Swart (swart@lanl.gov), # Dan Schult(dschult@colgate.edu) """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 orginal graph object. We provide three attributes related to the underlying graph object. G._graph : the parent graph used for looking up graph data. G.root_graph : the root graph of the potential chain of views. For example, if you have a subgraph of a reversed view of an edge_subgraph of a graph, this points to original graph. G.fresh_copy() : a method to return a null copy of the graph represented by the view. This is useful if you want to create a graph with the same data structure (directed/multi) as the current view. This is similar to G.root_graph.__class__() but reflects the fact that (Un)DirectedView could make the type of data structure different from the root_graph. 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. """ from collections import Mapping from networkx.classes import Graph, DiGraph, MultiGraph, MultiDiGraph from networkx.classes.coreviews import ReadOnlyGraph, \ AtlasView, AdjacencyView, MultiAdjacencyView, \ FilterAtlas, FilterAdjacency, FilterMultiAdjacency, \ UnionAdjacency, UnionMultiAdjacency from networkx.classes.filters import no_filter, show_nodes, show_edges from networkx.exception import NetworkXError, NetworkXNotImplemented from networkx.utils import not_implemented_for __all__ = ['SubGraph', 'SubDiGraph', 'SubMultiGraph', 'SubMultiDiGraph', 'ReverseView', 'MultiReverseView', 'DiGraphView', 'MultiDiGraphView', 'GraphView', 'MultiGraphView', ] class SubGraph(ReadOnlyGraph, Graph): def __init__(self, graph, filter_node=no_filter, filter_edge=no_filter): self._graph = graph self.root_graph = graph.root_graph self._NODE_OK = filter_node self._EDGE_OK = filter_edge # Set graph interface self.graph = graph.graph self._node = FilterAtlas(graph._node, filter_node) self._adj = FilterAdjacency(graph._adj, filter_node, filter_edge) class SubDiGraph(ReadOnlyGraph, DiGraph): def __init__(self, graph, filter_node=no_filter, filter_edge=no_filter): self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self._NODE_OK = filter_node self._EDGE_OK = filter_edge # Set graph interface self.graph = graph.graph self._node = FilterAtlas(graph._node, filter_node) self._adj = FilterAdjacency(graph._adj, filter_node, filter_edge) self._pred = FilterAdjacency(graph._pred, filter_node, lambda u, v: filter_edge(v, u)) self._succ = self._adj class SubMultiGraph(ReadOnlyGraph, MultiGraph): def __init__(self, graph, filter_node=no_filter, filter_edge=no_filter): self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self._NODE_OK = filter_node self._EDGE_OK = filter_edge # Set graph interface self.graph = graph.graph self._node = FilterAtlas(graph._node, filter_node) self._adj = FilterMultiAdjacency(graph._adj, filter_node, filter_edge) class SubMultiDiGraph(ReadOnlyGraph, MultiDiGraph): def __init__(self, graph, filter_node=no_filter, filter_edge=no_filter): self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self._NODE_OK = filter_node self._EDGE_OK = filter_edge # Set graph interface self.graph = graph.graph self._node = FilterAtlas(graph._node, filter_node) FMA = FilterMultiAdjacency self._adj = FMA(graph._adj, filter_node, filter_edge) self._pred = FMA(graph._pred, filter_node, lambda u, v, k: filter_edge(v, u, k)) self._succ = self._adj class ReverseView(ReadOnlyGraph, DiGraph): def __init__(self, graph): if not graph.is_directed(): msg = "not implemented for undirected type" raise NetworkXNotImplemented(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph # Set graph interface self.graph = graph.graph self._node = graph._node self._adj = graph._pred self._pred = graph._succ self._succ = self._adj class MultiReverseView(ReadOnlyGraph, MultiDiGraph): def __init__(self, graph): if not graph.is_directed(): msg = "not implemented for undirected type" raise NetworkXNotImplemented(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph # Set graph interface self.graph = graph.graph self._node = graph._node self._adj = graph._pred self._pred = graph._succ self._succ = self._adj class DiGraphView(ReadOnlyGraph, DiGraph): def __init__(self, graph): if graph.is_multigraph(): msg = 'Wrong View class. Use MultiDiGraphView.' raise NetworkXError(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self.graph = graph.graph self._node = graph._node if graph.is_directed(): self._pred = graph._pred self._succ = graph._succ else: self._pred = graph._adj self._succ = graph._adj self._adj = self._succ class MultiDiGraphView(ReadOnlyGraph, MultiDiGraph): def __init__(self, graph): if not graph.is_multigraph(): msg = 'Wrong View class. Use DiGraphView.' raise NetworkXError(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self.graph = graph.graph self._node = graph._node if graph.is_directed(): self._pred = graph._pred self._succ = graph._succ else: self._pred = graph._adj self._succ = graph._adj self._adj = self._succ class GraphView(ReadOnlyGraph, Graph): UnionAdj = UnionAdjacency def __init__(self, graph): if graph.is_multigraph(): msg = 'Wrong View class. Use MultiGraphView.' raise NetworkXError(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self.graph = graph.graph self._node = graph._node if graph.is_directed(): self._adj = self.UnionAdj(graph._succ, graph._pred) else: self._adj = graph._adj class MultiGraphView(ReadOnlyGraph, MultiGraph): UnionAdj = UnionMultiAdjacency def __init__(self, graph): if not graph.is_multigraph(): msg = 'Wrong View class. Use GraphView.' raise NetworkXError(msg) self._graph = graph self.root_graph = graph while hasattr(self.root_graph, '_graph'): self.root_graph = self.root_graph._graph self.graph = graph.graph self._node = graph._node if graph.is_directed(): self._adj = self.UnionAdj(graph._succ, graph._pred) else: self._adj = graph._adj