00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00028 #include <coconut_config.h>
00029 #include <model.h>
00030 #include <vector>
00031 #include <algorithm>
00032 #include <g_algo.h>
00033 #include <api_exception.h>
00034
00035 namespace coco {
00036
00038
00041 class graphorder_visitor : public postorder_visitor<expression_node, unsigned int, unsigned int>
00042 {
00043 private:
00046 std::vector<unsigned int>* phi;
00049 std::vector<bool>* phi_defined;
00051 unsigned int k;
00052
00053 public:
00055 graphorder_visitor(std::vector<unsigned int>& __v,
00056 std::vector<bool>& __b,
00057 unsigned int __k = 0) : phi(&__v), phi_defined(&__b),
00058 k(__k)
00059 { }
00060
00062 graphorder_visitor(const graphorder_visitor& __c) : phi(__c.phi),
00063 phi_defined(__c.phi_defined), k(__c.k)
00064 { }
00065
00067
00068 unsigned int vvalue() { return k; }
00069 unsigned int value() { return k; }
00070
00071 bool postorder(const expression_node &r)
00072 {
00073 if(!(*phi_defined)[r.node_num])
00074 {
00075 (*phi_defined)[r.node_num] = true;
00076 (*phi)[r.node_num] = k;
00077 k++;
00078 }
00079 return false;
00080 }
00081
00082 void collect(const expression_node &r, unsigned int __v)
00083 {
00084 if(__v > k) k = __v;
00085 }
00086
00087 void vcollect(unsigned int __v)
00088 {
00089 if(__v > k) k = __v;
00090 }
00092 };
00093
00094 void graphorder(const model& DAG, std::vector<unsigned int>& order)
00095 {
00096 unsigned int n_nodes(DAG.number_of_nodes());
00097 std::vector<unsigned int> phi(n_nodes, 0);
00098 std::vector<bool> phi_defined(n_nodes, false);
00099
00100 graphorder_visitor gov(phi, phi_defined, 0);
00101
00102 unsigned int ndef_nodes = recursive_postorder_walk(DAG.ground(), gov);
00103
00104 order.clear();
00105 order.insert(order.end(), ndef_nodes, 0);
00106
00107 for(unsigned int i = 0; i < n_nodes; ++i)
00108 if(phi_defined[i]) order[phi[i]] = i;
00109 }
00110
00111 }