具有公共源约束边的有向网络中的流扩充必须具有相同的流

Question

我目前正在尝试创建一个程序，在一个约束条件下，找到通过网络的最大流，即具有公共源节点的边必须具有相同的流。正是这种约束让我感到困扰

目前，我有代码来获取所有的流增强路由，但我对编写增强代码犹豫不决，因为我不知道如何添加约束。我正在考虑一种回溯算法，它尝试使用Ford Fulkerson方法分配流量，然后尝试调整以适应约束

所以我的代码：
有一个graph类，它具有所有顶点和边的属性，以及将关联边获取到顶点和将前面的边获取到顶点的方法：

class WeightedEdge:
    def __init__(self, from_vertex, to_vertex, capacity):
        self.tail = from_vertex
        self.head = to_vertex
        self.capacity = capacity

class Graph:
    def __init__(self, vertices, edges, capacities):
        self.vertices = vertices
        self.edges = [WeightedEdge(edges[i][0], edges[i][1], capacities[i]) for i in range(len(edges))]

        self.__forward_list = {v : [] for v in vertices}
        self.__reverse_list = {v: [] for v in vertices}

        for i in range(len(edges)):
            self.__forward_list[edges[i][0]].append((edges[i][1], capacities[i]))
            self.__reverse_list[edges[i][1]].append((edges[i][0], capacities[i]))

    def out_edges(self, vertex):
        return [WeightedEdge(vertex, next_vertex, capacity) for (next_vertex, capacity) in self.__forward_list[vertex]]
    
    def in_edges(self, vertex):
        return [WeightedEdge(prev_vertex, vertex, capacity) for (prev_vertex, capacity) in self.__reverse_list[vertex]]

每个边都是具有尾部顶点属性、容量属性和头部顶点属性的对象。 到目前为止，这是我的函数，用于获取流量增加路由：

def max_equal_split_flow(graph, source, sink):
    def find_augmenting_routes(vertex):
        route_buffer.append(vertex)
        if vertex == sink:
            flow_augmenting_routes.append([v for v in route_buffer])
            return
        else:
            out_edges = graph.out_edges(vertex)
            for edge in out_edges:
                find_augmenting_routes(edge.head)
                route_buffer.pop()
    flow_augmenting_routes = []
    route_buffer = []
    find_augmenting_routes(source)
    print(flow_augmenting_routes)

TLDR：当共享源节点的所有边缘必须具有相同的流时，如何找到通过网络的最大流？

Answer 1

我猜您有一个输入，指定通过每条边的最大流量

然后，算法是：

1. 由于具有公共源的边必须具有相同的实际最终流量，因此第一步必须进行一些预处理，以将每条边上的最大流量减少到来自公共源的最小流量

2. 应用标准最大流算法

3. 从流量原点（我假设只有一个）执行深度优先搜索，直到找到流出不相等的节点。将此节点所有边上的最大流减少为算法指定的最小流。重新应用算法

重复步骤3，直到没有不均匀流动

=======================================

第二种算法：

1. 将每个输出边的容量调整为等于公共顶点所有输出边的最小容量

2. 通过图形执行广度优先搜索。添加边时，将通过边的流量设置为最小值

• 流入源节点的流除以退出边的数量
• 边缘容量

1. 搜索完成后，总和流入目标节点

作为参考，这里是用递归

进行深度优先搜索的C++代码

void cPathFinder::depthRecurse(int v)
{
    // record new node on the search
    myPred.push_back(v);

    // remember this node has been visted
    myPath[v] = 1;

    // look for new adjacent nodes
    for (int w : myGraph.adjacent(v))
        if (!myPath[w])
        {
            // search from new node
            depthRecurse(w);
        }
}

下面是一个最简单的示例图，它表明调整外缘的容量不足以平衡实际流出

format flows
g
l src a 210
l a b 200
l a c 200
l b d 500
l c d 500
s src
e d

（如果此规范格式不明显，则为documented here）

节点“a”有两个输出边，其容量已调整为平衡。但是，“src”节点没有提供足够的流来填充边缘，因此输出是无效的

total flow 210
a     b capacity 200 used 10
a     c capacity 200 used 200
src   a capacity 210 used 210
b     d capacity 500 used 10
c     d capacity 500 used 200

这就提出了另一种算法#3：

1. 将每个输出边的容量调整为等于公共顶点所有输出边的最小容量

2. 应用标准最大流算法

3. 从流量原点执行深度优先搜索，直到找到流出不相等的节点。重新分配流量，使其平衡。“删除边到节点”，并使其成为新的流源，流等于“删除边”的总和

4. 应用修改的最大流算法处理多个源

5. 重复步骤3和4，直到所有流量平衡

将步骤3和4应用到前面的示例

format multiflows
g
l a1 b 105
l a2 c 105
l b d 500
l c d 500
s a1
s a2
e d

b   d capacity 500 used 105
a1   b capacity 105 used 105
c   d capacity 500 used 105
a2   c capacity 105 used 105
total flow 210.000000

符合要求

=====================================================================

这是Nestor算法的PathFinder实现

 void cPathFinder::equiflows()
        {
            // source outflows
            int outlinkpercent = 100 / node(myStart).outdegree();
            for (auto &outlink : node(myStart).myLink)
                outlink.second.myValue = outlinkpercent;

            // function to call each time a node is visited in BFS
            myVisitor.set(
                [this](int v)
                {
                    static int X = INT_MAX;

                    if( v == myEnd ) {
                        // destination reached, report maximum flow
                        std::cout << "maximum flow is " << X << "\n";
                        return;
                    }
                    
                    // sum the inputs
                    int sumInput = 0;
                    for (auto &inlink : inlinks(v)) {
                        sumInput += inlink.second.myValue;
                    }

                    // node outflows
                    int outValue = sumInput / node(v).outdegree();
                    for (auto &outlink : node(v).myLink) {
                        outlink.second.myValue = outValue;

                        // check if this outflow reduces maximum flow through network
                        int x = outlink.second.myCost * 100 / outValue;
                        if( x < X )
                            X = x;
                    }

                });

            // do a breadth first search, updating flows as we go along
            breadth();
        }
    }