Блог

В настоящее время я пытаюсь создать программу, которая находит максимальный поток через сеть при ограничении, что края с общим исходным узлом должны иметь один и тот же поток. Именно с этим ограничением у меня и возникают проблемы.

В настоящее время у меня есть код для получения всех маршрутов увеличения потока, но я не решаюсь кодировать увеличение, потому что не могу понять, как добавить ограничение. Я думаю, возможно, об алгоритме обратного отслеживания, который пытается назначить поток с помощью метода Форда-Фулкерсона, а затем пытается приспособиться к ограничению.

Итак, мой код:
Существует класс графа, который имеет в качестве атрибутов все вершины и ребра, а также методы для передачи падающих ребер в вершину и предыдущих ребер в вершину:

 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: Как я могу найти максимальный поток через сеть, когда все ребра, которые совместно используют исходный узел, должны иметь один и тот же поток?

Я бы предположил, что у вас есть входные данные, которые определяют максимальный поток через каждое ребро.

Алгоритм тогда:

1. Поскольку ребра с общим источником должны иметь одинаковый фактический конечный поток, первым шагом должна быть небольшая предварительная обработка, чтобы уменьшить максимальный поток на каждом ребре до минимального потока из общего источника.
2. примените стандартный алгоритм максимального потока.
3. сначала выполните поиск по глубине от источника потока ( я предполагаю, что есть только один), пока не найдете узел с неравными потоками. Уменьшите максимальные потоки на всех ребрах от этого узла до минимального потока, назначенного алгоритмом. Повторно примените алгоритм.

Повторяйте шаг 3 до тех пор, пока не останется неравномерных потоков.

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

Второй алгоритм:

1. Отрегулируйте пропускную способность каждого выходного ребра так, чтобы она была равна минимальной пропускной способности всех выходных ребер из общей вершины
2. Выполните поиск по ширине сначала по графику. При добавлении ребра установите поток через ребро минимальным

• поток в исходный узел делится на количество выходящих ребер
• емкость края

3. Когда поиск завершен, сумма поступает в узел назначения.

Для справки, вот код 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
 

( если этот формат спецификации не сразу очевиден, он задокументирован здесь )

Узел » а » имеет два внешних края, пропускная способность которых была скорректирована для обеспечения баланса. Однако узел » 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
 

что соответствует требованиям.

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

Вот реализация PathFinder алгоритма Нестора

  void cPathFinder::equiflows()
        {
            // source outflows
            int outlinkpercent = 100 / node(myStart).outdegree();
            for (auto amp;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 amp;inlink : inlinks(v)) {
                        sumInput  = inlink.second.myValue;
                    }

                    // node outflows
                    int outValue = sumInput / node(v).outdegree();
                    for (auto amp;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();
        }
    }