Find isolated components in graph

Question

What is the best algorithm for finding isolated components in a graph? That is, components that do not lose information.

In this image, the only isolated component is H, because it only receives "information".

Answer 1

It is difficult to understand what is being asked, because both your question and some sources I have consulted use different names for the same concept, and vice versa. I will define some terms, some in Portuguese and others in English, according to what I could understand:

• strongly Connected Component ("strongly connected components"): sets of vertices in which each has a path to the other. In your question, would be the 4 sets outlined ({a,b,e}, {c,d}, {f,g} and {h}).

• sorvedgold (Sink): in the case of vertices, they are vertices that have no edges coming out of it at most by entering; in the case of a set of vertices, sets in which no vertices have edges coming out. In your case, the whole {h} is a sorvedouro. The vertex h, on the other hand, it has an incoming edge - the one that comes out of itself.

• isolated set: a set of vertices that is both a source and a sorvedouro. In other words, sets that have no edges in or out - just between their own vertices. In their case, there are no non-trivial isolated sets (i.e. the empty set, and the set of all vertices).

If you already have a list of strongly Connected Components, and wants to know which ones are sorvedores, do as @utluiz suggested in the comments: check all the vertices of a component, if all the edges leaving lead only to vertices in the component itself. If that’s true, that component is sorvedouro. If some vertex in the component leads to another outside of the component, then the component is not a sorvedouro.

If your problem on the other hand is finding these strongly Connected Components, there is already more complicated. I will transcribe here (translating freely) the algorithm proposed in "Introduction to Algorithms", but without going into too much detail because the content is quite extensive.

STRONGLY-CONNECTED-COMPONENTS(G)

1. Chame DFS(G) para encontrar os tempos de término f[u] de cada vértice u
2. Faça a tranposição de G (Gt)
3. Chame DFS(Gt), mas no loop principal itere na ordem decrescente de f[u]
                                           (tal como computado no passo 1)
4. Os vértices de cada árvore na floresta do passo 3 são um strongly connected component

In case you already have the end times f[u] (in your example figure, are the numbers inside each vertex, after the bar: d[u]/f[u]), just call DFS in the transposed graph. I won’t put here the transpose algorithm, because it must be trivial (just reverse the direction of all edges).

---

DFS is the deep search algorithm. d[u] and f[u] are by-products of this algorithm, showing the order in which each vertex was visited (d[u] is the moment when the vertex was first found, and f[u] the time when all its outgoing edges were visited). I will not transcribe the algorithm from the same book, as the link above gives a more comprehensible implementation, in C++. I will only adapt it to include f[u], since the original only contemplates d[u] (there called pre).

/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */
static int conta, d[maxV], f[maxV];

/* A função DIGRAPHdfs visita todos os vértices e todos os arcos do digrafo G.
   A função atribui um número de ordem d[x] a cada vértice x:  o k-ésimo vértice visitado
   recebe número de ordem k.  (Código inspirado no programa 18.3 de Sedgewick.) */
void DIGRAPHdfs( Digraph G) 
{ 
   Vertex v;
   conta = 0;
   for (v = 0; v < G->V; v++) 
      d[v] = -1;
   for (v = 0; v < G->V; v++)
      if (d[v] == -1) 
         dfsR( G, v);
}

/* A função dfsR supõe que o digrafo G é representado por uma matriz de adjacência.
  (Inspirado no programas 18.1 de Sedgewick.) */
void dfsR( Digraph G, Vertex v) 
{ 
   Vertex w;
   d[v] = conta++; 
   for (w = 0; w < G->V; w++)
      if (G->adj[v][w] != 0 && d[w] == -1)
         dfsR( G, w); 
   f[v] = conta++;
}

Alternative to graphs represented by an adjacency list (also adapted):

/* A função dfsR supõe que o digrafo G é representado por listas de adjacência.
  (Inspirado no programas 18.2 de Sedgewick.) */
void dfsR( Digraph G, Vertex v) 
{ 
   link a; 
   d[v] = conta++; 
   for (a = G->adj[v]; a != NULL; a = a->next)
      if (d[a->w] == -1) 
         dfsR( G, a->w); 
   f[v] = conta++; 
}

---

If step 4 of the main algorithm is not clear, the "forest" that interests you is formed by all the vertices visited in DIGRAPHdfs. That is, if the first vertex has d[u] = 0 and f[u] = N, every vertex it has d[u] > 0 e f[u] < N are part of this tree. The next tree would be the vertex with d[u] = N+1 and f[u] = M, and so on until the vertices are finished.

Note: according to the cited source, the above algorithm is efficient (linear time in V + A) and although it doesn’t seem correct - the proof is in 4 pages of theorems that I won’t transcribe here.