BreadthFirstShortestPaths.cs

/***
 * Computes Shortest-Paths for Unweighted Graphs using the Breadth-First Search algorithm.
 * It provides the capability to find shortest-paths from a single-source and multiple-sources, in addition to looking up reachable and unreachable nodes.
 */

usingSystem;
usingSystem.Diagnostics;
usingSystem.Collections.Generic;

usingAlgorithms.Common;
usingDataStructures.Graphs;

namespaceAlgorithms.Graphs
{
publicclassBreadthFirstShortestPaths<T>whereT:IComparable<T>
{
privateint_edgesCount{get;set;}
privateint_verticesCount{get;set;}
privatebool[]_visited{get;set;}
privateInt64[]_distances{get;set;}
privateint[]_predecessors{get;set;}

// A dictionary that maps node-values to integer indeces
privateDictionary<T,int>_nodesToIndices{get;set;}

// A dictionary that maps integer index to node-value
privateDictionary<int,T>_indicesToNodes{get;set;}

// A const that represent an infinite distance
privateconstInt64INFINITY=Int64.MaxValue;


/// <summary>
/// CONSTRUCTOR.
/// Breadth First Searcher from Single Source.
/// </summary>
publicBreadthFirstShortestPaths(IGraph<T>Graph,TSource)
{
if(Graph==null)
thrownewArgumentNullException();
if(!Graph.HasVertex(Source))
thrownewArgumentException("The source vertex doesn't belong to graph.");

// Init
_initializeDataMembers(Graph);

// Single source BFS
_breadthFirstSearch(Graph,Source);

//bool optimalityConditionsSatisfied = checkOptimalityConditions (Graph, Source);
Debug.Assert(checkOptimalityConditions(Graph,Source));
}


/// <summary>
/// CONSTRUCTOR.
/// Breadth First Searcher from Multiple Sources.
/// </summary>
publicBreadthFirstShortestPaths(IGraph<T>Graph,IList<T>Sources)
{
if(Graph==null)
thrownewArgumentNullException();
if(Sources==null||Sources.Count==0)
thrownewArgumentException("Sources list is either null or empty.");

// Init
_initializeDataMembers(Graph);

// Multiple sources BFS
_breadthFirstSearch(Graph,Sources);
}


/************************************************************************************************************/


/// <summary>
/// Constructors helper function. Initializes some of the data memebers.
/// </summary>
privatevoid_initializeDataMembers(IGraph<T>Graph)
{
_edgesCount=Graph.EdgesCount;
_verticesCount=Graph.VerticesCount;

_visited=newbool[_verticesCount];
_distances=newInt64[_verticesCount];
_predecessors=newint[_verticesCount];

_nodesToIndices=newDictionary<T,int>();
_indicesToNodes=newDictionary<int,T>();

// Reset the visited, distances and predeccessors arrays
inti=0;
foreach(varnodeinGraph.Vertices)
{
if(i>=_verticesCount)
break;

_visited[i]=false;
_distances[i]=INFINITY;
_predecessors[i]=-1;

_nodesToIndices.Add(node,i);
_indicesToNodes.Add(i,node);

++i;
}
}

/// <summary>
/// Privat helper. Breadth First Search from Single Source.
/// </summary>
privatevoid_breadthFirstSearch(IGraph<T>graph,Tsource)
{
// Set distance to current to zero
_distances[_nodesToIndices[source]]=0;

// Set current to visited: true.
_visited[_nodesToIndices[source]]=true;

varqueue=newQueue<T>(_verticesCount);
queue.Enqueue(source);

while(queue.Count>0)
{
varcurrent=queue.Dequeue();
intindexOfCurrent=_nodesToIndices[current];

foreach(varadjacentingraph.Neighbours(current))
{
intindexOfAdjacent=_nodesToIndices[adjacent];

if(!_visited[indexOfAdjacent])
{
_predecessors[indexOfAdjacent]=indexOfCurrent;
_distances[indexOfAdjacent]=_distances[indexOfCurrent]+1;
_visited[indexOfAdjacent]=true;

queue.Enqueue(adjacent);
}
}//end-foreach
}//end-while
}

/// <summary>
/// Privat helper. Breadth First Search from Multiple Sources.
/// </summary>
privatevoid_breadthFirstSearch(IGraph<T>graph,IList<T>sources)
{
// Define helper variables.
varqueue=newQueue<T>(_verticesCount);

foreach(varsourceinsources)
{
if(!graph.HasVertex(source))
thrownewException("Graph doesn't has a vertex '"+source+"'");

intindex=_nodesToIndices[source];
_distances[index]=0;
_visited[index]=true;
queue.Enqueue(source);
}

while(queue.Count>0)
{
varcurrent=queue.Dequeue();
intindexOfCurrent=_nodesToIndices[current];

foreach(varadjacentingraph.Neighbours(current))
{
intindexOfAdjacent=_nodesToIndices[adjacent];

if(!_visited[indexOfAdjacent])
{
_predecessors[indexOfAdjacent]=indexOfCurrent;
_distances[indexOfAdjacent]=_distances[indexOfCurrent]+1;
_visited[indexOfAdjacent]=true;

queue.Enqueue(adjacent);
}
}//end-foreach
}//end-while
}

/// <summary>
/// Private helper. Checks optimality conditions for single source
/// </summary>
privateboolcheckOptimalityConditions(IGraph<T>graph,Tsource)
{
intindexOfSource=_nodesToIndices[source];

// check that the distance of s = 0
if(_distances[indexOfSource]!=0)
{
Console.WriteLine("Distance of source '"+source+"' to itself = "+_distances[indexOfSource]);
returnfalse;
}

// check that for each edge v-w dist[w] <= dist[v] + 1
// provided v is reachable from s
foreach(varnodeingraph.Vertices)
{
intv=_nodesToIndices[node];

foreach(varadjacentingraph.Neighbours(node))
{
intw=_nodesToIndices[adjacent];

if(HasPathTo(node)!=HasPathTo(adjacent))
{
Console.WriteLine("edge "+node+"-"+adjacent);
Console.WriteLine("hasPathTo("+node+") = "+HasPathTo(node));
Console.WriteLine("hasPathTo("+adjacent+") = "+HasPathTo(adjacent));
returnfalse;
}
if(HasPathTo(node)&&(_distances[w]>_distances[v]+1))
{
Console.WriteLine("edge "+node+"-"+adjacent);
Console.WriteLine("distanceTo["+node+"] = "+_distances[v]);
Console.WriteLine("distanceTo["+adjacent+"] = "+_distances[w]);
returnfalse;
}
}
}

// check that v = edgeTo[w] satisfies distTo[w] + distTo[v] + 1
// provided v is reachable from source
foreach(varnodeingraph.Vertices)
{
intw=_nodesToIndices[node];

if(!HasPathTo(node)||node.IsEqualTo(source))
continue;

intv=_predecessors[w];

if(_distances[w]!=_distances[v]+1)
{
Console.WriteLine("shortest path edge "+v+"-"+w);
Console.WriteLine("distanceTo["+v+"] = "+_distances[v]);
Console.WriteLine("distanceTo["+w+"] = "+_distances[w]);
returnfalse;
}
}

returntrue;
}


/************************************************************************************************************/


/// <summary>
/// Determines whether there is a path from the source vertex to this specified vertex.
/// </summary>
publicboolHasPathTo(Tdestination)
{
if(!_nodesToIndices.ContainsKey(destination))
thrownewException("Graph doesn't have the specified vertex.");

intdstIndex=_nodesToIndices[destination];
return(_visited[dstIndex]);
}

/// <summary>
/// Returns the distance between the source vertex and the specified vertex.
/// </summary>
publiclongDistanceTo(Tdestination)
{
if(!_nodesToIndices.ContainsKey(destination))
thrownewException("Graph doesn't have the specified vertex.");

intdstIndex=_nodesToIndices[destination];
return(_distances[dstIndex]);
}

/// <summary>
/// Returns an enumerable collection of nodes that specify the shortest path from the source vertex to the destination vertex.
/// </summary>
publicIEnumerable<T>ShortestPathTo(Tdestination)
{
if(!_nodesToIndices.ContainsKey(destination))
thrownewException("Graph doesn't have the specified vertex.");
if(!HasPathTo(destination))
returnnull;

intdstIndex=_nodesToIndices[destination];
varstack=newDataStructures.Lists.Stack<T>();

intindex;
for(index=dstIndex;_distances[index]!=0;index=_predecessors[index])
stack.Push(_indicesToNodes[index]);

// Push the source vertex
stack.Push(_indicesToNodes[index]);

returnstack;
}

}

}