Skip to content

CGDFG also needs findShortestPathDijkstra #713

Open
@dehann

Description

@dehann

Prototype here:

function findShortestPathDijkstra end

LightDFG already has an implementation:

"""
$SIGNATURES
Speciallized function available to only LightDFG at this time.
Example
```julia
using IncrementalInference
# canonical example graph as example
fg = generateCanonicalFG_Kaess()
@show path = findShortestPathDijkstra(fg, :x1, :x3)
@show isVariable.(path)
@show isFactor.(path)
```
DevNotes
- # TODO expand to other AbstractDFG entities.
Related
[findFactorsBetweenNaive](@ref), `LightGraphs.dijkstra_shortest_paths`
"""
function findShortestPathDijkstra( dfg::LightDFG,
from::Symbol,
to::Symbol )
#
# LightDFG internally uses Integers
frI = dfg.g.labels[from]
toI = dfg.g.labels[to]
path = LightGraphs.dijkstra_shortest_paths(dfg.g.graph, [toI;])
# path = LightGraphs.enumerate_paths(path_state, toI)
# assemble into the list
dijkpath = Symbol[]
# test for connectivity
if path.dists[frI] < Inf
cursor = frI
push!(dijkpath, dfg.g.labels[cursor])
# walk the path
while cursor != toI
cursor = path.parents[cursor]
push!(dijkpath, dfg.g.labels[cursor])
end
end
# return the list of symbols
return dijkpath
end

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions