# networkx.algorithms.dag.transitive_reduction¶

transitive_reduction(G)[source]

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