Max flow Ford-Fulkerson using DFS augmented path retrieval

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
2
down vote

favorite












I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?



#include <stdio.h>
#include <stdlib.h>

#define SZ 20

int flow[SZ][SZ];
int residue[SZ][SZ];
int N, E, u, v, c;
int Source, Sink;

int visited[SZ];

inline int min(int a, int b) return a < b ? a : b;
inline int abs(int n) return n < 0 ? -n : n;

void print(int graph[SZ][SZ])

for (register int i = 0; i < N; i++)
for (register int j = 0; j < N; j++)
printf("%d ", graph[i][j]);

printf("n");

printf("n");


int dfs(int u, int rescap)

if (u == Sink

/*void input()

freopen("input.txt", "wt", stdout);

printf("%d %dn", SZ, 5*SZ);

for (register int i = 0; i < 5 * SZ; i++)

int a = rand() % SZ;
int b = rand() % SZ;
int c = rand() % SZ;

printf("%d %d %dn", a, b, c);


fclose(stdout);
*/

void maxflow()

freopen("input.txt", "rt", stdin);
scanf("%d %d", &N, &E);

Source = 0;
Sink = N - 1;

for (register int i = 0; i < E; i++)
scanf("%d %d %d", &u, &v, &c);
residue[u][v] = c;


int total = 0;
int rescap = 0;
while (rescap = dfs(Source, 1 << 30))
total += rescap;

printf("total flow: %dn", total);

print(flow);
print(residue);







share|improve this question



























    up vote
    2
    down vote

    favorite












    I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?



    #include <stdio.h>
    #include <stdlib.h>

    #define SZ 20

    int flow[SZ][SZ];
    int residue[SZ][SZ];
    int N, E, u, v, c;
    int Source, Sink;

    int visited[SZ];

    inline int min(int a, int b) return a < b ? a : b;
    inline int abs(int n) return n < 0 ? -n : n;

    void print(int graph[SZ][SZ])

    for (register int i = 0; i < N; i++)
    for (register int j = 0; j < N; j++)
    printf("%d ", graph[i][j]);

    printf("n");

    printf("n");


    int dfs(int u, int rescap)

    if (u == Sink

    /*void input()

    freopen("input.txt", "wt", stdout);

    printf("%d %dn", SZ, 5*SZ);

    for (register int i = 0; i < 5 * SZ; i++)

    int a = rand() % SZ;
    int b = rand() % SZ;
    int c = rand() % SZ;

    printf("%d %d %dn", a, b, c);


    fclose(stdout);
    */

    void maxflow()

    freopen("input.txt", "rt", stdin);
    scanf("%d %d", &N, &E);

    Source = 0;
    Sink = N - 1;

    for (register int i = 0; i < E; i++)
    scanf("%d %d %d", &u, &v, &c);
    residue[u][v] = c;


    int total = 0;
    int rescap = 0;
    while (rescap = dfs(Source, 1 << 30))
    total += rescap;

    printf("total flow: %dn", total);

    print(flow);
    print(residue);







    share|improve this question























      up vote
      2
      down vote

      favorite









      up vote
      2
      down vote

      favorite











      I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?



      #include <stdio.h>
      #include <stdlib.h>

      #define SZ 20

      int flow[SZ][SZ];
      int residue[SZ][SZ];
      int N, E, u, v, c;
      int Source, Sink;

      int visited[SZ];

      inline int min(int a, int b) return a < b ? a : b;
      inline int abs(int n) return n < 0 ? -n : n;

      void print(int graph[SZ][SZ])

      for (register int i = 0; i < N; i++)
      for (register int j = 0; j < N; j++)
      printf("%d ", graph[i][j]);

      printf("n");

      printf("n");


      int dfs(int u, int rescap)

      if (u == Sink

      /*void input()

      freopen("input.txt", "wt", stdout);

      printf("%d %dn", SZ, 5*SZ);

      for (register int i = 0; i < 5 * SZ; i++)

      int a = rand() % SZ;
      int b = rand() % SZ;
      int c = rand() % SZ;

      printf("%d %d %dn", a, b, c);


      fclose(stdout);
      */

      void maxflow()

      freopen("input.txt", "rt", stdin);
      scanf("%d %d", &N, &E);

      Source = 0;
      Sink = N - 1;

      for (register int i = 0; i < E; i++)
      scanf("%d %d %d", &u, &v, &c);
      residue[u][v] = c;


      int total = 0;
      int rescap = 0;
      while (rescap = dfs(Source, 1 << 30))
      total += rescap;

      printf("total flow: %dn", total);

      print(flow);
      print(residue);







      share|improve this question













      I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?



      #include <stdio.h>
      #include <stdlib.h>

      #define SZ 20

      int flow[SZ][SZ];
      int residue[SZ][SZ];
      int N, E, u, v, c;
      int Source, Sink;

      int visited[SZ];

      inline int min(int a, int b) return a < b ? a : b;
      inline int abs(int n) return n < 0 ? -n : n;

      void print(int graph[SZ][SZ])

      for (register int i = 0; i < N; i++)
      for (register int j = 0; j < N; j++)
      printf("%d ", graph[i][j]);

      printf("n");

      printf("n");


      int dfs(int u, int rescap)

      if (u == Sink

      /*void input()

      freopen("input.txt", "wt", stdout);

      printf("%d %dn", SZ, 5*SZ);

      for (register int i = 0; i < 5 * SZ; i++)

      int a = rand() % SZ;
      int b = rand() % SZ;
      int c = rand() % SZ;

      printf("%d %d %dn", a, b, c);


      fclose(stdout);
      */

      void maxflow()

      freopen("input.txt", "rt", stdin);
      scanf("%d %d", &N, &E);

      Source = 0;
      Sink = N - 1;

      for (register int i = 0; i < E; i++)
      scanf("%d %d %d", &u, &v, &c);
      residue[u][v] = c;


      int total = 0;
      int rescap = 0;
      while (rescap = dfs(Source, 1 << 30))
      total += rescap;

      printf("total flow: %dn", total);

      print(flow);
      print(residue);









      share|improve this question












      share|improve this question




      share|improve this question








      edited Apr 17 at 4:24









      user1118321

      10.2k11144




      10.2k11144









      asked Apr 17 at 3:26









      Sazzad Hissain Khan

      1112




      1112

























          active

          oldest

          votes











          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );








           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f192254%2fmax-flow-ford-fulkerson-using-dfs-augmented-path-retrieval%23new-answer', 'question_page');

          );

          Post as a guest



































          active

          oldest

          votes













          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes










           

          draft saved


          draft discarded


























           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f192254%2fmax-flow-ford-fulkerson-using-dfs-augmented-path-retrieval%23new-answer', 'question_page');

          );

          Post as a guest













































































          Popular posts from this blog

          Greedy Best First Search implementation in Rust

          Function to Return a JSON Like Objects Using VBA Collections and Arrays

          C++11 CLH Lock Implementation