README
¶
go-mcf
A Go port of LEMON 1.3.1's primal Network Simplex min-cost-flow solver, specialised for DeFi.
Scope
go-mcf targets DeFi routing on EVM-compatible networks: flows and capacities
are *uint256.Int to match 256-bit token amounts, while costs are int64.
If your workload fits in int64 flows, a general-purpose min-cost-flow
library will serve you better.
Features
- Primal Network Simplex ported from LEMON 1.3.1.
*uint256.Intflows and capacities;int64costs.- Strict-fill semantics with configurable tolerance for negative-cost cycles.
- Context cancellation in
Solve. - In-place flow writes on caller-owned
Arcslices. - Invariant-checking test helpers (see
checksolution_test.go).
Install
go get github.com/branched-services/go-mcf
Quickstart
package main
import (
"context"
"fmt"
"log"
mcf "github.com/branched-services/go-mcf"
"github.com/holiman/uint256"
)
func main() {
arcs := []mcf.Arc{
{From: 0, To: 1, Cost: 10, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
{From: 1, To: 2, Cost: 20, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
{From: 0, To: 2, Cost: 50, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
}
result, err := mcf.Solve(context.Background(), arcs, 3, 0, 2, uint256.NewInt(50))
if err != nil {
log.Fatal(err)
}
fmt.Println("TotalFlow:", result.TotalFlow)
fmt.Println("TotalCost:", result.TotalCost)
}
Runnable version: examples/basic.
Documentation
- API reference: https://pkg.go.dev/github.com/branched-services/go-mcf
- Algorithmic notes and invariants:
docs/spec.md.
Contributing
See CONTRIBUTING.md.
Security
See SECURITY.md. Report vulnerabilities privately via GitHub Security Advisories.
Acknowledgements
This project is derived from LEMON 1.3.1. See NOTICE for attribution.
License
Boost Software License 1.0 — see LICENSE.
Documentation
¶
Overview ¶
Package mcf provides a primal Network Simplex min-cost-flow solver ported from LEMON 1.3.1. It uses github.com/holiman/uint256.Int for flow and capacity values and int64 for costs, targeting DeFi applications that require 256-bit unsigned arithmetic on EVM-compatible networks.
Example ¶
Example demonstrates routing 50 units of flow across a three-node network with two parallel paths. The cheaper path (0->1->2, cost 30/unit) is saturated in preference to the direct arc (0->2, cost 50/unit).
package main
import (
"context"
"fmt"
mcf "github.com/branched-services/go-mcf"
"github.com/holiman/uint256"
)
func main() {
arcs := []mcf.Arc{
{From: 0, To: 1, Cost: 10, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
{From: 1, To: 2, Cost: 20, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
{From: 0, To: 2, Cost: 50, Capacity: uint256.NewInt(100), Flow: new(uint256.Int)},
}
result, err := mcf.Solve(context.Background(), arcs, 3, 0, 2, uint256.NewInt(50))
if err != nil {
fmt.Println("error:", err)
return
}
fmt.Println("TotalFlow:", result.TotalFlow)
fmt.Println("TotalCost:", result.TotalCost)
}
Output: TotalFlow: 50 TotalCost: 1500
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrInfeasible = errors.New("mcf: demand cannot be routed from source to sink")
ErrInfeasible is returned when the requested demand cannot be routed from source to sink within the network's capacity constraints.
var ErrInvalidInput = errors.New("mcf: invalid input")
ErrInvalidInput is returned when Solve receives input that violates preconditions (see Solve documentation for the full list).
Functions ¶
This section is empty.
Types ¶
type Arc ¶
Arc represents a directed arc in the network. From and To are zero-based node indices, Cost is the per-unit cost of sending flow along the arc, and Capacity is the maximum flow the arc can carry.
On a successful call to Solve, Flow is written in place to the optimal flow value for this arc. Callers must not share the same []Arc slice across concurrent Solve calls.
type Result ¶
type Result struct {
// TotalFlow is the total flow pushed from source to sink.
TotalFlow *uint256.Int
// TotalCost is the sum of arc costs weighted by their flows, computed as
// int64. Because individual arc flows may exceed int64 range, TotalCost is
// advisory and may under-report for very large flows where the true
// weighted sum exceeds math.MaxInt64.
TotalCost int64
}
Result holds the output of a successful Solve call.
func Solve ¶
func Solve(ctx context.Context, arcs []Arc, n, source, sink int, demand *uint256.Int) (Result, error)
Solve computes a minimum-cost flow of the given demand from source to sink in a network with n nodes and the provided arcs. On success it returns a Result and writes each arc's optimal flow into Arc.Flow in place.
Solve is safe to call concurrently from multiple goroutines on independent inputs. Callers must not share the same arcs slice across concurrent Solve calls because Arc.Flow is written in place.
If ctx is cancelled or its deadline expires, Solve returns (Result{}, ctx.Err()) with no partial results written to arcs.
Example (Infeasible) ¶
ExampleSolve_infeasible shows how Solve reports an infeasible instance: the requested demand exceeds every source-to-sink cut in the network.
package main
import (
"context"
"errors"
"fmt"
mcf "github.com/branched-services/go-mcf"
"github.com/holiman/uint256"
)
func main() {
arcs := []mcf.Arc{
{From: 0, To: 1, Cost: 1, Capacity: uint256.NewInt(10), Flow: new(uint256.Int)},
}
_, err := mcf.Solve(context.Background(), arcs, 2, 0, 1, uint256.NewInt(20))
if errors.Is(err, mcf.ErrInfeasible) {
fmt.Println("infeasible")
}
}
Output: infeasible
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
examples
|
|
|
basic
command
Command basic is the runnable version of the README quickstart: a three-node network with two parallel source-to-sink paths.
|
Command basic is the runnable version of the README quickstart: a three-node network with two parallel source-to-sink paths. |