C言語関係掲示板

過去ログ

No.944 グラフの最大流問題

[戻る] [ホームページ]
No.12015

グラフの最大流問題
投稿者---ボル(2004/01/21 23:48:18)


グラフ(ネットワーク)上における始点v0から終点v6へ流した時の最大流と最大流を実現したときの各辺に流れる量を出力(例参照)したいのですが、うまくいきません。下記のようなプログラムを組みましたが全パス(約390通り)を出力するのみとなってしまいます。どなたかご教示願います。[Windows XP/bcc]
【出力例】
最大流は・・・です。
最大流時の各辺に流れる量は
0 0 8 0 0 0・・0
0 0 0 2 0 0・・0
0 0 0 0 5 0・・0
・・・・・・・・・
・・・・・・・・・


  #include <stdio.h>

  #define N 14        /* 頂点の数 */
  #define E -1        /* 配列内のデータの終わりの記号 */
  #define START 0   /* 始点の頂点番号 */
  #define END 6    /* 終点の頂点番号 */

  int g[N][N] = {    /* グラフGはN行N列の配列 */
  /*   0   1   2   3   4   5   6   7   8   9  10  11  12  13 */
    {  0, 10,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0},
    {-10,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  6,  0,  0},
    {  0, -2,  0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0},
    {  0,  0, -5,  0,  8,  0,  0,  0,  0,  0,  0,  0, -8, -1},
    {  0,  0,  0, -8,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0},
    {  0,  0,  0,  0, -2,  0, 10,  0, -4,  0,  0,  0, -2,  0},
    {  0,  0,  0,  0,  0,-10,  0,-10,  0,  0,  0,  0,  0,  0},
    {  0,  0,  0,  0,  0,  0, 10,  0,-10,  0,  0,  0,  0,  0},
    {  0,  0,  0,  0,  0,  4,  0, 10,  0, -5,  0,  0,  0, -3},
    {  0,  0,  0,  0,  0,  0,  0,  0,  5,  0, -2, -3,  7,  1},
    {-10,  0,  0,  0,  0,  0,  0,  0,  0,  2,  0,  6,  0,  0},
    {  0, -6,  0,  0,  0,  0,  0,  0,  0,  3, -6,  0,  5,  0},
    {  0,  0, -4,  8,  0,  2,  0,  0,  0, -7,  0, -5,  0,  1},
    {  0,  0,  0,  1,  0,  0,  0,  0,  3, -1,  0,  0, -1,  0}
  };

  int existp(int,int []);
  void search_path(int,int []);
  void set_tv(int, int []);
  void add_path(int [],int);
  void print_path(int []);

  int main()
  {
    int tv[N];
    int path[N];

    path[0] = E;
    search_path(START,path);

  return 0;
  }

  void search_path(int v,int path[])
  {
    int path2[N];
    int tv[N];
    int i,w;

    for(i = 0;path[i] != E;i++) path2[i] = path[i];
      path2[i] = v; path2[i+1] = E;

      set_tv(v,tv);

      for(i = 0;(w = tv[i]) != E;i++){
        if(w == END){
          print_path(path2); /* ←この辺がおかしい? */
        }else if(!(existp(w,path2))){
          search_path(w,path2);
        }
      }
  }

  void set_tv(int v,int tv[])
  {
    int i,k = 0;

    for(i = 0;i < N;i++){
      if(g[v][i] != 0){
        tv[k] = i; k++;
      }
    }
    tv[k] = E;
  }

  int existp(int w,int path[])
  {
    int i;

    for(i = 0;path[i] != E;i++){
      if(w == path[i]) return 1;
    }
    return 0;
  }

  void print_path(int path[])
  {
    int i;

    for(i = 0;path[i] != E;i++) printf("%d ",path[i]);
      printf("%d\n",END);
  }

  void add_path(int path[],int w)
  {
    int i;

    for(i = 0;path[i] != E;i++);
      path[i] = w, path[i+1] = E;
  }




No.12016

Re:グラフの最大流問題
投稿者---たか(2004/01/21 23:53:40)


Boost::graph::edmunds_karp_max_flow またはBoost::graph::push_relabel_max_flow
を使うとか。使わなくてもヘッダにプログラムが書かれているので
何かの足しになるかもしれません。

手元にグラフ理論の本がありますが今日は時間が遅いのでまた日をおいて
考えてみます。

No.12017

Re:グラフの最大流問題
投稿者---たか(2004/01/21 23:55:19)


ところで確かめておきますがこの行列は隣接行列ですよね。

No.12024

Re:グラフの最大流問題
投稿者---ボル(2004/01/22 07:35:36)


>ところで確かめておきますがこの行列は隣接行列ですよね。

たかさんその通りで隣接行列です。
宜しくお願い致します。


No.12047

Re:グラフの最大流問題
投稿者---たか(2004/01/22 21:15:21)


遅くなりまして済みません。見つけた資料は、一番最初のノードから
一番最後のノードへの最大流を発見するものでした。だから今回のように
ノード数14でノード0からノード5への最大流を見つけるには、行列を書き
変えてノード5が最後になるようにする必要があります。

任意のノードから任意のノードへの最大流を発見するアルゴリズムを探し
たのですがちょっとわかりませんでした。push relabelアルゴリズムだと
うまく行くのかな?

現在の状態はノード0からノード13への最大流を表示するようになってい
ます。

#include <stdio.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 14
#define oo 1000000000

int g[MAX_NODES][MAX_NODES] = {    /* グラフGはN行N列の配列(重み付き無向グラフ) */
/*   0   1   2   3   4   5   6   7   8   9  10  11  12  13 */
  {  0, 10,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0},
  {-10,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  6,  0,  0},
  {  0, -2,  0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0},
  {  0,  0, -5,  0,  8,  0,  0,  0,  0,  0,  0,  0, -8, -1},
  {  0,  0,  0, -8,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0, -2,  0, 10,  0, -4,  0,  0,  0, -2,  0},
  {  0,  0,  0,  0,  0,-10,  0,-10,  0,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0,  0,  0, 10,  0,-10,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0,  0,  4,  0, 10,  0, -5,  0,  0,  0, -3},
  {  0,  0,  0,  0,  0,  0,  0,  0,  5,  0, -2, -3,  7,  1},
  {-10,  0,  0,  0,  0,  0,  0,  0,  0,  2,  0,  6,  0,  0},
  {  0, -6,  0,  0,  0,  0,  0,  0,  0,  3, -6,  0,  5,  0},
  {  0,  0, -4,  8,  0,  2,  0,  0,  0, -7,  0, -5,  0,  1},
  {  0,  0,  0,  1,  0,  0,  0,  0,  3, -1,  0,  0, -1,  0},
};

//Declarations
int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search
int pred[MAX_NODES];  // array to store augmenting path

inline template <typename T>
T min(T x, T y)
{
  return (x < y) ? x : y;  // returns minimum of x and y
}

// A Queue for Breadth-First Search
int head, tail;
int q[MAX_NODES + 2];

inline void enqueue(int x)
{
  q[tail++] = x;
  color[x] = GRAY;
}

inline int dequeue()
{
  int x = q[head++];
  color[x] = BLACK;

  return x;
}

//Breadth-First Search for an augmenting path
int bfs(int start, int target)
{
  int u, v;
  for (u = 0; u < n; u++)
    color[u] = WHITE;
  head = tail = 0;
  enqueue(start);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue();
    // Search all adjacent white nodes v. If the capacity
    // from u to v in the residual network is positive,
    // enqueue v.
    for (v = 0; v < n; v++) {
      if (color[v] == WHITE && capacity[u][v] - flow[u][v] > 0) {
        enqueue(v);
        pred[v] = u;
      }
    }
  }
  // If the color of the target node is black now,
  // it means that we reached it.
  return color[target] == BLACK;
}

//Ford-Fulkerson Algorithm
int max_flow(int source, int sink)
{
  int i, j, u;
  // Initialize empty flow.
  int max_flow = 0;
  for (i = 0; i < n; i++) 
    for (j = 0; j < n; j++)
      flow[i][j] = 0;

  // While there exists an augmenting path,
  // increment the flow along this path.
  while (bfs(source, sink)) {
    // Determine the amount by which we can increment the flow.
    int increment = oo;
    for (u = n - 1; pred[u] >= 0; u = pred[u])
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    // Now increment the flow.
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    max_flow += increment;
  }
  // No augmenting path anymore. We are done.
  return max_flow;
}

void assign_input()
{
  int i, j;
  
  e = 0;
  n = MAX_NODES;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
       if (capacity[i][j] = g[i][j]) e++;
//  e /= 2;
}

int main()
{
  int i, j;

  assign_input();
  printf("最大流は %d です。\n", max_flow(0, n - 1));
  printf("最大流時の各辺に流れる量は\n");
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
      printf("%3d ", (flow[i][j] > 0) ? flow[i][j] : 0);
    printf("\n");
  }
}



No.12048

Re:グラフの最大流問題
投稿者---たか(2004/01/22 21:15:56)


printf("最大流は %d です。\n", max_flow(0, n - 1));



printf("最大流は %d です。\n", max_flow(0, 6 - 1));

などにすると現在のプログラムでは永久ループに入るようです。

No.12053

Re:グラフの最大流問題
投稿者---ボル(2004/01/22 23:14:43)


たかさんありがとうございました。
たかさんのレスからチャレンジしてみます。結果等は後日ご報告致します。
取り急ぎお礼まで。

No.12056

Re:グラフの最大流問題
投稿者---たか(2004/01/22 23:54:25)


>たかさんありがとうございました。
>たかさんのレスからチャレンジしてみます。結果等は後日ご報告致します。
>取り急ぎお礼まで。

いえいえ、私の方でも時間が空き次第何かいいアルゴリズムを調べてみ
ます。基本的に幅優先探索と「最大流最小カット定理」maxflow-mincut
theoremを組み合わせたFord-Fulkersonのアルゴリズムしか見つからない
ようなので困ったものです。push relabel algorithm は余り使われてな
いのかなあ。誰か知りませんか?

最初このアルゴリズムを探すのにEdmonds-Karpから探し始めたのでなかな
か見つからずに弱りました(^^;

No.12059

Re:グラフの最大流問題
投稿者---ボル(2004/01/23 00:31:33)


たかさんへ。
取り急ぎレス頂いたプログラムをコンパイル(Borland C++ 5.5)したところ、35行と45行付近で「宣言の構文エラー」表示が出てしまいます。
何故でしょうか?とたかさんご連絡しつつ自分でもチョット考えてみます。

inline template <typename T> ←35行(この辺?)
T min(T x, T y)
{
return (x < y) ? x : y; // returns minimum of x and y
}

// A Queue for Breadth-First Search
int head, tail;
int q[MAX_NODES + 2];

inline void enqueue(int x) ←45行(この辺?)
{
q[tail++] = x;
color[x] = GRAY;
}



No.12060

Re:グラフの最大流問題
投稿者---通りすがり(2004/01/23 00:49:39)


>たかさんへ。
>取り急ぎレス頂いたプログラムをコンパイル(Borland C++ 5.5)したところ、35行と45行付近で「宣言の構文エラー」表示が出てしまいます。
>何故でしょうか?とたかさんご連絡しつつ自分でもチョット考えてみます。
>
>inline template <typename T> ←35行(この辺?)
>T min(T x, T y)
>{
> return (x < y) ? x : y; // returns minimum of x and y
>}
>
>// A Queue for Breadth-First Search
>int head, tail;
>int q[MAX_NODES + 2];
>
>inline void enqueue(int x) ←45行(この辺?)
>{
> q[tail++] = x;
> color[x] = GRAY;
>}
>

templateやinlineはC++の予約語ですから、ソースの拡張子を
.cppに変えればうまくいくはず。


No.12067

Re:グラフの最大流問題
投稿者---たか(2004/01/23 13:17:51)


あっそうでした。これはC++で書いたので(元資料はC)、

inline template <typename T>
T min(T x, T y)



int min(int x, int y)

それから関数の頭に inline と付いているのを全部取って下さい。
これでCとしてコンパイルできるはずです。

No.12134

Re:グラフの最大流問題
投稿者---ボル(2004/01/25 21:17:55)


>inline template <typename T>
>T min(T x, T y)
>を
>int min(int x, int y)
>
>それから関数の頭に inline と付いているのを全部取って下さい。
>これでCとしてコンパイルできるはずです。

たかさんありがとうございます。
上記のように変更した結果、コンパイルすることができました。
しかし、たかさんの言うとおり、
>printf("最大流は %d です。\n", max_flow(0, n - 1));
>を

これはノード0からノード13までの最大流。

>printf("最大流は %d です。\n", max_flow(0, 6 - 1));
>などにすると現在のプログラムでは永久ループに入るようです。

これにすると永久ループですよね。
その後色々と参考書等を読みトライしましたが、いまだ結果が得られていない状態です。
今回のプログラムはノード0(始点)からノード6(終点)時の最大流と各辺に流れる量を求めるものですが、このようなプログラムは難しいのでしょうかねえ。

No.12142

Re:グラフの最大流問題
投稿者---たか(2004/01/26 07:31:40)


>その後色々と参考書等を読みトライしましたが、いまだ結果が得られていない状態です。
>今回のプログラムはノード0(始点)からノード6(終点)時の最大流と各辺に流れる量を求めるものですが、このようなプログラムは難しいのでしょうかねえ。

お早うございます。昨晩のうちに完成した(と思われる)プログラムを
UPします。

原理は簡単で、このプログラムのsinkが最後尾の行と列に当たるのなら、
その行と列を最後に持って行き、出力する時に元に戻すというだけの
ものです。出力結果が正しいかまでは確かめていません。ご確認願い
ます。

#include <stdio.h>

enum Colors {WHITE, GRAY, BLACK};

#define MAX_NODES 14
#define END 5 // sink番号
#define oo 1000000000

int g[MAX_NODES][MAX_NODES] = {    /* グラフGはN行N列の配列(重み付き無向グラフ) */
/*   0   1   2   3   4   5   6   7   8   9  10  11  12  13 */
  {  0, 10,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0},
  {-10,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  6,  0,  0},
  {  0, -2,  0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0},
  {  0,  0, -5,  0,  8,  0,  0,  0,  0,  0,  0,  0, -8, -1},
  {  0,  0,  0, -8,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0, -2,  0, 10,  0, -4,  0,  0,  0, -2,  0},
  {  0,  0,  0,  0,  0,-10,  0,-10,  0,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0,  0,  0, 10,  0,-10,  0,  0,  0,  0,  0},
  {  0,  0,  0,  0,  0,  4,  0, 10,  0, -5,  0,  0,  0, -3},
  {  0,  0,  0,  0,  0,  0,  0,  0,  5,  0, -2, -3,  7,  1},
  {-10,  0,  0,  0,  0,  0,  0,  0,  0,  2,  0,  6,  0,  0},
  {  0, -6,  0,  0,  0,  0,  0,  0,  0,  3, -6,  0,  5,  0},
  {  0,  0, -4,  8,  0,  2,  0,  0,  0, -7,  0, -5,  0,  1},
  {  0,  0,  0,  1,  0,  0,  0,  0,  3, -1,  0,  0, -1,  0},
};

// sink節点番号を最後に置くための変換配列
int dt[MAX_NODES];

//Declarations
int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
enum Colors color[MAX_NODES]; // needed for breadth-first search
int pred[MAX_NODES];  // array to store augmenting path

int min(int x, int y)
{
  return (x < y) ? x : y;  // returns minimum of x and y
}

// A Queue for Breadth-First Search
int head, tail;
int q[MAX_NODES + 2];

void enqueue(int x)
{
  q[tail++] = x;
  color[x] = GRAY;
}

int dequeue()
{
  int x = q[head++];
  color[x] = BLACK;

  return x;
}

//Breadth-First Search for an augmenting path
int bfs(int start, int target)
{
  int u, v;
  for (u = 0; u < n; u++)
    color[u] = WHITE;
  head = tail = 0;
  enqueue(start);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue();
    // Search all adjacent white nodes v. If the capacity
    // from u to v in the residual network is positive,
    // enqueue v.
    for (v = 0; v < n; v++) {
      if (color[v] == WHITE && capacity[u][v] - flow[u][v] > 0) {
//        printf("%d->%d ", u, v); // print edge from u to v
        enqueue(v);
        pred[v] = u;
      }
    }
  }
  // If the color of the target node is black now,
  // it means that we reached it.
  return color[target] == BLACK;
}

//Ford-Fulkerson Algorithm
int max_flow(int source, int sink)
{
  int i, j, u;
  // Initialize empty flow.
  int max_flow = 0;
  for (i = 0; i < n; i++) 
    for (j = 0; j < n; j++)
      flow[i][j] = 0;

  // While there exists an augmenting path,
  // increment the flow along this path.
  while (bfs(source, sink)) {
    // Determine the amount by which we can increment the flow.
    int increment = oo;
    for (u = n - 1; pred[u] >= 0; u = pred[u])
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    // Now increment the flow.
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    max_flow += increment;
  }
  // No augmenting path anymore. We are done.
  return max_flow;
}

void assign_input()
{
  int i, j;
  
  e = 0;
  n = MAX_NODES;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
       if ((capacity[dt[i]][dt[j]] = (g[i][j] > 0) ? g[i][j] : 0) != 0) e++;
    }
}

// sink番号を変換する行列作成ルーチン。手を加えればsource番号も変更できる
void init_dt(int end)
{
  int i, j = 0, f = 0;
  
  for (i = 0; i < MAX_NODES - 1; i++, j++) {
    if (i == end) {
      dt[i] = MAX_NODES - 1;
      f = 1;
    } else 
      dt[i] = (f) ? j - 1 : j;
  }
  dt[i] = MAX_NODES - ((end == MAX_NODES - 1) ? 1 : 2);
  
  printf("変換行列: ");
  for (i = 0; i < MAX_NODES; i++)
    printf("%d ", dt[i]);
  printf("\n");
}

int main(void)
{
  int i, j;

  init_dt(END);
  assign_input();
  printf("最大流は %d です。\n", max_flow(0, n - 1));
  printf("最大流時の各辺に流れる量は\n");
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
      printf("%3d ", (flow[dt[i]][dt[j]] > 0) ? flow[dt[i]][dt[j]] : 0);
    printf("\n");
  }
  return 0;
}


No.12214

Re:グラフの最大流問題
投稿者---ボル(2004/01/27 21:55:23)


>お早うございます。昨晩のうちに完成した(と思われる)プログラムを
>UPします。
>
>原理は簡単で、このプログラムのsinkが最後尾の行と列に当たるのなら、
>その行と列を最後に持って行き、出力する時に元に戻すというだけの
>ものです。出力結果が正しいかまでは確かめていません。ご確認願い
>ます。

たかさんありがとうございました。
出力した結果、希望通りの結果が得られました。
(C言語には関係ないかも知れませんが、最大流の結果は机上でチェーンフロー法等を使用して確認)

本当にたかさんに感謝するのみです。


No.12118

Re:グラフの最大流問題
投稿者---ボル(2004/01/24 20:50:35)


>templateやinlineはC++の予約語ですから、ソースの拡張子を
>.cppに変えればうまくいくはず。

通りすがりさんご協力ありがとうございます。
このやり方でもチャレンジしてみます。