Skip to main content
`Ctrl`+`K`

# transitive_reduction

transitive_reduction(G)

  Returns transitive reduction of a directed graph

  The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is in E and there is no path from v to w in G with length greater than 1.

  Parameters:
    G NetworkX DiGraph

      A directed acyclic graph (DAG)

  Returns:
    NetworkX DiGraph

      The transitive reduction of `G`

  Raises:
    NetworkXError

      If `G` is not a directed acyclic graph (DAG) transitive reduction is not uniquely defined and a `NetworkXError` exception is raised.

  References

  https://en.wikipedia.org/wiki/Transitive_reduction

  Examples

  To perform transitive reduction on a DiGraph:

      >>> DG = nx.DiGraph([(1, 2), (2, 3), (1, 3)])
      >>> TR = nx.transitive_reduction(DG)
      >>> list(TR.edges)
      [(1, 2), (2, 3)]

  To avoid unnecessary data copies, this implementation does not return a DiGraph with node/edge data. To perform transitive reduction on a DiGraph and transfer node/edge data:

      >>> DG = nx.DiGraph()
      >>> DG.add_edges_from([(1, 2), (2, 3), (1, 3)], color="red")
      >>> TR = nx.transitive_reduction(DG)
      >>> TR.add_nodes_from(DG.nodes(data=True))
      >>> TR.add_edges_from((u, v, DG.edges[u, v]) for u, v in TR.edges)
      >>> list(TR.edges(data=True))
      [(1, 2, {'color': 'red'}), (2, 3, {'color': 'red'})]