Mercurial > defical

annotate defical-c/src/main.cpp @ 0:ebed2bd0d300

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import from svn. History be damned.
author Edho P. Arief <me@myconan.net>
date Fri, 02 Apr 2010 23:11:57 +0700
parents
children 758381a85d76
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
1 #include "main.h"
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
2
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
3 const uint32_t INTMAX=100000;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
4 const char separator[40]= "=======================================";
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
5
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
6 int main(int argc, const char *argv[])
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
7 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
8 uint32_t numVer,numDef,graphType,isAllI;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
9 int32_t start,end;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
10 string graphTypeS,algorithm;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
11 bool isAll;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
12 //defaults
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
13 numVer=numDef=isAllI=INTMAX;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
14 isAllI=1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
15 isAll=false;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
16 graphTypeS="x";
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
17 algorithm="x";
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
18 //end defaults
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
19 dsr::Argument_helper ah;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
20 ah.set_author("Edho Prima Arief <me@myconan.net>");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
21 ah.set_description("Calculates deficiency for various graphs.");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
22 ah.set_build_date("2009");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
23 ah.set_name("defical");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
24 ah.set_version("0.1");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
25 ah.new_named_unsigned_int('n',"numver","","Number of vertices.",numVer);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
26 ah.new_named_unsigned_int('d',"numdef","","Number of deficiencies.",numDef);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
27 ah.new_named_string('g',"graph","","Type of graph.",graphTypeS);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
28 ah.new_named_string('a',"algorithm","","Choice of algorithm.",algorithm);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
29 ah.new_named_unsigned_int('c',"complete","","Don't stop on found.",isAllI);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
30 ah.process(argc,argv);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
31 if(isAllI==1)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
32 isAll=true;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
33 if(graphTypeS=="wheel")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
34 graphType=3;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
35 else if(graphTypeS=="fan")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
36 graphType=4;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
37 else if(graphTypeS=="doublefan")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
38 graphType=5;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
39 else
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
40 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
41 printf("Invalid graph type. Accepted: wheel, fan, doublefan.\n");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
42 return 1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
43 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
44 if(numVer<5 || numVer>=INTMAX)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
45 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
46 printf("Number of vertices must be more than 5 (or less than %d).\n",INTMAX);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
47 return 1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
48 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
49 if(numDef>=INTMAX)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
50 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
51 printf("Ha ha ha funny. Just give up (number of deficiencies must be less than %d.\n",INTMAX);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
52 return 1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
53 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
54 if(algorithm!="backtrack")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
55 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
56 printf("Invalid algorithm specified.\n");
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
57 return 1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
58 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
59 printf(separator);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
60 printf("\nNumber of vertices: %d\n",numVer);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
61 printf("Number of deficiencies: %d\n",numDef);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
62 cout << "Graph type: " << graphTypeS << endl;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
63 cout << "Algorithm: " << algorithm << endl;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
64 cout << separator << endl;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
65 gettime *mytime=new gettime();
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
66 cout << "[I] " << mytime->time_v << ": Started" << endl;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
67 cout << separator << endl;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
68 if(algorithm=="backtrack")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
69 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
70 start=1;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
71 end=(numVer+numDef+1)/2;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
72 bool isFinished=false;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
73 #ifdef _OPENMP
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
74 #pragma omp parallel for num_threads(3)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
75 #endif
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
76 for(int32_t i=start;i<=end;i++){
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
77 if(!isFinished){
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
78 bt::backtrack *bt1=new bt::backtrack(graphType,numVer,numDef,i,isAll);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
79 bt1->Walk();
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
80 if(!isFinished)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
81 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
82 if(bt1->IsSemt)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
83 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
84 if(!isAll)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
85 isFinished=true;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
86 gettime *mytime=new gettime();
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
87 printf("[F] %s: Found\n%s\n%s%s\n",mytime->time_v,separator,bt1->Result.c_str(),separator);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
88 bt1->IsSemt=false;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
89 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
90 else {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
91 if(!isFinished)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
92 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
93 gettime *mytime=new gettime();
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
94 printf("[N] %s: Unable to construct with first label %d\n",mytime->time_v,i);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
95 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
96 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
97 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
98 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
99 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
100 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
101 return 0;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
102 }