Finding all the paths from A to B

[Edmondo Porcu]

Dear all,

I have to model the following problem. I have N nodes, which are connected according to a Boolean expression.

 I need to implement the following for all node of type != T and without predecessors, ensure that there is one and only one path to a node of type T. I could model this by using a DiEdge and that worked correctly, my problem is that the the pathUntil returns a single optional path and not a collection. In a later stage , I need to walk over the path in reverse order (from the end to the beginning)

 Is there a simple way to do this?

 Best Regards

 

[Edmondo Porcu]

To clarify a little bit the problem. I have a trait T and three concrete implementations : A,B,C.

Given a collection of T and a f: (T,T) => Boolean I can build the graph.

I am creating a builder for a given data structure which has to verify that the graph has certain connectivity characteristics, namely that for every node of class B or C with no predecessors exist 1 and only 1 path to a node of class A.

I have implemented the following method which lets me count the paths:

  def findAllPathFrom[N, E[X] <: EdgeLikeIn[X]](graph:Graph[N,E])(node:graph.NodeT, exitCondition: graph.NodeT => Boolean):Seq[graph.Path] = {
    @tailrec
    def findAllPathFrom(node:graph.NodeT, exitCondition: graph.NodeT => Boolean,  previousFoundPath:Seq[graph.Path]):Seq[graph.Path] = {
      val newPath = node pathUntil( node => exitCondition(node), node => ! previousFoundPath.exists(_.endNode == node))
      newPath match{
        case Some(path) => findAllPathFrom(node, exitCondition, previousFoundPath:+path)
        case None => previousFoundPath
      }
    }
    findAllPathFrom(node,exitCondition,Seq.empty[graph.Path])

  }

And now the game is simple, because I can simply filter the initial nodes and run my function. However, the following questions stay open for me:

- Would it not make sense to have a pathUntilS in the standard library?
- I need , later, to follow the path inversely, from end to beginning. Is this feasible with minimum performance cost? Or should I make a unidrected graph?


Thank you for your help

Best Regards

Edmondo

[Peter Empen]

Hi Edmpndo,

yes, it would make perfectly sense to add a function to the library to find all paths between two nodes. There are plenty of algorithms missing...

I don't think it is a performance issue to follow paths reversely. There is absolutely no need to swith to undirected graphs for this purpose since you can traverse in any direction including predeseccors in any kind of graph.

Peter

[Peter Empen]

Edmondo,

Since you're telling that your main concern is to ensure a certain condition for the graph as a whole, it seems that http://www.scala-graph.org/guides/constrained.html  would be a perfect fit. The constrained graph would serve as your builder. You had just to check for the existence of a single path to decide on whether node/edge addition is allowed or must be rejected.

Have you already taken a look at the Constrained package?

Peter

[lucas....@nubank.com.br]

Does the library already have a function to find all paths between to nodes? I browsed the documentation, but couldn't find anything other than `pathTo`, and `shortestPathTo`...

[Peter Empen]

Still not available. Feel free to add an enhancement request on GitHub.

[lucas....@nubank.com.br]

Thank you for your reply. I'll try to read the guidelines on how to open a request.

I spoke to a coworker, and he suggested me to in fact reverse the graph and try to use "withSubGraph" to find out all paths exhaustively. Might be a workaround - not sure if it applicable in any situation, but it seems to be to mine, at least. Once again, thank you!

[Peter Empen]

I just meant https://github.com/scala-graph/scala-graph/issues where we will mark your issue as an enhancement.