Inaccessible Vertices returned when getting distances from DijkstraShortestPathAlgorithm

[SimonTC]

Issue
When using DijkstraShortestPathAlgorithm to calculate distances to a specific vertex, all vertices in the graph are returned when accessing DijkstraShortestPathAlgorithm.Distances. Even those vertices that are not accessible from source vertex.

I would expect that only the vertices accessible from the source vertex would be included.

Reason
The reason that inaccessible vertices are being returned is that all vertices in the graph are added to VerticesColors and Distances in the Initialize method in DijkstraShortestPathAlgorithm:

protected override void Initialize()
{
	base.Initialize();

	// Initialize colors and distances
	double initialDistance = DistanceRelaxer.InitialDistance;
	foreach (TVertex vertex in VisitedGraph.Vertices)
	{
		VerticesColors.Add(vertex, GraphColor.White);
		Distances.Add(vertex, initialDistance);
	}

	_vertexQueue = new FibonacciQueue<TVertex, double>(DistancesIndexGetter());
}

With the current implementation of at least BreadthFirstSearchAlgorithm.FlushVisitQueue and ShortestPathAlgorithmBase.Relax it is necessary to add all vertices to the dictionaries since they are expected to exist:

protected bool Relax([NotNull] TEdge edge)
{
	[...]
	double du = Distances[source];
	[...]
}

private void FlushVisitQueue()
{
	[...]
	GraphColor vColor = VerticesColors[v];
	[...]
}

Why is this an issue
I see two problems with this:

1. In case of graphs with many vertices the initial looping over all the vertices in the graph could become rather expensive.
2. When using the Distances dictionary it would be better if no distance was returned for an inaccessible vertex instead of a Double since that a) leads to unnecessary extra logic on the callers side to make sure a vertex is accessible and b) can result in unnecessary looping in case the caller wants to do something with all the key-value pairs in the dictionary.

Possible solution
The easiest would be to use TryGetValue together with a default value when accessing the dictionaries instead of getting values by key directly:

private void FlushVisitQueue()
{
	[...]
	GraphColor vColor;
	if (!VerticesColors.TryGetValue(v, out vColor)) vColor = GraphColor.White;
	[...]
}

Then there is no need for the looping in Initialize.

A problem with this approach is that it isn't backwards compatible. Maybe it would be possible to add a flag to the Initialize method to pre-populate the dictionaries?:

protected override void Initialize(bool prePopulateDictionaries = false)
{
	base.Initialize();

	// Initialize colors and distances
	if (prePopulateDictionaries)
	{
		double initialDistance = DistanceRelaxer.InitialDistance;
		foreach (TVertex vertex in VisitedGraph.Vertices)
		{
			VerticesColors.Add(vertex, GraphColor.White);
			Distances.Add(vertex, initialDistance);
		}
	}

	_vertexQueue = new FibonacciQueue<TVertex, double>(DistancesIndexGetter());
}

Of course, if this flag only is used in DijkstraShortestPathAlgorithm it doesn't make much sense to have it there. Could the flag be added to the constructor directly?

[KeRNeLith]

Hello,

I understand your point about inaccessible vertices. QuikGraph is mostly based on the C++ Boost graph library.

Concerning the Dijkstra algorithm it seems that it initializes the full set of vertices. Maybe I'm wrong but it seems to be the case. I also looked at BFS implementation.

[SimonTC]

But do you think it is strictly necessary to do it? As long as the default distance and color is set when a new vertex is discovered I don't think it is necessary to initialize them at the beginning.

[KeRNeLith]

Well you're right on the fact that not having any distance for the vertex if not reachable seems to be a possible solution as it depicted well the case.
We can also think about having an infinite distance while not reached.

BTW not only the Dijktra algorithm can be concerned by such behavior.

[SimonTC]

BTW not only the Dijktra algorithm can be concerned by such behavior.

