A tiny command line interface tool for solving (non) integer & network optimization problems.
- Clone this repo.
- Open console, navigate to repo, execute
pip install -r requirements.txt. - You're ready to go.
Introduction:
$ python3 main.py
Usage: main.py [OPTIONS] COMMAND [ARGS]...
Simple CLI for optimization problems.
Options:
-h, --help Show this message and exit.
Part 1a:
branchbound IP relaxation on an Ax<=b system. File must have the sheets named 'A', 'b' an...
hyperplanes Retruns basic & feasible solutions of an Ax<=b system with 2 or 3 dimensions....
matanalysis Basic matrix analysis insights.
plot Plots a 2D system of inequalities provided in Ax<=b form. File must have the...
simplex Applies Simplex on an Ax<=b system with 2 or 3 dimensions. File must have the...
Part 2a:
aitken Returns the Aitken sequence for a value series of at least 3.
broyden Iterating optimization using Broyden's method given a function and starting v...
broydeninter Iterating optimization using Broyden's method given the interim results start...
diffbeauty Returns the derivative in pretty form.
difftree Returns all partial derivatives as a tree.
evaluate Evaluates a function with a given substitution (assumes alphabetic order).
gradient Returns the gradient of the given function.
hessian Returns Hessian matrix or its determinant of a given function.
newton Applies one step of Newton's method.
succhalv Applies Gradient method with successive halving and parabola fitting on 2D or...
Part 2b:
dijkstra All shortest paths to all other nodes from given starting node using an (un)d...
drawgraph Plots a graph based on provided adjacency matrix.
floydwarshall Returns matrix with shortest distances between all nodes.
maxflow Finds maximum flow based on provided edge list.
maxmatch Maximum matchings of a bipartite graph based on provided adjacency matrix.
mincostmaxflow Returns a maximum s-t flow of minimum cost based on provided edge list with weights and costs.
mincut Finds minimum s-t-cut based on provided edge list or adjacency matrix.
mst Returns the minimum spanning tree of an undirected graph.
traverse Traverses graph provided as (un)directed adjacency matrix either breadth-first...
Get linearly independent components and inversion of matrix:
$ python3 main.py matanalysis /path/to/matrix.ods --pretty
โโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโคโโโโโโโโโโโโโโ
โ insight โ descr โ matrix โ
โโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโชโโโโโโโโโโโโโโก
โ provided input โ - โ โก0 -1โค โ
โ โ โ โข โฅ โ
โ โ โ โฃ2 -1โฆ โ
โโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโผโโโโโโโโโโโโโโค
โ independent cols โ (0, 1) โ โก0 -1โค โ
โ โ โ โข โฅ โ
โ โ โ โฃ2 -1โฆ โ
โโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโผโโโโโโโโโโโโโโค
โ independent rows โ (0, 1) โ โก0 -1โค โ
โ โ โ โข โฅ โ
โ โ โ โฃ2 -1โฆ โ
โโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโผโโโโโโโโโโโโโโค
โ inverse โ - โ โก-1/2 1/2โค โ
โ โ โ โข โฅ โ
โ โ โ โฃ -1 0 โฆ โ
โโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโงโโโโโโโโโโโโโโGet basic & feasible solutions of an Ax<=b system. Matrices are provided via an ODF-file with two sheets, namely 'A' and 'b':
$ python3 main.py hyperplanes /path/to/FileWithSheets_A_b.ods --pretty
โโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโคโโโโโโโโคโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ possibility* โ ABi โ ABi^(-1) โ bBi โ xBi.T โ conclusion โ
โโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโชโโโโโโโโชโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโก
โ B1=(2, 4, 5) โ โก-1 -1 -1โค โ โก0 0 -1โค โ โก-2โค โ [0 1 1] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข0 -1 0 โฅ โ โข0 -1 0 โฅ โ โข-1โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ-1 0 0 โฆ โ โฃ-1 1 1 โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B2=(2, 4, 6) โ โก-1 -1 -1โค โ not invertible โ - โ - โ not a basic selection as โ
โ โ โข โฅ โ โ โ โ row(s) {4, 6} are โ
โ โ โข0 -1 0 โฅ โ โ โ โ linearly dependent โ
โ โ โข โฅ โ โ โ โ โ
โ โ โฃ0 -1 0 โฆ โ โ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B3=(2, 4, 7) โ โก-1 -1 -1โค โ โก-1 1 1 โค โ โก-2โค โ [1 1 0] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข0 -1 0 โฅ โ โข0 -1 0 โฅ โ โข-1โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 0 -1โฆ โ โฃ0 0 -1โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B4=(2, 5, 6) โ โก-1 -1 -1โค โ โก0 -1 0 โค โ โก-2โค โ [0 0 2] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข-1 0 0 โฅ โ โข0 0 -1โฅ โ โข0 โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 -1 0 โฆ โ โฃ-1 1 1 โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B5=(2, 5, 7) โ โก-1 -1 -1โค โ โก0 -1 0 โค โ โก-2โค โ [0 2 0] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข-1 0 0 โฅ โ โข-1 1 1 โฅ โ โข0 โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 0 -1โฆ โ โฃ0 0 -1โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B6=(2, 6, 7) โ โก-1 -1 -1โค โ โก-1 1 1 โค โ โก-2โค โ [2 0 0] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข0 -1 0 โฅ โ โข0 -1 0 โฅ โ โข0 โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 0 -1โฆ โ โฃ0 0 -1โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B7=(4, 5, 6) โ โก0 -1 0โค โ not invertible โ - โ - โ not a basic selection as โ
โ โ โข โฅ โ โ โ โ row(s) {4, 5, 6} are โ
โ โ โข-1 0 0โฅ โ โ โ โ linearly dependent โ
โ โ โข โฅ โ โ โ โ โ
โ โ โฃ0 -1 0โฆ โ โ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B8=(4, 5, 7) โ โก0 -1 0 โค โ โก0 -1 0 โค โ โก-1โค โ [0 1 0] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข-1 0 0 โฅ โ โข-1 0 0 โฅ โ โข0 โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 0 -1โฆ โ โฃ0 0 -1โฆ โ โฃ0 โฆ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B9=(4, 6, 7) โ โก0 -1 0 โค โ not invertible โ - โ - โ not a basic selection as โ
โ โ โข โฅ โ โ โ โ row(s) {4, 6, 7} are โ
โ โ โข0 -1 0 โฅ โ โ โ โ linearly dependent โ
โ โ โข โฅ โ โ โ โ โ
โ โ โฃ0 0 -1โฆ โ โ โ โ โ
โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโผโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ B10=(5, 6, 7) โ โก-1 0 0 โค โ โก-1 0 0 โค โ โก0โค โ [0 0 0] โ if equal to vertex โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ -> feasible โ
โ โ โข0 -1 0 โฅ โ โข0 -1 0 โฅ โ โข0โฅ โ โ otherwise infeasible โ
โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ
โ โ โฃ0 0 -1โฆ โ โฃ0 0 -1โฆ โ โฃ0โฆ โ โ โ
โโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโงโโโโโโโโงโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโ
*skipped rows due to duplicate: {2, 4}Find optimum using Simplex with all itermediate results. Matrices are provided via an ODF-file with sheets named 'A', 'b' and 'c'. Together they must represent the LP in inequality form as maximization problem. A basic selection of hyperplanes of the starting point must be provided. In the example below it is
$ python3 main.py simplex /path/to/matrix_A_b_c.ods 1 5 --pretty
โโโโโโโโโโคโโโโโโโโโโโโโโคโโโโโโโโโโโคโโโโโโโคโโโโโโโโโโโโโโโคโโโโโโคโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโคโโโโโโโโโคโโโโโโโคโโโโโโโโโคโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโคโโโโโโโ
โ iter โ selection โ AB โ bB โ ร=AB^(-1) โ c โ v = ร*bB โ u = c*ร^(T) โ d โ Av โ Ad โ b โ ฮป = min(stepsizes) โ selection_new โ v' โ
โโโโโโโโโโชโโโโโโโโโโโโโโชโโโโโโโโโโโชโโโโโโโชโโโโโโโโโโโโโโโชโโโโโโชโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโชโโโโโโโโโชโโโโโโโชโโโโโโโโโชโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโชโโโโโโโก
โ 0 โ B0 = (4, 5) โ โก-1 0 โค โ โก0โค โ โก-1 0 โค โ โก6โค โ โก0โค โ โก-6โค โ -ร4 = โ โก0โค โ โก1 โค โ โก12โค โ 5 = ฮป = min([12, 5, 5]) โ B1 = {2, 5} โ โก5โค โ
โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โข โฅ โ โข โฅ โ โข โฅ โ i.e. selection โ out = j = 4 โ โข โฅ โ
โ โ โ โฃ0 -1โฆ โ โฃ0โฆ โ โฃ0 -1โฆ โ โฃ5โฆ โ โฃ0โฆ โ โฃ-5โฆ โ โก1โค โ โข0โฅ โ โข6 โฅ โ โข30โฅ โ k = (1, 2, 3) โ in = k = 2 โ โฃ0โฆ โ
โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ cand. sel. = (2, 3) โ โ โ
โ โ โ โ โ โ โ โ โ โฃ0โฆ โ โข0โฅ โ โข3 โฅ โ โข15โฅ โ took k = 2 โ write as: โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {4, 5} - {4} โ โ
โ โ โ โ โ โ โ โ โ โ โข0โฅ โ โข-1โฅ โ โข0 โฅ โ โ โช โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {2} โ โ
โ โ โ โ โ โ โ โ โ โ โฃ0โฆ โ โฃ0 โฆ โ โฃ0 โฆ โ โ = {2, 5} โ โ
โโโโโโโโโโผโโโโโโโโโโโโโโผโโโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโค
โ 1 โ B1 = (2, 5) โ โก6 2 โค โ โก30โค โ โก1/6 1/3โค โ โก6โค โ โก5โค โ โก1 โค โ -ร5 = โ โก5 โค โ โก8/3โค โ โก12โค โ 0 = ฮป = min([21/8, 0, 15]) โ B2 = {2, 3} โ โก5โค โ
โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โข โฅ โ โข โฅ โ โข โฅ โ i.e. selection โ out = j = 5 โ โข โฅ โ
โ โ โ โฃ0 -1โฆ โ โฃ0 โฆ โ โฃ 0 -1 โฆ โ โฃ5โฆ โ โฃ0โฆ โ โฃ-3โฆ โ โก-1/3โค โ โข30โฅ โ โข 0 โฅ โ โข30โฅ โ k = (1, 3, 4) โ in = k = 3 โ โฃ0โฆ โ
โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ cand. sel. = (3,) โ โ โ
โ โ โ โ โ โ โ โ โ โฃ 1 โฆ โ โข15โฅ โ โข 1 โฅ โ โข15โฅ โ took k = 3 โ write as: โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {2, 5} - {5} โ โ
โ โ โ โ โ โ โ โ โ โ โข-5โฅ โ โข1/3โฅ โ โข0 โฅ โ โ โช โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {3} โ โ
โ โ โ โ โ โ โ โ โ โ โฃ0 โฆ โ โฃ-1 โฆ โ โฃ0 โฆ โ โ = {2, 3} โ โ
โโโโโโโโโโผโโโโโโโโโโโโโโผโโโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโค
โ 2 โ B2 = (2, 3) โ โก6 2โค โ โก30โค โ โก1/3 -1/3โค โ โก6โค โ โก5โค โ โก-1/2โค โ -ร2 = โ โก5 โค โ โก7/6 โค โ โก12โค โ 6 = ฮป = min([6, 15]) โ B3 = {1, 3} โ โก3โค โ
โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โข โฅ โ โข โฅ โ โข โฅ โ i.e. selection โ out = j = 2 โ โข โฅ โ
โ โ โ โฃ3 2โฆ โ โฃ15โฆ โ โฃ-1/2 1 โฆ โ โฃ5โฆ โ โฃ0โฆ โ โฃ 3 โฆ โ โก-1/3โค โ โข30โฅ โ โข -1 โฅ โ โข30โฅ โ k = (1, 4) โ in = k = 1 โ โฃ3โฆ โ
โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ cand. sel. = (1,) โ โ โ
โ โ โ โ โ โ โ โ โ โฃ1/2 โฆ โ โข15โฅ โ โข 0 โฅ โ โข15โฅ โ took k = 1 โ write as: โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {2, 3} - {2} โ โ
โ โ โ โ โ โ โ โ โ โ โข-5โฅ โ โข1/3 โฅ โ โข0 โฅ โ โ โช โ โ
โ โ โ โ โ โ โ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โ {1} โ โ
โ โ โ โ โ โ โ โ โ โ โฃ0 โฆ โ โฃ-1/2โฆ โ โฃ0 โฆ โ โ = {1, 3} โ โ
โโโโโโโโโโผโโโโโโโโโโโโโโผโโโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโผโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโค
โ 3 โ B3 = (1, 3) โ โก1 3โค โ โก12โค โ โก-2/7 3/7 โค โ โก6โค โ โก3โค โ โก3/7 โค โ DONE โ DONE โ DONE โ DONE โ DONE โ DONE โ โก3โค โ
โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โข โฅ โ โ โ โ โ โ โ โข โฅ โ
โ โ โ โฃ3 2โฆ โ โฃ15โฆ โ โฃ3/7 -1/7โฆ โ โฃ5โฆ โ โฃ3โฆ โ โฃ13/7โฆ โ โ โ โ โ โ โ โฃ3โฆ โ
โโโโโโโโโโงโโโโโโโโโโโโโโงโโโโโโโโโโโงโโโโโโโงโโโโโโโโโโโโโโโงโโโโโโงโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโงโโโโโโโโโงโโโโโโโงโโโโโโโโโงโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโงโโโโโโโ
result = SimplexResult.OPTIMAL
v* = [[3], [3]]
optimal_value = c^T * v = 33 (maximization problem)
optimal_value = -c^T * v = -33 (minimization problem)
unique = TruePlots a 2D system of inequalities provided in Ax<=b form. File must have the sheets named 'A' and 'b'. See image below (left plot).
$ python3 main.py plot /path/to/FileWithSheets_A_b.ods -x -1 6 -y 0 5
result saved as: ./plot.pngAlso possible to show an instructed Gomory Chvatal Cut provided as
$ python3 main.py plot /path/to/FileWithSheets_A_b.ods -x -1 6 -y 0 5 -gc 0.2 1 0.1 2
result saved as: ./plot.png
gc-cut with 0.2*(1) + 0.1*(2)
= (0.2*[-x + 4โ
y]) + (0.1*[2โ
x + 2โ
y]) โค โ(0.2*[8]) + (0.1*[9])โ
= 1.0โ
y โค 2
IP relaxation on an Ax<=b system. File must have the sheets named 'A', 'b' and 'c' which together represent the LP in inequality form as maximization problem. See sample file below (Knapsack problem).
Knapsack encoding:
A: holds volumes in first row
b: holds capacity in first row
c: holds values in first row
$ python3 main.py branchbound '/path/to//knapsack.ods' -k
โโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโคโโโโโโโโโคโโโโโโโโโโโโโโโคโโโโโโโโโคโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโ
โ step โ c โ x_ub โ z_ub โ x_lb โ z_lb โ global update โ stop criteria โ
โโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโชโโโโโโโโโชโโโโโโโโโโโโโโโชโโโโโโโโโชโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโก
โ [1] r=0 โ [64 57 48 11] โ [1 1 5/8 0] โ 151 โ [1 1 0 0] โ 121 โ [1]: z_lb = 121 โ โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [2] r=2 โ [64 57 48 11] โ โก 10 โค โ 142 โ [1 0 1 0] โ 112 โ โ โ
โ โ โ โข1 โโ 1 0โฅ โ โ โ โ โ โ
โ โ โ โฃ 19 โฆ โ โ โ โ โ โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [3] r=4 โ [64 57 48 11] โ [7/16 1 1 0] โ 133 โ [0 1 1 0] โ 105 โ โ โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [4] r=6 โ โ โ โ โ โ โ infeasible โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [5] r=5 โ [64 57 48 11] โ [0 1 1 7/8] โ 917/8 โ [0 1 1 0] โ 105 โ โ dominance โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [6] r=3 โ [64 57 48 11] โ [1 0 1 1] โ 123 โ [1 0 1 1] โ 123 โ [6]: z_lb = 123 โ optimal โ
โโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค
โ [7] r=1 โ [64 57 48 11] โ [1 1 0 1] โ 132 โ [1 1 0 1] โ 132 โ [7]: z_lb = 132 โ optimal โ
โโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโงโโโโโโโโโงโโโโโโโโโโโโโโโงโโโโโโโโโงโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโ
result saved as: ./tree.png
Differenciate a function once w.r.t. x and print beatifuly.
$ python3 main.py diffbeauty '(x^2-2xy+x)^2' --wrt=x
fx:
โ 2 โ
(4โ
x - 4โ
y + 2)โ
โx - 2โ
xโ
y + xโ Get complete partial differenciation tree w.r.t. all variables.
$ python3 main.py difftree '(x^2-2xy+x)^2'
f: (x^2 - 2xy + x)^2
โโโ f1x_: (4x - 4y + 2)(x^2 - 2xy + x)
โ โโโ f2x_x: 4x^2 - 8xy + 4x + (2x - 2y + 1)(4x - 4y + 2)
โ โ โโโ f3x_xx: 24x - 24y + 12
โ โ โ โโโ f4x_xxx: 24
โ โ โ โโโ f4y_xxx: -24
โ โ โโโ f3y_xx: -24x + 16y - 8
โ โ โโโ f4x_yxx: -24
โ โ โโโ f4y_yxx: 16
โ โโโ f2y_x: -4x^2 + 8xy - 2x(4x - 4y + 2) - 4x
โ โโโ f3x_yx: -24x + 16y - 8
โ โ โโโ f4x_xyx: -24
โ โ โโโ f4y_xyx: 16
โ โโโ f3y_yx: 16x
โ โโโ f4x_yyx: 16
โโโ f1y_: -4x(x^2 - 2xy + x)
โโโ f2x_y: -4x^2 + 8xy - 4x(2x - 2y + 1) - 4x
โ โโโ f3x_xy: -24x + 16y - 8
โ โ โโโ f4x_xxy: -24
โ โ โโโ f4y_xxy: 16
โ โโโ f3y_xy: 16x
โ โโโ f4x_yxy: 16
โโโ f2y_y: 8x^2
โโโ f3x_yy: 16x
โโโ f4x_xyy: 16Evaluate an expression with given input values.
$ python3 main.py evaluate '2^(1/2)'
13276383826/9387821033
$ python3 main.py evaluate '2x + y' 4 3
11Receive the gradient vector/matrix.
$ python3 main.py gradient '(x^2-2xy+x)^2'
[['2x(x - 2y + 1)(2x - 2y + 1)', '4x^2(-x + 2y - 1)']]
$ python3 main.py gradient '(x^2-2xy+x)^2' --pretty
โก 2 โค
โฃ2โ
xโ
(x - 2โ
y + 1)โ
(2โ
x - 2โ
y + 1) 4โ
x โ
(-x + 2โ
y - 1)โฆEvaluate the gradient of a function at a given point.
$ python3 main.py gradient '(x^2-2xy+x)^2' -s x 2 -s y 2 --pretty
[-4 16]Next better point using Gradient method with successive halving (incl. parabola fitted point
$ python3 main.py succhalv '(x-2)^4 + (x-2y)^2' 2 0
# B (x1, y1) f(x1, y1) < 4 ?
--- --------- ------------------- ----------- -------
0 1 (-2, 8) 580 False
1 0.5 (0, 4) 80 False
2 0.25 (1, 2) 10 False
3 0.125 (1.5, 1) 0.3125 True
B* 0.0969626 (1.61215, 0.775701) 0.026319 -
(x1, y1) = (1.5, 1)
(x1, y1) = (1.61215, 0.775701) <-- parabola fitted using B*Also works for 3 dimensional functions. Use the double dash (--) when working with negative values as after it all further parameters are accepted as arguments.
python3 main.py succhalv 'x^2 + y^2 +z^2' -- 3 1 -2
# B (x1, y1) f(x1, y1) < 14 ?
--- --- ----------- ----------- --------
0 1 (-3, -1, 2) 14 False
1 0.5 (0, 0, 0) 0 True
B* 0.5 (0, 0, 0) 0 -
(x1, y1) = (0, 0, 0)
(x1, y1) = (0, 0, 0) <-- parabola fitted using B*
Receive the Hessian matrix of a given function.
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2'
[['12(x - 2)^2 + 2', '-4'], ['-4', '8']]
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' --pretty
โก 2 โค
โข12โ
(x - 2) + 2 -4โฅ
โข โฅ
โฃ -4 8 โฆSolve for given substitution.
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' -s x 0 -s y 0
[['50', '-4'], ['-4', '8']]
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' -s x 0 -s y 0 --pretty
โก50 -4โค
โข โฅ
โฃ-4 8 โฆDeterminant of Hessian matrix:
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' --det
96x^2 - 384x + 384
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' --det --pretty
2
96โ
x - 384โ
x + 384
$ python3 main.py hessian '(x-2)^4 + (x-2y)^2' -s x 0 -s y 0 --det
384One iteration from a given point to a next better point using Newton's method:
$ python3 main.py newton '(x^2-2xy+x)^2' -s x 2 -s y 2
a=(x0, y0) H b=H^(-1) c=โf(x0, y0) a-bc=(x1, y1)
------------ ------------------ ---------------------- -------------- ---------------
[[2], [2]] [[-6, 0], [0, 32]] [[-1/6, 0], [0, 1/32]] [[-4, 16]] [[4/3], [3/2]]
$ python3 main.py newton '(x^2-2xy+x)^2' -s x 2 -s y 2 --pretty
a=(x0, y0) H b=H^(-1) c=โf(x0, y0) a-bc=(x1, y1)
------------ -------- ------------ -------------- ---------------
โก2โค โก-6 0 โค โก-1/6 0 โค [-4 16] โก4/3โค
โข โฅ โข โฅ โข โฅ โข โฅ
โฃ2โฆ โฃ0 32โฆ โฃ 0 1/32โฆ โฃ3/2โฆCustom amount of interations using Broyden's method:
$ python3 main.py broyden '(x^2-2xy+x)^2' 2 2 --pretty -s 4
โโโโโโโคโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโ
โ i โ [Xi, Yi] โ di โ gi โ Ai โ โf(Xi, Yi) โ [X(i+1), Y(i+1)] โ
โโโโโโโชโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโก
โ 0 โ โก2.0โค โ [] โ [] โ โก -0.166666666666667 3.93940421025525e-126โค โ โก-4.0โค โ โก1.33333333333333โค โ
โ โ โข โฅ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ
โ โ โฃ2.0โฆ โ โ โ โฃ3.93940421025525e-126 0.03125 โฆ โ โฃ16.0โฆ โ โฃ 1.5 โฆ โ
โโโโโโโผโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโค
โ 1 โ โก1.33333333333333โค โ [-0.666666666666667 -0.500000000000000] โ [2.81481481481481 -11.2592592592593] โ โก-0.211578947368421 0.00631578947368421โค โ โก-1.18518518518519โค โ โก1.05263157894737โค โ
โ โ โข โฅ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ
โ โ โฃ 1.5 โฆ โ โ โ โฃ-0.0336842105263158 0.0359868421052632 โฆ โ โฃ4.74074074074074 โฆ โ โฃ1.28947368421053โฆ โ
โโโโโโโผโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโค
โ 2 โ โก1.05263157894737โค โ [-0.280701754385965 -0.210526315789474] โ [0.602009795186643 -2.40803918074657] โ โก-0.35841561423651 0.0269646957520092โค โ โก-0.583175389998542โค โ โก0.780711825487945โค โ
โ โ โข โฅ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ
โ โ โฃ1.28947368421053โฆ โ โ โ โฃ-0.143811710677382 0.0514735218140069โฆ โ โฃ 2.33270155999417 โฆ โ โฃ1.08553386911596 โฆ โ
โโโโโโโผโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโค
โ 3 โ โก0.780711825487945โค โ [-0.271919753459424 -0.203939815094568] โ [0.345249185044140 -1.38099674017656] โ โก-0.564066771922377 0.0558843898015843โค โ โก-0.237926204954403โค โ โก0.593320115976839โค โ
โ โ โข โฅ โ โ โ โข โฅ โ โข โฅ โ โข โฅ โ
โ โ โฃ1.08553386911596 โฆ โ โ โ โฃ-0.298050078941783 0.0731632923511883โฆ โ โฃ 0.95170481981761 โฆ โ โฃ0.944990086982629โฆ โ
โโโโโโโงโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโ
$ python3 main.py broyden '(x^2-2xy+x)^2' 2 2 --rational
โโโโโโโคโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโโ
โ i โ [Xi, Yi] โ di โ gi โ Ai โ โf(Xi, Yi) โ [X(i+1), Y(i+1)] โ
โโโโโโโชโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโโก
โ 0 โ [2 2] โ [] โ [] โ [[-1/6 0] โ [-4 16] โ [4/3 3/2] โ
โ โ โ โ โ [0 1/32]] โ โ โ
โโโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโค
โ 1 โ [4/3 3/2] โ [-2/3 -1/2] โ [76/27 -304/27] โ [[-201/950 3/475] โ [-32/27 128/27] โ [20/19 49/38] โ
โ โ โ โ โ [-16/475 547/15200]] โ โ โ
โโโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโค
โ 2 โ [20/19 49/38] โ [-16/57 -4/19] โ [111488/185193 -24080285991/9999956057] โ [[-15609/43550 18789/696800] โ [-4000/6859 16000/6859] โ [680/871 1891/1742] โ
โ โ โ โ โ [-6263/43550 143467/2787200]] โ โ โ
โโโโโโโงโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโโThere is also the possibility to pass the interim results in case the original function is not known. In order to have two iteration, two gradients must be passed in the right order. The hessian inverse matrix is interpreted as a
$ python3 main.py broydeninter --startingpoint 3.3 0.4 --gradient 1 0 --gradient 0 1 --hessian_inv 5 0 0 2 -p -r
โโโโโโโคโโโโโโโโโโโโโคโโโโโโโโโคโโโโโโโโโคโโโโโโโโโคโโโโโโโโโโโโโโโคโโโโโโโโโโโโโโโโโโโโโ
โ i โ [Xi, Yi] โ di โ gi โ Ai โ โf(Xi, Yi) โ [X(i+1), Y(i+1)] โ
โโโโโโโชโโโโโโโโโโโโโชโโโโโโโโโชโโโโโโโโโชโโโโโโโโโชโโโโโโโโโโโโโโโชโโโโโโโโโโโโโโโโโโโโโก
โ 0 โ โก33 โค โ [] โ [] โ โก5 0โค โ โก1โค โ โก-17 โค โ
โ โ โขโโ โฅ โ โ โ โข โฅ โ โข โฅ โ โขโโโโโฅ โ
โ โ โข10 โฅ โ โ โ โฃ0 2โฆ โ โฃ0โฆ โ โข 10 โฅ โ
โ โ โข โฅ โ โ โ โ โ โข โฅ โ
โ โ โฃ2/5โฆ โ โ โ โ โ โฃ2/5 โฆ โ
โโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโค
โ 1 โ โก-17 โค โ [-5 0] โ [-1 1] โ โก5 0โค โ โก0โค โ โก-17 โค โ
โ โ โขโโโโโฅ โ โ โ โข โฅ โ โข โฅ โ โขโโโโโฅ โ
โ โ โข 10 โฅ โ โ โ โฃ2 2โฆ โ โฃ1โฆ โ โข 10 โฅ โ
โ โ โข โฅ โ โ โ โ โ โข โฅ โ
โ โ โฃ2/5 โฆ โ โ โ โ โ โฃ-8/5โฆ โ
โโโโโโโงโโโโโโโโโโโโโงโโโโโโโโโงโโโโโโโโโงโโโโโโโโโงโโโโโโโโโโโโโโโงโโโโโโโโโโโโโโโโโโโโโOptimize a series of at least 3 values using Aitken sequence:
$ python3 main.py aitken 100 10 2 0.5
i Xi Aitken Yi
--- ----- -------------------
0 100 -
1 10 -
2 2 1.2195121951219512
3 0.5 0.15384615384615385Plotting a graph based on an adjacency matrix. When no edge is shared, enter 0 weight. See example below.
$ cat adjmat.csv
Attribute,Brugg,Basel,Bern,Chur,Geneva
Brugg,0,58,101,149,250
Basel,58,0,93,198,243
Bern,101,93,0,237,156
Chur,149,198,237,0,386
Geneva,250,243,156,386,0
$ python3 main.py drawgraph "./adjmat.csv"
result saved as: ./graph.html
Or as directed graph.
$ cat adjmat2.csv
Attribute,a,b,c,d,e,f,g
a,0,1,0,1,0,0,0
b,0,0,1,0,0,1,0
c,0,0,0,0,1,0,0
d,0,1,0,0,0,0,0
e,0,0,0,0,0,0,1
f,1,0,0,1,0,0,0
g,0,0,1,0,0,0,0
$ python3 main.py drawgraph "./adjmat2.csv" --directed
result saved as: ./graph.html
Return minimum spanning tree.
$ cat adjmat.csv
Attribute,A,B,C,D,E,F
A,0,200,580,0,250,1200
B,200,0,500,820,0,0
C,580,500,0,230,150,1100
D,0,820,230,0,380,0
E,250,0,150,380,0,0
F,1200,0,1100,0,0,0
$ python3 main.py mst adjmat.csv
From To Weight
------ ---- --------
A B 200
A E 250
C D 230
C E 150
C F 1100
---- SUM: 1930Get the shortest paths from a given node to all other nodes.
$ python3 main.py dijkstra adjmat.csv A
Shortest Path Total Weight
--------------- --------------
['A'] 0
['A', 'B'] 200
['A', 'E', 'C'] 400
['A', 'E'] 250
['A', 'F'] 1200
['A', 'E', 'D'] 630Traverse a graph either breadth-first or dept-first starting from node A.
$ python3 main.py traverse adjmat.csv A bf
Step From To
------ ------ ----
0 A B
1 A C
2 A E
3 A F
4 B D
Encounter Order: A โ B โ C โ E โ F โ D
$ python3 main.py traverse adjmat.csv A df
...
Encounter Order: E โ D โ F โ C โ B โ AShortest distances between all nodes using Floyd-Warshall. Right-hand side shows changes.
$ python3 main.py floydwarshall adjmat.csv
A B C D E F | A B C D E F
-- --- --- --- --- --- --- ----- ---- ---- ---- ---- ---- ----
A 0 60 160 180 520 480 | 0 0 0 180 -180 -120
B 60 0 160 140 480 440 | 0 0 -60 0 480 -360
C 160 160 0 20 360 320 | 0 -60 0 0 -540 -180
D 180 140 20 0 340 300 | 180 0 0 0 -460 0
E 520 480 360 340 0 40 | -180 480 -540 -460 0 0
F 480 440 320 300 40 0 | -120 -360 -180 0 0 0
# constrain intermediate nodes to A and D only:
$ python3 main.py floydwarshall adjmat.csv --onlyuse "A, D"
A B C D E F | A B C D E F
-- --- --- --- --- --- --- ----- --- ---- ---- --- --- ----
A 0 60 160 inf 700 600 | 0 0 0 inf 0 0
B 60 0 160 140 760 440 | 0 0 -60 0 760 -360
C 160 160 0 20 820 320 | 0 -60 0 0 -80 -180
D inf 140 20 0 800 300 | inf 0 0 0 0 0
E 700 760 820 800 0 40 | 0 760 -80 0 0 0
F 600 440 320 300 40 0 | 0 -360 -180 0 0 0Maximum flow of a directed graph provided an edge list (cost is irrelevant here).
$ cat edges.csv
from,to,weight,cost
s,2,10,0
s,3,5,0
s,4,15,0
2,5,9,0
2,6,15,0
2,3,4,0
3,4,4,0
3,6,8,0
4,7,30,0
5,6,15,0
5,t,10,0
6,7,15,0
6,t,10,0
7,3,6,0
7,t,10,0
$ python3 main.py maxflow edges.csv s t
max flow: 28
node routed values
------ --------------------------
s {'2': 10, '3': 5, '4': 13}
2 {'5': 9, '6': 1, '3': 0}
3 {'4': 0, '6': 8}
4 {'7': 13}
5 {'6': 0, 't': 9}
6 {'7': 0, 't': 9}
7 {'3': 3, 't': 10}
t {}Find a minimum s-t-cut based on edge list or adjacency.
$ python3 main.py mincut edges.csv s t
cut value: 28
# partitions
--- -----------------------------------------------
0 ['a1', 'a2', 'a4', 'a5', 'b1', 'b3', 'b4', 's']
1 ['a3', 'b2', 'b5', 't']
cut edges: [('b3', 't'), ('b4', 't'), ('s', 'a3'), ('b1', 't')]
cut value: 4.0
$ python3 main.py mincut adjmat.csv s t -adj
# partitions
--- -----------------------------------------------
0 ['a1', 'a2', 'a4', 'a5', 'b1', 'b3', 'b4', 's']
1 ['a3', 'b2', 'b5', 't']
cut edges: [('b3', 't'), ('b4', 't'), ('s', 'a3'), ('b1', 't')]
cut value: 4.0Find a maximum matching.
$ python3 main.py maxmatch adjmat.csv
matches
---------
3 - 4
7 - t
s - 2
5 - 6
maximum matches = 4Returns a maximum s-t flow of minimum cost based on provided edge list with weights and costs.
$ python3 main.py mincostmaxflow edges.csv s t
min cost: 13
max flow: 3
node routed values
------ ----------------
s {'b': 0, 'c': 3}
b {'d': 1}
c {'b': 1, 'e': 2}
d {'t': 1}
e {'t': 2}
t {}