networkx.algorithms.minors.quotient_graph

quotient_graph(G, partition, edge_relation=None, node_data=None, edge_data=None, relabel=False, create_using=None)

Returns the quotient graph of G under the specified equivalence relation on nodes.

Parameters

• G (NetworkX graph) – The graph for which to return the quotient graph with the specified node relation.

• partition (function or list of 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 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_relation (Boolean function with two arguments) – This function must represent an edge relation on the blocks of G in the partition induced by node_relation. 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 of G.

• edge_data (function) – 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_data (function) – 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.

• relabel (bool) – 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 in partition.

• create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.

Returns

The quotient graph of G under the equivalence relation specified by partition. If the partition were given as a list of set instances and relabel is False, each node will be a frozenset corresponding to the same set.

Return type

NetworkX graph

Raises

NetworkXException – If the given partition is not a valid partition of the nodes of G.

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)]

References

1

Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj. Generalized Blockmodeling. Cambridge University Press, 2004.