The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

graph algorithm question

Hello all!

I need a graph algorithm that finds ALL of the paths from (possibly) multiple sources to (possibly) multiple sinks.  I've googled and googled and found many references to shortest paths algorithms (Dijkstra, all pairs shortest paths, A*) but I need all of the paths.

Does anyone know of anything like this?  I'm in the process of trying to modify some of the shortest path algorithms to remove the "shortest path" restriction.

Thanks!
should've paid more attention in my algorithms class
Wednesday, June 11, 2008
 
 
Sounds a bit like the Travelling Salesman problem: http://en.wikipedia.org/wiki/Travelling_salesman_problem
John Topley Send private email
Wednesday, June 11, 2008
 
 
There might be an infinite number of them.
quant dev Send private email
Wednesday, June 11, 2008
 
 
Although not infinite (assuming non-infinite nodes), it may quickly become computationally infeasible to deal with.
Odysseus Send private email
Wednesday, June 11, 2008
 
 
I agree with the previous 2 posters. You may need to narrow your problem down a little.
Developer #13
Wednesday, June 11, 2008
 
 
The second your graph has a loop in it you have an infinite number of solutions situation.  When you remove the loop you are pretty much looking at tree traversal.
Brian
Wednesday, June 11, 2008
 
 
and that is if you write it such that you don't fall into the  a->b->a->b and variations there in infinite solution.
Brian
Wednesday, June 11, 2008
 
 
I think you want Warshall's algorithm.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

If you skip down to the part about Applications & Generalizations, it explains how to do Warshall's algorithm, as apposed to the Floyd/Warshall algorithm.

The result is basically a matrix that says "yes, there is a path from A to B" or "no, there is not."
Michael Gibson Send private email
Wednesday, June 11, 2008
 
 
Okay, so I figured out how to solve your actual problem.  But now I'm wondering if this is a homework problem.  If it is truly not, let me know and I'll post the answer.
Michael Gibson Send private email
Wednesday, June 11, 2008
 
 
"The result is basically a matrix that says "yes, there is a path from A to B" or "no, there is not.""

Well, F-W algorithm actually finds the shortest paths too.

To the OP: http://www.amazon.co.uk/Introduction-Algorithms-Thomas-H-Cormen/dp/0262032937/ref=sr_1_2?ie=UTF8&s=books&qid=1213222038&sr=8-2
quant dev Send private email
Wednesday, June 11, 2008
 
 
Indeed, but pure Warshall's doesn't, which seems to be what the OP wanted.
Michael Gibson Send private email
Wednesday, June 11, 2008
 
 
I am very sure we saw this exact same question in this forum within the past two years, probably one. Perhaps the OP is taking the same course as the previous poster.

The reason it sounds like a homework problem is that it doesn't have much practical application. Questions of more practical interest are finding a maximal set of disjoint paths, or a minimal set of disconnecting cut points.
Mikkin
Wednesday, June 11, 2008
 
 
Hi,

This is the OP.  This is not a homework problem, it's actually for work.  We're developing a network simulator where we can define sources, sinks and intermediate nodes.  The links between all of the nodes change every so often and I need to evaluate the network to see if there is a path from any source to any sink every time the links between the nodes change. 

So, I'm not concerned with shortest path, I just want to know if there is a link from a source to a sink.  HOWEVER, the way our code works (it's not the way I would write it) is that all of the possible links from sources to sinks have to be defined in the beginning of the simulation.  Every time the links change, we evaluate a set of node hops from source to sink to see if the network is up, hence my need for a complete set of paths from all sources to all sinks.

By the way, thank you all for your responses!!
OP
Wednesday, June 11, 2008
 
 
Okay, you probably want to do a breadth-first search.  Something like this:

Let Result = empty set
Let Current = set of paths consisting of (source_i)
  (In other words, for each source S, create a path of length 0, starting at S)

While (Current is not empty) {
    Let P = first element in Current.
    Pop P out of Current
    Let x = last vertex in P
    If (x is a sink) {
        Add P to Result
        continue with while loop
    } otherwise
    For each link (x, y) in the edge set {
          if (P contains y) {
              cycle - ignore and continue with for loop
          }
          Let P' = P + y
          Add P' to Current
    }
}
Michael Gibson Send private email
Wednesday, June 11, 2008
 
 
With regard to coping with loops, you might want to look into the Ariadne algorithm.  It's like the Theseus algorithm, only better for some situations.
Walter Mitty Send private email
Thursday, June 12, 2008
 
 
That's a simple backtracking problem. Here is some pseudocode.

Given is a list of nodes and their connections. Each node is a source, a sink or a normal node, and each node has a WasVisited flag. It could either be a flag or a separate list/hashmap where visited nodes are stored.

VisitNode (Source, Node)
  if Node.WasVisited then return
  Node.WasVisited = true

  if Node.IsSink then StoreResult(Source, Node)

  for each Target in Node.ConnectedNodes
    VisitNode(Source, Target)
  next

  (*)
end VisitNode

for each Source in SourceNodes
  ClearVisitedState(AllNodes) 
  VisitNode(Source, Source)
next

This gives you a list of source-sink connections. If you want to get ALL possible paths without loops, then add
Node.WasVisited = false
for the (*). Note that this may result in exponential behaviour, depending on the structure. And you should track the current path to store it, too.

Of course the recursion behaviour can be optimized, or you could get rid of the recursion by using a queue like Michael, but premature optimization... you know...
Secure
Thursday, June 12, 2008
 
 
By the way, it's really worth having a copy of Steven Skiena's _The Algorithm Design Manual_ on hand just to answer questions like this one.
Robert Rossney Send private email
Thursday, June 12, 2008
 
 
It sounds like you don't want to know ALL the paths, just if a path exists from each point to each point.

Just apply modified A* on each combination of points. If it finds a path, yeay, break and mark the path as valid.

Store it all in a list.
Steve Send private email
Wednesday, June 18, 2008
 
 
"With regard to coping with loops, you might want to look into the Ariadne algorithm.  It's like the Theseus algorithm, only better for some situations."

But you get dumped in the end, tho.
quant dev Send private email
Friday, June 20, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz