Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / graphs... Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
haba

May 11, 2005, 05:31 AM

Hi,

How can I find the number of paths between two vertices, x and y, of a graph, represented by an adjacency list?

Thanks

 
Wernaeh

May 11, 2005, 06:00 AM

Guessing from your other posts, it is homework time again, isn't it ? =)

Well anyways, one possible solution to your question would probably be to recursively trace through your graph, starting at the origin vertex. Then just end each time you either reach a dead end or arrive at your target vertex, sum up all pathes that arrive at the target.

Warning: If there are cycles in your graph, there is an infinite number of solutions, since each cycle can be traced infinitely often. This problem even gets worse with interleaved cycles, where you may repeat any combination of cycles as often as you like.

To counter this, you should probably add visited marks to all your edges, and remove them when stepping up again from recursion.

You should be able to work the details of an actual implementation out yourself,

Cheers,
- Wernaeh

 
Chris

May 11, 2005, 09:52 AM

Give each edge a weight of 1, and calculate a minimum cut. Any path must run through it, so you've got a lower bound now.

Perform the cut, and the graph gets split into two disjoint subgraphs. Recursively apply the algorithm onto the disjoint subgraphs, possibly improving your lower bound.

Eventually you'll end up with a trivial graph (one node, zero edges), within which there'll obviously be 0 ways, and the recursion terminates.

Or maybe I've missed something.
Anyway, read you graph theory books, it's all in there.

 
haba

May 11, 2005, 02:49 PM

i came up with this solution that takes too much time however:

int countpaths(int start, int end)
{
int c = 0;
struct vertex *t;
stackinit();
push(start);
while(!stackempty())
{
start = pop();
if(start == end)
c++;
for(t=graph[start]; t!=z; t=t->next)
{
if(t->next != z)
push(t->next->v);
}
}
free(t);
return c;
}

it uses a stack (instead of recursion)... do u guys see any thing I can change to make it faster?

thanks again

 
Wernaeh

May 11, 2005, 04:01 PM

First you should use the (cpp) (/cpp) tags to post code (replace the ( and ) with [ and ]), or see the manual above the posting box.

Second, I guess there is a bug in your code because you don't take any cautions for cycles in your graph. Just consider the case of a circle with two nudges, like this:

  1.  
  2. Start ---> v1 ---> v2
  3.             ^       |
  4.             |       v
  5. End <----- v4 <--- v3
  6.  


When arriving at v1, you will walk along the path with the first index, to v2 for example. Then you continue to v3, v4. If you are at v4 and you choose to go on to v1 (since v1 has a lower index than v4) you arrive at v1 again, and start over again and again and again (Which I guess causes your speed problems, since I doubt you have graphs that huge that you actually notice calculation time). To avoid this, mark edges you visited already.

Also, what is the z variable in your code ? A define for Null ?

Furthermore the Free(p) looks suspicious to me, I don't know why though. Perhaps because you shouldn't free a pointer you didn't malloc anywhere, but assigned to a seemingly random object in your graph.

About speeding it up, I guess just marking nodes you already visited and found that they don't connect to the target will do (note this is not like marking edges, marked edges may still count as "just another route" to a target, and should be unmarked as you proceed upwards in your recursion).

Finally, let me again mention that your problem only is solvable when you only allow each edge to be taken once in a path.

Cheers,
- Wernaeh

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.