nownikhil's blog

Finding cycles in a directed Graph
By nownikhil, 11 years ago, In English

Can anyone suggest me a method for finding all the cycles and their lengths in a directed graph. Cycles might be overlapping. Lets say the graph had 2 OVERLAPPING cycles, so answer should be 3 along with their lengths. We must find smaller as well as larger cycles in the graph.

Thanks in advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it 
int n;
vector < vector<int> > g;
vector<char> cl;
vector<int> p;
int cycle_st, cycle_end;

bool dfs (int v) {
	cl[v] = 1;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (cl[to] == 0) {
			p[to] = v;
			if (dfs (to))  return true;
		}
		else if (cl[to] == 1) {
			cycle_end = v;
			cycle_st = to;
			return true;
		}
	}
	cl[v] = 2;
	return false;
}

int main() {
	... read the graph ...

	p.assign (n, -1);
	cl.assign (n, 0);
	cycle_st = -1;
	for (int i=0; i<n; ++i)
		if (dfs (i))
			break;

	if (cycle_st == -1)
		puts ("Acyclic");
	else {
		puts ("Cyclic");
		vector<int> cycle;
		cycle.push_back (cycle_st);
		for (int v=cycle_end; v!=cycle_st; v=p[v])
			cycle.push_back (v);
		cycle.push_back (cycle_st);
		reverse (cycle.begin(), cycle.end());
		for (size_t i=0; i<cycle.size(); ++i)
			printf ("%d ", cycle[i]+1);
	}
}

This code is copied from e-maxx.ru , very good web-site.

This code checks the graph for being acyclic or cyclic and if it is cyclic it finds the cycle. So just modify this code so that it does what you need. Hope it helps you.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    AA: Can anyone help me? I want to learn dijkstra on heap.

    BB: Here is [link] standart dijkstra. So just modify this code so that it does what you need.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

This problem is NP (if exist polynomial solution for this problem, then it also gives polynomial solution for Hamiltonian cycle problem).

So, full search seems the best idea:)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there is solution in O(K*P(N)) where K is number of different cycles, P(N) — polynomial of N. But i don't think author understand what he wants.

    → Reply