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;
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
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
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
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
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109