max_dag.cpp
Go to the documentation of this file.
00001 #include "max_dag.h"
00002 
00003 #include <cassert>
00004 #include <iostream>
00005 using namespace std;
00006 
00007 vector<int> MaxDAG::get_result() {
00008     if(debug){
00009         for(int i = 0; i < weighted_graph.size(); i++) {
00010             cout << "From " << i << ":";
00011             for(int j = 0; j < weighted_graph[i].size(); j++)
00012                 cout << " " << weighted_graph[i][j].first
00013                     << " [weight " << weighted_graph[i][j].second << "]";
00014             cout << endl;
00015         }
00016     }
00017     vector<int> incoming_weights; // indexed by the graph's nodes
00018     incoming_weights.resize(weighted_graph.size(), 0);
00019     for(int node = 0; node < weighted_graph.size(); node++) {
00020         const vector<pair<int, int> > &weighted_edges = weighted_graph[node];
00021         for(int i = 0; i < weighted_edges.size(); i++)
00022             incoming_weights[weighted_edges[i].first] += weighted_edges[i].second;
00023     }
00024 
00025     // Build minHeap of nodes, compared by number of incoming edges.
00026     typedef multimap<int, int>::iterator HeapPosition;
00027 
00028     vector<HeapPosition> heap_positions;
00029     multimap<int, int> heap;
00030     for(int node = 0; node < weighted_graph.size(); node++) {
00031         if(debug)
00032             cout << "node "<< node << " has "<< incoming_weights[node] << " edges" << endl;
00033         HeapPosition pos = heap.insert(make_pair(incoming_weights[node], node));
00034         heap_positions.push_back(pos);
00035     }
00036     vector<bool> done;
00037     done.resize(weighted_graph.size(), false);
00038 
00039     vector<int> result;
00040     // Recursively delete node with minimal weight of incoming edges.
00041     while(!heap.empty()) {
00042         if(debug) cout << "minimal element is " << heap.begin()->second << endl;
00043         int removed = heap.begin()->second;
00044         done[removed] = true;
00045         result.push_back(removed);
00046         heap.erase(heap.begin());
00047         const vector<pair<int, int> > &succs = weighted_graph[removed];
00048         for(int i = 0; i < succs.size(); i++) {
00049             int target = succs[i].first;
00050             if(!done[target]) {
00051                 int arc_weight = succs[i].second;
00052                 while(arc_weight >= 100000)
00053                     arc_weight -= 100000;
00054                 //cout << "Looking at arc from " << removed << " to " << target << endl;
00055                 int new_weight = heap_positions[target]->first - arc_weight;
00056                 heap.erase(heap_positions[target]);
00057                 heap_positions[target] = heap.insert(make_pair(new_weight, target));
00058                 if(debug)
00059                     cout << "node " << target << " has now " << new_weight << " edges " << endl;
00060             }
00061         }
00062     }
00063     if(debug){
00064         cout << "result: " << endl;
00065         for(int i = 0; i < result.size(); i++)
00066             cout << result[i] <<" - ";
00067         cout << endl;
00068     }
00069     return result;
00070 }
00071 
00072 /*
00073 #include <iostream>
00074 using namespace std;
00075 
00076 int main() {
00077 #if 0
00078 int n0[] = {1, -1};
00079 int n1[] = {-1};
00080 int n2[] = {3, 4, -1};
00081 int n3[] = {2, 4, -1};
00082 int n4[] = {0, 3, -1};
00083 int *all_nodes[] = {n0, n1, n2, n3, n4, 0};
00084 #endif
00085 
00086 int n0[] = {-1};
00087 int n1[] = {3, -1};
00088 int n2[] = {1, 4, 5, -1};
00089 int n3[] = {2, 8, -1};
00090 int n4[] = {0, 7, -1};
00091 int n5[] = {4, -1};
00092 int n6[] = {5, 8, -1};
00093 int n7[] = {2, 5, -1};
00094 int *all_nodes[] = {n0, n1, n2, n3, n4, n5, n6, n7, 0};
00095 
00096 vector<vector<pair<int, int> > > graph;
00097 for(int i = 0; all_nodes[i] != 0; i++) {
00098 vector<pair<int, int> > weighted_successors;
00099 for(int j = 0; all_nodes[i][j] != -1; j++)
00100 weighted_successors.push_back(make_pair(all_nodes[i][j],all_nodes[i][j]));
00101 graph.push_back(weighted_successors);
00102 }
00103 
00104 vector<int> m = MaxDAG(graph).get_result();
00105 for(int i = 0; i < m.size(); i++) 
00106 cout << m[i] << " - ";
00107 cout << endl;
00108 }
00109 */


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06