DirectedDenseGraph.cs

/***
 * The Directed Dense Graph Data Structure.
 * 
 * Definition:
 * A dense graph is a graph G = (V, E) in which |E| = O(|V|^2).
 * A directed graph is a graph where each edge follow one direction only between any two vertices.
 * 
 * An incidence-matrix digraph representation. Follows almost the same implementation 
 * details of the Undirected version, except for managing the directed edges.
 * Implements the IGraph<T> interface.
 */

usingSystem;
usingSystem.Collections.Generic;

usingDataStructures.Common;
usingDataStructures.Lists;

namespaceDataStructures.Graphs
{
publicclassDirectedDenseGraph<T>:IGraph<T>whereT:IComparable<T>
{
/// <summary>
/// INSTANCE VARIABLES
/// </summary>
privateconstobjectEMPTY_VERTEX_SLOT=(object)null;

protectedvirtualint_edgesCount{get;set;}
protectedvirtualint_verticesCount{get;set;}
protectedvirtualint_verticesCapacity{get;set;}
protectedvirtualArrayList<object>_vertices{get;set;}
protectedvirtualT_firstInsertedNode{get;set;}
protectedvirtualbool[,]_adjacencyMatrix{get;set;}


/// <summary>
/// CONSTRUCTOR
/// </summary>
publicDirectedDenseGraph(uintcapacity=10)
{
_edgesCount=0;
_verticesCount=0;
_verticesCapacity=(int)capacity;

_vertices=newArrayList<object>(_verticesCapacity);
_adjacencyMatrix=newbool[_verticesCapacity,_verticesCapacity];
_adjacencyMatrix.Populate(rows:_verticesCapacity,columns:_verticesCapacity,defaultValue:false);
}


/// <summary>
/// Helper function. Checks if edge exist in graph.
/// </summary>
protectedvirtualbool_doesEdgeExist(intsource,intdestination)
{
return(_adjacencyMatrix[source,destination]==true);
}

/// <summary>
/// Returns true, if graph is directed; false otherwise.
/// </summary>
publicvirtualboolIsDirected
{
get{returntrue;}
}

/// <summary>
/// Returns true, if graph is weighted; false otherwise.
/// </summary>
publicvirtualboolIsWeighted
{
get{returnfalse;}
}

/// <summary>
/// Gets the count of vetices.
/// </summary>
publicvirtualintVerticesCount
{
get{return_verticesCount;}
}

/// <summary>
/// Gets the count of edges.
/// </summary>
publicvirtualintEdgesCount
{
get{return_edgesCount;}
}

/// <summary>
/// Returns the list of Vertices.
/// </summary>
publicvirtualIEnumerable<T>Vertices
{
get
{
foreach(varvertexin_vertices)
if(vertex!=null)
yieldreturn(T)vertex;
}
}


IEnumerable<IEdge<T>>IGraph<T>.Edges
{
get{returnthis.Edges;}
}

IEnumerable<IEdge<T>>IGraph<T>.IncomingEdges(Tvertex)
{
returnthis.IncomingEdges(vertex);
}

IEnumerable<IEdge<T>>IGraph<T>.OutgoingEdges(Tvertex)
{
returnthis.OutgoingEdges(vertex);
}


/// <summary>
/// An enumerable collection of all directed unweighted edges in graph.
/// </summary>
publicvirtualIEnumerable<UnweightedEdge<T>>Edges
{
get
{
foreach(varvertexin_vertices)
foreach(varoutgoingEdgeinOutgoingEdges((T)vertex))
yieldreturnoutgoingEdge;
}
}

/// <summary>
/// Get all incoming directed unweighted edges to a vertex.
/// </summary>
publicvirtualIEnumerable<UnweightedEdge<T>>IncomingEdges(Tvertex)
{
if(!HasVertex(vertex))
thrownewKeyNotFoundException("Vertex doesn't belong to graph.");

intsource=_vertices.IndexOf(vertex);

for(intadjacent=0;adjacent<_vertices.Count;++adjacent)
{
if(_vertices[adjacent]!=null&&_doesEdgeExist(adjacent,source))
{
yieldreturn(newUnweightedEdge<T>(
(T)_vertices[adjacent],// from
vertex// to
));
}
}//end-for
}

/// <summary>
/// Get all outgoing directed unweighted edges from a vertex.
/// </summary>
publicvirtualIEnumerable<UnweightedEdge<T>>OutgoingEdges(Tvertex)
{
if(!HasVertex(vertex))
thrownewKeyNotFoundException("Vertex doesn't belong to graph.");

intsource=_vertices.IndexOf(vertex);

for(intadjacent=0;adjacent<_vertices.Count;++adjacent)
{
if(_vertices[adjacent]!=null&&_doesEdgeExist(source,adjacent))
{
yieldreturn(newUnweightedEdge<T>(
vertex,// from
(T)_vertices[adjacent]// to
));
}
}//end-for
}


/// <summary>
/// Connects two vertices together in the direction: first->second.
/// </summary>
publicvirtualboolAddEdge(Tsource,Tdestination)
{
// Get indices of vertices
intsrcIndex=_vertices.IndexOf(source);
intdstIndex=_vertices.IndexOf(destination);

// Check existence of vertices and non-existence of edge
if(srcIndex==-1||dstIndex==-1)
returnfalse;
if(_doesEdgeExist(srcIndex,dstIndex))
returnfalse;

_adjacencyMatrix[srcIndex,dstIndex]=true;

// Increment edges count
++_edgesCount;

returntrue;
}

/// <summary>
/// Removes edge, if exists, from source to destination.
/// </summary>
publicvirtualboolRemoveEdge(Tsource,Tdestination)
{
// Get indices of vertices
intsrcIndex=_vertices.IndexOf(source);
intdstIndex=_vertices.IndexOf(destination);

// Check existence of vertices and non-existence of edge
if(srcIndex==-1||dstIndex==-1)
returnfalse;
if(!_doesEdgeExist(srcIndex,dstIndex))
returnfalse;

_adjacencyMatrix[srcIndex,dstIndex]=false;

// Increment edges count
--_edgesCount;

returntrue;
}

/// <summary>
/// Add a collection of vertices to the graph.
/// </summary>
publicvirtualvoidAddVertices(IList<T>collection)
{
if(collection==null)
thrownewArgumentNullException();

foreach(varvertexincollection)
AddVertex(vertex);
}

/// <summary>
/// Add vertex to the graph
/// </summary>
publicvirtualboolAddVertex(Tvertex)
{
// Return of the capacity is reached
if(_verticesCount>=_verticesCapacity)
returnfalse;

// Return if vertex already exists
if(HasVertex(vertex))
returnfalse;

// Initialize first inserted node
if(_verticesCount==0)
_firstInsertedNode=vertex;

// Try inserting vertex at previously lazy-deleted slot
intindexOfNull=_vertices.IndexOf(EMPTY_VERTEX_SLOT);

if(indexOfNull!=-1)
_vertices[indexOfNull]=vertex;
else
_vertices.Add(vertex);

// Increment vertices count
++_verticesCount;

returntrue;
}

/// <summary>
/// Removes the specified vertex from graph.
/// </summary>
publicvirtualboolRemoveVertex(Tvertex)
{
// Return if graph is empty
if(_verticesCount==0)
returnfalse;

// Get index of vertex
intindex=_vertices.IndexOf(vertex);

// Return if vertex doesn't exists
if(index==-1)
returnfalse;

// Lazy-delete the vertex from graph
//_vertices.Remove (vertex);
_vertices[index]=EMPTY_VERTEX_SLOT;

// Decrement the vertices count
--_verticesCount;

// Remove all outgoing and incoming edges to this vertex
for(inti=0;i<_verticesCapacity;++i)
{
// Source edge
if(_doesEdgeExist(index,i))
{
_adjacencyMatrix[index,i]=false;

// Decrement the edges count
--_edgesCount;
}

// Destination edge
if(_doesEdgeExist(i,index))
{
_adjacencyMatrix[i,index]=false;

// Decrement the edges count
--_edgesCount;
}
}

returntrue;
}

/// <summary>
/// Checks whether there is an edge from source to destination.
/// </summary>
publicvirtualboolHasEdge(Tsource,Tdestination)
{
// Get indices of vertices
intsrcIndex=_vertices.IndexOf(source);
intdstIndex=_vertices.IndexOf(destination);

// Check the existence of vertices and the directed edge
return(srcIndex!=-1&&dstIndex!=-1&&_doesEdgeExist(srcIndex,dstIndex));
}

/// <summary>
/// Determines whether this graph has the specified vertex.
/// </summary>
publicvirtualboolHasVertex(Tvertex)
{
return_vertices.Contains(vertex);
}

/// <summary>
/// Returns the neighbours doubly-linked list for the specified vertex.
/// </summary>
publicvirtualDataStructures.Lists.DLinkedList<T>Neighbours(Tvertex)
{
varneighbors=newDLinkedList<T>();
intsource=_vertices.IndexOf(vertex);

// Check existence of vertex
if(source!=-1)
for(intadjacent=0;adjacent<_vertices.Count;++adjacent)
if(_vertices[adjacent]!=null&&_doesEdgeExist(source,adjacent))
neighbors.Append((T)_vertices[adjacent]);

returnneighbors;
}

/// <summary>
/// Returns the degree of the specified vertex.
/// </summary>
publicvirtualintDegree(Tvertex)
{
if(!HasVertex(vertex))
thrownewKeyNotFoundException();

returnNeighbours(vertex).Count;
}

/// <summary>
/// Returns a human-readable string of the graph.
/// </summary>
publicvirtualstringToReadable()
{
stringoutput=string.Empty;

for(inti=0;i<_vertices.Count;++i)
{
if(_vertices[i]==null)
continue;

varnode=(T)_vertices[i];
varadjacents=string.Empty;

output=String.Format("{0}\r\n{1}: [",output,node);

foreach(varadjacentNodeinNeighbours(node))
adjacents=String.Format("{0}{1},",adjacents,adjacentNode);

if(adjacents.Length>0)
adjacents=adjacents.TrimEnd(newchar[]{',',' '});

output=String.Format("{0}{1}]",output,adjacents);
}

returnoutput;
}

/// <summary>
/// A depth first search traversal of the graph starting from the first inserted node.
/// Returns the visited vertices of the graph.
/// </summary>
publicvirtualIEnumerable<T>DepthFirstWalk()
{
returnDepthFirstWalk(_firstInsertedNode);
}

/// <summary>
/// A depth first search traversal of the graph, starting from a specified vertex.
/// Returns the visited vertices of the graph.
/// </summary>
publicvirtualIEnumerable<T>DepthFirstWalk(Tsource)
{
if(_verticesCount==0)
returnnewArrayList<T>();
if(!HasVertex(source))
thrownewException("The specified starting vertex doesn't exist.");

varstack=newLists.Stack<T>(_verticesCount);
varvisited=newHashSet<T>();
varlistOfNodes=newArrayList<T>(_verticesCount);

stack.Push(source);

while(!stack.IsEmpty)
{
varcurrent=stack.Pop();

if(!visited.Contains(current))
{
listOfNodes.Add(current);
visited.Add(current);

foreach(varadjacentinNeighbours(current))
if(!visited.Contains(adjacent))
stack.Push(adjacent);
}
}

returnlistOfNodes;
}

/// <summary>
/// A breadth first search traversal of the graphstarting from the first inserted node.
/// Returns the visited vertices of the graph.
/// </summary>
publicvirtualIEnumerable<T>BreadthFirstWalk()
{
returnBreadthFirstWalk(_firstInsertedNode);
}

/// <summary>
/// A breadth first search traversal of the graph, starting from a specified vertex.
/// Returns the visited vertices of the graph.
/// </summary>
publicvirtualIEnumerable<T>BreadthFirstWalk(Tsource)
{
if(_verticesCount==0)
returnnewArrayList<T>();
if(!HasVertex(source))
thrownewException("The specified starting vertex doesn't exist.");

varvisited=newHashSet<T>();
varqueue=newLists.Queue<T>(VerticesCount);
varlistOfNodes=newArrayList<T>(VerticesCount);

listOfNodes.Add(source);
visited.Add(source);

queue.Enqueue(source);

while(!queue.IsEmpty)
{
varcurrent=queue.Dequeue();
varneighbors=Neighbours(current);

foreach(varadjacentinneighbors)
{
if(!visited.Contains(adjacent))
{
listOfNodes.Add(adjacent);
visited.Add(adjacent);
queue.Enqueue(adjacent);
}
}
}

returnlistOfNodes;
}

/// <summary>
/// Clear this graph.
/// </summary>
publicvirtualvoidClear()
{
_edgesCount=0;
_verticesCount=0;
_vertices=newArrayList<object>(_verticesCapacity);
_adjacencyMatrix=newbool[_verticesCapacity,_verticesCapacity];
_adjacencyMatrix.Populate(rows:_verticesCapacity,columns:_verticesCapacity,defaultValue:false);
}

}

}