shortestPathTo does not adhere to Traversal restrictions #50

Closed
Calavoow opened this Issue Sep 28, 2015 · 16 comments

Comments

Projects
None yet
2 participants
@Calavoow
Contributor

Calavoow commented Sep 28, 2015

I want to try and find a shortest path of a constant maximum length. To do this, I tried using the withMaxDepth filter for traversals. This works nicely with pathTo, but shortestPathTo ignores the restrictions.

Example:

import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._
import scalax.collection.immutable.Graph

val g = Graph(1~2, 2~3, 3~4)
val traversal = g.get(1).withSubgraph(nodes = _ < 2)
traversal.pathTo(g.get(3))
// res1: Option[g.Path] = None

val traversal2 = g.get(1).withMaxDepth(1)
traversal2.pathTo(g.get(3))
// res2: Option[g.Path] = None

traversal2.shortestPathTo(g.get(3))
// res3: Option[g.Path] = Some(Path(1, 1~2, 2, 2~3, 3))

I expect that the shortestPathTo return None, but instead it returns a complete path.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 11, 2015

Contributor

withMaxDepth is currently just relevant in case of BFS. True, this is kind of shortcoming.

Contributor

peter-empen commented Oct 11, 2015

withMaxDepth is currently just relevant in case of BFS. True, this is kind of shortcoming.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 11, 2015

Contributor

Which other traversal restrictions did you see not being handeld by shortestPathTo?

Contributor

peter-empen commented Oct 11, 2015

Which other traversal restrictions did you see not being handeld by shortestPathTo?

@Calavoow

This comment has been minimized.

Show comment
Hide comment
@Calavoow

Calavoow Oct 12, 2015

Contributor

Sorry, the only thing I could come up with was not really a traversal:

val g = Graph(1~2, 2~3, 3~4)
val subGraph = g.get(2).withMaxDepth(1).toGraph
Contributor

Calavoow commented Oct 12, 2015

Sorry, the only thing I could come up with was not really a traversal:

val g = Graph(1~2, 2~3, 3~4)
val subGraph = g.get(2).withMaxDepth(1).toGraph
@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 13, 2015

Contributor

With my above question I intended to clear why you put "Trversal restrictions" (plural) in the issue title.

Contributor

peter-empen commented Oct 13, 2015

With my above question I intended to clear why you put "Trversal restrictions" (plural) in the issue title.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 13, 2015

Contributor

More efficient is the following workaround:

  • use a preparatory traversal with BSF and withMaxDepth as above but, instead of creating a new graph, just store the visited nodes in say validNodes.
  • start a second traversal like ...withSubgraph(node => validNodes containes node).shortestPathTo...
Contributor

peter-empen commented Oct 13, 2015

More efficient is the following workaround:

  • use a preparatory traversal with BSF and withMaxDepth as above but, instead of creating a new graph, just store the visited nodes in say validNodes.
  • start a second traversal like ...withSubgraph(node => validNodes containes node).shortestPathTo...
@Calavoow

This comment has been minimized.

Show comment
Hide comment
@Calavoow

Calavoow Oct 13, 2015

Contributor

Does withKind work on pathTo?

val g2 = Graph(1~2,2~3,3~4,1~4)
g2.get(1).withKind(DepthFirst).pathTo(g2.get(4))
g2.get(1).withKind(DepthFirst).pathTo(g2.get(2))
// res3: Option[g2.Path] = Some(Path(1, 1~4, 4))
// res4: Option[g2.Path] = Some(Path(1, 1~2, 2))

Both give a shortest path. It is not conclusive, but it seems like BFS is used instead?

For a simple graph, I would like to use BFS to find a shortest path of maximum length 6 (withMaxDepth(6)). From my tests on bigger graphs it seems pathTo does not find the shortest path on simple graphs, so it must not be BFS.

alpha.withMaxDepth(6).withKind(BreadthFirst).pathTo(beta)
Contributor

Calavoow commented Oct 13, 2015

Does withKind work on pathTo?

