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

Question

I have tried looking in stack overflow for an answer to my question. I've found those answers, but their solution doesn't really apply to my case, as I have non-directed edges. I cannot create a new vertex with edges going in at Vin and edges goint out at Vout, as there is no "going in" or "out" in a specific direction.

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

(there was a second stack question that I can't find, but it was the same answer)

Initial problem

My problem is that I have a graph where nodes have a capacity, all edges are bidirectional, and I need to find all the paths that allow me to maximize the flow of N elements through the graph.

Basically it's a lem-in with rooms of capacity 1 and bidirectional edges of infinite capacity.

Imagine a maze where you can have as many people in tunnel, but only one person per room. They can move from one room to another in one turn. How can I make it so that I get all the ways for people to go from the start to the end of the maze, without ever having 2 people in the same room.

Implementation of Edmonds-Karp

I have managed to implement an Edmonds-Karp (probably very poorly), using an adjacency matrix (it's a 1d array of integers using bits to check whether there is connection or not).

I have 3 function, a function that runs the algorithm itself (I'm simplifying the code a bit, such as removing protection for the mallocs, frees, etc... so that the algorithm looks better):

1. Main algorithm loop

This is the main loop. I try to find an augmenting path. If I don't, that means the end room's (sink) parent will be to the initial value (-1). Else I apply the path, print the path and continue.

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);
    }
}

2. Find the augmenting path

Then there is a function that finds an augmenting path. I just use a BFS with a queue, pop the the parent and then check all the children. If a children has a forward connection and still has capacity, I add it to the path, mark it visited and push it in the queue. If a children has a backward connection and flow going through it, I add it to the path, mark it visited and push it in the queue.

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);
}

3. Apply the augmenting path

The function that applies the augmenting path is quite simple, as in my case the capacity is 1 for all edges. We just go back from end (sink), till we reach the start (tap) by using the IDs saved in the path. For each room, we fill the capacity from parent to child and free capacity from child to 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;
    }
}

There is a check that I have added in following condition:

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

This check !map->rooms[child_id]->visited) is a visited flag that I add when building my way from the path that I found. It allows me to avoid taking the same room multiple times in some situations.

If I have multiple edges going in, in Edmond-Karps the flow is going to be limited by the edges. It means if I have 4 edge to a node, I can have 2 elements going in, as long as I have 2 other edges for the elements to go out. This checks avoid that situation.

BUT, and that is my main problem, by doing this, I block some possible paths through the maze.

The pictures that follow will show you the problem. Without my added check, Edmonds-Karp works well, but uses edges to find the best flow:

Here is the solution when I add my check to avoid using the same room twice:

Here is what I would like to find:

Is there any way to modify my Edmonds-Karp implementation to get what I want ? If not, is there any other algorithm that I could use ?

Thank you all so much for your patience !

PS: I cannot embed pictures as I don't have enough reputation :'(

Answer 1

Let's start with something simple, assuming that we have a simple graph with two nodes A and B, A connected to B: A <-> B

For each node, add one pair of node, SA and EA for A, and SB and EB for B. (S means start and E means end)

• From SA, add a directional edge to node EA with capacity equals capacity of node A.
• Apply same steps with node B,

Now, we have a graph looks like this:

SA -> EA  
SB -> EB

To represent the connection between A and B, we add a directional edge from EA -> SB with unlimited (very large) capacity, similarly, we add a directional edge from EB -> SA

So, our final graph is:

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

We realize that, this transformation can be applied easily for more complex graph too, using the similar process.

After applying the transformation, now, we can use standard max flow algorithm to solve this problem. Cheers!