| Author: | Lukas Prokop |
|---|---|
| Version: | 1.0.0 |
| license: | CC-0 |
Edmond's branching algorithm implementation in Python3 and Haskell. Edmond's branching algorithm takes a digraph and returns an arborescence. In that sense it is the digraph equivalent to minimum spanning trees.
You write a simple text file to specify the digraph. Its structure looks like this:
{# of vertices} {# of edges} {root vertex}
{edge source} {edge dest} {edge weight}
{edge source} {edge dest} {edge weight}
{edge source} {edge dest} {edge weight}
...
and returns text output like the following:
{# of vertices} {# of edges} {root vertex} {total weight of branching}
{edge source} {edge dest} {edge weight}
{edge source} {edge dest} {edge weight}
{edge source} {edge dest} {edge weight}
...
where the edges in the output are a subset of the edges of the input. A line might be prepended by a 'b' meaning this edge occured in the input graph, but does not occur in the output graph. A leading 'c' means this line is a comment and can be ignored.
Consider tests/07_two_cycles.in.graph as an example:
7 8 1 1 2 1 2 6 2 6 7 3 7 2 4 2 3 5 3 4 6 4 5 8 5 3 7
Leading to the following output with python3:
c computing spanning arborescence of minimum weight for [(1, 2, 1.0), (2, 6, 2.0), (6, 7, 3.0), (7, 2, 4.0), (2, 3, 5.0), (3, 4, 6.0), (4, 5, 8.0), (5, 3, 7.0)] with root=1 c P = [(1, 2, 1.0), (2, 3, 5.0), (3, 4, 6.0), (4, 5, 8.0), (2, 6, 2.0), (6, 7, 3.0)] c found no cycle, returning [(1, 2, 1.0), (2, 3, 5.0), (3, 4, 6.0), (4, 5, 8.0), (2, 6, 2.0), (6, 7, 3.0)] 7 6 1 25.0 b 1 2 1 b 2 6 2 b 6 7 3 b 7 2 4 b 2 3 5 b 3 4 6 b 4 5 8 b 5 3 7 1 2 1 2 3 5 3 4 6 4 5 8 2 6 2 6 7 3
The result is visualized as file 07_two_cycles.png.
Python is available as FLOSS at python.org and Haskell is recommended to be compiled using the Glasgow Haskell Compiler. My implementation is given in the
You can run the file by specifying the executable/script and providing the digraph file as parameter:
python3 python3/edmonds.py tests/07_two_cycles.in.graph ./haskell/edmonds tests/07_two_cycles.in.graph
where ./haskell/edmonds is the compiled executable.
The testsuite was compared with reference graphs generated by a brute force implementation and graphviz (namely the dot command line utility). The brute force approach generates all arborescences and selects the one of lowest total weight.
best regards, prokls