In this article, you will learn about a 100% C# Generic Graph Library, an attempt to port the Boost Graph Library (BGL) from C++ to C#.
- quickgraph_demo.zip
- Release
- QuickGraph.Algorithms.dll
- QuickGraph.Algorithms.Graphviz.dll
- QuickGraph.Collections.dll
- QuickGraph.Concepts.dll
- QuickGraph.dll
- QuickGraph.Exceptions.dll
- QuickGraph.Predicates.dll
- QuickGraph.Representations.dll
- QuickGraph.Web.dll
- QuickGraph_doc_v2.1.chm
- QuickGraphTest.exe
- quickgraph_src.zip
- QuickGraph.Algorithms.Graphviz
- QuickGraph.Algorithms
- QuickGraph.Collections
- QuickGraph.Concepts
- QuickGraph.Exceptions
- QuickGraph.Predicates
- QuickGraph.Representations
- QuickGraph.Web
- QuickGraph
- QuickGraphNUnit
- QuickGraphTest
|
namespace QuickGraph.Algorithms.MaximumFlow
{
using System;
using QuickGraph.Collections;
using QuickGraph.Predicates;
using QuickGraph.Algorithms.Visitors;
using QuickGraph.Algorithms.Search;
/// <summary>
/// Description r�sum�e de EdmundsKarpMaximumFlow.
/// </summary>
public class EdmundsKarpMaximumFlow : Algorithm
{
private EdgeDoubleDictionary m_ResidualEdgeCapacities;
private EdgeDoubleDictionary m_EdgeCapacities;
private VertexEdgeDictionary m_Predecessors;
public EdmundsKarpMaximumFlow(
Graph g,
EdgeDoubleDictionary edgeCapacities
) : base(g)
{
if (edgeCapacities == null)
throw new ArgumentNullException("Edge capacities");
m_EdgeCapacities = edgeCapacities;
m_ResidualEdgeCapacities = null;
m_Predecessors = new VertexEdgeDictionary();
}
public EdgeDoubleDictionary ResidualEdgeCapacities
{
get
{
return m_ResidualEdgeCapacities;
}
}
public EdgeDoubleDictionary EdgeCapacities
{
get
{
return m_EdgeCapacities;
}
}
public VertexEdgeDictionary Predecessors
{
get
{
return m_Predecessors;
}
}
public double Compute(Vertex src, Vertex sink)
{
m_ResidualEdgeCapacities = new EdgeDoubleDictionary();
// initializing
foreach(Vertex u in VisitedGraph.Vertices)
foreach(Edge e in u.OutEdges)
ResidualCapacities[e] = Capacities[e];
Colors[sink] = GraphColor.Gray;
while (Colors[sink] != GraphColor.White)
{
VertexBuffer Q = new VertexBuffer();
ResidualEdgePredicate ep = new ResidualEdgePredicate(ResidualCapacities);
BreadthFirstSearchAlgorithm bfs = new BreadthFirstSearchAlgorithm(resg,Q,Colors);
PredecessorVisitor pred = new PredecessorVisitor(Predecessors);
pred.RegisterHandlers(bfs);
bfs.Compute(src);
if (Colors[sink] != GraphColor.White)
Augment(src, sink, pred.Predecessors);
} // while
double flow = 0;
foreach(Edge e in src.OutEdges)
flow += (EdgeCapacities[e] - ResidualEdgeCapacities[e]);
return flow;
}
internal void Augment(Vertex src, Vertex sink, VertexEdgeDictionary predecessors)
{
// find minimum residual capacity along the augmenting path
double delta = double.MaxValue;
Edge e = predecessors[sink];
Vertex u = null;
do
{
delta = Math.Min(delta, ResidualEdgeCapacities[e]);
u = e.Source;
e = predecessors[u];
} while (u != src);
// push delta units of flow along the augmenting path
e = predecessors[sink];
do
{
ResidualEdgeCapacities[e] -= delta;
ResidualEdgeCapacities[ReverseEdges[e]] += delta;
u = e.Source;
e = predecessors[u];
} while (u != src);
}
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
Jonathan de Halleux is Civil Engineer in Applied Mathematics. He finished his PhD in 2004 in the rainy country of Belgium. After 2 years in the Common Language Runtime (i.e. .net), he is now working at Microsoft Research on Pex (http://research.microsoft.com/pex).