val g2 = Graph(1~2,2~3,3~4,1~4)
g2.get(1).withKind(DepthFirst).pathTo(g2.get(4))
g2.get(1).withKind(DepthFirst).pathTo(g2.get(2))
// res3: Option[g2.Path] = Some(Path(1, 1~4, 4))
// res4: Option[g2.Path] = Some(Path(1, 1~2, 2))

Both give a shortest path. It is not conclusive, but it seems like BFS is used instead?

For a simple graph, I would like to use BFS to find a shortest path of maximum length 6 (withMaxDepth(6)). From my tests on bigger graphs it seems pathTo does not find the shortest path on simple graphs, so it must not be BFS.

alpha.withMaxDepth(6).withKind(BreadthFirst).pathTo(beta)
@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 13, 2015

Contributor

withKind has currently no effect on pathTo. pathTo, implemented in terms of pathUntil, always selects DFS since it was not obvious that BFS would ever be desired by a users. Do you really think it would have any sense, if so why?
DFS, BFS and Dijkstra's shortestPath are distinct algorithms meaning you cannot combine them.
pathTo is specified to return any path satisfying the request but based on BSF the returned path would be the shortest one provided all edge weights are equal.

Contributor

peter-empen commented Oct 13, 2015

withKind has currently no effect on pathTo. pathTo, implemented in terms of pathUntil, always selects DFS since it was not obvious that BFS would ever be desired by a users. Do you really think it would have any sense, if so why?
DFS, BFS and Dijkstra's shortestPath are distinct algorithms meaning you cannot combine them.
pathTo is specified to return any path satisfying the request but based on BSF the returned path would be the shortest one provided all edge weights are equal.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 14, 2015

Contributor

You may also want to consider using BfsInformer.

Contributor

peter-empen commented Oct 14, 2015

You may also want to consider using BfsInformer.

@Calavoow

This comment has been minimized.

Show comment
Hide comment
@Calavoow

Calavoow Oct 14, 2015

Contributor

withKind has currently no effect on pathTo. pathTo, implemented in terms of pathUntil, always selects DFS since it was not obvious that BFS would ever be desired by a users. Do you really think it would have any sense, if so why?

If you have a very big graph, and you know the destination is a bounded distance, then DFS will be much less efficient.

How does one use a BfsInformer?

Contributor

Calavoow commented Oct 14, 2015

withKind has currently no effect on pathTo. pathTo, implemented in terms of pathUntil, always selects DFS since it was not obvious that BFS would ever be desired by a users. Do you really think it would have any sense, if so why?

If you have a very big graph, and you know the destination is a bounded distance, then DFS will be much less efficient.

How does one use a BfsInformer?

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 14, 2015

Contributor

Take a look at TTraversal.scala near line 324 where DfsInformer is tested.

Contributor

peter-empen commented Oct 14, 2015

Take a look at TTraversal.scala near line 324 where DfsInformer is tested.

@Calavoow

This comment has been minimized.

Show comment
Hide comment
@Calavoow

Calavoow Oct 15, 2015

Contributor

What does BfsQueue contain? A node and its depth? What does that mean.
And why does DfsInformer have a path, while BfsInformer doesn't? Because I want to construct a path to the node that I find.

Contributor

Calavoow commented Oct 15, 2015

What does BfsQueue contain? A node and its depth? What does that mean.
And why does DfsInformer have a path, while BfsInformer doesn't? Because I want to construct a path to the node that I find.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 15, 2015

Contributor

Informers allow you to inspect implementation-specific internal data structures during the traversal. As implementations vary so do these data structures. BFS works internally with a queue so you can inspect that queue containing known but not yet processed pairs of, yes, (NodeT, depth).

Since the BFS implementation does not maintain any path, you need to build it on your own.

What about the following: While traversing you build a map with (depth, NodeT). Once you got your target node, you could build the path from there back to your root node by selecting predecessors.

Contributor

peter-empen commented Oct 15, 2015

Informers allow you to inspect implementation-specific internal data structures during the traversal. As implementations vary so do these data structures. BFS works internally with a queue so you can inspect that queue containing known but not yet processed pairs of, yes, (NodeT, depth).

Since the BFS implementation does not maintain any path, you need to build it on your own.

