Package es.urjc.etsii.grafo.util.graph_algorithms

Class Dinic

java.lang.Object
es.urjc.etsii.grafo.util.graph_algorithms.Dinic
public class Dinic extends Object
Dinic's algorithm for the maxflow problem. See ...

  • Constructor Summary

    Constructors
    Constructor
    Description
    Dinic(int N)
    New Dinic algorithm or graph of size N

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(int v1, int v2, int cap)
    Just adds an edge and ALSO adds it going backwards.
    boolean
    bfs(int source, int sink)
    BFS
    int
    dfs(int source, int sink, int min)
    Runs inner DFS in Dinic's, from node pos with a flow of min.
    int
    flow(int source, int sink)
    Calculate flow from a source to a destination

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Dinic

      public Dinic(int N)
      New Dinic algorithm or graph of size N
      Parameters:
      N - graph size

  • Method Details

    • add

      public void add(int v1, int v2, int cap)
      Just adds an edge and ALSO adds it going backwards. EDGES ARE IGNORED IF ALREADY EXISTS FROM V1 TO V2
      Parameters:
      v1 - Origin
      v2 - Destination
      cap - Capacity

    • bfs

      public boolean bfs(int source, int sink)
      BFS
      Parameters:
      source - start point
      sink - end point
      Returns:
      true if path exists, false otherwise

    • dfs

      public int dfs(int source, int sink, int min)
      Runs inner DFS in Dinic's, from node pos with a flow of min.
      Parameters:
      source - start point
      sink - end point
      min - flow
      Returns:
      flow

    • flow

      public int flow(int source, int sink)
      Calculate flow from a source to a destination
      Parameters:
      source - start point
      sink - end point
      Returns:
      flow