I am trying to solve the problem of node/vertices disjoint paths in a directed graph and came to know about the idea of splitting nodes into in and out nodes respectively. I got the idea and how it works and all the related theorem's like menger theorem but still, I'm not sure how to code it in an efficient manner.
Which data structure should I use so that I can split the vertices and still manage to balance the time complexity? Is there any algorithm existing which tells how to approach the code.
Please help or suggest some appropriate link which may help me out.
Thanks
It's quite simple actually. Let's say you have graph as an edge list of pairs u v meaning theres an edge from u to v
If nodes are not integers already use a dictionary/hash/map to reduce them to integers in range 1..n where n is number of nodes.
Now we "split" all nodes, for each node i it will become 2 nodes i and i+n. where i is considered in-node and i+n out-node.
Now graph edges are modified, for every edge u --> v we instead store edge u+n --> v
Also we add edges from each nodes in-node to out-node, i.e. from node i to i+n
We can assign infinity capacities to all edges and capacities of 1 to edges that connect in-node to out-node
Now Node-disjoint paths from some node s to t can be found using any max-flow algorithm (Ford-Fulkerson, Edmonds-Karp, Dinic, etc)
pesudo-code for building residual network:
n = #nodes
for each node i in 1..n:
residual_graph.addEdge(i, i+n, capacity=1);
residual_graph.addEdge(i+n, i, capacity=0);
for each edge (u,v) in graph
residual_graph.addEdge(u+n, v, capacity=+Infinity);
residual_graph.addEdge(v, u+n, capacity=0);