MOCHA  0.9
/usr/src/RPM/BUILD/CoinMOCHA-1.0.0/MOCHA/src/matroid.h
Go to the documentation of this file.
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
 All Classes Files Functions Variables Friends Defines