JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) What is the meaning of potential? << PREV    [ 1 2 ]
 Re: What is the meaning of potential? (response to post by jbernadas) | Reply Thank you jbernadas, your comment helped me a lot.I still have question:in tutorial in procedure Reduce Cost (pi) there writes that ```c_rev[i, j] ``` should always, for each edge (I suppose that E is whole set), be 0. I understand that c[i, j] will be 0 if edge (i, j) is part of the shortest part (pi[j] = pi[i] + c[i, j]), but I don't see why c_rev should be 0 for each edge.So, why I am asking/writing that - in second part, figure 4, graph (g, h, i), edge (3, 2) has cost 6 and it is c_rev[2, 3] (please correct me if I am wrong). In graph (a) there is no edge (3, 2), so (3, 2) could be only c_rev[2, 3] (as result of residual network) and according to Reduce Cost, its cost should be 0, but as I see it's not always after Reduce Cost. Probably I don't understand something, but please show me that part. Am I missing something?Thank you.
 Re: What is the meaning of potential? (response to post by boba5551) | Reply Hello, I will try to explain this trick.First of all in Reduce_Cost (pi) there is not E but E_x (the set of reduced edges). That is why edge (3,2) is in E_x. Now about my trick: if the edge (i,j) is the part of the shortest path then the reduced costs c(i,j) and c_rev(i,j) will be zero (it is clear and you have understood it). But if there are no negative-cost cycles, reduced costs will always be nonnegative. That is why I assign c_rev(i,j)=0 in both cases (it could not be less than zero and if reduced c(i,j)>0 then the edge rev(i,j) is not in E_x). Actually I would have to write c_rev(i,j)=-c(i,j). But if there are no multiple edges in the input, this trick will always work. If there are multiple edges or both (i,j) and (j,i) are given in the input, you will have to make 4 edges: (i,j), rev(i,j), (j,i) and rev(j,i) because all of them could have different costs. But I used to solving problems with no multiple edges :)Now about that program you have shown me. In that program authors use adjacency list. So, the code```for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) if( cap[i][j] || cap[j][i] ) adj[i][deg[i]++] = j; ```creates 4 edges as I said (if both (i,j) and (j,i) are given). Authors don't use something like c_rev(i,j)=0 because they don't keep the reduced costs. They reduce costs "in process" with help of Pot(u,v) macro. The implementation you have shown me is better than mine, but it seems to me little more complex.As for my mistype with t instead of i - you are absolutely right! Thank you.
 Re: What is the meaning of potential? (response to post by Zealint) | Reply This problem makes me crazy :|First of all in Reduce_Cost (pi) there is not E but E_x (the set of reduced edges)Sorry, my (printer) mistake - on my printed version there wasn't _x. As I see, it is still whole set of edges (c and c_rev), but not only edges on the shortest path - according to "What is Ex?..." and Figure 4 (g) ((3, 2) is not part of the shortest path, but its cost is changed). Am I correct?I tried to change code according to my understanding of all yours explanations, but I am getting WA on http://icpcres.ecs.baylor.edu/onlinejudge/ 10594 - Data Flow after 0.76 sec (with before written code it AC after 0.8 sec).Please, can you provide code for Successive Shortest Path with potentials method that uses ReduceCost and really change costs (I suppose you have it written)? I think it also will help to others (as already posted codes help) to understand. I was talking with 3 my friends who are also doing TC and they also have trouble to code it and make to work.As for my mistype with t instead of i - you are absolutely right! Thank you.You are welcome. Thank you for all your patience to help me.
 Re: What is the meaning of potential? (response to post by boba5551) | Reply Don't worry about this problem, You will understand it, I believe in you! :)Don't blame your printer. It is my mistake, I wrote 'E_x', but this 'x' became invisible :( It is not whole set of edges; it is the set of edges with positive residual capacities. On figure 4(g) cost of edge (3,2) has been changed because it was 0, but pi[3]=6 and pi[2]=0. So, c(3,2)=0+6-0=6. This picture is correct.I have one realization of this method. But I have written it many years ago and this implementation is not very efficient. It uses adjacency matrix and doesnâ€™t allow using multiedges or undirected edges (as you need in 10594 Data Flow task). But this program is rather clear to understand. It really works because I have passed a lot of tasks using this code:```/** * ---------------------------------- * -- Min-Cost-Flow implementation -- * -- Successive Shortest Path -- * ---------------------------------- * * WARNINGS: * (1) No multiedges are allowed. * (2) Only one edge (i,j) or (j,i) could be * between nodes i and j. * (3) This program uses adjacency matrix * (could be slow). * */   #include   //--------------------------------------------------------------   #define N 256 // Number of nodes #define oo 1000000000 // Infinity   //--------------------------------------------------------------   using namespace std;   ifstream cin("file.in"); // Read from ofstream cout("file.out"); // Write to ofstream cerr("file.err"); // Write errors to   int n, m, source, sink; int G[N][N], // Graph matrix C[N][N], // Reduced costs matrix C_UsedToBe[N][N], // Given costs (not reduced) F[N][N]; // Flow matrix   // For Dijkstra's algorithm: int inq[N], // (Flag) Is node in the queue? d[N], // Distance label pi[N]; // Previous vertex at the shortest path   // It extracts the nearest node // from the Queue int extr_min() { int i, j(0); for(i=1; i<=n;i++) if(inq[i]>0&&d[i]0) { C[i][j]+=d[i]-d[j]; C[j][i]=0; } }   // It finds the shortest path // using Dijkstra's algorithm // and augments a flow along it. int augment() { int i, j;   for(i=0; i<=n; i++) { d[i]=oo; // Nodes are unreachable inq[i]=1; // All nodes are in the queue }   d[source]=0;   // While queue is not empty for( ; (i=extr_min())>0; ) { for(j=1; j<=n; j++) {   // If there is no residual edge (i,j) or // node j is not in the queue if(G[i][j] == 0 || inq[j] == 0) continue;   // If the distance label of j // bigger than the distance label // of i plus (residual) distance from i to j if(d[j]>d[i]+C[i][j]) { pi[j]=i; // Make i previous for j d[j]=d[i]+C[i][j]; // Relabel } } }   // Reduce costs reduce_cost();   // If there are no shortest (and any) // augmenting paths if(inq[sink]==1) return 0;   // Calculating the "bottleneck" of the path int width(oo); for(j=sink; j!=source; j=i) { i=pi[j]; if(width>G[i][j]) width=G[i][j]; }   // Make the augmentation for(j=sink; j!=source; j=i) { i=pi[j]; G[i][j]-=width; F[i][j]+=width; G[j][i]+=width; F[j][i]-=width; }   return width; }   int find_max_flow_min_cost() { int ans(0), i, j;   // While there is any shortest // augmenting path, augment flow // along it. while(augment());   // No calculate the total cost // of the maximum flow for(i=1; i<=n; i++) { for(j=1; j<=n; j++) if(F[i][j]>0) ans+=F[i][j]*C_UsedToBe[i][j]; }   return ans; }   int main() { int i, p, q, u, c;   // Read #Nodes, #Edges, Source node and Sink node. cin >> n >> m >> source >> sink; // Read edges for(i=1; i<=m; i++) { // "from" "to" "capacity" "cost" cin >> p >> q >> u >> c; // If there is a multiedge if(G[p][q]>0) { cerr << "Multiedge!" << endl; return 0; } G[p][q]=u; C[p][q]=C_UsedToBe[p][q]=c;   }   // Output the cost of the minimum-cost flow cout << find_max_flow_min_cost() << endl;   return 0; }   ```Input format is very simple:#Nodes #Edges Source Sinkfrom_1 to_1 capacity_1 cost_1from_2 to_2 capacity_2 cost_2... ... ... ...from_m to_m capacity_m cost_mI wish you good luck!
 Re: What is the meaning of potential? (response to post by Zealint) | Reply Thank you very much. I think I've got it completely now - thanks to code and your explanations. I will try to prove my understanding solving some tasks.
 Re: What is the meaning of potential? (response to post by boba5551) | Reply I too I'm trying to solve the 10594 problem in UVa.I still haven't figured out how negative costs came in to play in this problem... can someone give me some pointers.My current solution is using a implementation of Ford-Fulkerson with Dijkstra for path finding and using a cost of (time*min-flow-in-path). This is maybe too greedy, because sometimes choosing the shorter paths dont maximize the flow.
 Re: What is the meaning of potential? (response to post by felix_halim) | Reply Btw, here is nothing told about special meaning of these potentials. I've met the following fact: these potentials are the solution of a linear programming problem, dual to a usual min-cost-max-flow problem. (the article of Sokkalingam, Ahuja and Orlin "INVERSE SPANNING TREE PROBLEMS: FORMULATIONS AND ALGORITHMS"; they showed that inverse-MST problem can be expressed as a dual problem to an assignment problem).But in the article there is no proof of the fact (which is, I think, very interesting and useful). They refer to their book "Network Flows: Theory, Algorithms, and Applications", but I haven't found it in the Internet. And, what is very strange, I didn't see the fact in any other book...
 Re: What is the meaning of potential? (response to post by e-maxx) | Reply Here is my implementation:```#include #include #include #include #include #include #include #include #include   using namespace std;     bool bellman_ford(const std::vector >& graph, const std::vector >& enabled, int start, std::vector& distances) { int N = graph.size(); distances.assign(N, INT_MAX>>1); distances[start] = 0;   for(int s = 0; s < N-1; ++s) { for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) if (enabled[i][j]) distances[j] = std::min(distances[j], distances[i] + graph[i][j]); }   for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { if (enabled[i][j] && distances[j] > distances[i] + graph[i][j]) return false; } }   return true; }   std::pair, std::vector > dijkstra(const std::vector >& cost, const std::vector >& enabled, const std::vector& potentials, int start) { int N = cost.size();   std::vector distances(N, INT_MAX>>1); std::vector previous(N, -1);   std::priority_queue, std::vector >, std::greater > > q; q.push(std::make_pair(0, start) );   while(!q.empty()) { int v = q.top().second, d = q.top().first; q.pop(); distances[v] = d;   for (int i = 0; i < N; ++i) {   if (!enabled[v][i]) continue;   int new_d = d+potentials[v]-potentials[i] + cost[v][i]; if (distances[i] > new_d) { q.push(std::make_pair(new_d, i)); previous[i] = v; } } }     return std::make_pair(distances, previous); }   std::pair min_cost_max_flow(const std::vector >& capacities, const std::vector >& flow_cost, int source, int sink) { std::vector > residual(capacities); std::vector > cost(flow_cost);   int N = residual.size();   for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) if (capacities[i][j] > 0) cost[j][i] = -cost[i][j];   std::vector potentials; while(!bellman_ford(cost, residual, source, potentials)) { //fill up the negative cycles }     while(true) { std::pair, std::vector > dijkstra_result = dijkstra(cost, residual, potentials, source); const std::vector& distances = dijkstra_result.first; const std::vector& previous = dijkstra_result.second; potentials = distances;   if (previous[sink] == -1) break;   std::vector path; int v=sink; while(true) { if (v==-1) break;   path.push_back(v); v = previous[v]; }   std::reverse(path.begin(), path.end());   int flow = INT_MAX>>1; for(int i = 0; i < path.size()-1; ++i) flow = std::min(flow, residual[path[i]][path[i+1]]);   for(int i = 0; i < path.size()-1; ++i) { residual[path[i]][path[i+1]] -= flow; residual[path[i+1]][path[i]] += flow; } }   int flow = 0; for(int i = 0; i < N; ++i) flow += capacities[source][i] - residual[source][i];   int cost_flow = 0; for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { if (capacities[i][j]) cost_flow += (capacities[i][j] - residual[i][j])*cost[i][j]; } }   return std::make_pair(flow, cost_flow); }       int main(int argc, char* argv[]) { freopen("in.txt","r", stdin);   int n,m,source,sink; cin >> n >> m >> source >> sink;   vector > capacities(n, vector(n)); vector > costs(n, vector(n)); for(int i=0; i> from >> to >> capacity >> cost; capacities[from][to] = capacity; costs[from][to] = cost; } pair res = min_cost_max_flow(capacities, costs, source, sink);   cout << "flow = " << res.first << ", cost = " << res.second << "\n";   }   ```
 Re: What is the meaning of potential? (response to post by NotImplemented) | Reply I have go through the explanation of the trick:1. c(i,j) is on the shortest path - then c(i,j) = c(j,i) = 02. c(i,j) is not on the shortest path - then c(j,i) can be assigned to 0 because there will be no positive residual capacity along the arc c(j,i) and it flows from the fact that there are no negative cost cycles Am I correct? And what is the purpose of this trick?Why cannot we set c[j][i] = -c[i][j] at the beginning?
 Re: What is the meaning of potential? (response to post by NotImplemented) | Reply You're right, also I suggest you to read this post. But I also have some trouble with understanding potentials. There is an illustration from the Ahuja/Magnanti/Orlin book. At the figure d the potential of the node "3" changes to -3. Why is the cost of the edge 3-1 is still 2? Why is it not 2+(-3)-0? This edge is present in the residual network, and has non-zero residual capacity.Potentials are negative because in Ahuja's notation cpi(i, j) = c(i, j) + pi(j) - pi(i), so pi = -d.
 Re: What is the meaning of potential? (response to post by felix_halim) | Reply A good explanation of potentials is in wiki: Johnson's algorithm.