Strongly connected component

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Strongly connected component

Post by tryit1 »

Code: Select all


Where do we start the DFS from in SCC algorithm so that it we don't have to call it many times.

1) I run tarjan algorithm to find SCC first by trying all vertices of indegree 0. Find the SCC and store them in a set with one of the node as new vertex(NV). 
2) Check for each  new vertex (NV) edges from other sets.

This is slow (0.7 s on 11504) or even the { dfs(G), dfs(transpose(G)) algorithm } is slow in my case .


I do something like 
for(i=1;i<=N;i++) if(!visit[i]) dfs(i), now if we have a graph like 3->2->1 , it is going to visit 3 ,2 ,1 .

Can we make it faster.

Below is my code i run 2 dfs , one to find the connected components. 2nd to condense and get the acylic graph. Can this be done in a better way.

#define MAX 100010
//vector < vector < int > > arr (MAX);
//vector < set < int  > >out (MAX);
vector < vector < int >>arr (MAX);
vector < set < int >>out (MAX);
int p[MAX], r[MAX], inv[MAX];
int num[MAX], low[MAX], visit[MAX], top = -1, st[MAX], ind[MAX], visit1[MAX];
int tme;
int N, E;

/* START OF UNION FIND */
inline void
makeset (int x)
{
  p[x] = x;
  r[x] = 0;
}

inline int
findp (int x)
{
  if (x == p[x])
    return x;
  return p[x] = findp (p[x]);
}


inline void
union_set (int a, int b)
{

  a = findp (a);
  b = findp (b);

  if (a == b)
    return;

  if (r[a] > r[b])
    p[b] = a;
  else
    {
      p[a] = b;
      if (r[a] == r[b])
	r[b]++;
    }
}

/*END OF UNION _FIND */

/* FORM THE SCC FROM TARJAN ALGORITHM */
void
dfs (int x)
{
  //printf("Going into x=%d\n",x);
  visit[x] = 1;
  low[x] = num[x] = ++tme;
  st[++top] = x;
  int i, k;
  for (i = 0; i < arr[x].size (); i++)
    {
      k = arr[x][i];

      // THIS IS SO THAT IF WE VISITED SOME VERTEX Z prior to THIS VERTEX X  just becaue Z is number earlier , the num of it is not valid nor is the low

      if (inv[k])	continue;

      if (!visit[k])
	{
	  dfs (k);
	  low[x] = min (low[x], low[k]);
	}
      else
	low[x] = min (low[x], num[k]);
    }
  if (low[x] == num[x])
    {
      makeset (x);

      //     printf ("connected\n");
      do
	{
//        printf ("%d,", st[top]);
	  makeset (st[top]);
	  union_set (st[top], x);
	  inv[st[top]] = 1;
//        scc[x].insert(st[top]);
	}
      while (st[top--] != x);
//      printf ("\n");
    }
}

/* GET THE ACYCLIC DAG AND FIND THE NUMBER OF DISJOINT COMPONENTS */
void
dfs1 (int x)
{

  if (visit1[x])
    return;
  visit1[x] = 1;
  set < int >::iterator it;
  for (it = out[x].begin (); it != out[x].end (); it++)
    {
      dfs1 (*it);
    }
}

int
main ()
{
     // POPULATE GRAPH 
      tme = 0;
      for (i = 0; i < E; i++)
	{
	  scanf (" %d %d", &x, &y);
	  arr[x].push_back (y);
	  ind[y]++;
	}
      int total = 0;
      // CHECK FOR VERTICES WITH INDEGREE 0 and RUN DFS
      for (i = 1; i <= N; i++)
	{
	  if (!visit[i] && (ind[i] == 0))
	    {
	      top = -1;
	      dfs (i);
	    }
	}

// IF ALL THE VERTICES ARE PART OF A SCC
      for (i = 1; i <= N; i++)
	{
	  if (!visit[i])
	    {
	      top = -1;
	      dfs (i);
	    }
	}



      memset (ind, 0, sizeof (ind));
      int j, p = 0;
// GET THE SCC SET, TRY TO BUILD GRAPH FROM CONDENSED VERTEX TO OTHER CONDENSED VERTICES
      for (i = 1; i <= N; i++)
	{
	  for (p = 0; p < arr[i].size (); p++)
	    {
	      j = arr[i][p];
	      if (findp (i) != findp (j))
		{
		  if (out[findp (i)].count (findp (j)) == 0)
		    {
//                   printf("edge from %d to %d\n",findp(i),findp(j));
		      out[findp (i)].insert (findp (j));
		      ind[findp (j)]++;
		    }
		}
	    }
	}

/* CHECK IF THIS IS THE PARENT OF THE SCC AND ITS INDEGREE IS 0 , in a condensed DAG it is always possible 
i think  The call to visit1 is superfluous
*/
      for (i = 1; i <= N; i++)
	{
	  if ((findp (i) == i) && (visit1[i] == 0) && (ind[i] == 0))
	    {
//            printf("#%d,",i);
	      dfs1 (i);
	      total++;
	    }
	}

      printf ("%d\n", total);
    }

  return 0;
}




roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: Strongly connected component

Post by roticv »

Hello,

For Tarjan's algorithm, the main problem that caused that might slow down the algorithm is the part about checking whether the node is in the stack. I used direct addressing table, ie if node 5 is in the stack, I have an array inS[5] = true; With that I managed to get my runtime for 11504 to 0.460s.

In that question it is possible that there are 100 000 nodes which is a huge number.

Regards,
Victor

Post Reply

Return to “Algorithms”