# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Condense a graph by contracting strongly connected components

Contributed by:
Jon McLoone

ResourceFunction["CondenseGraph"][ contracts each strongly connected component of a directed graph |

The condensation of a directed graph is formed by contracting each strongly connected component into a single vertex.

A graph is strongly connected if every vertex can be reached from every other vertex via an edge path. A subgraph is strongly connected if this holds for vertices and edges within the subgraph.

Condensation of undirected graphs results in disconnected vertices.

Inforrmation about specific edges and vertices, such as capacity, cost and coordinates is discarded.

Vertices 1, 2 and 3 of this graph are strongly connected and are replaced with a single vertex in the condensation graph:

In[1]:= |

Out[1]= |

Each separate strongly connected subgraph is replaced with a different vertex:

In[2]:= |

Out[2]= |

Self-loops are included in the new vertex:

In[3]:= |

Out[3]= |

Disconnected components remain disconnected:

In[4]:= |

Out[4]= |

Graph condensation discards undirected edges. Condensing an undirected graph will result in disconnected vertices:

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

A condensation graph is acyclic:

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

A directed graph is acyclic, if and only if its condensation is isomorphic to itself:

In[9]:= |

Out[9]= |

Wolfram Language 13.0 (December 2021) or above

- 1.0.0 – 22 March 2024

This work is licensed under a Creative Commons Attribution 4.0 International License