具有非加权、双向边和具有流容量的节点流分辨率算法的实现

Question

我试着在堆叠溢出中寻找我的问题的答案。我已经找到了这些答案，但它们的解决方案并不真正适用于我的情况，因为我有无方向的边。我不能创建一个新的顶点，边进入Vin，边在Vout，因为没有“进入”或“输出”在一个特定的方向。

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

(还有第二个问题，我找不到，但答案是一样的)

初始问题

我的问题是，我有一个图，其中节点有一个容量，所有的边都是双向的，我需要找到所有的路径，使我能够最大化N个元素在图中的流动。

基本上，这是一个有容量1的房间和无限容量的双向边的问题。

想象一下，在一个迷宫里，你可以在隧道里有同样多的人，但每个房间只有一个人。他们可以轮流从一个房间搬到另一个房间。我怎样才能做到，这样我就能让人们从迷宫的起点一直走到迷宫的尽头，而不会有两个人在同一个房间里。

Edmonds-Karp的实现

我已经成功地实现了一个Edmonds(可能非常糟糕)，使用了一个邻接矩阵(它是一个使用位的一维整数数组来检查是否存在连接)。

我有3个函数，一个运行算法本身的函数(我正在稍微简化代码，比如删除对恶意代码的保护，释放，等等)。使算法看起来更好)

1. 主算法回路

这是主回路。我试着寻找一条加强的道路。如果我没有，这意味着结束房间的(接收器)父母将是初始值(-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);
    }
}

1. 查找增强路径

然后，有一个函数可以找到一条增强路径。我只使用带队列的BFS，弹出父程序，然后检查所有的子程序。如果一个子节点有一个前向连接，并且仍然有容量，我会将它添加到路径中，标记它所访问的，并将它推到队列中。如果一个子节点有一个向后连接并通过它进行流，我会将它添加到路径中，标记它所访问的，并将它推到队列中。

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. 应用增强路径

应用增强路径的函数非常简单，在我的例子中，所有边的容量都是1。通过使用保存在路径中的ID，我们只需要从结束(接收器)返回到开始(点击)。对于每个房间，我们填补了从父母到孩子的能力，免费的容量从孩子到家长。

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)是我在从找到的路径构建路径时添加的已访问标志。它允许我避免在某些情况下多次使用同一个房间。

如果我有多个边进入，在爱德蒙-卡普斯流将受到限制的边缘。这意味着，如果我有一个节点的4个边，我可以有2个元素进入，只要我有两个其他的边，让元素走出去。这种检查避免了这种情况。

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

下面的图片会告诉你问题的所在。没有我添加的检查，Edmonds工作得很好，但是使用边缘来找到最佳的流：

​

​

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

​

​

以下是我想要找到的：

​

​

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

非常感谢大家的耐心！

PS:我不能嵌入图片，因为我没有足够的声誉：

Answer 1

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

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

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

现在，我们有一幅图如下所示：

SA -> EA  
SB -> EB

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

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

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

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

经过变换，现在可以用标准的最大流算法来解决这个问题。干杯!