Maxflow-rs

Idea

• Generate StableGraph (petgraph)
  • run algo on that
• Create a custom to_graph method which displays a maxflow graph

TODOs

• Implementation of Algos:
  • Ford-Fulkersson (DFS zur Berechnung des flusserhöhenden/augmentierenden Pfads)
  • Edmonds-Karp (BFS zur Berechnung des flusserhöhenden/augmnetierenden Pfads)
  • Dinic
  • Goldberg-Tarjan/Preflow-Push
• Step-by-step implementation for all algos
  • Ford-Fulkerson
  • Edmonds-Karp
  • Dinic
  • Goldberg-Tarjan/Preflow-Push
• Mark edges which have active flows with a color
• Move GUI Graph conversion to a trait of StableGraph
• Add graph positioning strategy which looks "nicer"
  • Only insert nodes which are at least a distance of 40 away (default)
  • Pseudo-random node positioning strategy
• Handle residual edges properly
  • Add display option for residual edges
• Only show active flows (filter all edges with f=0)
• Show normal vs residual graph -> not needed, residual graph is shown by default
• When increasing flows, handle residual path
• Add unit tests
  • With small problems to prove correctness
  • For Benchmarking the algos
  • Check validity of the generated flows (incoming flows = outgoing flows; flow <= capacity)
• Add info display pane
  • is valid flow? (add trait to graph)
  • current total flow (add trait to calculate)
  • number of steps (is implemented for stepwise)
• implement PartialEq for StableGraph (not really possible -> how do you compare graphs?) -> implemented a prune_zero trait & compare node/edge weights for same index
• Step-by-step vizualisation with choosable time delay
• Dinic: add GUI options to show Layer Graph and Blocking flow
• Goldberg-Tarjan: show distance labels at nodes
• change GUI colors to accomodate color-blindness (blue-yellow rather than red-green)
• remove display option for residual graph -> this should be the default

DFS: Stack BFS: Queue

Bugs:

• if I generate a new graph, the algo runs on the old graph
• if I click reset & then step, the algo runs in one step
• when using edmonds karp the updated flow isn't displayed correctly
• the capacity on residual edges also gets displayed when using

Residual Graph:

• parallel arcs in the same direction can be summarized into a single arc by summing up the capcities

TODOs:

• gui colors in yellow blue (should be easy)
• no residual graph option, residual graph is default (medium, bit of effort)
  • do we need to delete the graph field in algos & use residual_graph instead?
  • check correctness of all algos by testing a small sample#
• gui display options (medium)
  • layer graph (done - TODO: check if correct) & blocking flow (for Dinic)
  • goldberg-tarjan: push-relabel step - current pre-flow, flow change in every step
• add time delay for algorithm (hard due to multithreading)
  • fix glitchy graph display (somewhere in update_graph function)
• implement goldberg tarjan (hard)
  • fix residual edges: algo pushes flows back but increases flow on the residual edge instead of decreasing the reverse edge
  • fix loops: somehow the algo produces loops towards the source node (not critical for calculating the total flow, but should be fixed)
  • big tests sometimes fail for goldberg-tarjan (panic when reading node from distance labelling)
• make MaxflowAlgorithm object-safe (remove from_problem & implement it per struct, then create a generic wrapper which creates new instances for each specific algorithm)
• add unit test environment (hard)
  • callable from gui
  • several test tuples [number of problems, node count, max capacity]
  • split MaxflowProblem:new into two functions (one for display, one for test environment)
  • apply to every algo
  • große testumgebung
  • testfunktion in seperatem thread ausführen, damit programm nicht hängt
  • check for:
    • flusserhaltung
    • kapazitätsbedingungen
    • saturierter schritt
  • testumgebung durch änderungen der lösung automatisch überprüfen (korrektheit, optimalität)
• reduce warnings

thread '' panicked at src/graph.rs:191:31 attempt to subtract with overflow note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

thread '' panicked at src/algorithms/goldberg_tarjan.rs:109:238: No distance label found note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Code erklären

• Graph generieren (random_generator.rs)
• GUI, Custom Layout (main.rs, layout.rs)
• Graph Hilfsfunktionen (graph.rs)
• Algorithmen (ford_fulkerson.rs, edmonds_karp.rs, dinic.rs, goldberg_tarjan.rs)