Maximum Flow using Breath-First-Search

Maximum Flow

In an undirected graph, it is possible to transmit or send data across vertices in an optimised manner and without collisions. This is the idea behind maximum flow, is to find which routes are optimal to send data through rather than using random ones. The routes shall not have any intersections whatsoever.

The idea is simple, we first use Breath-First-Search but instead of traversing the vertices, we traverse the edges to find the routes, then we resolve the ones whom are intertwined resulting in unintersected routes.

At last, we send the data through batches across the network.

Algorithm

This is a sample implementation of the BFS algorithm.

static t_lst	bfs(t_lst *open, t_hash *parent)
{
	t_lstnode	walk;
	t_edge		e;

	g_graph->source->seen = M_FRESH;
	g_graph->sink->seen = M_FRESH;
	*parent = hash_alloc(g_graph->n_vertices, lst_free);
	*open = lst_alloc(blob_keep);
	walk = lst_front(g_graph->source->edges);
	while (walk)
	{
		e = walk->blob;
		if (edge_fresh(e))
		{
			lst_push_back_blob(*open, e, sizeof(t_edge), false);
			hash_add_edge(*parent, e, NULL);
			if (e->dst == g_graph->sink)
			{
				edge_mark(e, M_BELONG_TO_PATH);
				return (lst_push_back_blob(lst_alloc(blob_keep),
											e, sizeof(t_edge), false));
			}
		}
		lst_node_forward(&walk);
	}
	return (NULL);
}

And this is the code source for the implementation of the whole algorithm.