networkx.algorithms.minors.quotient_graph¶
- quotient_graph(G, partition, edge_relation=None, node_data=None, edge_data=None, relabel=False, create_using=None)[source]¶
Returns the quotient graph of
G
under the specified equivalence relation on nodes.- Parameters
- GNetworkX graph
The graph for which to return the quotient graph with the specified node relation.
- partitionfunction, or dict or list of lists, tuples or sets
If a function, this function must represent an equivalence relation on the nodes of
G
. It must take two arguments u and v and return True exactly when u and v are in the same equivalence class. The equivalence classes form the nodes in the returned graph.If a dict of lists/tuples/sets, the keys can be any meaningful block labels, but the values must be the block lists/tuples/sets (one list/tuple/set per block), and the blocks must form a valid partition of the nodes of the graph. That is, each node must be in exactly one block of the partition.
If a list of sets, the list must form a valid partition of the nodes of the graph. That is, each node must be in exactly one block of the partition.
- edge_relationBoolean function with two arguments
This function must represent an edge relation on the blocks of the
partition
ofG
. It must take two arguments, B and C, each one a set of nodes, and return True exactly when there should be an edge joining block B to block C in the returned graph.If
edge_relation
is not specified, it is assumed to be the following relation. Block B is related to block C if and only if some node in B is adjacent to some node in C, according to the edge set ofG
.- edge_datafunction
This function takes two arguments, B and C, each one a set of nodes, and must return a dictionary representing the edge data attributes to set on the edge joining B and C, should there be an edge joining B and C in the quotient graph (if no such edge occurs in the quotient graph as determined by
edge_relation
, then the output of this function is ignored).If the quotient graph would be a multigraph, this function is not applied, since the edge data from each edge in the graph
G
appears in the edges of the quotient graph.- node_datafunction
This function takes one argument, B, a set of nodes in
G
, and must return a dictionary representing the node data attributes to set on the node representing B in the quotient graph. If None, the following node attributes will be set:‘graph’, the subgraph of the graph
G
that this block represents,‘nnodes’, the number of nodes in this block,
‘nedges’, the number of edges within this block,
‘density’, the density of the subgraph of
G
that this block represents.
- relabelbool
If True, relabel the nodes of the quotient graph to be nonnegative integers. Otherwise, the nodes are identified with
frozenset
instances representing the blocks given inpartition
.- create_usingNetworkX graph constructor, optional (default=nx.Graph)
Graph type to create. If graph instance, then cleared before populated.
- Returns
- Raises
- NetworkXException
If the given partition is not a valid partition of the nodes of
G
.
References
- 1
Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj. Generalized Blockmodeling. Cambridge University Press, 2004.
Examples
The quotient graph of the complete bipartite graph under the “same neighbors” equivalence relation is
K_2
. Under this relation, two nodes are equivalent if they are not adjacent but have the same neighbor set.>>> G = nx.complete_bipartite_graph(2, 3) >>> same_neighbors = lambda u, v: ( ... u not in G[v] and v not in G[u] and G[u] == G[v] ... ) >>> Q = nx.quotient_graph(G, same_neighbors) >>> K2 = nx.complete_graph(2) >>> nx.is_isomorphic(Q, K2) True
The quotient graph of a directed graph under the “same strongly connected component” equivalence relation is the condensation of the graph (see
condensation()
). This example comes from the Wikipedia article `Strongly connected component`_.>>> G = nx.DiGraph() >>> edges = [ ... "ab", ... "be", ... "bf", ... "bc", ... "cg", ... "cd", ... "dc", ... "dh", ... "ea", ... "ef", ... "fg", ... "gf", ... "hd", ... "hf", ... ] >>> G.add_edges_from(tuple(x) for x in edges) >>> components = list(nx.strongly_connected_components(G)) >>> sorted(sorted(component) for component in components) [['a', 'b', 'e'], ['c', 'd', 'h'], ['f', 'g']] >>> >>> C = nx.condensation(G, components) >>> component_of = C.graph["mapping"] >>> same_component = lambda u, v: component_of[u] == component_of[v] >>> Q = nx.quotient_graph(G, same_component) >>> nx.is_isomorphic(C, Q) True
Node identification can be represented as the quotient of a graph under the equivalence relation that places the two nodes in one block and each other node in its own singleton block.
>>> K24 = nx.complete_bipartite_graph(2, 4) >>> K34 = nx.complete_bipartite_graph(3, 4) >>> C = nx.contracted_nodes(K34, 1, 2) >>> nodes = {1, 2} >>> is_contracted = lambda u, v: u in nodes and v in nodes >>> Q = nx.quotient_graph(K34, is_contracted) >>> nx.is_isomorphic(Q, C) True >>> nx.is_isomorphic(Q, K24) True
The blockmodeling technique described in [1] can be implemented as a quotient graph.
>>> G = nx.path_graph(6) >>> partition = [{0, 1}, {2, 3}, {4, 5}] >>> M = nx.quotient_graph(G, partition, relabel=True) >>> list(M.edges()) [(0, 1), (1, 2)]
Here is the sample example but using partition as a dict of block sets.
>>> G = nx.path_graph(6) >>> partition = {0: {0, 1}, 2: {2, 3}, 4: {4, 5}} >>> M = nx.quotient_graph(G, partition, relabel=True) >>> list(M.edges()) [(0, 1), (1, 2)]
Partitions can be represented in various ways:
(0) a list/tuple/set of block lists/tuples/sets (1) a dict with block labels as keys and blocks lists/tuples/sets as values (2) a dict with block lists/tuples/sets as keys and block labels as values (3) a function from nodes in the original iterable to block labels (4) an equivalence relation function on the target iterable
As
quotient_graph
is designed to accept partitions represented as (0), (1) or (4) only, theequivalence_classes
function can be used to get the partitions in the right form, in order to callquotient_graph
.