parents of source vertices

[yeesian]

Following a discussion:

Technically, a node's parent is not itself unless there's an explicit edge between the node and itself, and that wouldn't ever exist (except possibly with A* and negative weights) in a shortest path calculation.

I don't know the original reason for making the source node its own parent, but it's not consistent with other packages (e.g., networkx) and will require an explicit check to ensure we're at the end of the (reversed) path so that we don't loop.

Should they be left as #undef, rather than pointing back to themselves?

[sbromberger]

I don't think we should change the parents vector. I think we should change hasparent only to reflect the fact that a source does not have a parent in a shortest-path calculation. Making this change only to this recent boolean vector means that other processing that might rely on the parents vector remains functional (though technically incorrect) but we move towards correct behavior going forward and can take advantage of the boolean vector for things like path termination.

[mlubin]

I have no strong opinion on this, we just need to pick a convention and document it well.

[sbromberger]

As far as documentation goes, we should be explicit that parents[i] is only accurate (and may only be accessible!) when hasparents[i] is true, and that relying on parents[src] to contain the source is deprecated behavior.

[yeesian]

The tests I took from @sbromberger were not exhaustive in covering graphs where the nodes are not their own indices, and so the implementation of enumerate_paths (on master) is throwing up the following error:

julia> g = Graphs.inclist([4,5,6,7],is_directed=true)
julia> Graphs.add_edge!(g, 4,6)
julia> Graphs.add_edge!(g, 5,7)
julia> Graphs.add_edge!(g, 6,7)
julia> sps = dijkstra_shortest_paths(g,4)
julia> enumerate_paths(sps)
ERROR: BoundsError()
 in enumerate_paths at /Users/yeesian/.julia/v0.3/Graphs/src/dijkstra_spath.jl:269
 in enumerate_paths at /Users/yeesian/.julia/v0.3/Graphs/src/dijkstra_spath.jl:279

The error can be traced down to the fact that the parent vector returns the Nodes themselves, rather than the indices of the Nodes.

julia> sps.hasparent
4-element Array{Bool,1}:
 false
 false
  true
  true

julia> sps.parents
4-element Array{Int64,1}:
 4
 0
 4
 6

As it currently stands, I'm unable to use enumerate_paths in OpenStreetMap (because I need the indices, rather than the nodes). Will it be more helpful to return the indices of the nodes, rather than the nodes themselves (in the parents vector -- for both dijkstra and bellmanford)?

Remark: this might be a breaking change, for people whose code relied on the previous behavior (in parents), so I thought I better throw it up for discussion first. It shouldn't affect @sbromberger's code though, since both the nodes and the indices were the same thing for him

cc @pozorvlak

[sbromberger]

We're not talking about changing parents, right? (I hope not.)

If not, can't we just call vertex_index() in enumerate_paths() to provide the fix? Maybe even something like (...; by_index=true) as an option to enumerate_paths().

[yeesian]

After revisiting the thread in #16, I think @sbromberger's suggestion is a reasonable workaround, since there seems to be a general philosophy of iterating over vertices in this package, rather than working with indices.

In that case, we'll need to access the graph in enumerate_paths, so the function signature (for enumerate_paths) will have to change too.

[sbromberger]

On the other hand, having parents be indices means we can use 0 to denote source / no parent, which means we can retire hasparent. It's worth further consideration.

[yeesian]

I'll replace has_parent with parent_indices for now; and leave the discussion of whether to keep the parents vector open for discussion

[sbromberger]

That's fine by me as long as we preserve the behavior of has_parent with respect to src - that is, parent_indices[src] == 0.