mochi-graph-algorithms

mochi-graph-algorithms is the library of graphs abstraction by Rust.

document

ちょっとずつ書いていきます.

• グラフ抽象化の抽象化パート -> ./kernel.md

algorithms

single_source_shortest_path

• bfs (only unit length) O(V + E)
• dijkstra(with binary heap) O((V + E)logV)
• dijkstra(with radix heap 32) O(E log log V)
• dijkstra(with radix heap 64) O(E log log V)
• bellman_ford O(VE)
• spfa O(VE) faster than BF
• dial O(E + V * Wmax)
• scaling_dijkstra O(Elog(Wmax))

all_pairs_shortest_path

• feasible_potential O(VE)
• warshall_floyd O(V^3)
• dijkstra_with_potential O(VE + V(V + E)logV)

k-th_shortest_paths

• yen O(k ( E log V ))
• eppistein O(E log V + k)

minimum_spanning_tree

• prim O(E log V)
• kruskal O(E log V + E α(V))
• boruvka O(E log V)

maxflow

• dinic O(V^2E)
• fifo_push_relabel O(V^3)
• ford_fulkerson O(EF)
• fujishige O(VElog(Cmax))

minimum_cost_flow

• successive shortest paths(primal dual?) O(VE + FElogV)

cardinality_bipartite_matching

• hopcroft_karp O(V^(1/2)E)

cardinality_general_matching

• gabow_e_algorithm O(VElogV)

TODO

• RHS-algorithm(min cost flow)
• Orlin scaling algorithm (min cost flow) (difficult)
• min cost circulation
• min cost transshipment
• mst
• wbm and wnbm