vignesh-m/dinic-visualization

visualization of dinic's algorithm

Dinic's Algorithm Visualization

Visualization of Dinic's algorithm to find max flow in graphs

Dependencies

• pydot2
• graphviz

dinic-visualization's Issues

Use find_distances in block_flow

complete dinic implementation

iteratively find blocking flow and subtract
maxflow/dinic.py

• construct residual graph after finding block flow
• iteratively find new flows
  depends on #2

Graph display enhancements

• Remove the axes labels if possible.
• Also show capacity of edges, while finding an augmenting path.
• While updating using blocking flow, show a comparison of previous and updated graphs

bfs for distances

implement maxflow/dinic.py find_distances

Gui enhancements

• Show steps before after finding blocking flow
• Create box showing the total flow, and flow of augmenting path
• Residual graph, show dotted lines(add weights?)
• Show current graph(smaller size) at all times
• Add button to skip the blocking flow(directly display blocking flow without showing iteration for each path)
• Add a close window button
• Show complete flow at end
• polish ui

Multigraph inputs

support graphs with repeated edges in input_graph

Correctness

Explain Correctness of the algo.

Resize image on update

The gui doesn't resize the image when its updated.
This is especially visible when showing capacities in the graph, which changes its size slightly

Residual graph incorrect

Negative weights are displayed for input:sample_graph3

Blocking flow path

In max_flow/block_flow.py , the function that finds blocking flow calls path. Make sure that after path_function, check if ret_path is not empty in order to continue with the loop

Input changes

Input should accept source and sink, modify code elsewhere also appropriately