Help required in Understanding Graph representation.

general
1

I ma learning Dinic algorithm from here Dinic.But in this link I am not able to get how graph is representing.

inline void add(int u, int v, int c) {
    to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[u], fin[u] = nEdge++;
    to[nEdge] = u, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[v], fin[v] = nEdge++;
}

the above lines are unclear for me.Any help :frowning:

2

It’s a list of directed edges for each vertex.
Given an edge (or more precise its integer index i) you can get the vertex it’s pointing to (to[i]), and the problem-specific capacity and flow (cap[i] , flow[i]). The starting vertex of an edge isn’t accessible from the edge index.

To iterate over the list of edges starting at an vertex v, you get the first edge (index) from fin[v] (it is actually the last edge you added to the list, but the order doesn’t matter). The next element of the list is given by next[i] (i=fin[v]) and so on.

In the code two directed edges are added in order to add one bi-directional edge.

1 Like