Network Flows structures and algortihms for Julia v0.4+
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
ioexample DIMACS and natural CSV format as input in io.jl + example in ioexampl… Sep 8, 2015
src
test
.gitignore NetworkFlows.jl generated files. Sep 7, 2015
.travis.yml Update requirement for package and travis Sep 7, 2015
LICENSE.md NetworkFlows.jl generated files. Sep 7, 2015
README.md
REQUIRE version 0.4 REQUIRE Oct 19, 2015
appveyor.yml Update CI URLs to point to new caching infrastructure May 18, 2017

README.md

NetworkFlows.jl

Build Status

This package development is currently stopped. All the functionalities have been added to LightGraphs.jl and LightGraphsExtras.jl. No speed efficiency comparison have done though. I will maintain the package for the next updates of Julia till v1.0.

NetworkFlows.jl is a Julia package that provides network flows algorithms. The design of this package is based on simple and fast flow algorithms. On mid/long term, it could be merged with other graphs packages in Julia (Graphs.jl,LightGraph.jl, etc). All data structures and algorithms are implemented in pure Julia, and thus they are portable.

Main Features

The network/graph structure used in NetworkFlows.jl tries to optimize the access time for Augmenting Shortest Paths max-flow algorithm. The structure is as follows:

  • The graph is simple (no parallel links) and the links are oriented (arcs)
  • The links are ordered by (tail,head) and adjacent in a Vector{Arc}. The type Arc has 3 fields: sym::Int for the symmetric(reverse) arc, head::Int for the index of the head node, and cap:Float64 for the value of its capacity. At the import/construction of the graph, a reverse link is added (unless it already exists).
  • The nodes are indexed starting from 1 (as the Vectors in julia). The function zero_to_one!() can be used on the links to transform a set of links starting from 0.
  • The IO are currently supporting manual input, DIMACS and CSV format input, and redefinition of print(::Network). Example of files for IO are in ioexample/ .
  • List of available algorithms:
    • max-flow (Edmonds-Karp): edmondsKarp(g::Network)
    • connectivity(g::Network)
    • multiroute flow (Kishimoto): kishimoto(g::Network, k::Int) where k is the number of routes
    • min-cut (BFS on maxflow): mincut(g::Network)
    • Extended Multiroute Flow (k is a non-integer parameter): breakingPoints(g::Network)
    • Multilink Attack (upper and lower bounds; success rate): mixedMLA(g::Network) and successMLA(g::Network)

Documentation (starter)

Examples of use are given in the test/runtest.jl

To get started with a simple graph:

edges = [(1,2,2.),(1,3,3.),(1,4,5.),(2,5,2.),(3,5,3.),(4,5,5.),(5,6,3.),(5,7,3.),(5,8,3.),(6,9,3.),(7,9,3.),(8,9,3.),(9,10,7.),(9,11,7.),(10,12,7.),(11,12,7.)]

g = Network(edges,true,1,12)

mixedMLA(g)