00001
00007 #include <pthread.h>
00008 #include <stdio.h>
00009 #include <vector>
00010 #include <queue>
00011 #include <map>
00012 #include <set>
00013 #include <algorithm>
00014 #include <utility>
00015 #include <sstream>
00016 #include <cmath>
00017 #include "Tree.hpp"
00018 #include "TreeGenerator.hpp"
00019 #include "DisjointSet.hpp"
00020 #include "SubsetDeltaGenerator.hpp"
00021 #include "Debug.hpp"
00022 #include <iostream>
00023 using namespace std;
00024
00025 #define MAX_NUM_THREADS 12
00026
00027 typedef map< vector<unsigned int>, vector<Tree> > TreeByDegSeqHash;
00028 typedef map< pair< vector<unsigned int>, vector<unsigned int> >, vector<Tree> > DegSeqPathNumHash;
00029 typedef map< vector<unsigned int>, int> kSlice;
00030 typedef vector< vector<SubsetDelta> > SubsetDeltaTable;
00031 typedef queue< vector<Tree> > TreeQueue;
00032
00033 DegSeqPathNumHash treeHash;
00034 TreeQueue treeQueue;
00035 SubsetDeltaTable subsetDeltaTable;
00036 unsigned int n;
00037 unsigned int numThreads;
00038 pthread_t myThreads[MAX_NUM_THREADS];
00039 pthread_mutex_t treeQueueMutex;
00040 pthread_mutex_t outputMutex;
00041
00042 void getTrees( unsigned int n );
00043 void *worker( void *arg );
00044 void testConjecture( unsigned int n );
00045
00046 int main( int argc, char **argv )
00047 {
00048 if( argc != 3 )
00049 {
00050 cout << "Usage: " << argv[0] << " <number of vertices> <number of cores to use>" << endl;
00051 cout << " Use the command nproc to find how many cores you have available." << endl;
00052 return 0;
00053 }
00054
00055 n = atoi( argv[1] );
00056 numThreads = atoi( argv[2] );
00057 if( numThreads > MAX_NUM_THREADS )
00058 {
00059 cout << "Only supporting 12 or less threads." << endl;
00060 return 0;
00061 }
00062
00063 testConjecture( n );
00064 pthread_exit( NULL );
00065 return 0;
00066 }
00067
00068 void getTrees( unsigned int n )
00069 {
00070 Tree t;
00071 TreeGenerator treeGen( n );
00072 vector<unsigned int> degSeq;
00073 vector<unsigned int> pathNums;
00074
00075 while( treeGen.nextTree( t ) )
00076 {
00077 t.getDegreeSequence( degSeq );
00078 t.getPathNums( pathNums );
00079 treeHash[ make_pair( degSeq, pathNums ) ].push_back( t );
00080 }
00081 }
00082
00083 void *worker( void *arg )
00084 {
00085 bool threadRunning = true;
00086 vector<Tree> treeList;
00087 while( threadRunning )
00088 {
00089 pthread_mutex_lock( &treeQueueMutex );
00090 if( !treeQueue.empty() )
00091 {
00092 treeList = treeQueue.front();
00093 treeQueue.pop();
00094 }
00095 else
00096 {
00097 threadRunning = false;
00098 }
00099 pthread_mutex_unlock( &treeQueueMutex );
00100
00101
00102 unsigned int k = 3;
00103 while( k < n and treeList.size() > 1 )
00104 {
00105 vector<kSlice> kSliceList;
00106
00107 int additive = ( k % 2 == 0 ) ? 1 : -1;
00108
00109 vector<SubsetDelta> deltas;
00110 deltas = subsetDeltaTable[k];
00111
00112 for( vector<Tree>::const_iterator it = treeList.begin();
00113 it != treeList.end();
00114 ++it )
00115 {
00116 vector<Edge> edgeSet = it->getEdges();
00117 kSlice currSlice;
00118
00119 DisjointSet components( n );
00120
00121 for( unsigned int i = 0; i < k; i++ )
00122 {
00123 components.setUnion( edgeSet[i].u, edgeSet[i].v );
00124 }
00125
00126 vector<unsigned int> lambdaOfS;
00127 components.getSetSizes( lambdaOfS );
00128 currSlice[lambdaOfS] += additive;
00129
00130 for( unsigned int i = 1; i < deltas.size(); i++ )
00131 {
00132 Edge removeEdge = edgeSet[deltas[i].oldValue];
00133 Edge addEdge = edgeSet[deltas[i].newValue];
00134
00135 components.split( removeEdge.u, removeEdge.v );
00136 components.setUnion( addEdge.u, addEdge.v );
00137
00138 components.getSetSizes( lambdaOfS );
00139 currSlice[lambdaOfS] += additive;
00140 }
00141
00142 kSliceList.push_back( currSlice );
00143 }
00144
00145 set<unsigned int> treesToKeep;
00146 for( unsigned int i = 0; i < kSliceList.size(); i++ )
00147 {
00148 for( unsigned int j = i + 1; j < kSliceList.size(); j++ )
00149 {
00150 kSlice slice1 = kSliceList[i];
00151 kSlice slice2 = kSliceList[j];
00152 bool equal = true;
00153 kSlice::iterator it1 = slice1.begin();
00154 kSlice::iterator it2 = slice2.begin();
00155 while( it1 != slice1.end() && it2 != slice2.end() )
00156 {
00157 if( it1->first != it2->first ||
00158 it1->second != it2->second )
00159 {
00160 equal = false;
00161 break;
00162 }
00163 ++it1;
00164 ++it2;
00165 }
00166 if( equal )
00167 {
00168 treesToKeep.insert( i );
00169 treesToKeep.insert( j );
00170 }
00171 }
00172 }
00173
00174 vector<Tree> treesKept;
00175 for( set<unsigned int>::iterator it = treesToKeep.begin();
00176 it != treesToKeep.end();
00177 ++it )
00178 {
00179 treesKept.push_back( treeList[*it] );
00180 }
00181 treeList = treesKept;
00182
00183 k++;
00184 }
00185
00186 if( treeList.size() > 1 )
00187 {
00188 pthread_mutex_lock( &outputMutex );
00189 cout << "COUNTEREXAMPLE FOUND!" << endl;
00190 for( unsigned int i = 0; i < treeList.size(); i++ )
00191 {
00192 treeList[i].print();
00193 }
00194 pthread_mutex_unlock( &outputMutex );
00195 }
00196 }
00197
00198 pthread_exit( NULL );
00199 }
00200
00201 void testConjecture( unsigned int n )
00202 {
00203 getTrees( n );
00204
00205
00206 SubsetDeltaGenerator subsetGen( n - 1 );
00207 vector<SubsetDelta> temp;
00208 for( unsigned int i = 0; i < 3; i++ )
00209 {
00210 subsetDeltaTable.push_back( temp );
00211 }
00212 for( unsigned int i = 3; i < n; i++ )
00213 {
00214 subsetGen.getDeltasForSubsetsOfFixedLength( i, temp );
00215 subsetDeltaTable.push_back( temp );
00216 }
00217
00218
00219
00220 for( DegSeqPathNumHash::const_iterator it = treeHash.begin();
00221 it != treeHash.end();
00222 ++it )
00223 {
00224 if( it->second.size() > 1 )
00225 {
00226 treeQueue.push( it->second );
00227 }
00228 }
00229 treeHash.clear();
00230
00231
00232 pthread_attr_t threadAttributes;
00233 pthread_mutex_init( &treeQueueMutex, NULL );
00234 pthread_mutex_init( &outputMutex, NULL );
00235 pthread_attr_init( &threadAttributes );
00236 pthread_attr_setdetachstate( &threadAttributes, PTHREAD_CREATE_JOINABLE );
00237
00238
00239 for( unsigned long i = 0; i < numThreads; i++ )
00240 {
00241 pthread_create( &myThreads[i], &threadAttributes, worker, (void *)i );
00242 }
00243
00244 pthread_attr_destroy( &threadAttributes );
00245
00246 void *status;
00247
00248 for( unsigned int i = 0; i < numThreads; i++ )
00249 {
00250 pthread_join( myThreads[i], &status );
00251 }
00252
00253 pthread_mutex_destroy( &treeQueueMutex );
00254 pthread_exit( NULL );
00255 }