00001 /*************************************************************************** 00002 * Copyright (C) 2007 by Sid Touati * 00003 * Sid-nospamDOTTouati-nospam@inria.fr * 00004 * Copyright INRIA and University of Versailles (France) * 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 General Public License * 00016 * along with this program; if not, write to the * 00017 * Free Software Foundation, Inc., * 00018 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * 00018 * Exception : this software requires a licence of the LEDA libary. * 00018 * You can buy a LEDA licence from algorithmic-solutions * 00018 * http://www.algorithmic-solutions.com * 00018 * LEDA source codes are excluded from this GPL. * 00018 * Obtaining a LEDA licence is not mandatory to use our GPL software * 00018 * If the user wants, he can create a free source-compatible replacement* 00018 * for LEDA, and he is allowed to use our software under GPL. * 00019 ***************************************************************************/ 00020 #ifndef __dilworthdecomposition_H 00021 #define __dilworthdecomposition_H 00022 00027 #include "LEDA/graph/graph.h" 00028 #include "LEDA/core/set.h" 00029 #include "LEDA/graph/graph_misc.h" /* Is_Acyclic */ 00030 #include "LEDA/graph/node_list.h" 00031 #include "LEDA/graph/basic_graph_alg.h" /* transitive closure */ 00032 #include "LEDA/graph/mcb_matching.h" /* bipartie matching algorithm */ 00033 #include "LEDA/core/d_array.h" // d_array 00034 00035 00036 using namespace LEDA; 00037 using namespace std; 00038 00039 /* set->list conversion */ 00040 template<class T> list<T> set_to_list(const set<T> l); 00041 /* list->set conversion */ 00042 template<class T> set<T> list_to_set(const list<T> l); 00043 00044 00045 00046 00047 00048 00049 00050 int MAXIMAL_ANTI_CHAIN(const graph &G, set<node>& MA); 00051 00052 00053 00054 int MINIMAL_CHAIN(const graph &G, node_array<int>& chain); 00055 00056 00057 #endif 00058