Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

QuickGraph: A 100% C# graph library with Graphviz Support.

, 23 Apr 2007
A generic directed graph library with a Graphviz Web Control Bonus!
quickgraph_demo.zip
Release
QuickGraph.dll
QuickGraph.Algorithms.Graphviz.dll
QuickGraph.Representations.dll
QuickGraph.Algorithms.dll
QuickGraphTest.exe
QuickGraph.Web.dll
QuickGraph_doc_v2.1.chm
QuickGraph.Concepts.dll
QuickGraph.Collections.dll
QuickGraph.Predicates.dll
QuickGraph.Exceptions.dll
quickgraph_src.zip
QuickGraph
QuickGraph
Providers
QuickGraph.csproj.user
Untitled.ndoc
QuickGraph.Algorithms
QuickGraph.Algorithms.csproj.user
Search
ShortestPath
Visitors
MaximumFlow
QuickGraph.Algorithms.Graphviz
QuickGraph.Algorithms.Graphviz.csproj.user
Collections
QuickGraph.Collections
QuickGraph.Collections.csproj.user
Collections
QuickGraph.Concepts
QuickGraph.Concepts.csproj.user
Traversals
Modifications
Predicates
Algorithms
Visitors
Providers
QuickGraph.Exceptions
QuickGraph.Exceptions.csproj.user
QuickGraph.Predicates
QuickGraph.Predicates.csproj.user
QuickGraph.Representations
QuickGraph.Representations.csproj.user
QuickGraph.Web
QuickGraph.Web.csproj.user
Controls
Design
bin
Debug
QuickGraph.Web
QuickGraph.Web
QuickGraphNUnit
App.ico
QuickGraphNUnit.csproj.user
GraphConcepts
Generators
Algorithms
Search
QuickGraphTest
App.ico
QuickGraphTest.csproj.user
bin
Debug
filedependency_127157114549330692.dot
fd_noname.PNG
filedependency_127157123413136692.dot
filedependency_127157123413136692.png
filedependency_127157123415941060.dot
filedependency_127157123415941060.png
fd_withnames.PNG
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Jonathan de Halleux
Engineer
United States United States
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).

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150123.1 | Last Updated 23 Apr 2007
Article Copyright 2003 by Jonathan de Halleux
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid