Lecture
The Malgrange algorithm — a method for partitioning a graph into strongly connected subgraphs.
A directed graph (digraph) is called strongly connected (English: strongly connected) if any two of its vertices s and t are strongly connected, that is, if there exists a directed path from 
to 
and, at the same time, a directed path from to 
The strongly connected components of a digraph are its maximal (by inclusion) strongly connected subgraphs. The strong connectivity region is the set of vertices of the strongly connected components.
A digraph that does not belong to the class of strongly connected graphs contains some set of strongly connected components, and some set of directed edges going from one component to another.
Any vertex of a digraph is strongly connected to itself.
A directed graph with its strongly connected components shown
The figure shows a digraph in which all three strongly connected components are indicated (shaded regions outlined with a dotted line).
Let a graph 
be given, where
is the set of vertices, in which ¯
, and 
is the set of arcs described by the adjacency matrix, in which 
. The partitioning algorithm is as follows:
we find the direct 
and inverse 
transitive closures.
. The set of vertices of this intersection form the vertices of the maximal strongly connected subgraph
.
.
as the original graph, and while 
steps 1, 2, 3 of the algorithm are repeated.The direct transitive closure is built using the function dfs, which takes as parameters the adjacency lists of the vertices g (the graph configuration, which does not change during the function's execution), the vertex v being examined, and a list of visited-vertex indicators used. At the start of the function, vertex v is marked as visited, and then for each unvisited vertex u to which there is an arc from v, the function dfs is called recursively.
The inverse transitive closure is built using the function inverse_dfs. It works similarly to dfs, but the recursive call to inverse_dfs is made for each unvisited vertex w from which there is an arc to vertex v. To determine which vertices have an arc to v, all vertices are checked for the presence of v in their adjacency lists.
The transitive closures themselves (direct and inverse) are actually built by the functions find_direct_transitive and find_inverse_transitive, which, for the selected vertex v, call the dfs and inverse_dfs functions described above, respectively, and return the list of visited vertices.
The find_components procedure works with the direct and inverse transitive closures already built for the selected vertex v. This procedure looks for vertices that belong to the same component as vertex v. The procedure also marks the found vertices and vertex v as visited, so that the same component is not searched for more than once.
Finally, the procedure malgranzh_strong performs a complete search for components in the given graph. All vertices of the graph are examined. Initially, all vertices are marked as unvisited. If the next vertex has not been visited, its direct and inverse transitive closures are found using the functions find_direct_transitive and find_inverse_transitive, and then the function find_components is called for that vertex. The vertex itself, and those vertices that fell into the same component with it, are marked as used and are not considered in the further search for components. The found component is stored in the list of components.
The program code implementing the Malgrange algorithm is given in Appendix A.
File MalgranzhStrong.cpp:
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
void dfs_inverse(vector <list <int>> g, vector <bool> & used, int v)
{
used[v] = true;
for (int u = 0; u < g.size(); u++)
for (int w : g[u])
if (w == v && !used[u])
dfs_inverse(g, used, u);
}
void dfs(vector <list <int>> g, vector <bool> & used, int v)
{
used[v] = true;
for (int u : g[v])
if (!used[u])
dfs(g, used, u);
}
vector <bool> find_direct_transitive(vector <list <int>> g, int u)
{
vector <bool> used(g.size(), false);
dfs(g, used, u);
return used;
}
vector <bool> find_inverse_transitive(vector <list <int>> g, int u)
{
vector <bool> used(g.size(), false);
dfs_inverse(g, used, u);
return used;
}
void find_component(vector <bool> direct_transitive, vector <bool> inverse_transitive, vector <bool> & used, vector <int> & component)
{
for (int u = 0; u < used.size(); u++)
if (!used[u])
{
used[u] = direct_transitive[u] && inverse_transitive[u];
if (used[u])
component.push_back(u);
}
}
void malgranzh_strong(vector <list <int>> g, vector <vector <int>> & components)
{
vector <bool> used(g.size(), false);
for (int u = 0; u < g.size(); u++)
if (!used[u])
{
vector <int> component;
// Obtain the direct transitive closure for vertex v
vector <bool> direct_transitive = find_direct_transitive(g, u);
// Obtain the inverse transitive closure for vertex v
vector <bool> inverse_transitive = find_inverse_transitive(g, u);
// Find the strongly connected component
find_component(direct_transitive, inverse_transitive, used, component);
// Store the strongly connected component
components.push_back(component);
}
}
int main()
{
ifstream rd("graph.txt");
int n;
rd >> n;
vector <list <int>> g(n);
while (!rd.eof())
{
int u, v;
rd >> u >> v;
g[u - 1].push_back(v - 1);
}
rd.close();
vector <vector <int>> components;
malgranzh_strong(g, components);
for (int i = 0; i < components.size(); i++)
{
cout << "Component:";
for (int v : components[i])
cout << " " << v + 1;
cout << endl;
}
system("pause");
return 0;
}
Comments