具有non-weighted、双向边和具有流动能力的节点的流量解析算法的C实现

Question

我已经尝试在堆栈溢出中查找我的问题的答案。我已经找到了这些答案，但他们的解决方案并不真正适用于我的情况，因为我有 non-directed 个边。我无法创建一个新的顶点，边在 Vin 处进入，边在 Vout 处出，因为在特定方向上没有 "going in" 或 "out"。

Edmonds-Karp Algorithm for a graph which has nodes with flow capacities

（有第二个堆栈问题我找不到，但答案是一样的）

初始问题

我的问题是我有一个图，其中节点具有容量，所有边都是双向的，我需要找到所有允许我通过图最大化 N 元素流的路径。

基本上它是一个lem-in，房间容量为 1，双向边缘容量为无限。

想象一个迷宫，隧道中可以容纳很多人，但每个房间只能容纳一个人。他们可以在一个回合内从一个房间移动到另一个房间。我怎样才能做到让人们从迷宫的起点走到终点，而不是让 2 个人在同一个房间里。

实施Edmonds-Karp

我已经设法实现了 Edmonds-Karp（可能非常糟糕），使用邻接矩阵（它是一维整数数组，使用位来检查是否存在连接）。

我有 3 个函数，一个运行算法本身的函数 （我稍微简化了代码，例如删除了对 malloc、frees 等的保护...以便算法看起来更好）:

主算法循环

这是主循环。我试图找到一条增广路径。如果我不这样做，那意味着最后一个房间的（水槽）parent 将是初始值（-1）。否则我应用路径，打印路径并继续。

void edmonds_karp(t_map *map)
{
    t_deque     *deque;
    uint32_t    *flow;
    int64_t     *path;
    t_way       *way;

    flow = ft_memalloc(sizeof(uint32_t) * map->size_rooms);

    while (TRUE)
    {
        deque = ft_deque_create();
        find_augmenting_path(deque, map, &flow, &path);
        if (path[get_end_room(map)->id] == -1)
            break ;
        apply_augmenting_path(map, &flow, path);
        way = build_way_from_path(path, map);
        print_way(way);
        ft_deque_delete(deque);
    }
}

求增广路

然后就是求增路的函数。我只是使用带有队列的 BFS，弹出 parent 然后检查所有 children。如果 children 有前向连接并且仍然有容量，我将它添加到路径中，将其标记为已访问并将其推送到队列中。如果 children 有反向连接并且流经它，我将它添加到路径中，将其标记为已访问并将其推送到队列中。

static int64_t  find_augmenting_path(t_deque *deque, t_map *map, uint32_t **flow, int64_t **path)
{
    uint32_t    child_id;
    uint8_t     *visited;
    t_room      *parent;
    t_room      *child;

    visited = ft_memalloc(sizeof(uint8_t) * map->size_rooms);
    ft_deque_push_back(deque, get_start_room(map));
    *path = init_path(map->size_rooms);

    while (deque->head)
    {
        parent = ft_deque_pop_front(deque);
        child_id = 0;

        while (child_id < map->size_rooms)
        {
            if (!visited[child_id] && !map->rooms[child_id]->visited)
                if ((((map->adj_matrix[parent->id] & (1ULL << child_id)) && !((*flow)[parent->id] & (1ULL << child_id))) // There is a forward connection and we still have capacity
                    || ((map->adj_matrix[child_id] & (1ULL << parent->id)) && ((*flow)[child_id] & (1ULL << parent->id))))) // There is a backward connection and we have reverse capacity
                {
                    child = get_room_by_id(map, child_id);
                    visited[child_id] = TRUE;
                    (*path)[child_id] = parent->id;
                    ft_deque_push_back(deque, (void*)child);
                    if (child->type == END)
                        return (SUCCESS);
                }
            ++child_id;
        }
    }
    return (ERROR);
}

应用增广路径

应用增广路径的函数非常简单，在我的例子中，所有边的容量都是 1。我们只是从末端（sink）返回，直到我们使用保存在路径中的 ID 到达起点（tap）。对于每个房间，我们填充从 parent 到 child 的容量和从 child 到 parent 的可用容量。

static void     apply_augmenting_path(t_map *map, uint32_t **flow, int64_t *path)
{
    t_room  *start;
    t_room  *parent;
    t_room  *child;

    start = get_start_room(map);
    child = get_end_room(map);
    while (child->id != start->id)
    {
        parent = get_room_by_id(map, path[child->id]);
        (*flow)[parent->id] |= 1ULL << child->id;
        (*flow)[child->id] |= 0ULL << parent->id;
        child = parent;
    }
}

我在以下条件下添加了一个检查：

if (!visited[child_id] && !map->rooms[child_id]->visited)

此检查 !map->rooms[child_id]->visited) 是我在从找到的路径构建路径时添加的已访问标记。它可以让我避免在某些情况下多次使用同一个房间。

如果我有多个边进入，在 Edmond-Karps 中，流量将受到边的限制。这意味着如果我有 4 个边到一个节点，我可以有 2 个元素进入，只要我有 2 个其他边让元素出去。此检查可避免这种情况。

但是，这是我的主要问题，通过这样做，我阻止了一些可能通过迷宫的路径。

下面的图片会告诉你问题所在。没有我添加的检查，Edmonds-Karp 运行良好，但使用边缘找到最佳流：

这是我添加支票以避免使用同一个房间两次的解决方案：

这是我想找到的：

有什么方法可以修改我的 Edmonds-Karp 实现以获得我想要的吗？如果没有，我可以使用其他算法吗？

非常感谢大家的耐心等待！

PS: 我无法嵌入图片，因为我没有足够的声誉:'(

Answer 1

让我们从简单的事情开始，假设我们有一个包含两个节点 A 和 B 的简单图，A 连接到 B：A <-> B

对于每个节点，添加一对节点，A为SA和EA，B为SB和EB。（S表示开始，E表示结束）

从 SA 向节点 EA 添加一条方向边，其容量等于节点 A 的容量。
对节点 B 应用相同的步骤，

现在，我们的图表如下所示：

SA -> EA  
SB -> EB

为了表示 A 和 B 之间的连接，我们添加一条从 EA -> SB 的方向边，具有无限（非常大）的容量，类似地，我们添加一条从 EB -> SA 的方向边

所以，我们的最终图表是：

SA -> EA  
SB -> EB
EA -> SB
EB -> SA

我们意识到，使用类似的过程，这种转换也可以很容易地应用于更复杂的图形。

应用转换后，现在，我们可以使用标准的最大流算法来解决这个问题。干杯!

具有non-weighted、双向边和具有流动能力的节点的流量解析算法的C实现

C implementation of an algorithm for flow resolution with non-weighted, bidirectional edges, and nodes with flow capacity

c

algorithm

graph

adjacency-matrix

edmonds-karp

初始问题

实施Edmonds-Karp