Skip to content

Latest commit

 

History

History
53 lines (33 loc) · 1.36 KB

README.md

File metadata and controls

53 lines (33 loc) · 1.36 KB
Raw

pyedmond

Edmond's optimal branching algorithm in C++ wrapped by Python.

As it's in C++ internally, it's faster and more memory-efficient than networkx.maximum_spanning_arborescence

Example usage

import numpy as np
import networkx as nx
from pyedmond import find_minimum_branching

g = nx.complete_graph(10, create_using=nx.DiGraph())
weights = np.abs(np.random.rand(g.number_of_edges()))
for k, (i, j) in enumerate(g.edges_iter()):
    g[i][j]['weight'] = weights[k]

edges = find_minimum_branching(g, roots=[0, 1])  # returns a list of (int, int) edges

Installation

pip3 install pyedmond

Test

python3 setup.py test

notes on code

_core.cpp

the interface between python and edmonds algorithm

Main classes/functions

  • Graph: the graph type
  • build_graph: build graph from a list of edges and weights
  • optimal_branching: find the optimal branching (used internally, need to convert the graph by yourself)
  • find_optimal_branching: higher level function (graph is converted automatically)

Todo

  • setup.py
  • usage documentation
  • test coverage
  • benchmark plot

Reference

the C++ part is based on atofigh/edmonds-alg