RS.h

00001 /***************************************************************************
00002  *   Copyright (C) 2009 by Touati Sid                                      *
00003  *   Sid-nospam.Touati-nospam@univ-cotedazur.fr                                      *
00004  *   Copyright  INRIA and the University of Versailles                     *
00005  *   This program is free software; you can redistribute it and/or modify  *
00006  *   it under the terms of the GNU General Public License as published by  *
00007  *   the Free Software Foundation; either version 2 of the License, or     *
00008  *   (at your option) any later version.                                   *
00009  *                                                                         *
00010  *   This program is distributed in the hope that it will be useful,       *
00011  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00012  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
00013  *   GNU General Public License for more details.                          *
00014  *                                                                         *
00015  *   You should have received a copy of the GNU Library General Public     *
00016  *   License along with this program (LGPL); if not, write to the          *
00017  *   Free Software Foundation, Inc.,                                       *
00018  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
00019  *   Exception : this software requires a licence  of the LEDA libary.     *
00020  *   If you are from academia, you can get a free leda binary licence 
00021  *   allowing you to use freely our DDG library.                           *
00022  *   Otherwise, you can buy a LEDA licence from algorithmic-solutions      *
00023  *   http://www.algorithmic-solutions.com                                  *
00024  *   LEDA binaries and source codes are excluded from this LGPL.           *
00025  *   Obtaining a LEDA licence is not mandatory to use our GPL software     *
00026  *   If the user wants, he can  create a free source-compatible replacement*
00027  *   for LEDA, and he is allowed to use our software under LGPL.           *
00028  ***************************************************************************/
00029 
00030 #ifndef __RS_H
00031 #define __RS_H
00032 
00038 namespace DDG{
00039 class EN;
00040 }
00041 
00042 namespace leda {
00048 int compare(const DDG::EN& u1, const DDG::EN& u2);
00049 }
00050 
00051 
00052 #include "DDG.h"
00053 #include <list>
00054 using namespace std;
00055 using namespace leda;
00056 namespace DDG{  
00061 class CBC{
00062     public:
00063         set<node> S, T;
00064         set<edge> E_CB;
00065         CBC(): S(), T(), E_CB(){}
00066         void clear(){T.clear();S.clear(); E_CB.clear();}
00067         friend ostream& operator<<(ostream &os, const CBC & x){}
00068         friend istream& operator>>(istream &is, CBC& x) {}
00069 };
00070 
00075 class EN{ 
00076     public:
00077         node t;
00078         rational rho;
00079         friend istream& operator>>(istream &is, EN& x){
00080             is>>x.t>>x.rho;
00081         }
00082         friend ostream& operator<<(ostream &os, const EN & x){
00083             os<<"("<<x.t<<" , "<<x.rho<<")";
00084         }
00085 };
00086 
00093 LEDA::list<CBC> decompose_into_cbc(const DAG &PKG);
00094 
00102 std::list<CBC> override_decompose_into_cbc(const DAG &G);
00103 
00117 void SKS_greedy(const DAG &G, const DAG & PKG, const node_map<node> original_node, const node_map<node> pk_node, const CBC cb,  node_array<node> &k);
00118 
00119 
00131 void SKS_greedy(const DAG &G, int t, const DAG & PKG, const node_map<node> original_node, const node_map<node> pk_node, const CBC cb,  node_array<node> &k);
00132 
00133 
00146 rational rho(const DAG &G, const set<node> X, const set<node> Y, const node t, const set<node>  GammaMinus_t);
00147 
00148 
00149 
00161 rational rho(const DAG &G, int regtype, const set<node> X, const set<node> Y, const node t, const set<node>  GammaMinus);
00162 
00177 void compute_children_cost(const set<node> X, const set<node> Y, leda::list<EN> &T,  const DAG &G, const DAG &PKG, const node_map<node> original_node, const node_map<node> pk_node);
00178 
00192 void compute_children_cost(int regtype, const set<node> X, const set<node> Y, leda::list<EN> &T,  const DAG &G, const DAG &PKG, const node_map<node> original_node, const node_map<node> pk_node);
00193 
00205 void get_PKG(const DAG &G, DAG &PKG, node_map<node> &original_node, node_map<node> &pk_node);
00206 
00217 void get_PKG(const DAG &G, int t, DAG &PKG, node_map<node> &original_node, node_map<node> &pk_node);
00218 
00231 void get_DVG(const DAG &G, const node_array<node> kill, DAG &DVG, node_map<node> &original_node, node_map<node> &dvg_node);
00232 
00243 void get_DVG(const DAG &G, int t, const node_array<node> k, DAG &DVG, node_map<node> &original_node, node_map<node> &dvg_node);
00244 }
00245 
00246 #endif