MOCHA 0.9
|
00001 // Copyright 2009 by Jesus De Loera, David Haws, Jon Lee, Allison O'Hair, University 00002 // of California at Davis, IBM, Inc. All rights reserved. 00003 // 00004 // Distributed under the Eclipse Public License v 1.0. See ../LICENSE 00005 00006 // $Rev$ $Date$ 00007 00008 00010 #ifndef MATROID_H 00011 #define MATROID_H 00012 00013 #include <iostream> 00014 #include <fstream> 00015 #include <cstdlib> 00016 #include <set> 00017 #include <list> 00018 #include <cmath> 00019 #include "graph.h" 00020 #include "matrix.h" 00021 00022 using namespace::std; 00023 00024 #define VECTOR_MATROID 1 00025 #define GRAPH_MATROID 2 00026 #define ABSTRACT_MATROID 3 00027 #define POINTSET_MATROID 4 00028 #define UNIFORM_MATROID 4 00029 00030 //needed for bases estimation 00031 const int MAXDIM = 300; 00032 //RAND_MAX declared in cstdlib as max value returned by rand function 00033 const int MAXIMAL_RAND = RAND_MAX; 00034 // I didn't know what to put here 00035 //const int MAXIMAL_RAND = 100000; 00036 const double SOLVER_ACCURACY = 0.000001; 00037 const double PI = 3.14159254; 00038 00039 class Matroid { 00040 public: 00041 Matroid (); 00042 Matroid (std::istream &); 00043 virtual ~Matroid (); 00044 friend std::ostream& operator<< (std::ostream& o, Matroid &someMatroid); 00045 friend std::istream& operator>> (std::istream& in, Matroid &someMatroid); 00046 virtual int rank () {return -1;}; 00047 virtual int calcBases () {return -1;}; //Returns number of bases 00048 virtual int isBasis (set <unsigned> S) {return -1;}; //Returns 1 if it is a basis, 0 else 00049 virtual int setRank (set <unsigned> S) {return -1;}; //Returns the rank of the set 00050 virtual set <unsigned> randomBasis () = 0; //Returns a random basis 00051 int getNumElements() {return numElements;}; 00052 // This will initialize all data for enumerating 00053 // Neighbors of initBasis. This is so specialized 00054 // techniques can be used for graphical matroids for example 00055 virtual void initializePivot(set <unsigned> initBasis) = 0; 00056 // This will set &pivot to the next pivot from initBasis 00057 // Returns 1 if &pivot is set, i.e. there is a next pivot 00058 // Returns 0 else. Only returns basis 00059 virtual int nextPivot(set <unsigned> &pivot) = 0; 00060 int matroidType (); 00061 00062 // Given a column vector Weight, this returns the max basis under the weighting. 00063 set <unsigned> GreedyAlgorithmMax(Matrix Weight); 00064 00065 //functions used in EstimateBases 00066 float random_weight_logistic(float x); 00067 float H_fn_logistic(float t); 00068 float upper_logistic(float avg_GAMMA, int k); 00069 float lower_logistic(float avg_GAMMA, int k); 00070 int modified_rand(); 00071 00072 //Will estimate the number of bases of a matrix using Barvinok 00073 //void EstimateBases(); 00074 00075 // This will calculate all bases and project by the matrix Weight 00076 virtual set <Matrix, ltcolvec> calcAllBasesProj(Matrix &Weight); 00077 protected: 00078 virtual void printMatroid (std::ostream &o) { o << "Matroid called\n";}; 00079 virtual void getMatroid (std::istream &in) { }; 00080 int numElements; 00081 int matroidRank; 00082 int thisMatroidType; 00083 list < set <unsigned> > Bases; 00084 list < set <unsigned> > Independents; 00085 list < set <unsigned> > Circuits; 00086 list < set <unsigned> > Cocircuits; 00087 }; 00088 00089 class VectorMatroid : public Matroid { 00090 public: 00091 VectorMatroid(); 00092 VectorMatroid(std::istream &in); 00093 VectorMatroid(Matrix M); 00094 ~VectorMatroid(); 00095 00096 int rank (); 00097 int calcBases (); 00098 int isBasis (set <unsigned> S); //Returns 1 if it is a basis, 0 else 00099 int setRank (set <unsigned> S); //Returns the rank of the set 00100 set <unsigned> randomBasis (); //Returns a random basis 00101 00102 // This will initialize all data for enumerating 00103 // Neighbors of initBasis. This is so specialized 00104 // techniques can be used for graphical matroids for example 00105 // This uses no specialized technique. Simply checks all (i,j) and 00106 // see if initbasis - i + j is a basis 00107 void initializePivotGeneric(set <unsigned> initBasis); 00108 // This will set &pivot to the next pivot from initBasis 00109 // Returns 1 if &pivot is set, i.e. there is a next pivot 00110 // Returns 0 else. Only returns basis 00111 int nextPivotGeneric(set <unsigned> &pivot); 00112 00113 // This uses a specialized technique for vector matroids 00114 // If B is the matrix given by initBasis and A_j is 00115 // some column of matrixRep, then if we solve 00116 // Bx=A_j, for any x_i that are non-zero (considering some error) 00117 // A_i can be swaped for A_j. 00118 // This calls LAPACK dgesv_ function to solve Bx=A_j 00119 void initializePivotLAPACK(set <unsigned> initBasis); 00120 int nextPivotLAPACK(set <unsigned> &pivot); 00121 00122 void initializePivot(set <unsigned> initBasis); 00123 int nextPivot(set <unsigned> &pivot); 00124 00125 protected: 00126 void printMatroid (std::ostream &o); 00127 void getMatroid(std::istream &in); 00128 00129 set <unsigned> pivotBasis; 00130 set <unsigned> currentBasis; 00131 set <unsigned> remSet, addSet; // These hold all elements to try and remove and add 00132 set <unsigned>::iterator remEl, addEl,si; 00133 set <unsigned> currentCycle; 00134 Matrix currentInitBasis; 00135 unsigned remSetCount; 00136 unsigned addSetCount; 00137 00138 Matrix matrixRep; 00139 }; 00140 00141 class GraphicalMatroid : public Matroid { 00142 public: 00143 GraphicalMatroid(); 00144 GraphicalMatroid(std::istream &in); 00145 GraphicalMatroid(Graph G); 00146 ~GraphicalMatroid(); 00147 00148 int rank (); 00149 //int calcBases (); 00150 00151 // someElements is indexed by the total elements, not by internal graph index 00152 int isBasis (set <unsigned> S); //Returns 1 if it is a basis, 0 else 00153 int setRank (set <unsigned> S); //Returns the rank of the set 00154 00155 //int setRank (set <unsigned> S); //Returns the rank of the set 00156 set <unsigned> randomBasis (); //Returns a random basis 00157 00158 // This will initialize all data for enumerating 00159 // Neighbors of initBasis. This is so specialized 00160 // techniques can be used for graphical matroids for example 00161 void initializePivot(set <unsigned> initBasis); 00162 // This will set &pivot to the next pivot from initBasis 00163 // Returns 1 if &pivot is set, i.e. there is a next pivot 00164 // Returns 0 else. Only returns basis 00165 int nextPivot(set <unsigned> &pivot); 00166 00167 // This functions returns data with respect to the pivot basis 00168 // This return the cycle formed by adding the edge (n1,n2) 00169 // Since pivot basis is a spanning forest, there will always 00170 // be a cycle if (n1,n2) is NOT in pivotBasis. 00171 set <unsigned> getCycle (unsigned n1, unsigned n2); 00172 00173 set <Matrix, ltcolvec> calcAllBasesProj(Matrix &Weight); 00174 00175 protected: 00176 void printMatroid (std::ostream &o); 00177 void getMatroid(std::istream &in); 00178 00179 set <unsigned> pivotBasis; 00180 set <unsigned> currentBasis; 00181 set <unsigned> addSet; // These hold all elements to try and remove and add 00182 set <unsigned>::iterator remEl, addEl,si; 00183 set <unsigned> currentCycle; 00184 unsigned remSetCount; 00185 unsigned addSetCount; 00186 00187 Graph graphRep; 00188 // This holds the predecessor matrix for initialize pivot 00189 // If want path from node i to j, take path i to predMatrix(i,j) to j 00190 Matrix predMatrix; 00191 }; 00192 00193 class PointSetMatroid : public Matroid { 00194 public: 00195 00196 protected: 00197 }; 00198 00199 class AbstractMatroid : public Matroid { 00200 public: 00201 protected: 00202 }; 00203 00204 class UniformMatroid : public Matroid { 00205 public: 00206 UniformMatroid (); 00207 UniformMatroid (int rank, int elements); 00208 int rank () {return matroidRank;}; 00209 //int calcBases (); //Returns number of bases 00210 int isBasis (set <unsigned> S); //Returns 1 if it is a basis, 0 else 00211 int setRank (set <unsigned> S); //Returns the rank of the set 00212 set <unsigned> randomBasis () ; //Returns a random basis 00213 00214 // This will initialize all data for enumerating 00215 // Neighbors of initBasis. This is so specialized 00216 // techniques can be used for graphical matroids for example 00217 void initializePivot(set <unsigned> initBasis); 00218 // This will set &pivot to the next pivot from initBasis 00219 // Returns 1 if &pivot is set, i.e. there is a next pivot 00220 // Returns 0 else. Only returns basis 00221 int nextPivot(set <unsigned> &pivot); 00222 00223 protected: 00224 void printMatroid (std::ostream &o) ; 00225 void getMatroid (std::istream &in) ; 00226 00227 set <unsigned> pivotBasis; 00228 set <unsigned> currentBasis; 00229 set <unsigned> remSet, addSet; // These hold all elements to try and remove and add 00230 set <unsigned>::iterator remEl, addEl,si; 00231 unsigned remSetCount; 00232 unsigned addSetCount; 00233 }; 00234 00235 #endif