DirectedWeightedDenseGraph.cs

/***
 * The Directed Weighted 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.
 * A weighted graph is a graph where each edge has a weight (zero weights mean there is no edge).
 * 
 * An adjacency-matrix (two dimensional array of longs) weighted digraph representation. 
 * Inherits and extends the Directed Dense verion (DirectedDenseGraph<T> class).
 * Implements the IWeightedGraph<T> interface.
 */

usingSystem;
usingSystem.Collections.Generic;

usingDataStructures.Common;
usingDataStructures.Lists;

namespaceDataStructures.Graphs
{

/// <summary>
/// This class represents the graph as an adjacency-matrix (two dimensional integer array).
/// </summary>
publicclassDirectedWeightedDenseGraph<T>:DirectedDenseGraph<T>,IWeightedGraph<T>whereT:IComparable<T>
{
/// <summary>
/// INSTANCE VARIABLES
/// </summary>
privateconstlongEMPTY_EDGE_SLOT=0;
privateconstobjectEMPTY_VERTEX_SLOT=(object)null;

// Store edges and their weights as integers.
// Any edge with a value of zero means it doesn't exist. Otherwise, it exist with a specific weight value.
// Default value for positive edges is 1.
protectednewlong[,]_adjacencyMatrix{get;set;}


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

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


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

/// <summary>
/// Helper function. Gets the weight of a directed edge.
/// </summary>
privatelong_getEdgeWeight(intsource,intdestination)
{
return_adjacencyMatrix[source,destination];
}


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

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

/// <summary>
/// Get all incoming unweighted edges to a vertex.
/// </summary>
publicvirtualIEnumerable<WeightedEdge<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(newWeightedEdge<T>(
(T)_vertices[adjacent],// from
vertex,// to
_getEdgeWeight(source,adjacent)// weight
));
}
}//end-for
}

/// <summary>
/// Get all outgoing unweighted edges from a vertex.
/// </summary>
publicvirtualIEnumerable<WeightedEdge<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(newWeightedEdge<T>(
vertex,// from
(T)_vertices[adjacent],// to
_getEdgeWeight(source,adjacent)// weight
));
}
}//end-for
}


/// <summary>
/// Obsolete. Another AddEdge function is implemented with a weight parameter.
/// </summary>
[Obsolete("Use the AddEdge method with the weight parameter.")]
publicnewboolAddEdge(Tsource,Tdestination)
{
thrownewNotImplementedException();
}

/// <summary>
/// Connects two vertices together with a weight, in the direction: first->second.
/// </summary>
publicvirtualboolAddEdge(Tsource,Tdestination,longweight)
{
// Return if the weight is equals to the empty edge value
if(weight==EMPTY_EDGE_SLOT)
returnfalse;

// 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]=weight;

// Increment edges count
++_edgesCount;

returntrue;
}

/// <summary>
/// Removes edge, if exists, from source to destination.
/// </summary>
publicoverrideboolRemoveEdge(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]=EMPTY_EDGE_SLOT;

// Increment edges count
--_edgesCount;

returntrue;
}

/// <summary>
/// Updates the edge weight from source to destination.
/// </summary>
publicvirtualboolUpdateEdgeWeight(Tsource,Tdestination,longweight)
{
// Return if the weight is equals to the empty edge value
if(weight==EMPTY_EDGE_SLOT)
returnfalse;

// 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]=weight;

returntrue;
}

/// <summary>
/// Removes the specified vertex from graph.
/// </summary>
publicoverrideboolRemoveVertex(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)
{
// Outgoing edge
if(_doesEdgeExist(index,i))
{
_adjacencyMatrix[index,i]=EMPTY_EDGE_SLOT;

// Decrement the edges count
--_edgesCount;
}

// Incoming edge
if(_doesEdgeExist(i,index))
{
_adjacencyMatrix[i,index]=EMPTY_EDGE_SLOT;

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

returntrue;
}

/// <summary>
/// Get edge object from source to destination.
/// </summary>
publicvirtualWeightedEdge<T>GetEdge(Tsource,Tdestination)
{
// Get indices of vertices
intsrcIndex=_vertices.IndexOf(source);
intdstIndex=_vertices.IndexOf(destination);

// Check the existence of vertices and the directed edge
if(srcIndex==-1||dstIndex==-1)
thrownewException("One of the vertices or both of them doesn't exist.");
if(!_doesEdgeExist(srcIndex,dstIndex))
thrownewException("Edge doesn't exist.");

return(newWeightedEdge<T>(source,destination,_getEdgeWeight(srcIndex,dstIndex)));
}

/// <summary>
/// Returns the edge weight from source to destination.
/// </summary>
publicvirtuallongGetEdgeWeight(Tsource,Tdestination)
{
returnGetEdge(source,destination).Weight;
}

/// <summary>
/// Returns the neighbours of a vertex as a dictionary of nodes-to-weights.
/// </summary>
publicvirtualDictionary<T,long>NeighboursMap(Tvertex)
{
if(!HasVertex(vertex))
returnnull;

varneighbors=newDictionary<T,long>();
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.Add((T)_vertices[adjacent],_getEdgeWeight(source,adjacent));

returnneighbors;
}

/// <summary>
/// Returns a human-readable string of the graph.
/// </summary>
publicoverridestringToReadable()
{
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(varadjacentNodeinNeighboursMap(node))
adjacents=String.Format("{0}{1}({2}), ",adjacents,adjacentNode.Key,adjacentNode.Value);

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

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

returnoutput;
}

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

}

}