What about the following: While traversing you build a map with (depth, NodeT). Once you got your target node, you could build the path from there back to your root node by selecting predecessors.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Oct 15, 2015

Contributor

See also PathBuilder in case you decide to investigate into the above idea.

Contributor

peter-empen commented Oct 15, 2015

See also PathBuilder in case you decide to investigate into the above idea.

@Calavoow

This comment has been minimized.

Show comment
Hide comment
@Calavoow

Calavoow Jul 26, 2016

Contributor

While I like the idea of building the stack as we go, it is unclear at call time of the BfsInformer what the predecessor of the current node was. Thus it is not possible to build a path.

If instead you build the path as in one of your previous comments, you get something like

        val x = alpha.innerNodeTraverser.withKind(BreadthFirst).withMaxDepth(6)
        val visited = mutable.ListBuffer.empty[g.NodeT]

        object AllDone extends Exception
        try {
            x.foreach {
                g.ExtendedNodeVisitor((node, count, depth, informer) => {
                    assert(depth <= 6, "Depth too high")
                    informer match {
                        case BfsInformer(queue) =>
                            visited += node
                            if(node == beta) {
                                throw AllDone
                            }
                        case _ => throw new RuntimeException("Unexpected informer")
                    }
                })
            }
        } catch {
            case AllDone =>
                val subG = g.filter(node => visited.contains(node))
                val subA = subG.get(alpha)
                val subB = subG.get(beta)
                val subPath = subA.shortestPathTo(subB)
                // Convert subG.Path to g.Path
        }

Which is of course also far from ideal. Any suggestions?

Please keep in mind high performance requirements. Currently, I run my own implementation of Dijkstra and this line is 50% of my runtime

val newPaths = path.head.neighbors.filterNot(x => visited.contains(x.id)).map(_ :: path)

Where the neighbors is actually 25% of my runtime, and filterNot is 30% (so together 55%) on the 25s I profiled. The program actually runs for hours.

Contributor

Calavoow commented Jul 26, 2016

While I like the idea of building the stack as we go, it is unclear at call time of the BfsInformer what the predecessor of the current node was. Thus it is not possible to build a path.

If instead you build the path as in one of your previous comments, you get something like

        val x = alpha.innerNodeTraverser.withKind(BreadthFirst).withMaxDepth(6)
        val visited = mutable.ListBuffer.empty[g.NodeT]

        object AllDone extends Exception
        try {
            x.foreach {
                g.ExtendedNodeVisitor((node, count, depth, informer) => {
                    assert(depth <= 6, "Depth too high")
                    informer match {
                        case BfsInformer(queue) =>
                            visited += node
                            if(node == beta) {
                                throw AllDone
                            }
                        case _ => throw new RuntimeException("Unexpected informer")
                    }
                })
            }
        } catch {
            case AllDone =>
                val subG = g.filter(node => visited.contains(node))
                val subA = subG.get(alpha)
                val subB = subG.get(beta)
                val subPath = subA.shortestPathTo(subB)
                // Convert subG.Path to g.Path
        }

Which is of course also far from ideal. Any suggestions?

Please keep in mind high performance requirements. Currently, I run my own implementation of Dijkstra and this line is 50% of my runtime

val newPaths = path.head.neighbors.filterNot(x => visited.contains(x.id)).map(_ :: path)

Where the neighbors is actually 25% of my runtime, and filterNot is 30% (so together 55%) on the 25s I profiled. The program actually runs for hours.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Aug 7, 2016

Contributor

Hi, withMaxDepth support has now been added to shortestPathTo. Please check out the preview at http://www.scala-graph.org/temp/. (This link is now obsolate.)
Looking forward to your feedback.

Contributor

peter-empen commented Aug 7, 2016

Hi, withMaxDepth support has now been added to shortestPathTo. Please check out the preview at http://www.scala-graph.org/temp/. (This link is now obsolate.)
Looking forward to your feedback.

@peter-empen

This comment has been minimized.

Show comment
Hide comment
@peter-empen

peter-empen Aug 20, 2016

Contributor

Included in release 1.11.2.

Contributor

peter-empen commented Aug 20, 2016

Included in release 1.11.2.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment