具有非整数边容量的 Dinic 最大流算法

Question

有一个 C++ implementation Dinic 的最大流问题算法，我正在尝试使用。在该 C++ 代码中，假定所有参数都是整数。我尝试将代码转换为等效代码，其中边的容量可以是连续的（非整数）。这是我的代码：

// C++ implementation of Dinic's Algorithm 
// #include "HEADERS.h"

#include<bits/stdc++.h> 



using namespace std; 

double EPSILON = 1e-6 ;
// A structure to represent a edge between 
// two vertex 
struct Edge 
{ 
    int v ; // Vertex v (or "to" vertex) 
            // of a directed edge u-v. "From" 
            // vertex u can be obtained using 
            // index in adjacent array. 

    double flow ; // flow of data in edge 

    double C; // capacity 

    int rev ; // To store index of reverse 
            // edge in adjacency list so that 
            // we can quickly find it. 
}; 

// Residual Graph 
class Graph 
{ 
    int V; // number of vertex 
    int *level ; // stores level of a node 
    vector< Edge > *adj; 
public : 
    Graph(int V) 
    { 
        adj = new vector<Edge>[V]; 
        this->V = V; 
        level = new int[V]; 
    } 

    // add edge to the graph 
    void addEdge(int u, int v, double C) 
    { 
        // Forward edge : 0 flow and C capacity 
        Edge a{v, 0, C, static_cast<int> (adj[v].size()) }; 

        // Back edge : 0 flow and 0 capacity 
        Edge b{u, 0, 0, static_cast<int> (adj[u].size()) }; 

        adj[u].push_back(a); 
        adj[v].push_back(b); // reverse edge 
    } 

    bool BFS(int s, int t); 
    int sendFlow(int s, double flow, int t, int ptr[]); 
    double DinicMaxflow(int s, int t); 
}; 

// Finds if more flow can be sent from s to t. 
// Also assigns levels to nodes. 
bool Graph::BFS(int s, int t) 
{ 
    for (int i = 0 ; i < V ; i++) 
        level[i] = -1; 

    level[s] = 0; // Level of source vertex 

    // Create a queue, enqueue source vertex 
    // and mark source vertex as visited here 
    // level[] array works as visited array also. 
    list< int > q; 
    q.push_back(s); 

    vector<Edge>::iterator i ; 
    while (!q.empty()) 
    { 
        int u = q.front(); 
        q.pop_front(); 
        for (i = adj[u].begin(); i != adj[u].end(); i++) 
        { 
            Edge &e = *i; 
            if (level[e.v] < 0 && e.flow < e.C) 
            { 
                // Level of current vertex is, 
                // level of parent + 1 
                level[e.v] = level[u] + 1; 

                q.push_back(e.v); 
            } 
        } 
    } 

    // IF we can not reach to the sink we 
    // return false else true 
    return level[t] < 0 ? false : true ; 
} 

// A DFS based function to send flow after BFS has 
// figured out that there is a possible flow and 
// constructed levels. This function called multiple 
// times for a single call of BFS. 
// flow : Current flow send by parent function call 
// start[] : To keep track of next edge to be explored. 
//       start[i] stores count of edges explored 
//       from i. 
// u : Current vertex 
// t : Sink 
int Graph::sendFlow(int u, double flow, int t, int start[]) 
{ 
    // Sink reached 
    if (u == t) 
        return flow; 

    // Traverse all adjacent edges one -by - one. 
    for ( ; start[u] < static_cast <int> (adj[u].size()) ; start[u]++) 
    { 
        // Pick next edge from adjacency list of u 
        Edge &e = adj[u][start[u]]; 

        if (level[e.v] == level[u]+1 && e.flow < e.C) 
        { 
            // find minimum flow from u to t 
            double curr_flow = min(flow, e.C - e.flow); 

            double temp_flow = sendFlow(e.v, curr_flow, t, start); 

            // flow is greater than zero 
            if (temp_flow > 0) 
            { 
                // add flow to current edge 
                e.flow += temp_flow; 

                // subtract flow from reverse edge 
                // of current edge 
                adj[e.v][e.rev].flow -= temp_flow; 
                return temp_flow; 
            } 
        } 
    } 

    return 0; 
} 
// Returns maximum flow in graph 
double Graph::DinicMaxflow(int s, int t) 
{ 
    // Corner case 
    if (s == t) 
        return -1; 

    double total = 0; // Initialize result 

    // Augment the flow while there is path 
    // from source to sink 
    while (BFS(s, t) == true) 
    { 
        // store how many edges are visited 
        // from V { 0 to V } 
        int *start = new int[V+1]; 
        double flow = sendFlow(s, INT_MAX, t, start) ;
        // while flow is not zero in graph from S to D 
        while (flow > EPSILON )
        {
            // Add path flow to overall flow 
            total += flow;
            flow = sendFlow(s, INT_MAX, t, start) ;
        }
    } 

    // return maximum flow 
    return total; 
} 

// Driver program to test above functions 
int main() 
{ 
    Graph g(6); 
    g.addEdge(0, 1, 16 ); 
    g.addEdge(0, 2, 13 ); 
    g.addEdge(1, 2, 10 ); 
    g.addEdge(1, 3, 12 ); 
    g.addEdge(2, 1, 4 ); 
    g.addEdge(2, 4, 14); 
    g.addEdge(3, 2, 9 ); 
    g.addEdge(3, 5, 20 ); 
    g.addEdge(4, 3, 7 ); 
    g.addEdge(4, 5, 4); 

    // next exmp 
    /*g.addEdge(0, 1, 3 ); 
    g.addEdge(0, 2, 7 ) ; 
    g.addEdge(1, 3, 9); 
    g.addEdge(1, 4, 9 ); 
    g.addEdge(2, 1, 9 ); 
    g.addEdge(2, 4, 9); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 5, 3); 
    g.addEdge(4, 5, 7 ); 
    g.addEdge(0, 4, 10); 

    // next exp 
    g.addEdge(0, 1, 10); 
    g.addEdge(0, 2, 10); 
    g.addEdge(1, 3, 4 ); 
    g.addEdge(1, 4, 8 ); 
    g.addEdge(1, 2, 2 ); 
    g.addEdge(2, 4, 9 ); 
    g.addEdge(3, 5, 10 ); 
    g.addEdge(4, 3, 6 ); 
    g.addEdge(4, 5, 10 ); */
    cout << "Maximum flow " << g.DinicMaxflow(0, 5) << endl ; 
    return 0; 
}

在此代码中，我已将 flow 和 C 的类型更改为 double。我还更改了部分代码以使其适应这种新的 double 类型。该代码仅偶尔有效！它要么输出正确的输出 Maximum flow 23，要么抛出 Segmentation fault (core dumped) 错误。我真的不知道这段代码有什么问题。有什么想法吗？

Answer 1

我不知道算法是否正确，但假设是这样，link 处的代码有几个问题。

#include<bits/stdc++.h>header.
内存泄漏。

首先，使用 bits/stdc++.h should be avoided，并且应该使用正确的 #include 文件。

其次，使用 std::vector 可以解决内存泄漏问题。该代码在某些地方使用std::vector，但在其他地方完全拒绝使用它。例如：

int *start = new int[V+1];

应替换为：

std::vector<int> start(V+1);

前者由于代码中缺少 delete [] start; 而导致内存泄漏。使用 std::vector，内存泄漏消失。

引入std::vector后，Graphclass中的V成员变量就不需要跟踪顶点数了。原因是 vector 成员的大小为 V 个顶点，并且 vector 已经通过使用 vector::size() 成员函数知道了它们自己的大小。所以V这个成员变量是多余的，可以去掉。

可以进行的最后更改是在 Graph class 内移动 struct Edge。

考虑到所有提到的变化，这里是一个清理版本 returns 与原始代码相同的结果运行并且在 main() 中设置了测试图功能：

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <climits>

class Graph
{
    struct Edge
    {
        int v; 
        int flow; 
        int C; 
        int rev; 
    };

    std::vector<int> level;
    std::vector<std::vector< Edge >> adj;

public:
    Graph(int V) : level(V), adj(V) {}
    void addEdge(int u, int v, int C)
    {
        adj[u].push_back({ v, 0, C, static_cast<int>(adj[v].size()) });
        adj[v].push_back({ u, 0, 0, static_cast<int>(adj[u].size()) }); 
    }

    bool BFS(int s, int t);
    int sendFlow(int s, int flow, int t, std::vector<int>& ptr);
    int DinicMaxflow(int s, int t);
};

bool Graph::BFS(int s, int t)
{
    std::fill(level.begin(), level.end(), -1);
    level[s] = 0; 
    std::list< int > q;
    q.push_back(s);
    std::vector<Edge>::iterator i;
    while (!q.empty())
    {
        int u = q.front();
        q.pop_front();
        for (i = adj[u].begin(); i != adj[u].end(); i++)
        {
            Edge &e = *i;
            if (level[e.v] < 0 && e.flow < e.C)
            {
                level[e.v] = level[u] + 1;
                q.push_back(e.v);
            }
        }
    }
    return level[t] < 0 ? false : true;
}

int Graph::sendFlow(int u, int flow, int t, std::vector<int>& start)
{
    if (u == t)
        return flow;
    for (; start[u] < static_cast<int>(adj[u].size()); start[u]++)
    {
        // Pick next edge from adjacency list of u 
        Edge &e = adj[u][start[u]];

        if (level[e.v] == level[u] + 1 && e.flow < e.C)
        {
            int curr_flow = std::min(flow, e.C - e.flow);
            int temp_flow = sendFlow(e.v, curr_flow, t, start);

            if (temp_flow > 0)
            {
                e.flow += temp_flow;
                adj[e.v][e.rev].flow -= temp_flow;
                return temp_flow;
            }
        }
    }
    return 0;
}

int Graph::DinicMaxflow(int s, int t)
{
    if (s == t)
        return -1;
    int total = 0; 
    while (BFS(s, t) == true)
    {
        std::vector<int> start(level.size() + 1);
        while (int flow = sendFlow(s, INT_MAX, t, start))
            total += flow;
    }
    return total;
}

测试函数如下：

int main() 
{ 
    Graph g(6); 
    g.addEdge(0, 1, 16 ); 
    g.addEdge(0, 2, 13 ); 
    g.addEdge(1, 2, 10 ); 
    g.addEdge(1, 3, 12 ); 
    g.addEdge(2, 1, 4 ); 
    g.addEdge(2, 4, 14); 
    g.addEdge(3, 2, 9 ); 
    g.addEdge(3, 5, 20 ); 
    g.addEdge(4, 3, 7 ); 
    g.addEdge(4, 5, 4); 
    std::cout << "Maximum flow " << g.DinicMaxflow(0, 5); 
}

Live Example

现在，如果你想看看如果你使用 double 而不是 int 作为流量会发生什么，最简单的方法是创建一个基于 class 的模板在上面的代码上。目标是获取使用 int 的位置，而不是将 int 替换为 double，而是将 int 替换为模板参数（例如，T）。生成的代码如下：

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <climits>

template <typename T>
class Graph
{
    struct Edge
    {
        int v;
        T flow;
        T C;
        int rev;
    };

    std::vector<int> level;
    std::vector<std::vector<Edge>> adj;

public:
    Graph(int V) : level(V), adj(V) {}
    void addEdge(int u, int v, T C)
    {
        adj[u].push_back({ v, T(), C, static_cast<int>(adj[v].size())});
        adj[v].push_back({ u, T(), T(), static_cast<int>(adj[u].size())}); // reverse edge 
    }
    bool BFS(int s, int t);
    T sendFlow(int s, T flow, int t, std::vector<int>& ptr);
    T DinicMaxflow(int s, int t);
};

template <typename T>
bool Graph<T>::BFS(int s, int t)
{
    std::fill(level.begin(), level.end(), -1);
    level[s] = 0; 
    std::list< int > q;
    q.push_back(s);

    typename std::vector<Edge>::iterator i;
    while (!q.empty())
    {
        int u = q.front();
        q.pop_front();
        for (i = adj[u].begin(); i != adj[u].end(); i++)
        {
            Edge &e = *i;
            if (level[e.v] < 0 && e.flow < e.C)
            {
                level[e.v] = level[u] + 1;
                q.push_back(e.v);
            }
        }
    }
    return level[t] < 0 ? false : true;
}

template <typename T>
T Graph<T>::sendFlow(int u, T flow, int t, std::vector<int>& start)
{
    if (u == t)
        return flow;

    for (; start[u] < static_cast<int>(adj[u].size()); start[u]++)
    {
        Edge &e = adj[u][start[u]];
        if (level[e.v] == level[u] + 1 && e.flow < e.C)
        {
            T curr_flow = std::min(flow, e.C - e.flow);
            T temp_flow = sendFlow(e.v, curr_flow, t, start);
            if (temp_flow > 0)
            {
                e.flow += temp_flow;
                adj[e.v][e.rev].flow -= temp_flow;
                return temp_flow;
            }
        }
    }
    return 0;
}

template <typename T>
T Graph<T>::DinicMaxflow(int s, int t)
{
    if (s == t)
        return -1;
    T total = 0; 

    while (BFS(s, t) == true)
    {
        std::vector<int> start(level.size() + 1);
        while (T flow = sendFlow(s, INT_MAX, t, start))
            total += flow;
    }
    return total;
}

Live Example

main 测试示例将简单地使用 Graph<double> 或 Graph<int> 而不是简单地 Graph - main 函数中的所有其他内容都保留一样。

现在该函数是一个模板，任何支持与 int 或 double 相同操作的数字类型都可以通过创建 Graph<numerical_type>.[=50 来轻松替换=]

具有非整数边容量的 Dinic 最大流算法

Dinic’s algorithm for Maximum Flow with non-integer edge capacities

c++

type-conversion

segmentation-fault

coredump

max-flow