Skip to content

haskell project for non-procedural programming class. Implementation of edmonds-karp max-flow algorithm with application to vertex-connectivity

Notifications You must be signed in to change notification settings

nathan-chappell/haskell-project

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 

Repository files navigation

--UPDATES

The previous implementation needed correction, and now there is the added requirement that vertex labels be greater than 0.  The previous max-connectivity algorithm was incorrect, and now uses negative-labeled vertices for internal use.

--

This is a haskell implemenation of the Edmonds-Karp max-flow algorithm (see: https://en.wikipedia.org/wiki/Edmonds-Karp_algorithm for more information).  The usage is as follows:

./flow (-f -c) filename

The program takes as input an option and filename, and then executes either the maximum flow algorithm, or uses the maximum flow algorithm to test the vertex connectivity of the graph.

  -f Maximum Flow.  This option reads the graph as described under "max flow format" and determine a (not necessarily unique) set of values for flow along edges corresponding to a max-flow, and print the results to standard output.
  
  -c Connectivity.  This option reads the graph as described under "connectivity format" and outputs the calculated vertex connectivity to standard output.
  
This program does not expect very large graphs as input, as it would not likely be very useful for large graphs anyways (time complexity is O(V^8) for -c and space is O(E+V) with a non-trivial coefficient).  The implementation actually expects that there will not be too many vertices, and uses vertices labled 10000 and higher for internal purposes (see the formats for more information).  The Connectivity algorithm proceeds roughly as follows: an undirected graph is expected on input, which is then transformed into a new graph with each vertex "expanded."  This means that each vertex is turned into an edge and two new vertices, such that contracting this edge and removing parallel edges would result in the original graph.  At this point, each edge is doubled and given a capacity of 1, and the maximum flow algorithm is run on each pair of vertices from the original graph.  A "maximum" flow in this graph corresponds to the maximum number of vertex independent paths from one vertex to the other (this is because to get from one "side" of a vertex to the other, the entire capacity must be used).  Then, the minimal value of "max-flow" between all vertices is the vertex connectivity.

  Max Flow Format
  The input format for the max-flow option is as follows:

start-label terminal-label
vertex-label vertex-label capacity
vertex-label vertex-label capacity
vertex-label vertex-label capacity
...

Each label should be an integer between 1 and 1000, and each capacity should be an integer (< 2^31).

  Connectivity Format
  The input for the connectivity option is as follows:

vertex-label vertex-label
vertex-label vertex-label
vertex-label vertex-label
...

Each label should be an integer between 1 and 1000.  These are the edges of the graph, which is assumed to be undirected for this application.  If a duplicate edges are included they will be ignored (they are nubbed out).

If you have any problems, questions, comments, concerns, bitches, gripes, complaints, or just want to say hi, please email: [email protected], and I will respond to you if I feel like it.

Sincerely,
Nathan Chappell

About

haskell project for non-procedural programming class. Implementation of edmonds-karp max-flow algorithm with application to vertex-connectivity

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published