You are right. It seems to be all the shortest path algorithms (AStar, BellmanFord, Dag and Dijkstra).
Interestingly enough there is actually a difference between how they initialize the Distance dictionary. BellmanFord uses double.PositiveInfinity as initial distance whereas the the other algorithms uses DistanceRelaxer.InitialDistance which is double.MaxValue. Do you know if there is any special reason for that?

Returning inifinity for an unreachable vertex does make sense too. I have seen that approach in other libraries too.

It would be nice if that was a fall back value though. So we don't add all the values when initializing the algorithm but just return that value if it is specifically requested for an unreachable vertex.

In ShortestPathAlgorithmBase we could add a bool field AddAllVerticesOnInitialization that is set to true by default. If that is false when the initialization method is called then no vertices are added on initialization.

That flag can then be set when instantiating ShortestPathAlgorithmBase.

To avoid having to change all places where the dictionaries are accessed by indexer we could instantiate the dictionaries as some kind of default value dictionaries where a default value is returned if the key isn't found. Not sure how that would interact with use of TryGetValue though.

[KeRNeLith]

There are indeed inconsistencies between the shortest path finder algorithms. I think all these should be uniformized or at least the implementation detail requiring some initialization must not be visible in the library API.
I made some cleaning on such kind of stuff, but in fact there were many flaws.

In some algorithm there is for vertex colors a get like TryGetColor. I think it's the approach we should have rather than exposing dictionaries. Or maybe propose both. The real problem is that having a dictionary open wide doors to implementation details.

So, in my opinion doing such change require to have a high level vision and not limited to the Dijktra algorithm regading this kind of behavior. The result will be a uniformized API that help user to get in touch with one or another algorithm.

Having double.PositiveInfinity as fallback seems a good alternative and indeed can be computed on demand rather than fully initialized on algorithm init. Concerning the distance relaxer maybe it's another inconsistency and both values would fit. But infinite seems better.

So to keep an retro compatible API we can think about having a way to specify we want such init and in the same time depreciate the old usage, in order to remove it after.

[SimonTC]

In some algorithm there is for vertex colors a get like TryGetColor. I think it's the approach we should have rather than exposing dictionaries.

I agree. The good thing is that it currently is exposing IDictionary and no specific implementation. That at least makes it a bit less prone to exposing implementation details. But I agree that TryGet would be even better.

I think the easiest way to specify the initialization behavior would be through constructors. Either with a flag or some kind of config object (if more flags are needed in the future).

Would it make sense to split this ticket up in the following smaller tickets to continue discussion of each part there?:

• Add TryGetX method to all algorithm implementations for external access to values stored in dictionaries. Depreciate direct access to dictionaries.
• Use TryGetValue to get values from dictionaries in algorithm implementations. Return a suitable fallback value if key doesn't exist (fall back value is most likely double.PositiveInfinity but I guess that depends on the algorithm itself).
• Add flag or config object to constructors to be able to specify how the algorithm objects are initialized

[KeRNeLith]

Yeah that's the minimal move I did in order to "hide" implementation but in fact it requires much more harmonization.

You're right a flag in constructor would be great indeed in a first approach.

That makes sense to split this into several sub tasks. The split you suggested is good enough to work on it.
Maybe the third one should be the starting point and then we go to hide better interface algorithms.

Side note: I was working on a more generic version of graph equate helpers as well as dealing with serialization in other branches.

[SimonTC]

I have added #14 and #15 to cover 1 and 3. Would it make sense to join point 2 with 3 since they are dependent on each other?

And as a side note: Is it possible for me to either not assign you to a ticket or assign myself to one? Having you assigned to all tickets opened by others is most likely rather confusing for you :-)

[KeRNeLith]

Yes 1 and 3 are quite linked each other.

I managed to assign these issues to you, is it ok for you?
That's quite strange you can't assign it to you BTW :D

[SimonTC]

That is completely fine. I should be able to manage that :-)

Apparently I need to be designated as a collaborator to be able to assign issues to myself (https://stackoverflow.com/a/26761256)

I will close this issue wince the actual implementation will continue in the other tickets.