depth first search algorithm

Naweed

unread,

Dec 13, 2008, 11:23:02 PM12/13/08

to

Would anyone know what is wrong with my depth first search algorithm? I'm using it to detect cycles in an undirected graph. It always ends up reporting that a graph contains cycles.

30 for i=1:num_of_verts
31 if (colour(i) == 0)
32 dfs(i);
33 end
34 end
35

50 function y = dfs(u)
51 time = time + 1;
52 d(u) = time;
53 colour(u) = 1;
54 for c=1:num_of_verts
55 v = list(u,c);
56 if (v ~= 0)
57 if (colour(v) == 0)
58 p(v) = u;
59 dfs(v);
60 elseif (colour(v) == 1)
61 if (p(u) ~= v)
62 acyclic = 0;
63 end
64 end
65 end
66 end
67 time = time + 1;
68 f(u) = time;
69 colour(u) = 2;
70 end

Naweed

unread,

Dec 14, 2008, 3:00:07 AM12/14/08

to

> Would anyone know what is wrong with my depth first search algorithm? I'm using it to detect cycles in an undirected graph. It always ends up reporting that a graph contains cycles.
>

> <code>

Please ignore the above message. The dfs code looks to be fine, the bug was somewhere else.

Rashid Iqbal

unread,

Jan 20, 2009, 7:29:02 AM1/20/09

to

"Naweed " <naw...@hotmail.com> wrote in message <gi2ee7$3p5$1...@fred.mathworks.com>...

> > Would anyone know what is wrong with my depth first search algorithm? I'm using it to detect cycles in an undirected graph. It always ends up reporting that a graph contains cycles.
> >
> > <code>
>
> Please ignore the above message. The dfs code looks to be fine, the bug was somewhere else.

Dear Naveed

My name is Rashid Iqbal and I am a student of MS(IT)
I am working on P-Cycle
I a m facing problems in finding the cycles in network and after that perform further operations on the network.

Please help me

I will be highly obliged.

Regards,

Rashid Iqbal
Pakistan

Rashid Iqbal

unread,

Jan 20, 2009, 7:31:02 AM1/20/09

to

"Naweed " <naw...@hotmail.com> wrote in message <gi2ee7$3p5$1...@fred.mathworks.com>...

Naweed

unread,

Jan 20, 2009, 10:20:18 PM1/20/09

to

>
> My name is Rashid Iqbal and I am a student of MS(IT)
> I am working on P-Cycle
> I a m facing problems in finding the cycles in network and after that perform further operations on the network.
>

Rashid,

See Marshall's post in the thread below for an interesting way to detect cycles.

http://www.mathworks.com/matlabcentral/newsreader/view_thread/240766

Naweed

Rashid Iqbal

unread,

Jan 29, 2009, 7:53:01 AM1/29/09

to

Naveed

I need further help to understand the cycles and then I want to perform some further operations.
I use the Johnson's algorithm to find all the cycles in a directed graph.

and if the link goes down between two nodes then how to reroute the traffic between them through p-cycles.

please reply

Rashid

"Naweed " <naw...@hotmail.com> wrote in message <gl649i$6oi$1...@fred.mathworks.com>...

Naweed

unread,

Jan 29, 2009, 10:57:01 PM1/29/09

to

"Rashid Iqbal" <rashid...@hotmail.com> wrote in message <gls8rd$pck$1...@fred.mathworks.com>...

> Naveed
>
> I need further help to understand the cycles and then I want to perform some further operations.
> I use the Johnson's algorithm to find all the cycles in a directed graph.
>
> and if the link goes down between two nodes then how to reroute the traffic between them through p-cycles.
>
> please reply
>
> Rashid
>

Sorry Rashid, I'm not familiar with Johnson's algorithm nor with p-cycles. Perhaps someone else here can help you.

Good luck.

- Naweed

Rashid Iqbal

unread,

Feb 5, 2009, 11:39:01 PM2/5/09

to

"Naweed " <naw...@hotmail.com> wrote in message <glttqd$44h$1...@fred.mathworks.com>...

Naweed

I am interested to learn the Dijkstra's algorithm implemention in matlab from you.
can you please guide me about the requested.

Rashid