Dikjstra's shortest path ?

[renoust]

Hi everyone,

I'm posting this to keep it as a reminder (it should be easy to adapt from the existing code).

Although Dikjstra is implemented in the path highlighter interaction plugin (https://github.com/Tulip-Dev/tulip/tree/master/plugins/interactor/PathFinder/PathFinding/Dikjstra), path finding between two nodes is one most-useful basic graph manipulation lacking in Tulip core.
DFS and BFS are now directly ported to the python api, so maybe the PathFinding component could become a similar component? (path finding itself does not depend on GUI elements).

Cheers,

[renoust]

A quick follow up to this comment: is there an efficient alternative to know if a pair of nodes are connected in a graph?
So far, we can use tlp.ConnectedTest.computeConnectedComponents(graph), then test whether both nodes belong to the same list, but it feels a bit of an overkill to this issue.

[p-mary]

Thanks for your report.
The function
tlp::bool selectShortestPaths(const Graph *const graph, node src, node tgt, ...)
has been recently added to the Tulip C++ api (commit 54691cf) and is also accessible througth the Python binding (commit 35e8942).

[renoust]

For reference, here are the details:

tlp.selectShortestPaths(graph, src, tgt, pathType, weights, selection)

:param graph: The graph to compute on. :type graph: :class:tlp.Graph
:param src: The source node of the paths :type node: :class:tlp.node
:param tgt: The target node of the paths :type node: :class:tlp.node
:param pathType: The type of path to consider :type pathType: tlp.OnePath, tlp.OneDirectedPath, tlp.OneReversedPath, tlp.AllPaths, tlp.AllDirectedPaths, tlp.AllReversedPaths (Reversed means directed with reversed direction)
:param weights: A graph property giving the edges weight if weighted paths have to be considered. Can be set to null to select unweighted paths. :type weights:class:tlp.DoubleProperty
:param selection: The graph property to consider as selection. :type selection:class:tlp.BooleanProperty
:rtype: boolean (True if a path is found)
:throws: an exception if one of the source or target nodes does not belong to the graph.

One usage would be:
tlp.selectShortestPaths(graph, tlp.node(1), tlp.node(2), tlp.AllPaths, graph['viewMetric'], graph['viewSelection'])
the paths are stored in the edges (and connected nodes) of graph with graph['viewSelection'] value equal to True.