Mercurial > defical
changeset 0:ebed2bd0d300
Initial import from svn. History be damned.
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/LICENSE Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,13 @@ +Copyright (c) 2009, Edho Prima Arief <me@myconan.net> + +Permission to use, copy, modify, and/or distribute this software for any +purpose with or without fee is hereby granted, provided that the above +copyright notice and this permission notice appear in all copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/Makefile Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,18 @@ +default_target: all + +all: + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -c src/basic/Argument_helper.cpp -o src/basic/Argument_helper.o + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -c src/basic/inefficient.cpp -o src/basic/inefficient.o + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -c src/graphmagic.cpp -o src/graphmagic.o + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -c src/backtrack.cpp -o src/backtrack.o + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -c src/main.cpp -o src/main.o + g++ -fopenmp -Wall -fno-strict-aliasing -O3 -o defical src/basic/Argument_helper.o src/basic/inefficient.o src/graphmagic.o src/backtrack.o src/main.o + +win-all: + +clean: + rm defical src/*.o src/basic/*.o + +win-clean: + del defical.exe + del src\*.o src\basic\*.o
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/build/defical-vc2008/defical.sln Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,20 @@ + +Microsoft Visual Studio Solution File, Format Version 10.00 +# Visual C++ Express 2008 +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "defical", "defical.vcproj", "{83BFDD09-F368-4B7E-AD4B-42AD07C05711}" +EndProject +Global + GlobalSection(SolutionConfigurationPlatforms) = preSolution + Debug|Win32 = Debug|Win32 + Release|Win32 = Release|Win32 + EndGlobalSection + GlobalSection(ProjectConfigurationPlatforms) = postSolution + {83BFDD09-F368-4B7E-AD4B-42AD07C05711}.Debug|Win32.ActiveCfg = Debug|Win32 + {83BFDD09-F368-4B7E-AD4B-42AD07C05711}.Debug|Win32.Build.0 = Debug|Win32 + {83BFDD09-F368-4B7E-AD4B-42AD07C05711}.Release|Win32.ActiveCfg = Release|Win32 + {83BFDD09-F368-4B7E-AD4B-42AD07C05711}.Release|Win32.Build.0 = Release|Win32 + EndGlobalSection + GlobalSection(SolutionProperties) = preSolution + HideSolutionNode = FALSE + EndGlobalSection +EndGlobal
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/build/defical-vc2008/defical.vcproj Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,280 @@ +<?xml version="1.0" encoding="Windows-1252"?> +<VisualStudioProject + ProjectType="Visual C++" + Version="9,00" + Name="defical" + ProjectGUID="{83BFDD09-F368-4B7E-AD4B-42AD07C05711}" + RootNamespace="deficalcpp" + TargetFrameworkVersion="196613" + > + <Platforms> + <Platform + Name="Win32" + /> + </Platforms> + <ToolFiles> + </ToolFiles> + <Configurations> + <Configuration + Name="Debug|Win32" + OutputDirectory="$(SolutionDir)$(ConfigurationName)" + IntermediateDirectory="$(ConfigurationName)" + ConfigurationType="1" + CharacterSet="2" + > + <Tool + Name="VCPreBuildEventTool" + /> + <Tool + Name="VCCustomBuildTool" + /> + <Tool + Name="VCXMLDataGeneratorTool" + /> + <Tool + Name="VCWebServiceProxyGeneratorTool" + /> + <Tool + Name="VCMIDLTool" + /> + <Tool + Name="VCCLCompilerTool" + Optimization="0" + MinimalRebuild="true" + BasicRuntimeChecks="3" + RuntimeLibrary="3" + OpenMP="false" + WarningLevel="3" + DebugInformationFormat="4" + /> + <Tool + Name="VCManagedResourceCompilerTool" + /> + <Tool + Name="VCResourceCompilerTool" + /> + <Tool + Name="VCPreLinkEventTool" + /> + <Tool + Name="VCLinkerTool" + GenerateDebugInformation="true" + TargetMachine="1" + /> + <Tool + Name="VCALinkTool" + /> + <Tool + Name="VCManifestTool" + /> + <Tool + Name="VCXDCMakeTool" + /> + <Tool + Name="VCBscMakeTool" + /> + <Tool + Name="VCFxCopTool" + /> + <Tool + Name="VCAppVerifierTool" + /> + <Tool + Name="VCPostBuildEventTool" + /> + </Configuration> + <Configuration + Name="Release|Win32" + OutputDirectory="$(SolutionDir)$(ConfigurationName)" + IntermediateDirectory="$(ConfigurationName)" + ConfigurationType="1" + CharacterSet="1" + WholeProgramOptimization="3" + > + <Tool + Name="VCPreBuildEventTool" + /> + <Tool + Name="VCCustomBuildTool" + /> + <Tool + Name="VCXMLDataGeneratorTool" + /> + <Tool + Name="VCWebServiceProxyGeneratorTool" + /> + <Tool + Name="VCMIDLTool" + /> + <Tool + Name="VCCLCompilerTool" + Optimization="2" + EnableIntrinsicFunctions="true" + FavorSizeOrSpeed="1" + RuntimeLibrary="0" + EnableFunctionLevelLinking="true" + OpenMP="false" + ObjectFile="$(IntDir)\" + WarningLevel="3" + DebugInformationFormat="3" + /> + <Tool + Name="VCManagedResourceCompilerTool" + /> + <Tool + Name="VCResourceCompilerTool" + /> + <Tool + Name="VCPreLinkEventTool" + /> + <Tool + Name="VCLinkerTool" + LinkLibraryDependencies="true" + ManifestFile="$(IntDir)\$(TargetFileName).manifest" + GenerateDebugInformation="false" + OptimizeReferences="2" + EnableCOMDATFolding="2" + OptimizeForWindows98="0" + LinkTimeCodeGeneration="1" + TargetMachine="1" + /> + <Tool + Name="VCALinkTool" + /> + <Tool + Name="VCManifestTool" + /> + <Tool + Name="VCXDCMakeTool" + /> + <Tool + Name="VCBscMakeTool" + /> + <Tool + Name="VCFxCopTool" + /> + <Tool + Name="VCAppVerifierTool" + /> + <Tool + Name="VCPostBuildEventTool" + /> + </Configuration> + </Configurations> + <References> + </References> + <Files> + <Filter + Name="Header Files" + Filter="h;hpp;hxx;hm;inl;inc;xsd" + UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}" + > + <File + RelativePath="..\..\src\basic\Argument_helper.h" + > + </File> + <File + RelativePath="..\..\src\backtrack.h" + > + </File> + <File + RelativePath="..\..\src\graphmagic.h" + > + </File> + <File + RelativePath="..\..\src\includes.h" + > + </File> + <File + RelativePath="..\..\src\basic\inefficient.h" + > + </File> + <File + RelativePath="..\..\src\main.h" + > + </File> + <File + RelativePath="..\..\src\msvc\stdint.h" + > + </File> + </Filter> + <Filter + Name="Resource Files" + Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav" + UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}" + > + </Filter> + <Filter + Name="Source Files" + Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx" + UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}" + > + <File + RelativePath="..\..\src\basic\Argument_helper.cpp" + > + <FileConfiguration + Name="Release|Win32" + > + <Tool + Name="VCCLCompilerTool" + DefaultCharIsUnsigned="true" + CompileAsManaged="0" + /> + </FileConfiguration> + </File> + <File + RelativePath="..\..\src\backtrack.cpp" + > + <FileConfiguration + Name="Release|Win32" + > + <Tool + Name="VCCLCompilerTool" + DefaultCharIsUnsigned="true" + CompileAsManaged="0" + /> + </FileConfiguration> + </File> + <File + RelativePath="..\..\src\graphmagic.cpp" + > + <FileConfiguration + Name="Release|Win32" + > + <Tool + Name="VCCLCompilerTool" + DefaultCharIsUnsigned="true" + CompileAsManaged="0" + /> + </FileConfiguration> + </File> + <File + RelativePath="..\..\src\basic\inefficient.cpp" + > + <FileConfiguration + Name="Release|Win32" + > + <Tool + Name="VCCLCompilerTool" + DefaultCharIsUnsigned="true" + CompileAsManaged="0" + /> + </FileConfiguration> + </File> + <File + RelativePath="..\..\src\main.cpp" + > + <FileConfiguration + Name="Release|Win32" + > + <Tool + Name="VCCLCompilerTool" + Detect64BitPortabilityProblems="false" + /> + </FileConfiguration> + </File> + </Filter> + </Files> + <Globals> + </Globals> +</VisualStudioProject>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/backtrack.cpp Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,121 @@ +#include "backtrack.h" + +namespace bt{ + backtrack::backtrack() {} + + backtrack::backtrack(uint32_t graphType,uint32_t numVer,uint32_t numDef,uint32_t firstLabel,bool isAll) + { + this->theGraph=new semtd(graphType,numVer,numDef); + this->graphType=graphType; + this->usedLabels.resize(this->theGraph->TotalVer+1,false); + this->IsSemt=false; + setLabel(1,firstLabel); + this->firstLabel=firstLabel; + this->Result=""; + this->RecurseAll=isAll; + this->pathLabel=this->startPath=this->endPath=0; + switch(graphType) + { + case 4: + { + this->startPath=2; + this->endPath=this->theGraph->NumVer; + break; + } + case 3: + case 5: + { + this->startPath=3; + this->endPath=this->theGraph->NumVer; + break; + } + } + } + + inline void backtrack::setLabel(uint32_t verPos,uint32_t verLabel) + { + this->usedLabels[verLabel]=true; + this->theGraph->SetVerLabel(verPos,verLabel); + } + + inline void backtrack::removeLabel(uint32_t verPos) + { + this->usedLabels[this->theGraph->VerLabels[verPos]]=false; + this->theGraph->RemoveVerLabel(verPos); + } + + void backtrack::walk(uint32_t currentLevel) + { + if (this->IsProcessing) + { + if (currentLevel > this->theGraph->NumVer) + { + if (this->theGraph->IsSemt()) + { + if(!this->RecurseAll) + { + this->IsProcessing = false; + } + this->Result += this->theGraph->Print(1); + //setDual(); + //this->Result+="\nDual:\n"+this->theGraph->Print()+"\n"; + //setDual(); //undo the damage + this->IsSemt = true; + } + removeLabel(currentLevel - 1); + } + else + { + //List<int> availableLabels = new List<int>(); + vector<uint32_t> availableLabels; + uint32_t start=1; + uint32_t end=this->theGraph->TotalVer; + if(currentLevel==2 && this->firstLabel != this->theGraph->TotalVer) + { + if(this->graphType==3) + start=end; //optimization for wheel + else if(this->graphType==5) + start=this->firstLabel+1; + } + else if(this->startPath!=0) + { + if(currentLevel==this->endPath) + start=this->pathLabel+1; //remove possibility for reversed path labeling + else if(currentLevel==this->startPath && start<end) + end=this->theGraph->TotalVer-1; //no need to test last label as it'll be checked already on all previous cases + } + for (uint32_t i = start; i <= end; i++) + if (!this->usedLabels[i]) + availableLabels.push_back(i); + if(availableLabels.size()>0) + { + for (int32_t x = availableLabels.size()-1; x >= 0; x--) + { + if((this->startPath!=0) && (currentLevel==this->startPath)) + this->pathLabel=availableLabels[x]; + if (this->theGraph->IsValidToLabel(currentLevel, availableLabels[x])) + { + setLabel(currentLevel,availableLabels[x]); + walk(currentLevel + 1); + } + if (!this->IsProcessing) + break; + } + } + if (currentLevel != 2) { removeLabel(currentLevel - 1); } + } + } + } + void backtrack::Walk() + { + if(this->theGraph->numDef>=this->theGraph->MinDef()) + { + this->IsProcessing=true; + walk(2); + } + else + { + this->IsSemt=false; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/backtrack.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,25 @@ +#include "includes.h" +#include "graphmagic.h" + +//using namespace std; + +namespace bt{ + class backtrack + { + private: + vector<bool> usedLabels; + uint32_t graphType,firstLabel,startPath,endPath,pathLabel; + semtd * theGraph; + inline void setLabel(uint32_t verPos,uint32_t verLabel); + inline void removeLabel(uint32_t verPos); + void walk(uint32_t currentLevel); + public: + backtrack(); + backtrack(uint32_t graphType,uint32_t numVer,uint32_t numDef,uint32_t firstLabel,bool isAll); + bool RecurseAll; + bool IsProcessing; + bool IsSemt; + void Walk(); + std::string Result; + }; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/basic/Argument_helper.cpp Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,651 @@ +/* +* +* Argument Helper +* +* Daniel Russel drussel@alumni.princeton.edu +* Stanford University +* +* +* This software is not subject to copyright protection and is in the +* public domain. Neither Stanford nor the author assume any +* responsibility whatsoever for its use by other parties, and makes no +* guarantees, expressed or implied, about its quality, reliability, or +* any other characteristic. +* +*/ + +#include "Argument_helper.h" + + +#include <iostream> +#include <cstdlib> +#include <cstdio> +//#include <limits> +#include <cassert> + + + +namespace dsr { + + bool verbose=false, VERBOSE=false; + + + + // This is a base class for representing one argument value. + /* + This is inherited by many classes and which represent the different types. + */ + class Argument_helper::Argument_target { + public: + char key; + std::string long_name; + std::string description; + std::string arg_description; + + Argument_target(char k, const std::string lname, + const std::string descr, + const std::string arg_descr) { + key=k; + long_name=lname; + description=descr; + arg_description=arg_descr; + } + Argument_target(const std::string descr, + const std::string arg_descr) { + key=0; + long_name=""; + description=descr; + arg_description=arg_descr; + } + virtual bool process(int &, const char **&)=0; + virtual void write_name(std::ostream &out) const; + virtual void write_value(std::ostream &out) const=0; + virtual void write_usage(std::ostream &out) const; + virtual ~Argument_target(){} + }; + + void Argument_helper::Argument_target::write_name(std::ostream &out) const { + if (key != 0) out << '-' << key; + else if (!long_name.empty()) out << "--" << long_name; + else out << arg_description; + } + + + void Argument_helper::Argument_target::write_usage(std::ostream &out) const { + if (key != 0) { + out << '-' << key; + out << "/--" << long_name; + } + out << ' ' << arg_description; + out << "\t" << description; + out << " Value: "; + write_value(out); + out << std::endl; + } + + class Argument_helper::FlagTarget: public Argument_helper::Argument_target{ + public: + bool &val; + FlagTarget(char k, const char *lname, + const char *descr, + bool &b): Argument_target(k, std::string(lname), std::string(descr), + std::string()), val(b){} + virtual bool process(int &, const char **&){ + val= !val; + return true; + } + virtual void write_value(std::ostream &out) const { + out << val; + } + + virtual void write_usage(std::ostream &out) const { + if (key != 0) { + out << '-' << key; + out << "/--" << long_name; + } + out << "\t" << description; + out << " Value: "; + write_value(out); + out << std::endl; + } + virtual ~FlagTarget(){} + }; + + class Argument_helper::DoubleTarget: public Argument_target{ + public: + double &val; + DoubleTarget(char k, const char *lname, + const char *arg_descr, + const char *descr, double &b): Argument_target(k, std::string(lname), + std::string(descr), + std::string(arg_descr)), val(b){} + DoubleTarget(const char *arg_descr, + const char *descr, double &b): Argument_target(std::string(descr), + std::string(arg_descr)), val(b){} + virtual bool process(int &argc, const char **&argv){ + if (argc==0){ + std::cerr << "Missing value for argument." << std::endl; + return false; + } + if (my_sscanf(argv[0], "%le", &val) ==1){ + --argc; + ++argv; + return true; + } else { + std::cerr << "Double not found at " << argv[0] << std::endl; + return false; + } + } + virtual void write_value(std::ostream &out) const { + out << val; + } + virtual ~DoubleTarget(){} + }; + + class Argument_helper::IntTarget: public Argument_target{ + public: + int &val; + IntTarget(const char *arg_descr, + const char *descr, int &b): Argument_target(0, std::string(), + std::string(descr), + std::string(arg_descr)), + val(b){} + IntTarget(char k, const char *lname, + const char *arg_descr, + const char *descr, int &b): Argument_target(k, std::string(lname), + std::string(descr), + std::string(arg_descr)), + val(b){} + virtual bool process(int &argc, const char **&argv){ + if (argc==0){ + std::cerr << "Missing value for argument." << std::endl; + return false; + } + if (my_sscanf(argv[0], "%d", &val) ==1){ + --argc; + ++argv; + return true; + } else { + std::cerr << "Integer not found at " << argv[0] << std::endl; + return false; + } + } + virtual void write_value(std::ostream &out) const { + out << val; + } + virtual ~IntTarget(){} + }; + + class Argument_helper::UIntTarget: public Argument_target{ + public: + unsigned int &val; + UIntTarget(const char *arg_descr, + const char *descr, unsigned int &b): Argument_target(0, std::string(), + std::string(descr), + std::string(arg_descr)), + val(b){} + UIntTarget(char k, const char *lname, + const char *arg_descr, + const char *descr, unsigned int &b): Argument_target(k, std::string(lname), + std::string(descr), + std::string(arg_descr)), + val(b){} + virtual bool process(int &argc, const char **&argv){ + if (argc==0){ + std::cerr << "Missing value for argument." << std::endl; + return false; + } + if (my_sscanf(argv[0], "%ud", &val) ==1){ + --argc; + ++argv; + return true; + } else { + std::cerr << "Unsigned integer not found at " << argv[0] << std::endl; + return false; + } + } + virtual void write_value(std::ostream &out) const { + out << val; + } + virtual ~UIntTarget(){} + }; + + + class Argument_helper::CharTarget: public Argument_target{ + public: + char &val; + CharTarget(char k, const char *lname, + const char *arg_descr, + const char *descr, char &b): Argument_target(k, std::string(lname), + std::string(descr), + std::string(arg_descr)), val(b){} + CharTarget(const char *arg_descr, + const char *descr, char &b): Argument_target(std::string(descr), + std::string(arg_descr)), val(b){} + virtual bool process(int &argc, const char **&argv){ + if (argc==0){ + std::cerr << "Missing value for argument." << std::endl; + return false; + } + if (my_sscanf(argv[0], "%c", &val) ==1){ + --argc; + ++argv; + return true; + } else { + std::cerr << "Character not found at " << argv[0] << std::endl; + return false; + } + } + virtual void write_value(std::ostream &out) const { + out << val; + } + virtual ~CharTarget(){} + }; + + + class Argument_helper::StringTarget: public Argument_target{ + public: + std::string &val; + StringTarget(const char *arg_descr, + const char *descr, std::string &b): Argument_target(0, std::string(), + descr, + arg_descr), + val(b){} + + StringTarget(char k, const char *lname, const char *arg_descr, + const char *descr, std::string &b): Argument_target(k, lname, descr, + arg_descr), + val(b){} + + virtual bool process(int &argc, const char **&argv){ + if (argc==0){ + std::cerr << "Missing string argument." << std::endl; + return false; + } + val= argv[0]; + --argc; + ++argv; + return true; + } + virtual void write_value(std::ostream &out) const { + out << val; + } + virtual ~StringTarget(){} + }; + + + class Argument_helper::StringVectorTarget: public Argument_target{ + public: + std::vector<std::string> &val; + + StringVectorTarget(char k, const char *lname, const char *arg_descr, + const char *descr, std::vector<std::string> &b): Argument_target(k, lname, descr, + arg_descr), + val(b){} + + virtual bool process(int &argc, const char **&argv){ + while (argc >0 && argv[0][0] != '-'){ + val.push_back(argv[0]); + --argc; + ++argv; + } + return true; + } + virtual void write_value(std::ostream &out) const { + for (unsigned int i=0; i< val.size(); ++i){ + out << val[i] << " "; + } + } + virtual ~StringVectorTarget(){} + }; + + + + + Argument_helper::Argument_helper(){ + author_="Someone"; + description_= "This program does something."; + date_= "A long long time ago."; + version_=-1; + extra_arguments_=NULL; + seen_end_named_=false; + new_flag('v', "verbose", "Whether to print extra information", verbose); + new_flag('V', "VERBOSE", "Whether to print lots of extra information", VERBOSE); + } + + + + void Argument_helper::set_string_vector(const char *arg_description, + const char *description, + std::vector<std::string> &dest){ + assert(extra_arguments_==NULL); + extra_arguments_descr_= description; + extra_arguments_arg_descr_= arg_description; + extra_arguments_= &dest; + } + + void Argument_helper::set_author(const char *author){ + author_=author; + } + + void Argument_helper::set_description(const char *descr){ + description_= descr; + } + + void Argument_helper::set_name(const char *descr){ + name_= descr; + } + + void Argument_helper::set_version(float v){ + version_=v; + } + + void Argument_helper::set_version(const char *s){ + std::stringstream f; + f << s; + f >> version_; + } + + void Argument_helper::set_build_date(const char *date){ + date_=date; + } + + void Argument_helper::new_argument_target(Argument_target *t) { + assert(t!= NULL); + if (t->key != 0){ + if (short_names_.find(t->key) != short_names_.end()){ + std::cerr << "Two arguments are defined with the same character key, namely" << std::endl; + short_names_[t->key]->write_usage(std::cerr); + std::cerr << "\n and \n"; + t->write_usage(std::cerr); + std::cerr << std::endl; + } + short_names_[t->key]= t; + } + if (!t->long_name.empty()){ + if (long_names_.find(t->long_name) != long_names_.end()){ + std::cerr << "Two arguments are defined with the same long key, namely" << std::endl; + long_names_[t->long_name]->write_usage(std::cerr); + std::cerr << "\n and \n"; + t->write_usage(std::cerr); + std::cerr << std::endl; + } + long_names_[t->long_name]= t; + } + all_arguments_.push_back(t); + } + + void Argument_helper::new_flag(char key, const char *long_name, const char *description,bool &dest){ + Argument_target *t= new FlagTarget(key, long_name, description, dest); + new_argument_target(t); + }; + + + + void Argument_helper::new_string(const char *arg_description, const char *description, + std::string &dest){ + Argument_target *t= new StringTarget(arg_description, description, dest); + unnamed_arguments_.push_back(t); + all_arguments_.push_back(t); + }; + void Argument_helper::new_optional_string(const char *arg_description, const char *description, + std::string &dest){ + Argument_target *t= new StringTarget(arg_description, description, dest); + optional_unnamed_arguments_.push_back(t); + }; + void Argument_helper::new_named_string(char key, const char *long_name, + const char *arg_description, const char *description, + std::string &dest){ + Argument_target *t= new StringTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + + void Argument_helper::new_named_string_vector(char key, const char *long_name, + const char *arg_description, const char *description, + std::vector<std::string> &dest){ + Argument_target *t= new StringVectorTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + + + void Argument_helper::new_int(const char *arg_description, const char *description, + int &dest){ + Argument_target *t= new IntTarget(arg_description, description, dest); + unnamed_arguments_.push_back(t); + all_arguments_.push_back(t); + }; + void Argument_helper::new_optional_int(const char *arg_description, const char *description, + int &dest){ + Argument_target *t= new IntTarget(arg_description, description, dest); + optional_unnamed_arguments_.push_back(t); + }; + void Argument_helper::new_named_int(char key, const char *long_name, + const char *arg_description, const char *description, + int &dest){ + Argument_target *t= new IntTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + void Argument_helper::new_unsigned_int(const char *arg_description, const char *description, + unsigned int &dest){ + Argument_target *t= new UIntTarget(arg_description, description, dest); + unnamed_arguments_.push_back(t); + all_arguments_.push_back(t); + }; + void Argument_helper::new_optional_unsigned_int(const char *arg_description, const char *description, + unsigned int &dest){ + Argument_target *t= new UIntTarget(arg_description, description, dest); + optional_unnamed_arguments_.push_back(t); + }; + void Argument_helper::new_named_unsigned_int(char key, const char *long_name, + const char *arg_description, const char *description, + unsigned int &dest){ + Argument_target *t= new UIntTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + + void Argument_helper::new_double(const char *arg_description, const char *description, + double &dest){ + Argument_target *t= new DoubleTarget(arg_description, description, dest); + unnamed_arguments_.push_back(t); + all_arguments_.push_back(t); + }; + void Argument_helper::new_optional_double(const char *arg_description, const char *description, + double &dest){ + Argument_target *t= new DoubleTarget(arg_description, description, dest); + optional_unnamed_arguments_.push_back(t); + }; + void Argument_helper::new_named_double(char key, const char *long_name, + const char *arg_description, const char *description, + double &dest){ + Argument_target *t= new DoubleTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + void Argument_helper::new_char(const char *arg_description, const char *description, + char &dest){ + Argument_target *t= new CharTarget(arg_description, description, dest); + unnamed_arguments_.push_back(t); + all_arguments_.push_back(t); + }; + void Argument_helper::new_optional_char(const char *arg_description, const char *description, + char &dest){ + Argument_target *t= new CharTarget(arg_description, description, dest); + optional_unnamed_arguments_.push_back(t); + }; + void Argument_helper::new_named_char(char key, const char *long_name, + const char *arg_description, const char *description, + char &dest){ + Argument_target *t= new CharTarget(key, long_name, arg_description, description, dest); + new_argument_target(t); + }; + + + + void Argument_helper::write_usage(std::ostream &out) const { + out << name_ << " version " << version_ << ", by " << author_ << std::endl; + out << description_ << std::endl; + out << "Compiled on " << date_ << std::endl << std::endl; + out << "Usage: " << name_ << " "; + for (UVect::const_iterator it= unnamed_arguments_.begin(); it != unnamed_arguments_.end(); ++it){ + (*it)->write_name(out); + out << " "; + } + for (UVect::const_iterator it= optional_unnamed_arguments_.begin(); + it != optional_unnamed_arguments_.end(); ++it){ + out << "["; + (*it)->write_name(out); + out << "] "; + } + if (extra_arguments_ != NULL) { + out << "[" << extra_arguments_arg_descr_ << "]"; + } + + out << std::endl << std::endl; + out << "All arguments:\n"; + for (UVect::const_iterator it= unnamed_arguments_.begin(); it != unnamed_arguments_.end(); ++it){ + (*it)->write_usage(out); + } + for (UVect::const_iterator it= optional_unnamed_arguments_.begin(); + it != optional_unnamed_arguments_.end(); ++it){ + (*it)->write_usage(out); + } + + //out << extra_arguments_arg_descr_ << ": " << extra_arguments_descr_ << std::endl; + for (SMap::const_iterator it= short_names_.begin(); it != short_names_.end(); ++it){ + (it->second)->write_usage(out); + } + } + + + + void Argument_helper::write_values(std::ostream &out) const { + for (UVect::const_iterator it= unnamed_arguments_.begin(); it != unnamed_arguments_.end(); ++it){ + out << (*it)->description; + out << ": "; + (*it)->write_value(out); + out << std::endl; + } + for (UVect::const_iterator it= optional_unnamed_arguments_.begin(); + it != optional_unnamed_arguments_.end(); ++it){ + out << (*it)->description; + out << ": "; + (*it)->write_value(out); + out << std::endl; + } + if (extra_arguments_!=NULL){ + for (std::vector<std::string>::const_iterator it= extra_arguments_->begin(); + it != extra_arguments_->end(); ++it){ + out << *it << " "; + } + } + + for (SMap::const_iterator it= short_names_.begin(); it != short_names_.end(); ++it){ + out << it->second->description; + out << ": "; + it->second->write_value(out); + out << std::endl; + } + } + + Argument_helper::~Argument_helper(){ + for (std::vector<Argument_target*>::iterator it= all_arguments_.begin(); + it != all_arguments_.end(); ++it){ + delete *it; + } + } + + + void Argument_helper::process(int argc, const char **argv){ + name_= argv[0]; + ++argv; + --argc; + + current_unnamed_= unnamed_arguments_.begin(); + current_optional_unnamed_= optional_unnamed_arguments_.begin(); + + for ( int i=0; i< argc; ++i){ + if (strcmp(argv[i], "--help") == 0){ + write_usage(std::cout); + exit(0); + } + } + + while (argc != 0){ + + const char* cur_arg= argv[0]; + if (cur_arg[0]=='-' && !seen_end_named_){ + --argc; ++argv; + if (cur_arg[1]=='-'){ + if (cur_arg[2] == '\0') { + //std::cout << "Ending flags " << std::endl; + seen_end_named_=true; + } else { + // long argument + LMap::iterator f= long_names_.find(cur_arg+2); + if ( f != long_names_.end()){ + if (!f->second->process(argc, argv)) { + handle_error(); + } + } else { + std::cerr<< "Invalid long argument "<< cur_arg << ".\n"; + handle_error(); + } + } + } else { + if (cur_arg[1]=='\0') { + std::cerr << "Invalid argument " << cur_arg << ".\n"; + handle_error(); + } + SMap::iterator f= short_names_.find(cur_arg[1]); + if ( f != short_names_.end()){ + if (!f->second->process(argc, argv)) { + handle_error(); + } + } else { + std::cerr<< "Invalid short argument "<< cur_arg << ".\n"; + handle_error(); + } + } + } else { + if (current_unnamed_ != unnamed_arguments_.end()){ + Argument_target *t= *current_unnamed_; + t->process(argc, argv); + ++current_unnamed_; + } else if (current_optional_unnamed_ != optional_unnamed_arguments_.end()){ + Argument_target *t= *current_optional_unnamed_; + t->process(argc, argv); + ++current_optional_unnamed_; + } else if (extra_arguments_!= NULL){ + extra_arguments_->push_back(cur_arg); + --argc; + ++argv; + } else { + std::cerr << "Invalid extra argument " << argv[0] << std::endl; + handle_error(); + } + } + } + + if (current_unnamed_ != unnamed_arguments_.end()){ + std::cerr << "Missing required arguments:" << std::endl; + for (; current_unnamed_ != unnamed_arguments_.end(); ++current_unnamed_){ + (*current_unnamed_)->write_name(std::cerr); + std::cerr << std::endl; + } + std::cerr << std::endl; + handle_error(); + } + + if (VERBOSE) verbose=true; + } + + void Argument_helper::handle_error() const { + write_usage(std::cerr); + exit(1); + } +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/basic/Argument_helper.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,161 @@ +/* +* +* Argument Helper +* +* Daniel Russel drussel@alumni.princeton.edu +* Stanford University +* +* +* This software is not subject to copyright protection and is in the +* public domain. Neither Stanford nor the author assume any +* responsibility whatsoever for its use by other parties, and makes no +* guarantees, expressed or implied, about its quality, reliability, or +* any other characteristic. +* +*/ +#ifdef _MSC_VER +#define my_sscanf sscanf_s +#else +#define my_sscanf sscanf +#endif +#include <sstream> + +#ifndef _DSR_ARGS_H_ +#define _DSR_ARGS_H_ +#include <vector> +#include <map> +#include <list> +#include <string> +#include <string.h> + +namespace dsr{ + extern bool verbose, VERBOSE; + + + class Argument_helper{ + private: + class Argument_target; + + + class FlagTarget; + class DoubleTarget; + class IntTarget; + class UIntTarget; + class StringTarget; + class CharTarget; + class StringVectorTarget; + + public: + Argument_helper(); + void new_flag(char key, const char *long_name, const char *description,bool &dest); + + void new_string( const char *arg_description, const char *description, std::string &dest); + void new_named_string(char key, const char *long_name, + const char *arg_description, + const char *description, std::string &dest); + void new_optional_string( const char *arg_description, const char *description, std::string &dest); + + void new_int( const char *arg_description, const char *description, int &dest); + void new_named_int(char key, const char *long_name,const char *value_name, + const char *description, + int &dest); + void new_optional_int(const char *value_name, + const char *description, + int &dest); + + void new_double(const char *value_name, + const char *description, + double &dest); + + void new_named_double(char key, const char *long_name,const char *value_name, + const char *description, + double &dest); + void new_optional_double(const char *value_name, + const char *description, + double &dest); + + void new_char(const char *value_name, + const char *description, + char &dest); + void new_named_char(char key, const char *long_name,const char *value_name, + const char *description, + char &dest); + void new_optional_char(const char *value_name, + const char *description, + char &dest); + + void new_unsigned_int(const char *value_name, const char *description, + unsigned int &dest); + void new_optional_unsigned_int(const char *value_name, const char *description, + unsigned int &dest); + void new_named_unsigned_int(char key, const char *long_name, + const char *value_name, const char *description, + unsigned int &dest); + + + + void new_named_string_vector(char key, const char *long_name, + const char *value_name, const char *description, + std::vector<std::string> &dest); + + + void set_string_vector(const char *arg_description, const char *description, std::vector<std::string> &dest); + + void set_author(const char *author); + + void set_description(const char *descr); + + void set_version(float v); + void set_version(const char *str); + + void set_name(const char *name); + + void set_build_date(const char *date); + + + void process(int argc, const char **argv); + void process(int argc, char **argv){ + process(argc, const_cast<const char **>(argv)); + } + void write_usage(std::ostream &out) const; + void write_values(std::ostream &out) const; + + ~Argument_helper(); + protected: + typedef std::map<char, Argument_target*> SMap; + typedef std::map<std::string, Argument_target*> LMap; + typedef std::vector<Argument_target*> UVect; + // A map from short names to arguments. + SMap short_names_; + // A map from long names to arguments. + LMap long_names_; + std::string author_; + std::string name_; + std::string description_; + std::string date_; + float version_; + bool seen_end_named_; + // List of unnamed arguments + std::vector<Argument_target*> unnamed_arguments_; + std::vector<Argument_target*> optional_unnamed_arguments_; + std::vector<Argument_target*> all_arguments_; + std::string extra_arguments_descr_; + std::string extra_arguments_arg_descr_; + std::vector<std::string> *extra_arguments_; + std::vector<Argument_target*>::iterator current_unnamed_; + std::vector<Argument_target*>::iterator current_optional_unnamed_; + void new_argument_target(Argument_target*); + void handle_error() const; + private: + Argument_helper(const Argument_helper &){}; + const Argument_helper& operator=(const Argument_helper &){return *this;} + }; + +} + +#define ARGUMENT_HELPER_BASICS(ah) ah.set_author("Daniel Russel, drussel@stanford.edu");\ + ah.set_version(VERSION);\ + ah.set_build_date(__DATE__); + +#endif +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/basic/inefficient.cpp Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,52 @@ +#include <sstream> +#include "inefficient.h" + +string uint32_t_to_str(uint32_t myint) +{ + stringstream tempstr; + tempstr<<myint; + return tempstr.str(); +} + +double stdev(uint32_t * numbers) +{ + //TODO + return 0; +} + +gettime::gettime() +{ + uint32_t year,month,day,hour,min,sec; +#ifdef _MSC_VER + SYSTEMTIME st; + GetLocalTime(&st); + char temp[5]; + sprintf_s(temp,5,"%04d",st.wYear); + year=atoi(temp); + sprintf_s(temp,3,"%02d",st.wMonth); + month=atoi(temp); + sprintf_s(temp,3,"%02d",st.wDay); + day=atoi(temp); + sprintf_s(temp,3,"%02d",st.wHour); + hour=atoi(temp); + sprintf_s(temp,3,"%02d",st.wMinute); + min=atoi(temp); + sprintf_s(temp,3,"%02d",st.wSecond); + sec=atoi(temp); + sprintf_s(time_v,20,"%04d-%02d-%02d %02d:%02d:%02d",year,month,day,hour,min,sec); + sprintf_s(time_s,16,"%04d%02d%02d_%02d%02d%02d",year,month,day,hour,min,sec); +#else + struct tm *mytm; + time_t mytime; + time(&mytime); + mytm=gmtime(&mytime); + year=mytm->tm_year+1900; + month=mytm->tm_mon+1; + day=mytm->tm_mday; + hour=mytm->tm_hour; + min=mytm->tm_min; + sec=mytm->tm_sec; + sprintf(time_v,"%04d-%02d-%02d %02d:%02d:%02d",year,month,day,hour,min,sec); + sprintf(time_s,"%04d%02d%02d_%02d%02d%02d",year,month,day,hour,min,sec); +#endif +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/basic/inefficient.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,23 @@ +#ifdef _MSC_VER +#include <windows.h> +#include "../msvc/stdint.h" +#else +#include <stdint.h> +#include <sys/time.h> +#endif +#include <time.h> +#include <string> +#include <stdio.h> +using namespace std; + +string uint32_t_to_str(uint32_t myint); +double stdev(uint32_t * numbers); + +class gettime; + +class gettime +{ +public: + char time_v[20],time_s[16]; + gettime(); +};
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/graphmagic.cpp Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,433 @@ +#include "graphmagic.h" + +semtd::semtd(){} + +semtd::semtd(uint32_t graphType,uint32_t NumVer, uint32_t numDef) +{ + if(NumVer>3){ + this->NumVer=NumVer; + this->numDef=numDef; + this->graphType=graphType; + this->TotalVer=NumVer+numDef; + this->numEdges=0; + this->isSureFail=false; + this->edgeLabelAbsoluteMax=this->TotalVer*2-1; + //initialize graph array + //this->theGraph.resize(this->NumVer+1,vector<bool>(this->NumVer+1,false)); + for (int i=0; i<1000;i++) + { + for (int j=0;j<1000;j++) + { + this->theGraph[i][j]=false; + } + } + draw(this->graphType,1,this->NumVer); + resetLabels(0); + } +} + +void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end) +{ + switch(drawType) + { + case 0: + { + for (uint32_t i=start;i<end;i++) + connectVertices(i,i+1); + break; + } + case 1: + { + draw(0,start,end); + connectVertices(start,end); + break; + } + case 3: + { + draw(1,start+1,end); + draw(2,start+1,end,start); + break; + } + case 4: + { + draw(0,start+1,end); + draw(2,start+1,end,start); + break; + } + case 5: + { + draw(4,start+1,end); + draw(2,start+2,end,start); + break; + } + } +} + +void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end, uint32_t extra) +{ + switch(drawType) + { + case 2: + { + for (uint32_t i=start;i<=end;i++) + connectVertices(i,extra); + break; + } + } +} + +inline void semtd::connectVertices(uint32_t a,uint32_t b) +{ + if(!this->theGraph[a][b]) + { + this->theGraph[a][b]=this->theGraph[b][a]=true; + this->numEdges++; + } +} + +void semtd::resetLabels(uint32_t mode) +{ + if(mode==0) + { + this->VerLabels.clear(); + this->VerLabels.resize(this->NumVer+1,0); + } + this->edgeLabels.clear(); + this->edgeLabels.resize(NumVer+1,vector<uint32_t>(NumVer+1,0)); + this->isQuickMode=false; + this->scoreCache=-1; + //uint32_t *edgeLabelsUsedPtr; + //edgeLabelsUsedPtr=(uint32_t*)malloc(this->edgeLabelAbsoluteMax+1*sizeof(uint32_t)); + this->edgeLabelsUsed.clear(); + this->edgeLabelsUsed.resize(this->edgeLabelAbsoluteMax+1,0); + this->edgeLabelMax=0;this->edgeLabelMin=this->edgeLabelAbsoluteMax; + refreshEdgeLabelsMinMax(); +} + +void semtd::refreshEdgeLabelsMinMax() +{ + uint32_t i; + for (i = 1; i <= this->edgeLabelAbsoluteMax; i++) + { + if (this->edgeLabelsUsed[i] > 0) + { + this->edgeLabelMin = i; + break; + } + } + for (int32_t x = this->edgeLabelAbsoluteMax; x >= 0; x--) + { + if (this->edgeLabelsUsed[x] > 0) + { + this->edgeLabelMax = x; + break; + } + } +} + +inline uint32_t semtd::edgeLabelRange() +{ + return this->edgeLabelMax-this->edgeLabelMin+1; +} + +void semtd::setEdgeLabels(uint32_t verPos) +{ + uint32_t newLabel,i; + for (i = 1; i <= this->NumVer; i++) + { + if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos) + { + newLabel = this->VerLabels[verPos] + this->VerLabels[i]; + this->edgeLabels[i][verPos] = this->edgeLabels[i][verPos] = newLabel; + this->edgeLabelsUsed[newLabel]++; + if (this->edgeLabelsUsed[newLabel] != 1) + this->isSureFail = true; + } + } + refreshEdgeLabelsMinMax(); +} + +void semtd::removeEdgeLabels(uint32_t verPos) +{ + uint32_t i; + for (i = 1; i <= this->NumVer; i++) + { + if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos) + { + int oldLabel = this->edgeLabels[i][verPos]; + this->edgeLabelsUsed[oldLabel]--; + this->edgeLabels[i][verPos] = this->edgeLabels[verPos][i] = 0; + } + } + refreshEdgeLabelsMinMax(); +} + +void semtd::SetVerLabel(uint32_t verPos,uint32_t verLabel) +{ + if (this->VerLabels[verPos] > 0) { RemoveVerLabel(verPos); } + this->VerLabels[verPos] = verLabel; + setEdgeLabels(verPos); +} + +void semtd::RemoveVerLabel(uint32_t verPos) +{ + if (this->VerLabels[verPos] > 0) + { + this->VerLabels[verPos] = 0; + removeEdgeLabels(verPos); + } +} + + + +bool semtd::IsValidToLabel(uint32_t verPos,uint32_t verLabel) +{ + uint32_t i,tempLabel; + //uint32_t tempMax=this->edgeLabelMax; + //uint32_t tempMin=this->edgeLabelMin; + for (i = 1; i <= this->NumVer; i++) + { + tempLabel=this->VerLabels[i] + verLabel; + if (i != verPos && + this->theGraph[i][verPos] && + this->VerLabels[i] > 0 && + this->edgeLabelsUsed[tempLabel] == 1) + { + return false; + } + /*if(tempLabel>tempMax) + tempMax=tempLabel; + if(tempLabel<tempMin) + tempMin=tempLabel; + if(!isValidRange(tempMin,tempMax)) + return false;*/ + } + return true; +} + +bool semtd::isValidRange(uint32_t min,uint32_t max) +{ + uint32_t delta=1+max-min; + if(delta<=this->numEdges) + return true; + return false; +} + +double semtd::SemtScore() +{ + //TODO + return 0; +} + +void semtd::FixLabel() +{ + //TODO +} + +void semtd::SwapLabel() +{ + //TODO +} + +string semtd::Print(uint32_t withDual) +{ + uint32_t i,j; + string ret = ""; + string n = "\n"; + bool dualRun=false; + bool keepPrinting=true; + while (keepPrinting) + { + ret+="graph: "; + switch(this->graphType) + { + case 3: + { + ret+="wheel"; + break; + } + case 4: + { + ret+="fan"; + break; + } + case 5: + { + ret+="doublefan"; + break; + } + default: + { + ret+="unknown"; + break; + } + } + ret+=" | edges: "+uint32_t_to_str(this->numEdges)+" | vertices: " + uint32_t_to_str(this->NumVer)+" | deficiencies: " + uint32_t_to_str(this->numDef) + " | "; + uint32_t edgeweight=0,k,edgelabel=0; + for (i=1;i<=this->edgeLabelAbsoluteMax;i++) + { + if(this->edgeLabelsUsed[i]) + { + edgeweight=i; + edgelabel=this->numEdges+this->TotalVer; + break; + } + } + if(dualRun) + { + edgeweight=2*(this->TotalVer)+2-edgeweight; + edgelabel=2*this->TotalVer+this->numEdges+1-edgelabel; + } + k=edgeweight+edgelabel; + ret+="mnum: "+uint32_t_to_str(k)+" | "; + for (i = 1; i <= this->NumVer; i++) + { + uint32_t theLabel; + if(dualRun) + theLabel=this->TotalVer+1-this->VerLabels[i]; + else + theLabel=this->VerLabels[i]; + if(i==1 && this->graphType==3) + ret+="c: " + uint32_t_to_str(theLabel) +" | l: "; + else if(i==1 && this->graphType==4) + ret+="c: " + uint32_t_to_str(theLabel) +" | p: "; + else if(i==1 && this->graphType==5) + ret+="c: " + uint32_t_to_str(theLabel) + ","; + else if(i==2 && this->graphType==5) + ret+=uint32_t_to_str(theLabel) + " | p: "; + else if(i==this->NumVer) + ret+=uint32_t_to_str(theLabel) + " | def: "; + else + ret+=uint32_t_to_str(theLabel)+","; + } + if(this->numDef>0) + { + vector<bool> usedLabels (this->TotalVer+1,false); + for(i=1;i<=this->NumVer;i++) + usedLabels[this->VerLabels[i]]=true; + j=0; + for(i=1;i<=this->TotalVer;i++) + { + uint32_t theLabel; + if(!usedLabels[i]) + { + if(dualRun) + theLabel=this->TotalVer+1-i; + else + theLabel=i; + if(j==this->numDef-1) + { + if(dualRun) + ret+=uint32_t_to_str(theLabel)+" (dual)"+n; + else + ret+=uint32_t_to_str(theLabel)+n; + j++; + } + else + { + ret+=uint32_t_to_str(theLabel)+","; + j++; + } + } + } + } + /* + ret += n+"Deficiency: " + uint32_t_to_str(this->numDef); + ret += n+"GraphViz code: " + n + "----------------------------------"; + //tempstr1<<this->graphType; //TODO: graphtype is now integer instead of string. create a convert method + ret += n+"graph " + uint32_t_to_str(this->graphType)+ "{"; + ret += n+"graph[bgcolor=\"transparent\"]"; + ret += n+"node [fontname=\"Bitstream Vera Sans\", fontsize=\"22.00\", shape=circle, style=\"bold,filled\" fillcolor=white];"; + ret += n+"edge [style=bold];"; + ret += n+" "; + for (i = 1; i <= this->TotalVer; i++) + { + ret += uint32_t_to_str(i) + ";"; + } + for (i = 1; i <= this->NumVer; i++) + { + for (j = i + 1; j <= this->NumVer; j++) + { + if (this->theGraph[i][j]) + { + uint32_t theLabel; + if(dualRun) + theLabel=this->TotalVer+1-this->VerLabels[i]; + else + theLabel=this->VerLabels[i]; + ret += n+uint32_t_to_str(this->VerLabels[i])+ " -- " + uint32_t_to_str(theLabel)+ ";"; + } + } + } + ret += n+"}"; + ret += n+"----------------------------------" + n + "End GraphViz code";*/ + if(withDual==1) + { + withDual=0; + dualRun=true; + }else + keepPrinting=false; + } + return ret; +} + + + +bool semtd::IsSemt() +{ + uint32_t i; + if (this->isSureFail) { return false; } + else + { + if (edgeLabelRange() == numEdges) + { + uint32_t edgeLabelMin = this->edgeLabelMin; + uint32_t edgeLabelMax = this->edgeLabelMax; + for (i = edgeLabelMin; i <= edgeLabelMax; i++) + { + if (this->edgeLabelsUsed[i] != 1) + { + return false; + } + } + return true; + } + } + return false; +} + +uint32_t semtd::MinDef() +{ + uint32_t ret=0; + switch(this->graphType) + { + case 3: + switch (this->NumVer) + { + case 3: + case 4: + case 6: + case 7: + { + ret = 1; + break; + } + default: + { + ret = 2; + break; + } + } + case 4: + { + ret=1; + break; + } + case 5: + { + ret = (this->NumVer - 3) / 2; + break; + } + } + return ret; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/graphmagic.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,43 @@ +#include "includes.h" +using namespace std; + +class semtd; + +class semtd +{ +private: + //graphType: 0=path, 1=cycle, 2=completebipartite, 3=wheel, 4=fan, 5=doublefan + //vector< vector<bool> > theGraph; + bool theGraph[1000][1000]; + bool isQuickMode; + bool isSureFail; + vector< vector<uint32_t> > edgeLabels; + vector<uint32_t> edgeLabelsUsed; + uint32_t edgeLabelAbsoluteMax,edgeLabelMin,edgeLabelMax; + double scoreCache; + inline uint32_t edgeLabelRange(); + void setEdgeLabels(uint32_t verPos); + void removeEdgeLabels(uint32_t verPos); + void refreshEdgeLabelsMinMax(); + void resetLabels(uint32_t mode); + void draw(uint32_t drawType,uint32_t start,uint32_t end); + void draw(uint32_t drawType,uint32_t start,uint32_t end,uint32_t extra); + inline void connectVertices(uint32_t a,uint32_t b); + bool isValidRange(uint32_t min,uint32_t max); +public: + uint32_t numDef,numEdges,graphType; + semtd(); + semtd(uint32_t graphType, uint32_t numVer, uint32_t numDef); + uint32_t NumVer,TotalVer; + vector<uint32_t> VerLabels; + string Print(uint32_t withDual); + void FixLabel(); + void SwapLabel(); + bool IsSemt(); + double SemtScore(); + void SetVerLabel(uint32_t verPos,uint32_t verLabel); + void RemoveVerLabel(uint32_t verPos); + bool IsValidToLabel(uint32_t verPos,uint32_t verLabel); + uint32_t MinDef(); +}; +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/includes.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,13 @@ +#ifndef INCLUDED +#define INCLUDED +#ifdef _MSC_VER +#include "msvc/stdint.h" +#else +#include <stdint.h> +#include <omp.h> +#endif +#include <string> +#include <sstream> +#include <vector> +#include "basic/inefficient.h" +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/main.cpp Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,102 @@ +#include "main.h" + +const uint32_t INTMAX=100000; +const char separator[40]= "======================================="; + +int main(int argc, const char *argv[]) +{ + uint32_t numVer,numDef,graphType,isAllI; + int32_t start,end; + string graphTypeS,algorithm; + bool isAll; + //defaults + numVer=numDef=isAllI=INTMAX; + isAllI=1; + isAll=false; + graphTypeS="x"; + algorithm="x"; + //end defaults + dsr::Argument_helper ah; + ah.set_author("Edho Prima Arief <me@myconan.net>"); + ah.set_description("Calculates deficiency for various graphs."); + ah.set_build_date("2009"); + ah.set_name("defical"); + ah.set_version("0.1"); + ah.new_named_unsigned_int('n',"numver","","Number of vertices.",numVer); + ah.new_named_unsigned_int('d',"numdef","","Number of deficiencies.",numDef); + ah.new_named_string('g',"graph","","Type of graph.",graphTypeS); + ah.new_named_string('a',"algorithm","","Choice of algorithm.",algorithm); + ah.new_named_unsigned_int('c',"complete","","Don't stop on found.",isAllI); + ah.process(argc,argv); + if(isAllI==1) + isAll=true; + if(graphTypeS=="wheel") + graphType=3; + else if(graphTypeS=="fan") + graphType=4; + else if(graphTypeS=="doublefan") + graphType=5; + else + { + printf("Invalid graph type. Accepted: wheel, fan, doublefan.\n"); + return 1; + } + if(numVer<5 || numVer>=INTMAX) + { + printf("Number of vertices must be more than 5 (or less than %d).\n",INTMAX); + return 1; + } + if(numDef>=INTMAX) + { + printf("Ha ha ha funny. Just give up (number of deficiencies must be less than %d.\n",INTMAX); + return 1; + } + if(algorithm!="backtrack") + { + printf("Invalid algorithm specified.\n"); + return 1; + } + printf(separator); + printf("\nNumber of vertices: %d\n",numVer); + printf("Number of deficiencies: %d\n",numDef); + cout << "Graph type: " << graphTypeS << endl; + cout << "Algorithm: " << algorithm << endl; + cout << separator << endl; + gettime *mytime=new gettime(); + cout << "[I] " << mytime->time_v << ": Started" << endl; + cout << separator << endl; + if(algorithm=="backtrack") + { + start=1; + end=(numVer+numDef+1)/2; + bool isFinished=false; +#ifdef _OPENMP +#pragma omp parallel for num_threads(3) +#endif + for(int32_t i=start;i<=end;i++){ + if(!isFinished){ + bt::backtrack *bt1=new bt::backtrack(graphType,numVer,numDef,i,isAll); + bt1->Walk(); + if(!isFinished) + { + if(bt1->IsSemt) + { + if(!isAll) + isFinished=true; + gettime *mytime=new gettime(); + printf("[F] %s: Found\n%s\n%s%s\n",mytime->time_v,separator,bt1->Result.c_str(),separator); + bt1->IsSemt=false; + } + else { + if(!isFinished) + { + gettime *mytime=new gettime(); + printf("[N] %s: Unable to construct with first label %d\n",mytime->time_v,i); + } + } + } + } + } + } + return 0; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/main.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,8 @@ +#include <iostream> +#include <stdio.h> +#include "includes.h" +#include "backtrack.h" +#include "basic/Argument_helper.h" + +int main(int argc, const char *argv[]); +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/msvc/gettimeofday.c Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,51 @@ +#include <time.h> +#include <windows.h> + +#if defined(_MSC_VER) || defined(_MSC_EXTENSIONS) + #define DELTA_EPOCH_IN_MICROSECS 11644473600000000Ui64 +#else + #define DELTA_EPOCH_IN_MICROSECS 11644473600000000ULL +#endif + +struct timezone +{ + int tz_minuteswest; /* minutes W of Greenwich */ + int tz_dsttime; /* type of dst correction */ +}; + +int gettimeofday(struct timeval *tv, struct timezone *tz) +{ + FILETIME ft; + unsigned __int64 tmpres = 0; + static int tzflag = 0; + + if (NULL != tv) + { + GetSystemTimeAsFileTime(&ft); + + tmpres |= ft.dwHighDateTime; + tmpres <<= 32; + tmpres |= ft.dwLowDateTime; + + tmpres /= 10; /*convert into microseconds*/ + /*converting file time to unix epoch*/ + tmpres -= DELTA_EPOCH_IN_MICROSECS; + tv->tv_sec = (long)(tmpres / 1000000UL); + tv->tv_usec = (long)(tmpres % 1000000UL); + } + + if (NULL != tz) + { + if (!tzflag) + { + _tzset(); + tzflag++; + } + tz->tz_minuteswest = _get_timezone(tz) / 60; + tz->tz_dsttime = _daylight; + } + + return 0; +} + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-c/src/msvc/stdint.h Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,233 @@ +// ISO C9x compliant stdint.h for Microsoft Visual Studio +// Based on ISO/IEC 9899:TC2 Committee draft (May 6, 2005) WG14/N1124 +// +// Copyright (c) 2006-2008 Alexander Chemeris +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright +// notice, this list of conditions and the following disclaimer in the +// documentation and/or other materials provided with the distribution. +// +// 3. The name of the author may be used to endorse or promote products +// derived from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED +// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO +// EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; +// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, +// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR +// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF +// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifndef _MSC_VER // [ +#error "Use this header only with Microsoft Visual C++ compilers!" +#endif // _MSC_VER ] + +#ifndef _MSC_STDINT_H_ // [ +#define _MSC_STDINT_H_ + +#if _MSC_VER > 1000 +#pragma once +#endif + +#include <limits.h> + +// For Visual Studio 6 in C++ mode wrap <wchar.h> include with 'extern "C++" {}' +// or compiler give many errors like this: +// error C2733: second C linkage of overloaded function 'wmemchr' not allowed +#if (_MSC_VER < 1300) && defined(__cplusplus) + extern "C++" { +#endif +# include <wchar.h> +#if (_MSC_VER < 1300) && defined(__cplusplus) + } +#endif + +// Define _W64 macros to mark types changing their size, like intptr_t. +#ifndef _W64 +# if !defined(__midl) && (defined(_X86_) || defined(_M_IX86)) && _MSC_VER >= 1300 +# define _W64 __w64 +# else +# define _W64 +# endif +#endif + + +// 7.18.1 Integer types + +// 7.18.1.1 Exact-width integer types +typedef __int8 int8_t; +typedef __int16 int16_t; +typedef __int32 int32_t; +typedef __int64 int64_t; +typedef unsigned __int8 uint8_t; +typedef unsigned __int16 uint16_t; +typedef unsigned __int32 uint32_t; +typedef unsigned __int64 uint64_t; + +// 7.18.1.2 Minimum-width integer types +typedef int8_t int_least8_t; +typedef int16_t int_least16_t; +typedef int32_t int_least32_t; +typedef int64_t int_least64_t; +typedef uint8_t uint_least8_t; +typedef uint16_t uint_least16_t; +typedef uint32_t uint_least32_t; +typedef uint64_t uint_least64_t; + +// 7.18.1.3 Fastest minimum-width integer types +typedef int8_t int_fast8_t; +typedef int16_t int_fast16_t; +typedef int32_t int_fast32_t; +typedef int64_t int_fast64_t; +typedef uint8_t uint_fast8_t; +typedef uint16_t uint_fast16_t; +typedef uint32_t uint_fast32_t; +typedef uint64_t uint_fast64_t; + +// 7.18.1.4 Integer types capable of holding object pointers +#ifdef _WIN64 // [ + typedef __int64 intptr_t; + typedef unsigned __int64 uintptr_t; +#else // _WIN64 ][ + typedef _W64 int intptr_t; + typedef _W64 unsigned int uintptr_t; +#endif // _WIN64 ] + +// 7.18.1.5 Greatest-width integer types +typedef int64_t intmax_t; +typedef uint64_t uintmax_t; + + +// 7.18.2 Limits of specified-width integer types + +#if !defined(__cplusplus) || defined(__STDC_LIMIT_MACROS) // [ See footnote 220 at page 257 and footnote 221 at page 259 + +// 7.18.2.1 Limits of exact-width integer types +#define INT8_MIN ((int8_t)_I8_MIN) +#define INT8_MAX _I8_MAX +#define INT16_MIN ((int16_t)_I16_MIN) +#define INT16_MAX _I16_MAX +#define INT32_MIN ((int32_t)_I32_MIN) +#define INT32_MAX _I32_MAX +#define INT64_MIN ((int64_t)_I64_MIN) +#define INT64_MAX _I64_MAX +#define UINT8_MAX _UI8_MAX +#define UINT16_MAX _UI16_MAX +#define UINT32_MAX _UI32_MAX +#define UINT64_MAX _UI64_MAX + +// 7.18.2.2 Limits of minimum-width integer types +#define INT_LEAST8_MIN INT8_MIN +#define INT_LEAST8_MAX INT8_MAX +#define INT_LEAST16_MIN INT16_MIN +#define INT_LEAST16_MAX INT16_MAX +#define INT_LEAST32_MIN INT32_MIN +#define INT_LEAST32_MAX INT32_MAX +#define INT_LEAST64_MIN INT64_MIN +#define INT_LEAST64_MAX INT64_MAX +#define UINT_LEAST8_MAX UINT8_MAX +#define UINT_LEAST16_MAX UINT16_MAX +#define UINT_LEAST32_MAX UINT32_MAX +#define UINT_LEAST64_MAX UINT64_MAX + +// 7.18.2.3 Limits of fastest minimum-width integer types +#define INT_FAST8_MIN INT8_MIN +#define INT_FAST8_MAX INT8_MAX +#define INT_FAST16_MIN INT16_MIN +#define INT_FAST16_MAX INT16_MAX +#define INT_FAST32_MIN INT32_MIN +#define INT_FAST32_MAX INT32_MAX +#define INT_FAST64_MIN INT64_MIN +#define INT_FAST64_MAX INT64_MAX +#define UINT_FAST8_MAX UINT8_MAX +#define UINT_FAST16_MAX UINT16_MAX +#define UINT_FAST32_MAX UINT32_MAX +#define UINT_FAST64_MAX UINT64_MAX + +// 7.18.2.4 Limits of integer types capable of holding object pointers +#ifdef _WIN64 // [ +# define INTPTR_MIN INT64_MIN +# define INTPTR_MAX INT64_MAX +# define UINTPTR_MAX UINT64_MAX +#else // _WIN64 ][ +# define INTPTR_MIN INT32_MIN +# define INTPTR_MAX INT32_MAX +# define UINTPTR_MAX UINT32_MAX +#endif // _WIN64 ] + +// 7.18.2.5 Limits of greatest-width integer types +#define INTMAX_MIN INT64_MIN +#define INTMAX_MAX INT64_MAX +#define UINTMAX_MAX UINT64_MAX + +// 7.18.3 Limits of other integer types + +#ifdef _WIN64 // [ +# define PTRDIFF_MIN _I64_MIN +# define PTRDIFF_MAX _I64_MAX +#else // _WIN64 ][ +# define PTRDIFF_MIN _I32_MIN +# define PTRDIFF_MAX _I32_MAX +#endif // _WIN64 ] + +#define SIG_ATOMIC_MIN INT_MIN +#define SIG_ATOMIC_MAX INT_MAX + +#ifndef SIZE_MAX // [ +# ifdef _WIN64 // [ +# define SIZE_MAX _UI64_MAX +# else // _WIN64 ][ +# define SIZE_MAX _UI32_MAX +# endif // _WIN64 ] +#endif // SIZE_MAX ] + +// WCHAR_MIN and WCHAR_MAX are also defined in <wchar.h> +#ifndef WCHAR_MIN // [ +# define WCHAR_MIN 0 +#endif // WCHAR_MIN ] +#ifndef WCHAR_MAX // [ +# define WCHAR_MAX _UI16_MAX +#endif // WCHAR_MAX ] + +#define WINT_MIN 0 +#define WINT_MAX _UI16_MAX + +#endif // __STDC_LIMIT_MACROS ] + + +// 7.18.4 Limits of other integer types + +#if !defined(__cplusplus) || defined(__STDC_CONSTANT_MACROS) // [ See footnote 224 at page 260 + +// 7.18.4.1 Macros for minimum-width integer constants + +#define INT8_C(val) val##i8 +#define INT16_C(val) val##i16 +#define INT32_C(val) val##i32 +#define INT64_C(val) val##i64 + +#define UINT8_C(val) val##ui8 +#define UINT16_C(val) val##ui16 +#define UINT32_C(val) val##ui32 +#define UINT64_C(val) val##ui64 + +// 7.18.4.2 Macros for greatest-width integer constants +#define INTMAX_C INT64_C +#define UINTMAX_C UINT64_C + +#endif // __STDC_CONSTANT_MACROS ] + + +#endif // _MSC_STDINT_H_ ] +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/LICENSE Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,13 @@ +Copyright (c) 2009, Edho Prima Arief <me@myconan.net> + +Permission to use, copy, modify, and/or distribute this software for any +purpose with or without fee is hereby granted, provided that the above +copyright notice and this permission notice appear in all copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/Program.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,15 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; + +namespace defical_cli +{ + partial class Program + { + static void Main(string[] args) + { + main run = new main(args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/Properties/AssemblyInfo.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,36 @@ +using System.Reflection; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +// General Information about an assembly is controlled through the following +// set of attributes. Change these attribute values to modify the information +// associated with an assembly. +[assembly: AssemblyTitle("defical-cli")] +[assembly: AssemblyDescription("")] +[assembly: AssemblyConfiguration("")] +[assembly: AssemblyCompany("")] +[assembly: AssemblyProduct("defical-cli")] +[assembly: AssemblyCopyright("Copyright © 2009")] +[assembly: AssemblyTrademark("")] +[assembly: AssemblyCulture("")] + +// Setting ComVisible to false makes the types in this assembly not visible +// to COM components. If you need to access a type in this assembly from +// COM, set the ComVisible attribute to true on that type. +[assembly: ComVisible(false)] + +// The following GUID is for the ID of the typelib if this project is exposed to COM +[assembly: Guid("90562622-0474-4959-a4c5-c60515117d24")] + +// Version information for an assembly consists of the following four values: +// +// Major Version +// Minor Version +// Build Number +// Revision +// +// You can specify all the values or you can default the Build and Revision Numbers +// by using the '*' as shown below: +// [assembly: AssemblyVersion("1.0.*")] +[assembly: AssemblyVersion("1.0.0.0")] +[assembly: AssemblyFileVersion("1.0.0.0")]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/argumentparser.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,131 @@ +namespace defical_cli +{ + public partial class Program + { + private partial class main + { + private bool getArguments(string[] args) + { + bool ret = true; + int numArgs = args.Length; + for (int i = 0; i < numArgs; i++) + { + switch (args[i].Substring(0, 1)) + { + case "-": + { + switch (args[i].Substring(1, 1)) + { + case "g": + { + args[i] = "--graph"; + i--; + break; + } + case "n": + { + args[i] = "--numver"; + i--; + break; + } + case "d": + { + args[i] = "--numdef"; + i--; + break; + } + case "a": + { + args[i] = "--algorithm"; + i--; + break; + } + case "-": + { + if (i < numArgs - 1) + { + switch (args[i].Substring(2)) + { + case "graph": + #region graphparser + { + switch (args[i + 1]) + { + case "wheel": + case "fan": + case "doublefan": + { + this.graphType = args[i + 1]; + break; + } + default: + { + ret = false; + break; + } + } + break; + } + #endregion + case "numver": + #region numverparser + { + int tempNumVer = -1; + if (parseNum(args[i + 1], 5, 10, out tempNumVer)) + { + this.numVer = tempNumVer; + } + else { ret = false; } + break; + } + #endregion + case "numdef": + #region numdefparser + { + int tempNumDef = -1; + if (parseNum(args[i + 1], 0, 10, out tempNumDef)) + { + this.numDef = tempNumDef; + } + else { ret = false; } + break; + } + #endregion + case "algorithm": + #region algorithmparser + { + switch (args[i + 1]) + { + case "backtrack": + this.algorithm = args[i + 1]; + break; + default: + ret = false; + break; + } + break; + } + #endregion + } + i++; + } + else { ret = false; } + break; + } + } + break; + } + default: + { + ret = false; + break; + } + } + } + //TODO + return ret; + } + + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/defical-cli.csproj Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,71 @@ +<?xml version="1.0" encoding="utf-8"?> +<Project ToolsVersion="3.5" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> + <PropertyGroup> + <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> + <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> + <ProductVersion>9.0.30729</ProductVersion> + <SchemaVersion>2.0</SchemaVersion> + <ProjectGuid>{67B23900-6656-4571-B890-216385DB552A}</ProjectGuid> + <OutputType>Exe</OutputType> + <AppDesignerFolder>Properties</AppDesignerFolder> + <RootNamespace>defical_cli</RootNamespace> + <AssemblyName>defical-cli</AssemblyName> + <TargetFrameworkVersion>v3.5</TargetFrameworkVersion> + <FileAlignment>512</FileAlignment> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> + <DebugSymbols>true</DebugSymbols> + <DebugType>full</DebugType> + <Optimize>false</Optimize> + <OutputPath>bin\Debug\</OutputPath> + <DefineConstants>DEBUG;TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> + <DebugType>pdbonly</DebugType> + <Optimize>true</Optimize> + <OutputPath>bin\Release\</OutputPath> + <DefineConstants>TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <ItemGroup> + <Reference Include="System" /> + <Reference Include="System.Core"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Xml.Linq"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data.DataSetExtensions"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data" /> + <Reference Include="System.Xml" /> + </ItemGroup> + <ItemGroup> + <Compile Include="argumentparser.cs" /> + <Compile Include="globals.cs" /> + <Compile Include="inputparser.cs" /> + <Compile Include="main.cs" /> + <Compile Include="Program.cs" /> + <Compile Include="Properties\AssemblyInfo.cs" /> + <Compile Include="threader-backtrack.cs" /> + <Compile Include="threader.cs" /> + </ItemGroup> + <ItemGroup> + <ProjectReference Include="..\libbacktrack\libbacktrack.csproj"> + <Project>{3E6EC10D-A9CE-4542-9931-D004955771F7}</Project> + <Name>libbacktrack</Name> + </ProjectReference> + </ItemGroup> + <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> + <!-- To modify your build process, add your task inside one of the targets below and uncomment it. + Other similar extension points exist, see Microsoft.Common.targets. + <Target Name="BeforeBuild"> + </Target> + <Target Name="AfterBuild"> + </Target> + --> +</Project> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/globals.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,18 @@ +namespace defical_cli +{ + public partial class Program + { + private partial class main + { + private string version = "0.1"; + private bool isProcessing; + private string graphType = ""; + private string result = ""; + private int numVer = -1; + private int numThreads; + private const string separator = "==================================="; + private int numDef = -1; + private string algorithm = ""; + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/inputparser.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,80 @@ +using System; + +namespace defical_cli +{ + public partial class Program + { + private partial class main + { + private void getInput() + { + int min, def; + if (graphType == "") + { + while (true) + { + Console.Write("Available graph type:\n1. Wheel\n2. Fan\n3. Double Fan\nGraph type (default: 1): "); + if (!parseGraphType(Console.ReadKey().KeyChar)) + { + Console.Write("\nInvalid graph type.\n"); + } + else + { + Console.Write("\n"); + break; + } + } + } + if (numVer == -1) + { + while (true) + { + min = 5; def = 10; + Console.Write("Number of vertices (default: {0}): ", def); + if (!parseNum(Console.ReadLine(), min, def, out this.numVer)) + { + Console.Write("Invalid number of vertices.\nPlease enter number with minimum of {0}.", min); + } + else + { + break; + } + } + } + if (numDef == -1) + { + while (true) + { + min = 0; def = 2; + Console.Write("Number of deficiencies (default: {0}): ", def); + if (!parseNum(Console.ReadLine(), min, def, out this.numDef)) + { + Console.Write("Please enter number (or press enter to use default)."); + } + else + { + break; + } + } + } + if (algorithm == "") + { + while (true) + { + Console.Write("Available algorithm:\n1. Backtrack\nYour choice (default: 1): "); + if (!parseAlgo(Console.ReadKey().KeyChar)) + { + Console.Write("\nInvalid algorithm.\n"); + } + else + { + Console.Write("\n"); + break; + } + } + Console.Write("\n"); + } + } + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/main.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,150 @@ +using System; +using System.Threading; +using libbacktrack; +using System.IO; + +namespace defical_cli +{ + partial class Program + { + private partial class main + { + public main() { throw new NotImplementedException(); } + public main(params string[] args) + { + this.numThreads = Environment.ProcessorCount + 1; + { + if (args.Length != 0 && !getArguments(args)) + { + Console.WriteLine("Failed"); + return; + } + printWelcome(); + getInput(); + printPreSummary(); + Console.WriteLine("Started: {0}", DateTime.Now.ToString()); + Console.WriteLine(separator); + go(); + Console.WriteLine(separator); + Console.WriteLine("Finished: {0}", DateTime.Now.ToString()); + //Console.ReadLine(); + } + } + private void printPreSummary() + { + Console.WriteLine(separator); + Console.WriteLine("Graph type: {0}", this.graphType); + Console.WriteLine("Number of vertices: {0}", this.numVer); + Console.WriteLine("Number of deficiencies: {0}", this.numDef); + Console.WriteLine("Algorithm: {0}", this.algorithm); + if (this.algorithm == "backtrack") + { + Console.WriteLine("Number of threads: {0}", this.numThreads); + } + Console.WriteLine(separator); + } + private void printWelcome() + { + Console.WriteLine("Defical_CLI v{0}", this.version); + Console.WriteLine("Super magic deficiency calculator"); + Console.WriteLine("By Edho <me@myconan.net>"); + Console.WriteLine(separator); + } + private bool parseNum(string input, int min, int def, out int ret) + { + if (input == "") + { + ret = def; + return true; + } + try { Convert.ToInt32(input); } + catch + { + ret = -1; + return false; + } + if (Convert.ToInt32(input) < min) + { + ret = -1; + return false; + } + else + { + ret = Convert.ToInt32(input); + return true; + } + } + private bool parseGraphType(char i) + { + switch (i) + { + case '1': + case '\r': + { + this.graphType = "wheel"; + return true; + } + case '2': + { + this.graphType = "fan"; + return true; + } + case '3': + { + this.graphType = "doublefan"; + return true; + } + default: + { return false; } + + } + } + private bool parseAlgo(char i) + { + switch (i) + { + case '1': + case '\r': + { + this.algorithm = "backtrack"; + return true; + } + default: + { return false; } + } + } + private void WriteToFile(string filePath, string line) + { + if (filePath == null || filePath.Length == 0) + return; + if (line == null || line.Length == 0) + return; + + StreamWriter fileWriter = null; + try + { + if (File.Exists(filePath)) + fileWriter = File.AppendText(filePath); + else + fileWriter = File.CreateText(filePath); + fileWriter.Write(line); + } + finally + { + if (fileWriter != null) + fileWriter.Close(); + } + } + private string getHomeDir() + { + if (Environment.OSVersion.Platform == PlatformID.Unix || + Environment.OSVersion.Platform == PlatformID.MacOSX) + { return Environment.GetEnvironmentVariable("HOME") + "/"; } + else + { + return Environment.ExpandEnvironmentVariables("%HOMEDRIVE%%HOMEPATH%") + "\\"; + } + } + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/threader-backtrack.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,103 @@ +using System; +using System.Threading; +using System.IO; +using libbacktrack; + +namespace defical_cli +{ + public partial class Program + { + private partial class main + { + private void goBT() + { + this.isProcessing = true; + this.result = ""; + Thread[] threads = new Thread[this.numThreads]; + int start; + int end = 0; + for (int i = 0; i < this.numThreads; i++) + { + threads[i] = new Thread(goThreadBT); + threads[i].IsBackground = true; + threads[i].Priority = ThreadPriority.Lowest; + start = end + 1; + end = start + ((this.numVer + this.numDef + 1) / 2) / this.numThreads; + if (i == this.numThreads - 1) + end = (this.numVer + this.numDef + 1) / 2; + threads[i].Start(new int[] { start, end, i }); + } + while (this.isProcessing) + { + Thread.Sleep(100); + bool threadsIsProcessing = false; + for (int i = 0; i < this.numThreads; i++) + { + if (threads[i].IsAlive) + { + threadsIsProcessing = true; + } + } + this.isProcessing = threadsIsProcessing; + } + if (this.result == "") { this.result = "SEMT labeling can't be constructed."; } + Console.WriteLine(this.result); + this.isProcessing = false; + for (int i = 0; i < this.numThreads; i++) + { + if (threads[i].IsAlive) + { + threads[i].Abort(); + } + } + + } + private void goThreadBT(object o) + { + int[] args = o as int[]; + int start = args[0]; + int end = args[1]; + int threadID = args[2]; + for (int i = start; i <= end; i++) + { + //if (this.isProcessing) + { + Backtrack todo = new Backtrack(this.graphType, this.numVer, this.numDef, i, true); + todo.Walk(); + if (this.isProcessing) + { + if (todo.IsSemt) + { + //this.isProcessing = false; + Console.Write("{0}",todo.Result); + this.result = todo.Result; + /*string filename = "log-" + + this.graphType + "-" + + "numver=" + this.numVer.ToString() + "-" + + "numdef=" + this.numDef.ToString() + "-" + + DateTime.UtcNow.ToString("yyyyMMdd_hhmmss"); + string filepath = getHomeDir() + filename; + int n = 1; + while (File.Exists(filepath + ".txt")) + { + if (!File.Exists(filepath + "-" + n.ToString() + ".txt")) + { + filepath += "-" + n.ToString(); + break; + } + n++; + } + WriteToFile(filepath + ".txt", this.result);*/ + //break; + } + else + { + Console.WriteLine("[404] SEMT labeling not found for first label of {0}", i); + } + } + } + } + } + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-cli/threader.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,27 @@ +using System; + +namespace defical_cli +{ + public partial class Program + { + private partial class main + { + private void go() + { + switch (this.algorithm) + { + case "backtrack": + { + goBT(); + break; + } + default: + { + Console.WriteLine("Not implemented!"); + break; + } + } + } + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/App.xaml Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,8 @@ +<Application x:Class="defical_gui.App" + xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" + xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" + StartupUri="main.xaml"> + <Application.Resources> + + </Application.Resources> +</Application>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/App.xaml.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,16 @@ +using System; +using System.Collections.Generic; +using System.Configuration; +using System.Data; +using System.Linq; +using System.Windows; + +namespace defical_gui +{ + /// <summary> + /// Interaction logic for App.xaml + /// </summary> + public partial class App : Application + { + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/Properties/AssemblyInfo.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,55 @@ +using System.Reflection; +using System.Resources; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using System.Windows; + +// General Information about an assembly is controlled through the following +// set of attributes. Change these attribute values to modify the information +// associated with an assembly. +[assembly: AssemblyTitle("defical-gui")] +[assembly: AssemblyDescription("")] +[assembly: AssemblyConfiguration("")] +[assembly: AssemblyCompany("")] +[assembly: AssemblyProduct("defical-gui")] +[assembly: AssemblyCopyright("Copyright © 2009")] +[assembly: AssemblyTrademark("")] +[assembly: AssemblyCulture("")] + +// Setting ComVisible to false makes the types in this assembly not visible +// to COM components. If you need to access a type in this assembly from +// COM, set the ComVisible attribute to true on that type. +[assembly: ComVisible(false)] + +//In order to begin building localizable applications, set +//<UICulture>CultureYouAreCodingWith</UICulture> in your .csproj file +//inside a <PropertyGroup>. For example, if you are using US english +//in your source files, set the <UICulture> to en-US. Then uncomment +//the NeutralResourceLanguage attribute below. Update the "en-US" in +//the line below to match the UICulture setting in the project file. + +//[assembly: NeutralResourcesLanguage("en-US", UltimateResourceFallbackLocation.Satellite)] + + +[assembly: ThemeInfo( + ResourceDictionaryLocation.None, //where theme specific resource dictionaries are located + //(used if a resource is not found in the page, + // or application resource dictionaries) + ResourceDictionaryLocation.SourceAssembly //where the generic resource dictionary is located + //(used if a resource is not found in the page, + // app, or any theme specific resource dictionaries) +)] + + +// Version information for an assembly consists of the following four values: +// +// Major Version +// Minor Version +// Build Number +// Revision +// +// You can specify all the values or you can default the Build and Revision Numbers +// by using the '*' as shown below: +// [assembly: AssemblyVersion("1.0.*")] +[assembly: AssemblyVersion("1.0.0.0")] +[assembly: AssemblyFileVersion("1.0.0.0")]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/Properties/Resources.Designer.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,70 @@ +//------------------------------------------------------------------------------ +// <auto-generated> +// This code was generated by a tool. +// Runtime Version:2.0.50727.4927 +// +// Changes to this file may cause incorrect behavior and will be lost if +// the code is regenerated. +// </auto-generated> +//------------------------------------------------------------------------------ + +namespace defical_gui.Properties { + using System; + + + /// <summary> + /// A strongly-typed resource class, for looking up localized strings, etc. + /// </summary> + // This class was auto-generated by the StronglyTypedResourceBuilder + // class via a tool like ResGen or Visual Studio. + // To add or remove a member, edit your .ResX file then rerun ResGen + // with the /str option, or rebuild your VS project. + [global::System.CodeDom.Compiler.GeneratedCodeAttribute("System.Resources.Tools.StronglyTypedResourceBuilder", "2.0.0.0")] + [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] + [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()] + internal class Resources { + + private static global::System.Resources.ResourceManager resourceMan; + + private static global::System.Globalization.CultureInfo resourceCulture; + + [global::System.Diagnostics.CodeAnalysis.SuppressMessageAttribute("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")] + internal Resources() { + } + + /// <summary> + /// Returns the cached ResourceManager instance used by this class. + /// </summary> + [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)] + internal static global::System.Resources.ResourceManager ResourceManager { + get { + if (object.ReferenceEquals(resourceMan, null)) { + global::System.Resources.ResourceManager temp = new global::System.Resources.ResourceManager("defical_gui.Properties.Resources", typeof(Resources).Assembly); + resourceMan = temp; + } + return resourceMan; + } + } + + /// <summary> + /// Overrides the current thread's CurrentUICulture property for all + /// resource lookups using this strongly typed resource class. + /// </summary> + [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)] + internal static global::System.Globalization.CultureInfo Culture { + get { + return resourceCulture; + } + set { + resourceCulture = value; + } + } + + internal static System.Drawing.Icon applications_system { + get { + object obj = ResourceManager.GetObject("applications_system", resourceCulture); + return ((System.Drawing.Icon)(obj)); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/Properties/Resources.resx Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,124 @@ +<?xml version="1.0" encoding="utf-8"?> +<root> + <!-- + Microsoft ResX Schema + + Version 2.0 + + The primary goals of this format is to allow a simple XML format + that is mostly human readable. The generation and parsing of the + various data types are done through the TypeConverter classes + associated with the data types. + + Example: + + ... ado.net/XML headers & schema ... + <resheader name="resmimetype">text/microsoft-resx</resheader> + <resheader name="version">2.0</resheader> + <resheader name="reader">System.Resources.ResXResourceReader, System.Windows.Forms, ...</resheader> + <resheader name="writer">System.Resources.ResXResourceWriter, System.Windows.Forms, ...</resheader> + <data name="Name1"><value>this is my long string</value><comment>this is a comment</comment></data> + <data name="Color1" type="System.Drawing.Color, System.Drawing">Blue</data> + <data name="Bitmap1" mimetype="application/x-microsoft.net.object.binary.base64"> + <value>[base64 mime encoded serialized .NET Framework object]</value> + </data> + <data name="Icon1" type="System.Drawing.Icon, System.Drawing" mimetype="application/x-microsoft.net.object.bytearray.base64"> + <value>[base64 mime encoded string representing a byte array form of the .NET Framework object]</value> + <comment>This is a comment</comment> + </data> + + There are any number of "resheader" rows that contain simple + name/value pairs. + + Each data row contains a name, and value. The row also contains a + type or mimetype. Type corresponds to a .NET class that support + text/value conversion through the TypeConverter architecture. + Classes that don't support this are serialized and stored with the + mimetype set. + + The mimetype is used for serialized objects, and tells the + ResXResourceReader how to depersist the object. This is currently not + extensible. For a given mimetype the value must be set accordingly: + + Note - application/x-microsoft.net.object.binary.base64 is the format + that the ResXResourceWriter will generate, however the reader can + read any of the formats listed below. + + mimetype: application/x-microsoft.net.object.binary.base64 + value : The object must be serialized with + : System.Runtime.Serialization.Formatters.Binary.BinaryFormatter + : and then encoded with base64 encoding. + + mimetype: application/x-microsoft.net.object.soap.base64 + value : The object must be serialized with + : System.Runtime.Serialization.Formatters.Soap.SoapFormatter + : and then encoded with base64 encoding. + + mimetype: application/x-microsoft.net.object.bytearray.base64 + value : The object must be serialized into a byte array + : using a System.ComponentModel.TypeConverter + : and then encoded with base64 encoding. + --> + <xsd:schema id="root" xmlns="" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:msdata="urn:schemas-microsoft-com:xml-msdata"> + <xsd:import namespace="http://www.w3.org/XML/1998/namespace" /> + <xsd:element name="root" msdata:IsDataSet="true"> + <xsd:complexType> + <xsd:choice maxOccurs="unbounded"> + <xsd:element name="metadata"> + <xsd:complexType> + <xsd:sequence> + <xsd:element name="value" type="xsd:string" minOccurs="0" /> + </xsd:sequence> + <xsd:attribute name="name" use="required" type="xsd:string" /> + <xsd:attribute name="type" type="xsd:string" /> + <xsd:attribute name="mimetype" type="xsd:string" /> + <xsd:attribute ref="xml:space" /> + </xsd:complexType> + </xsd:element> + <xsd:element name="assembly"> + <xsd:complexType> + <xsd:attribute name="alias" type="xsd:string" /> + <xsd:attribute name="name" type="xsd:string" /> + </xsd:complexType> + </xsd:element> + <xsd:element name="data"> + <xsd:complexType> + <xsd:sequence> + <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" /> + <xsd:element name="comment" type="xsd:string" minOccurs="0" msdata:Ordinal="2" /> + </xsd:sequence> + <xsd:attribute name="name" type="xsd:string" use="required" msdata:Ordinal="1" /> + <xsd:attribute name="type" type="xsd:string" msdata:Ordinal="3" /> + <xsd:attribute name="mimetype" type="xsd:string" msdata:Ordinal="4" /> + <xsd:attribute ref="xml:space" /> + </xsd:complexType> + </xsd:element> + <xsd:element name="resheader"> + <xsd:complexType> + <xsd:sequence> + <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" /> + </xsd:sequence> + <xsd:attribute name="name" type="xsd:string" use="required" /> + </xsd:complexType> + </xsd:element> + </xsd:choice> + </xsd:complexType> + </xsd:element> + </xsd:schema> + <resheader name="resmimetype"> + <value>text/microsoft-resx</value> + </resheader> + <resheader name="version"> + <value>2.0</value> + </resheader> + <resheader name="reader"> + <value>System.Resources.ResXResourceReader, System.Windows.Forms, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value> + </resheader> + <resheader name="writer"> + <value>System.Resources.ResXResourceWriter, System.Windows.Forms, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value> + </resheader> + <assembly alias="System.Windows.Forms" name="System.Windows.Forms, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" /> + <data name="applications_system" type="System.Resources.ResXFileRef, System.Windows.Forms"> + <value>..\Resources\applications-system.ico;System.Drawing.Icon, System.Drawing, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a</value> + </data> +</root> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/Properties/Settings.Designer.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,30 @@ +//------------------------------------------------------------------------------ +// <auto-generated> +// This code was generated by a tool. +// Runtime Version:2.0.50727.4927 +// +// Changes to this file may cause incorrect behavior and will be lost if +// the code is regenerated. +// </auto-generated> +//------------------------------------------------------------------------------ + +namespace defical_gui.Properties +{ + + + [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()] + [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Microsoft.VisualStudio.Editors.SettingsDesigner.SettingsSingleFileGenerator", "9.0.0.0")] + internal sealed partial class Settings : global::System.Configuration.ApplicationSettingsBase + { + + private static Settings defaultInstance = ((Settings)(global::System.Configuration.ApplicationSettingsBase.Synchronized(new Settings()))); + + public static Settings Default + { + get + { + return defaultInstance; + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/Properties/Settings.settings Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,7 @@ +<?xml version='1.0' encoding='utf-8'?> +<SettingsFile xmlns="uri:settings" CurrentProfile="(Default)"> + <Profiles> + <Profile Name="(Default)" /> + </Profiles> + <Settings /> +</SettingsFile> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/defical-gui.csproj Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,177 @@ +<?xml version="1.0" encoding="utf-8"?> +<Project ToolsVersion="3.5" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> + <PropertyGroup> + <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> + <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> + <ProductVersion>9.0.30729</ProductVersion> + <SchemaVersion>2.0</SchemaVersion> + <ProjectGuid>{33E73676-4A64-4E0D-A2A1-6FBFB05829EF}</ProjectGuid> + <OutputType>WinExe</OutputType> + <AppDesignerFolder>Properties</AppDesignerFolder> + <RootNamespace>defical_gui</RootNamespace> + <AssemblyName>Defical</AssemblyName> + <TargetFrameworkVersion>v3.5</TargetFrameworkVersion> + <FileAlignment>512</FileAlignment> + <ProjectTypeGuids>{60dc8134-eba5-43b8-bcc9-bb4bc16c2548};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids> + <WarningLevel>4</WarningLevel> + <ApplicationIcon>Resources\applications-system.ico</ApplicationIcon> + <IsWebBootstrapper>false</IsWebBootstrapper> + <ManifestCertificateThumbprint>58F4E9645D00E5E66F1920261DF55F6BDD8E596B</ManifestCertificateThumbprint> + <ManifestKeyFile>defical-gui_TemporaryKey.pfx</ManifestKeyFile> + <GenerateManifests>true</GenerateManifests> + <SignManifests>true</SignManifests> + <PublishUrl>publish\</PublishUrl> + <Install>true</Install> + <InstallFrom>Disk</InstallFrom> + <UpdateEnabled>false</UpdateEnabled> + <UpdateMode>Foreground</UpdateMode> + <UpdateInterval>7</UpdateInterval> + <UpdateIntervalUnits>Days</UpdateIntervalUnits> + <UpdatePeriodically>false</UpdatePeriodically> + <UpdateRequired>false</UpdateRequired> + <MapFileExtensions>true</MapFileExtensions> + <ApplicationRevision>0</ApplicationRevision> + <ApplicationVersion>1.0.0.%2a</ApplicationVersion> + <UseApplicationTrust>false</UseApplicationTrust> + <PublishWizardCompleted>true</PublishWizardCompleted> + <BootstrapperEnabled>true</BootstrapperEnabled> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> + <DebugSymbols>true</DebugSymbols> + <DebugType>full</DebugType> + <Optimize>false</Optimize> + <OutputPath>bin\Debug\</OutputPath> + <DefineConstants>DEBUG;TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> + <DebugType>pdbonly</DebugType> + <Optimize>true</Optimize> + <OutputPath>bin\Release\</OutputPath> + <DefineConstants>TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <ItemGroup> + <Reference Include="System" /> + <Reference Include="System.Core"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Drawing" /> + <Reference Include="System.Windows.Forms" /> + <Reference Include="System.Xml.Linq"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data.DataSetExtensions"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data" /> + <Reference Include="System.Xml" /> + <Reference Include="UIAutomationProvider"> + <RequiredTargetFramework>3.0</RequiredTargetFramework> + </Reference> + <Reference Include="WindowsBase"> + <RequiredTargetFramework>3.0</RequiredTargetFramework> + </Reference> + <Reference Include="PresentationCore"> + <RequiredTargetFramework>3.0</RequiredTargetFramework> + </Reference> + <Reference Include="PresentationFramework"> + <RequiredTargetFramework>3.0</RequiredTargetFramework> + </Reference> + </ItemGroup> + <ItemGroup> + <ApplicationDefinition Include="App.xaml"> + <Generator>MSBuild:Compile</Generator> + <SubType>Designer</SubType> + </ApplicationDefinition> + <Page Include="main.xaml"> + <Generator>MSBuild:Compile</Generator> + <SubType>Designer</SubType> + </Page> + <Compile Include="App.xaml.cs"> + <DependentUpon>App.xaml</DependentUpon> + <SubType>Code</SubType> + </Compile> + <Compile Include="main.xaml.cs"> + <DependentUpon>main.xaml</DependentUpon> + <SubType>Code</SubType> + </Compile> + </ItemGroup> + <ItemGroup> + <Compile Include="globals.cs" /> + <Compile Include="Properties\AssemblyInfo.cs"> + <SubType>Code</SubType> + </Compile> + <Compile Include="Properties\Resources.Designer.cs"> + <AutoGen>True</AutoGen> + <DesignTime>True</DesignTime> + <DependentUpon>Resources.resx</DependentUpon> + </Compile> + <Compile Include="Properties\Settings.Designer.cs"> + <AutoGen>True</AutoGen> + <DependentUpon>Settings.settings</DependentUpon> + <DesignTimeSharedInput>True</DesignTimeSharedInput> + </Compile> + <Compile Include="threader.cs" /> + <EmbeddedResource Include="Properties\Resources.resx"> + <Generator>ResXFileCodeGenerator</Generator> + <LastGenOutput>Resources.Designer.cs</LastGenOutput> + </EmbeddedResource> + <None Include="Properties\Settings.settings"> + <Generator>SettingsSingleFileGenerator</Generator> + <LastGenOutput>Settings.Designer.cs</LastGenOutput> + </None> + <AppDesigner Include="Properties\" /> + </ItemGroup> + <ItemGroup> + <ProjectReference Include="..\libbacktrack\libbacktrack.csproj"> + <Project>{3E6EC10D-A9CE-4542-9931-D004955771F7}</Project> + <Name>libbacktrack</Name> + </ProjectReference> + </ItemGroup> + <ItemGroup> + <None Include="Resources\applications-system.ico" /> + </ItemGroup> + <ItemGroup> + <BootstrapperPackage Include="Microsoft.Net.Client.3.5"> + <Visible>False</Visible> + <ProductName>.NET Framework Client Profile</ProductName> + <Install>false</Install> + </BootstrapperPackage> + <BootstrapperPackage Include="Microsoft.Net.Framework.2.0"> + <Visible>False</Visible> + <ProductName>.NET Framework 2.0 %28x86%29</ProductName> + <Install>false</Install> + </BootstrapperPackage> + <BootstrapperPackage Include="Microsoft.Net.Framework.3.0"> + <Visible>False</Visible> + <ProductName>.NET Framework 3.0 %28x86%29</ProductName> + <Install>false</Install> + </BootstrapperPackage> + <BootstrapperPackage Include="Microsoft.Net.Framework.3.5"> + <Visible>False</Visible> + <ProductName>.NET Framework 3.5</ProductName> + <Install>false</Install> + </BootstrapperPackage> + <BootstrapperPackage Include="Microsoft.Net.Framework.3.5.SP1"> + <Visible>False</Visible> + <ProductName>.NET Framework 3.5 SP1</ProductName> + <Install>true</Install> + </BootstrapperPackage> + <BootstrapperPackage Include="Microsoft.Windows.Installer.3.1"> + <Visible>False</Visible> + <ProductName>Windows Installer 3.1</ProductName> + <Install>true</Install> + </BootstrapperPackage> + </ItemGroup> + <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> + <!-- To modify your build process, add your task inside one of the targets below and uncomment it. + Other similar extension points exist, see Microsoft.Common.targets. + <Target Name="BeforeBuild"> + </Target> + <Target Name="AfterBuild"> + </Target> + --> +</Project> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/defical-gui.csproj.user Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,17 @@ +<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> + <PropertyGroup> + <PublishUrlHistory>publish\</PublishUrlHistory> + <InstallUrlHistory> + </InstallUrlHistory> + <SupportUrlHistory> + </SupportUrlHistory> + <UpdateUrlHistory> + </UpdateUrlHistory> + <BootstrapperUrlHistory> + </BootstrapperUrlHistory> + <ErrorReportUrlHistory> + </ErrorReportUrlHistory> + <FallbackCulture>en-US</FallbackCulture> + <VerifyUploadedFiles>false</VerifyUploadedFiles> + </PropertyGroup> +</Project> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/globals.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,12 @@ +using System.Threading; + +namespace defical_gui +{ + public partial class main + { + private int numVerMain, numVerDef; + private string graphType; + private bool isFindEverything,isProcessing; + private Thread mainThread; + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/main.xaml Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,38 @@ +<Window x:Class="defical_gui.main" + xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" + xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" + Title="Defical" MinHeight="320" MinWidth="500"> + <Grid> + <GroupBox Header="Graph" Margin="12,12,0,0" Name="grpGraph" HorizontalAlignment="Left" Width="210" Height="116" VerticalAlignment="Top"> + <Grid> + <Label Margin="6,6,112,0" Name="lblType" VerticalAlignment="Top" Target="{Binding ElementName=cmbGraphType}">_Type</Label> + <ComboBox Height="23" Margin="92,6,6,0" Name="cmbGraphType" VerticalAlignment="Top" SelectedIndex="0"> + <ComboBoxItem>Wheel</ComboBoxItem> + <ComboBoxItem>Fan</ComboBoxItem> + <ComboBoxItem>Double Fan</ComboBoxItem> + </ComboBox> + <Label Margin="6,35,112,0" Name="lblN" VerticalAlignment="Top" Target="{Binding ElementName=txtNumN}">_n</Label> + <TextBox Height="23" Margin="0,35,6,0" Name="txtNumN" VerticalAlignment="Top" HorizontalAlignment="Right" Width="100" TextChanged="txtNumN_TextChanged" /> + <Label Margin="6,64,112,0" Name="lblDef" VerticalAlignment="Top" Target="{Binding ElementName=txtNumDef}">_Deficiencies</Label> + <TextBox Margin="0,64,6,0" Name="txtNumDef" HorizontalAlignment="Right" Width="100" Height="23" VerticalAlignment="Top" TextChanged="txtNumDef_TextChanged" /> + </Grid> + </GroupBox> + <GroupBox Header="Options" Height="53" Margin="12,134,0,0" Name="grpLabels" VerticalAlignment="Top" HorizontalAlignment="Left" Width="210"> + <Grid> + + <CheckBox Margin="6,6,6,0" Name="chkIsFindAll" VerticalAlignment="Top">_Find all possible labelings</CheckBox> + </Grid> + </GroupBox> + <Button Height="23" HorizontalAlignment="Left" Margin="12,193,0,0" Name="btnStart" VerticalAlignment="Top" Width="102" IsDefault="True" IsEnabled="False" Click="btnStart_Click">_Start</Button> + <Button Height="23" Margin="120,193,0,0" Name="btnStop" VerticalAlignment="Top" HorizontalAlignment="Left" Width="102" IsEnabled="False" Click="btnStop_Click">S_top</Button> + <ProgressBar Height="13" Margin="12,222,0,0" Name="barProgress" VerticalAlignment="Top" HorizontalAlignment="Left" Width="210" /> + <GroupBox Header="Result" Margin="228,12,12,12" Name="grpResult"> + <Grid> + <TextBox Margin="6,6,6,35" Name="txtResult" TextChanged="txtResult_TextChanged" AcceptsReturn="True" AcceptsTab="False" VerticalScrollBarVisibility="Auto" TextWrapping="Wrap" IsReadOnly="True" HorizontalScrollBarVisibility="Auto" /> + <Button Height="23" HorizontalAlignment="Right" Margin="0,0,114,6" Name="btnClear" VerticalAlignment="Bottom" Width="102" Click="btnClear_Click">_Clear</Button> + <Button Height="23" HorizontalAlignment="Right" Margin="0,0,6,6" Name="btnSave" VerticalAlignment="Bottom" Width="102" Click="btnSave_Click">Sa_ve</Button> + </Grid> + </GroupBox> + <Button Height="23" HorizontalAlignment="Left" Margin="12,0,0,12" Name="btnExit" VerticalAlignment="Bottom" Width="102" Click="btnExit_Click">E_xit</Button> + </Grid> +</Window>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/main.xaml.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,212 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Windows; +using System.Windows.Controls; +using System.Windows.Data; +using System.Windows.Documents; +using System.Windows.Input; +using System.Windows.Media; +using System.Windows.Media.Imaging; +using System.Windows.Navigation; +using System.Windows.Shapes; +using System.IO; + +namespace defical_gui +{ + /// <summary> + /// Interaction logic for Window1.xaml + /// </summary> + public partial class main : Window + { + public main() + { + InitializeComponent(); + initBoxes(); + txtNumN.Focus(); + } + private delegate void StringDelegate(int errCode,string message); + private void printMessage(int errCode,string message) + { + switch (errCode) + { + case 0: + { + txtResult.Text += message; + break; + } + default: + { + switch (errCode) + { + case 200: + { + message = "Started"; + break; + } + case 201: + { + message = "Stopped"; + break; + } + case 400: + { + message = "Found"; + break; + } + case 401: + { + message = "SEMT Labeing can't be constructed with first label of " + message; + break; + } + + } + txtResult.Text += "[" + errCode.ToString() + "] " + DateTime.Now.ToString("[yyyy-MM-dd hh:mm:ss]") + ": " + message+"\n"; + break; + } + } + } + private void initBoxes() + { + this.isProcessing = false; + txtResult.Text = + txtNumDef.Text = + txtNumN.Text = ""; + validateInput(); + } + private void txtResult_TextChanged(object sender, TextChangedEventArgs e) + { + switchControls(this.isProcessing); + if (txtResult.Text == "") { btnSave.IsEnabled = false; } else { btnSave.IsEnabled = true; } + txtResult.ScrollToEnd(); + } + private bool validateInput() + { + btnStart.IsEnabled = false; + if (txtNumN.Text == "" || txtNumDef.Text == "") { return false; } + try + { + int numN = Convert.ToInt32(txtNumN.Text); + int numDef = Convert.ToInt32(txtNumDef.Text); + if (numN.ToString() == txtNumN.Text + && numDef.ToString() == txtNumDef.Text + && numN >= 3 + && numDef >= 0) + { + btnStart.IsEnabled = true; + return true; + } + } + catch { return false; } + return false; + } + private void switchControls(bool isWorking) + { + grpGraph.IsEnabled = + grpLabels.IsEnabled = + btnStart.IsEnabled = !isWorking; + btnStop.IsEnabled = + barProgress.IsIndeterminate = isWorking; + } + + private void txtNumN_TextChanged(object sender, TextChangedEventArgs e) + { + validateInput(); + } + + private void txtNumDef_TextChanged(object sender, TextChangedEventArgs e) + { + validateInput(); + } + + private void btnStart_Click(object sender, RoutedEventArgs e) + { + if (!validateInput()) { return; } + switchControls(true); + try + { + this.isFindEverything = (bool)chkIsFindAll.IsChecked; + switch (cmbGraphType.Text) + { + case "Wheel": + this.graphType= "wheel"; + break; + case "Fan": + this.graphType = "fan"; + break; + case "Double Fan": + this.graphType = "doublefan"; + break; + default: + throw new NotImplementedException(); + } + this.numVerDef = Convert.ToInt32(txtNumDef.Text); + int numExtraVer = 0; + switch (this.graphType) + { + case "wheel": + case "fan": + { + numExtraVer = 1; + break; + } + case "doublefan": + { + numExtraVer = 2; + break; + } + default: + throw new NotImplementedException(); + } + this.numVerMain = numExtraVer + Convert.ToInt32(txtNumN.Text); + mainThread = new System.Threading.Thread(go); + mainThread.IsBackground = true; + mainThread.Start(); + } + catch + { + switchControls(false); + } + } + + private void btnStop_Click(object sender, RoutedEventArgs e) + { + this.isProcessing = false; + switchControls(false); + } + + private void btnSave_Click(object sender, RoutedEventArgs e) + { + try + { + System.Windows.Forms.SaveFileDialog dialogSave = new System.Windows.Forms.SaveFileDialog(); + dialogSave.DefaultExt = "txt"; + dialogSave.Filter = "Text file (*.txt)|*.txt|All files (*.*)|*.*"; + dialogSave.AddExtension = true; + dialogSave.RestoreDirectory = true; + dialogSave.Title = "Save result"; + dialogSave.InitialDirectory = Environment.ExpandEnvironmentVariables("%HOMEDRIVE%%HOMEPATH%"); + dialogSave.FileName = "result-" + cmbGraphType.Text + "-" + txtNumN.Text + "," + txtNumDef.Text; + if (dialogSave.ShowDialog() == System.Windows.Forms.DialogResult.OK) + { + StreamWriter fileWriter = null; + if (File.Exists(dialogSave.FileName)) { fileWriter = File.AppendText(dialogSave.FileName); } + else { fileWriter = File.CreateText(dialogSave.FileName); } + fileWriter.Write(txtResult.Text); + fileWriter.Close(); + } + } + catch { } + } + + private void btnClear_Click(object sender, RoutedEventArgs e) + { + txtResult.Text = ""; + } + private void btnExit_Click(object sender, RoutedEventArgs e) + { + this.Close(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-gui/threader.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,91 @@ +using System.Threading; + +namespace defical_gui +{ + public partial class main + { + private void go() + { + this.isProcessing = true; + int numThreads = (System.Environment.ProcessorCount * 3)/2; + Thread[] threads = new Thread[numThreads]; + int start; + int end = 0; + txtResult.Dispatcher.BeginInvoke(new StringDelegate(printMessage), new object[] { 200, "" }); + for (int i = 0; i < numThreads; i++) + { + threads[i] = new Thread(goBT); + threads[i].IsBackground = true; + start = end + 1; + end = start + ((this.numVerMain + this.numVerDef + 1) / 2) / numThreads; + if (i == numThreads - 1) { end = (this.numVerMain + this.numVerDef + 1) / 2; } + threads[i].Start(new int[] { start, end, i }); + } + while (this.isProcessing) + { + Thread.Sleep(100); + if (!this.isProcessing) { break; } + bool threadIsProcessing = true; + switch (this.isFindEverything) + { + case true: + { + threadIsProcessing = false; + for (int i = 0; i < numThreads; i++) + { + if (threads[i].IsAlive) + { + threadIsProcessing = true; + break; + } + } + break; + } + case false: + { + threadIsProcessing = true; + for (int i = 0; i < numThreads; i++) + { + if (!threads[i].IsAlive) + { + threadIsProcessing = false; + break; + } + } + break; + } + } + this.isProcessing = threadIsProcessing; + } + txtResult.Dispatcher.BeginInvoke(new StringDelegate(printMessage), new object[] { 201, "" }); + for (int i = 0; i < numThreads; i++) + if (threads[i].IsAlive) + threads[i].Abort(); + } + private void goBT(object o) + { + int[] args = o as int[]; + int start = args[0]; + int end = args[1]; + int threadID = args[2]; + for (int i = start; i <= end; i++) + { + if (this.isProcessing) + { + libbacktrack.Backtrack myWork = new libbacktrack.Backtrack(this.graphType, this.numVerMain, this.numVerDef, i,this.isFindEverything); + myWork.Walk(); + if (this.isProcessing) + { + if (myWork.IsSemt) + { + txtResult.Dispatcher.BeginInvoke(new StringDelegate(printMessage), new object[] { 400, "" }); + txtResult.Dispatcher.BeginInvoke(new StringDelegate(printMessage), new object[] { 0, myWork.Result }); + if (!this.isFindEverything) { break; } + } + else { txtResult.Dispatcher.BeginInvoke(new StringDelegate(printMessage), new object[] { 401, i.ToString() }); } + } + } + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/defical-sharp.sln Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,38 @@ + +Microsoft Visual Studio Solution File, Format Version 10.00 +# Visual C# Express 2008 +Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "defical-cli", "defical-cli\defical-cli.csproj", "{67B23900-6656-4571-B890-216385DB552A}" +EndProject +Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "libsemtd", "libsemtd\libsemtd.csproj", "{3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}" +EndProject +Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "libbacktrack", "libbacktrack\libbacktrack.csproj", "{3E6EC10D-A9CE-4542-9931-D004955771F7}" +EndProject +Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "defical-gui", "defical-gui\defical-gui.csproj", "{33E73676-4A64-4E0D-A2A1-6FBFB05829EF}" +EndProject +Global + GlobalSection(SolutionConfigurationPlatforms) = preSolution + Debug|Any CPU = Debug|Any CPU + Release|Any CPU = Release|Any CPU + EndGlobalSection + GlobalSection(ProjectConfigurationPlatforms) = postSolution + {67B23900-6656-4571-B890-216385DB552A}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {67B23900-6656-4571-B890-216385DB552A}.Debug|Any CPU.Build.0 = Debug|Any CPU + {67B23900-6656-4571-B890-216385DB552A}.Release|Any CPU.ActiveCfg = Release|Any CPU + {67B23900-6656-4571-B890-216385DB552A}.Release|Any CPU.Build.0 = Release|Any CPU + {3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}.Debug|Any CPU.Build.0 = Debug|Any CPU + {3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}.Release|Any CPU.ActiveCfg = Release|Any CPU + {3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}.Release|Any CPU.Build.0 = Release|Any CPU + {3E6EC10D-A9CE-4542-9931-D004955771F7}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {3E6EC10D-A9CE-4542-9931-D004955771F7}.Debug|Any CPU.Build.0 = Debug|Any CPU + {3E6EC10D-A9CE-4542-9931-D004955771F7}.Release|Any CPU.ActiveCfg = Release|Any CPU + {3E6EC10D-A9CE-4542-9931-D004955771F7}.Release|Any CPU.Build.0 = Release|Any CPU + {33E73676-4A64-4E0D-A2A1-6FBFB05829EF}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {33E73676-4A64-4E0D-A2A1-6FBFB05829EF}.Debug|Any CPU.Build.0 = Debug|Any CPU + {33E73676-4A64-4E0D-A2A1-6FBFB05829EF}.Release|Any CPU.ActiveCfg = Release|Any CPU + {33E73676-4A64-4E0D-A2A1-6FBFB05829EF}.Release|Any CPU.Build.0 = Release|Any CPU + EndGlobalSection + GlobalSection(SolutionProperties) = preSolution + HideSolutionNode = FALSE + EndGlobalSection +EndGlobal
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/Properties/AssemblyInfo.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,36 @@ +using System.Reflection; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +// General Information about an assembly is controlled through the following +// set of attributes. Change these attribute values to modify the information +// associated with an assembly. +[assembly: AssemblyTitle("libbacktrack")] +[assembly: AssemblyDescription("")] +[assembly: AssemblyConfiguration("")] +[assembly: AssemblyCompany("")] +[assembly: AssemblyProduct("libbacktrack")] +[assembly: AssemblyCopyright("Copyright © 2009")] +[assembly: AssemblyTrademark("")] +[assembly: AssemblyCulture("")] + +// Setting ComVisible to false makes the types in this assembly not visible +// to COM components. If you need to access a type in this assembly from +// COM, set the ComVisible attribute to true on that type. +[assembly: ComVisible(false)] + +// The following GUID is for the ID of the typelib if this project is exposed to COM +[assembly: Guid("a5a6eab1-34ea-463e-85e2-ad7cf5b5aab8")] + +// Version information for an assembly consists of the following four values: +// +// Major Version +// Minor Version +// Build Number +// Revision +// +// You can specify all the values or you can default the Build and Revision Numbers +// by using the '*' as shown below: +// [assembly: AssemblyVersion("1.0.*")] +[assembly: AssemblyVersion("1.0.0.0")] +[assembly: AssemblyFileVersion("1.0.0.0")]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/backtrack.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,39 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using libsemtd; + +namespace libbacktrack +{ + public partial class Backtrack + { + public Backtrack() { throw new NotImplementedException(); } + public Backtrack(string graphType, int numVerMain, int numVerDef, int firstLabel, bool isRecurseAll) + { + this.result = ""; + this.myGraph = new Semtd(graphType, numVerMain, numVerDef); + this.labelVerUsed = new bool[this.myGraph.NumVerTotal + 1]; + this.isRecurseAll = isRecurseAll; + setLabel(0, firstLabel); + this.firstLabel = firstLabel; + this.pathLabel = this.pathStart = this.pathEnd = 0; + switch (graphType) + { + case "fan": + { + this.pathStart = 1; + this.pathEnd = this.myGraph.NumVerMain - 1; + break; + } + case "wheel": + case "doubefan": + { + this.pathStart = 2; + this.pathEnd = this.myGraph.NumVerMain - 1; + break; + } + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/basic.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,16 @@ +namespace libbacktrack +{ + public partial class Backtrack + { + private void setLabel(int verPos,int verLabel) + { + this.labelVerUsed[verLabel] = true; + this.myGraph.LabelSetVer(verPos, verLabel); + } + private void removeLabel(int verPos) + { + this.labelVerUsed[this.myGraph.LabelVer[verPos]] = false; + this.myGraph.LabelRemoveVer(verPos); + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/globals.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,15 @@ +using libsemtd; + +namespace libbacktrack +{ + public partial class Backtrack + { + private bool[] labelVerUsed; + private bool isProcessing; + private bool isSemt; + private bool isRecurseAll; + private string result; + private int firstLabel,pathStart,pathEnd,pathLabel; + private Semtd myGraph; + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/libbacktrack.csproj Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,69 @@ +<?xml version="1.0" encoding="utf-8"?> +<Project ToolsVersion="3.5" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> + <PropertyGroup> + <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> + <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> + <ProductVersion>9.0.30729</ProductVersion> + <SchemaVersion>2.0</SchemaVersion> + <ProjectGuid>{3E6EC10D-A9CE-4542-9931-D004955771F7}</ProjectGuid> + <OutputType>Library</OutputType> + <AppDesignerFolder>Properties</AppDesignerFolder> + <RootNamespace>libbacktrack</RootNamespace> + <AssemblyName>libbacktrack</AssemblyName> + <TargetFrameworkVersion>v3.5</TargetFrameworkVersion> + <FileAlignment>512</FileAlignment> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> + <DebugSymbols>true</DebugSymbols> + <DebugType>full</DebugType> + <Optimize>false</Optimize> + <OutputPath>bin\Debug\</OutputPath> + <DefineConstants>DEBUG;TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> + <DebugType>pdbonly</DebugType> + <Optimize>true</Optimize> + <OutputPath>bin\Release\</OutputPath> + <DefineConstants>TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <ItemGroup> + <Reference Include="System" /> + <Reference Include="System.Core"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Xml.Linq"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data.DataSetExtensions"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data" /> + <Reference Include="System.Xml" /> + </ItemGroup> + <ItemGroup> + <Compile Include="backtrack.cs" /> + <Compile Include="basic.cs" /> + <Compile Include="globals.cs" /> + <Compile Include="Properties\AssemblyInfo.cs" /> + <Compile Include="public.cs" /> + <Compile Include="walk.cs" /> + </ItemGroup> + <ItemGroup> + <ProjectReference Include="..\libsemtd\libsemtd.csproj"> + <Project>{3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}</Project> + <Name>libsemtd</Name> + </ProjectReference> + </ItemGroup> + <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> + <!-- To modify your build process, add your task inside one of the targets below and uncomment it. + Other similar extension points exist, see Microsoft.Common.targets. + <Target Name="BeforeBuild"> + </Target> + <Target Name="AfterBuild"> + </Target> + --> +</Project> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/public.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,9 @@ +namespace libbacktrack +{ + public partial class Backtrack + { + public bool IsSemt { get { return this.isSemt; } } + public string Result { get { return this.result; } } + public void Walk() { walk(); } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libbacktrack/walk.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,72 @@ +using System.Collections.Generic; + +namespace libbacktrack +{ + public partial class Backtrack + { + private void walk() + { + if (this.myGraph.MinDef() <= this.myGraph.NumVerDef) + { + this.isProcessing = true; + walk(1); + } + } + private void walk(int currentLevel) + { + if (this.isProcessing) + { + if (currentLevel >= this.myGraph.NumVerMain) + { + if (this.myGraph.IsSemt()) + { + if (!this.isRecurseAll) + this.isProcessing = false; + this.result += this.myGraph.Print(0); + this.result += "\n" + this.myGraph.Print(1)+"\n"; + this.isSemt = true; + } + removeLabel(currentLevel - 1); + } + else + { + List<int> availableLabels = new List<int>(); + int start = 1, end = this.myGraph.NumVerTotal; + if (currentLevel == 1 && this.firstLabel != this.myGraph.NumVerTotal) + { + if (this.myGraph.GraphType == "wheel") + start = end; //optimization for wheel + else if (this.myGraph.GraphType == "doublefan") + start = this.firstLabel + 1; //optimization for doublefan + } + else if (this.pathStart != 0) + { + if (currentLevel == this.pathEnd) + start = this.pathLabel + 1; //remove possibility for reversed path labeling + else if (currentLevel == this.pathStart && start < end) + end = this.myGraph.NumVerTotal - 1; //no need to test last label as it'll be checked already on all previous cases + } + for (int i = start; i <= end; i++) + if (!this.labelVerUsed[i]) + availableLabels.Add(i); + if (availableLabels.Count > 0) + { + for (int x = availableLabels.Count - 1; x >= 0; x--) + { + if (currentLevel == this.pathStart && this.pathStart != 0) + this.pathLabel = availableLabels[x]; + if (this.myGraph.IsValidToLabel(currentLevel, availableLabels[x])) + { + setLabel(currentLevel, availableLabels[x]); + walk(currentLevel + 1); + } + if (!this.isProcessing) + break; + } + } + if (currentLevel != 1) { removeLabel(currentLevel - 1); } + } + } + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/Properties/AssemblyInfo.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,36 @@ +using System.Reflection; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +// General Information about an assembly is controlled through the following +// set of attributes. Change these attribute values to modify the information +// associated with an assembly. +[assembly: AssemblyTitle("libsemtd")] +[assembly: AssemblyDescription("")] +[assembly: AssemblyConfiguration("")] +[assembly: AssemblyCompany("")] +[assembly: AssemblyProduct("libsemtd")] +[assembly: AssemblyCopyright("Copyright © 2009")] +[assembly: AssemblyTrademark("")] +[assembly: AssemblyCulture("")] + +// Setting ComVisible to false makes the types in this assembly not visible +// to COM components. If you need to access a type in this assembly from +// COM, set the ComVisible attribute to true on that type. +[assembly: ComVisible(false)] + +// The following GUID is for the ID of the typelib if this project is exposed to COM +[assembly: Guid("b6b3e2de-ffb2-4e08-af83-eee98bcb9a0b")] + +// Version information for an assembly consists of the following four values: +// +// Major Version +// Minor Version +// Build Number +// Revision +// +// You can specify all the values or you can default the Build and Revision Numbers +// by using the '*' as shown below: +// [assembly: AssemblyVersion("1.0.*")] +[assembly: AssemblyVersion("1.0.0.0")] +[assembly: AssemblyFileVersion("1.0.0.0")]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/Semtd.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,46 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; + +namespace libsemtd +{ + public partial class Semtd + { + public Semtd() + { + throw new NotSupportedException(); + } + public Semtd(string graphType, int numVerMain, int numVerDef) + { + switch (graphType) + { + case "wheel": + case "fan": + case "doublefan": + { + this.graphType = graphType; + break; + } + default: + { + throw new NotSupportedException(); + } + } + if ((numVerDef < 0) || (numVerMain < 4)) + { + throw new NotSupportedException(); + } + else + { + this.numVerMain = numVerMain; + this.numVerDef = numVerDef; + this.numVerTotal = this.numVerMain + this.numVerDef; + } + this.numEdges = 0; + this.graphConn = new bool[this.numVerMain, this.numVerMain]; + draw(this.graphType, 0, this.numVerMain - 1); + labelReset(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/ga.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,108 @@ +/*using System; + +namespace libsemtd +{ + public partial class Semtd + { + private void ga_LabelRemoveVer(int posVer) { this.labelVer[posVer] = 0; } + private void ga_LabelSetVer(int posVer, int labelVer) { this.labelVer[posVer] = labelVer; } + private double ga_ScoreAlgorithm(int start, int end, params int[] numbers) + { + //STANDARD DEVIATION + double mean = 0; + double nstdev = 0; + int numData = end - start + 1; + foreach (double num in numbers) + { + mean += num; + } + mean /= numData; + for (int i = start; i <= end; i++) + { + nstdev += Math.Pow((numbers[i] - mean), 2); + } + return Math.Sqrt(nstdev / numData); + } + private double ga_SemtScore() + { + if (this.scoreCache > -1) { return scoreCache; } + if (this.IsSemt()) { return 0; } + int rangeDelta = this.numEdges - this.labelRangeEdge(); + int upperBound = this.labelEdgeAbsoluteMax; + int edgeTempMax = this.labelEdgeMax; + int edgeTempMin = this.labelEdgeMin; + int[] edgeTempLabels = new int[upperBound + 1]; + if (rangeDelta > 0) + { + if ((edgeTempMax + rangeDelta) > upperBound) + { + edgeTempMax = upperBound; + edgeTempMin -= upperBound - edgeTempMax; + } + else + { + edgeTempMax += rangeDelta; + } + } + for (int i = 0; i < upperBound; i++) + { + edgeTempLabels[i] = this.labelEdgesUsed[i]; + } + this.scoreCache = ga_ScoreAlgorithm(edgeTempMin, edgeTempMax, edgeTempLabels); + return scoreCache; + } + private void ga_FixLabel() + { + bool[] labelVerUsed = new bool[this.numVerTotal+ 1]; + bool[] verPassed = new bool[this.numVerMain + 1]; + for (int i = 0; i < this.numVerMain; i++) + { + if (!labelVerUsed[this.labelVer[i]]) + { + labelVerUsed[this.labelVer[i]] = true; + verPassed[i] = true; + } + } + for (int i = 0; i < this.numVerMain; i++) + { + if (!verPassed[i]) + { + for (int nextLabel = 0; nextLabel < this.numVerMain; nextLabel++) + { + if (!labelVerUsed[nextLabel]) + { + this.labelVer[i] = nextLabel; + verPassed[i] = true; + labelVerUsed[nextLabel] = true; + break; + } + } + } + } + } + private void ga_SwapLabel() + { + Random random = new Random(); + int verA, verB, labelVerTemp; + verA = random.Next(this.numVerMain); + verB = verA; + while (verA == verB) + { + verB = random.Next(1, this.numVerMain); + } + labelVerTemp = this.labelVer[verA]; + this.labelSetVer(verA, this.labelVer[verB]); + this.labelSetVer(verB, labelVerTemp); + } + private bool ga_IsSemt() + { + int[] labelVerTemp = new int[this.numVerMain]; + for(int i=0;i<this.numVerMain;i++) + labelVerTemp[i] = this.labelVer[i]; + labelReset(); + for (int i = 0; i < this.numVerMain; i++) + labelSetVer(i, labelVerTemp[i]); + return isSemt(); + } + } +}*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/globals.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,15 @@ +namespace libsemtd +{ + public partial class Semtd + { + private int numVerMain, numVerDef, numVerTotal; + private int numEdges; + private string graphType; + private bool[,] graphConn; + private int[] labelVer; + private int[,] labelEdges; + private int[] labelEdgesUsed; + private int labelEdgeMin, labelEdgeMax, labelEdgeAbsoluteMax; + //private double scoreCache; + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/graph.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,63 @@ +namespace libsemtd +{ + public partial class Semtd + { + private void draw(string graphType, int start, int end, params int[] ver_others) + { + if (end < start) + { + int temp = start; + start = end; + end = temp; + } + switch (graphType) + { + case "path": + { + for (int i = start; i < end; i++) + connectVertices(i, i + 1); + break; + } + case "cycle": + { + draw("path", start, end); + connectVertices(start, end); + break; + } + case "completebipartite": + { + for (int i = start; i <= end; i++) + foreach (int other in ver_others) + connectVertices(i, other); + break; + } + case "wheel": + { + draw("cycle", start + 1, end); + draw("completebipartite", start + 1, end, start); + break; + } + case "fan": + { + draw("path", start + 1, end); + draw("completebipartite", start + 1, end, start); + break; + } + case "doublefan": + { + draw("path", start + 2, end); + draw("completebipartite", start + 2, end, start, start + 1); + break; + } + } + } + private void connectVertices(int a, int b) + { + if (!this.graphConn[a, b]) + { + this.graphConn[a, b] = this.graphConn[b, a] = true; + this.numEdges++; + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/label.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,138 @@ +namespace libsemtd +{ + partial class Semtd + { + private void labelReset() + { + this.labelVer = new int[this.numVerMain]; + this.labelEdges = new int[this.numVerMain, this.numVerMain]; + this.labelEdgeAbsoluteMax = 2 * this.numVerTotal - 1; + this.labelEdgesUsed = new int[this.labelEdgeAbsoluteMax + 1]; + //this.scoreCache = -1; + } + private int labelRangeEdge() + { + labelRefreshEdgeMinMax(); + return this.labelEdgeMax - this.labelEdgeMin + 1; + } + private void labelRefreshEdgeMinMax() + { + for (int i = 1; i <= this.labelEdgeAbsoluteMax; i++) + { + if (this.labelEdgesUsed[i] > 0) + { + this.labelEdgeMin = i; + break; + } + } + for (int i = this.labelEdgeAbsoluteMax; i >= 1; i--) + { + if (this.labelEdgesUsed[i] > 0) + { + this.labelEdgeMax = i; + break; + } + } + } + private void labelRemoveVer(int posVer) + { + if (this.labelVer[posVer] > 0) + { + this.labelVer[posVer] = 0; + labelRemoveEdges(posVer); + } + } + private void labelRemoveEdges(int posVer) + { + for (int i = 0; i < this.numVerMain; i++) + { + if (this.labelVer[i] > 0 && i != posVer && this.graphConn[posVer, i]) + { + int labelOld = this.labelEdges[i, posVer]; + this.labelEdgesUsed[labelOld]--; + this.labelEdges[i, posVer] = this.labelEdges[posVer, i] = 0; + } + } + } + private void labelSetVer(int posVer, int labelVer) + { + if (this.labelVer[posVer] > 0) { labelRemoveVer(posVer); } + this.labelVer[posVer] = labelVer; + labelSetEdges(posVer); + } + private void labelSetEdges(int posVer) + { + int labelNew; + for (int i = 0; i < this.numVerMain; i++) + if (i != posVer && + this.graphConn[posVer, i] && + this.labelVer[i] > 0) + { + labelNew = this.labelVer[posVer] + this.labelVer[i]; + this.labelEdges[i, posVer] = this.labelEdges[posVer, i] = labelNew; + this.labelEdgesUsed[labelNew]++; + } + } + private bool isValidToLabel(int posVer, int labelVer) + { + for (int i = 0; i < this.numVerMain; i++) + { + if (this.graphConn[i, posVer] && + this.labelVer[i] > 0 && + this.labelEdgesUsed[this.labelVer[i] + labelVer] == 1) + { + return false; + } + } + return true; + } + private bool isSemt() + { + if (labelRangeEdge() == numEdges) + { + for (int i = this.labelEdgeMin; i <= this.labelEdgeMax; i++) + { + if (this.labelEdgesUsed[i] != 1) + { + return false; + } + } + return true; + } + return false; + } + private int minDef() + { + int ret = 0; + switch (this.graphType) + { + case "wheel": //source: dissertation[1] + switch (this.numVerMain) + { + case 3 | 4 | 6 | 7: + ret = 1; + break; + default: + ret = 2; + break; + } + break; + case "fan": //source: dissertation[1] + if (this.numVerMain <= 7) + ret = 0; + else + ret = 1; + break; + case "doublefan": //source: dissertation[1] + ret = (this.numVerMain - 1) / 2; + break; + default: + // ret = Convert.ToInt32(Math.Ceiling(Convert.ToDecimal(this.numEdges / 2))) + 2 - this.numVertices; + //break; + ret = -1; + break; + } + return ret; + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/libsemtd.csproj Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,65 @@ +<?xml version="1.0" encoding="utf-8"?> +<Project ToolsVersion="3.5" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> + <PropertyGroup> + <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> + <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> + <ProductVersion>9.0.30729</ProductVersion> + <SchemaVersion>2.0</SchemaVersion> + <ProjectGuid>{3CEAFAC3-F7C9-4379-AC2E-F26BDE25E8AE}</ProjectGuid> + <OutputType>Library</OutputType> + <AppDesignerFolder>Properties</AppDesignerFolder> + <RootNamespace>libsemtd</RootNamespace> + <AssemblyName>libsemtd</AssemblyName> + <TargetFrameworkVersion>v3.5</TargetFrameworkVersion> + <FileAlignment>512</FileAlignment> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> + <DebugSymbols>true</DebugSymbols> + <DebugType>full</DebugType> + <Optimize>false</Optimize> + <OutputPath>bin\Debug\</OutputPath> + <DefineConstants>DEBUG;TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> + <DebugType>pdbonly</DebugType> + <Optimize>true</Optimize> + <OutputPath>bin\Release\</OutputPath> + <DefineConstants>TRACE</DefineConstants> + <ErrorReport>prompt</ErrorReport> + <WarningLevel>4</WarningLevel> + </PropertyGroup> + <ItemGroup> + <Reference Include="System" /> + <Reference Include="System.Core"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Xml.Linq"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data.DataSetExtensions"> + <RequiredTargetFramework>3.5</RequiredTargetFramework> + </Reference> + <Reference Include="System.Data" /> + <Reference Include="System.Xml" /> + </ItemGroup> + <ItemGroup> + <Compile Include="ga.cs" /> + <Compile Include="globals.cs" /> + <Compile Include="graph.cs" /> + <Compile Include="label.cs" /> + <Compile Include="print.cs" /> + <Compile Include="public.cs" /> + <Compile Include="Semtd.cs" /> + <Compile Include="Properties\AssemblyInfo.cs" /> + </ItemGroup> + <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> + <!-- To modify your build process, add your task inside one of the targets below and uncomment it. + Other similar extension points exist, see Microsoft.Common.targets. + <Target Name="BeforeBuild"> + </Target> + <Target Name="AfterBuild"> + </Target> + --> +</Project> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/print.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,221 @@ +namespace libsemtd +{ + public partial class Semtd + { + private string sep = " | "; + private string print(int mode) + { + return printBasic() + sep + + printMagicNum(mode) + sep + + printLabels(mode) + sep + + printDef(mode) + sep + + printMisc(mode); + } + private string printBasic() + { + string ret = ""; + ret += "graph: " + this.graphType + + sep + + "edges: " + this.numEdges.ToString() + + sep + + "vertices: " + this.numVerMain.ToString() + + sep + + "deficiencies: " + this.numVerDef.ToString(); + return ret; + } + private string printMagicNum(int mode) + { + string ret = ""; + int edgeWeight, edgeLabel; + edgeLabel = edgeWeight = 0; + for (int i = 1; i <= this.labelEdgeAbsoluteMax; i++) + { + if (this.labelEdgesUsed[i] > 0) + { + edgeWeight = i; + edgeLabel = this.numEdges + this.numVerTotal; + break; + } + } + if (mode == 1) + { + edgeWeight = 2 * (this.numVerTotal) + 2 - edgeWeight; + edgeLabel = 2 * this.numVerTotal + this.numEdges + 1 - edgeLabel; + } + ret += "mnum: " + (edgeWeight + edgeLabel).ToString(); + return ret; + } + private string printLabels(int mode) + { + string ret = ""; + int[] myLabelVer = new int[this.NumVerMain]; + for (int i = 0; i < this.NumVerMain; i++) + { + if (mode == 1) + { + myLabelVer[i] = this.numVerTotal + 1 - this.labelVer[i]; + } + else + { + myLabelVer[i] = this.labelVer[i]; + } + } + if (this.graphType == "doublefan" && myLabelVer[0] > myLabelVer[1]) + { + int temp = myLabelVer[0]; + myLabelVer[0] = myLabelVer[1]; + myLabelVer[1] = temp; + } + int startPath=0; + int endPath=0; + switch (graphType) + { + case "fan": + { + startPath = 1; + endPath=this.numVerMain-1; + break; + } + case "doublefan": + case "wheel": + { + startPath = 2; + endPath=this.numVerMain-1; + break; + } + } + if (startPath > 0 && myLabelVer[startPath] > myLabelVer[endPath]) + { + int a = startPath, b = endPath; + while (a < b) + { + int temp = myLabelVer[a]; + myLabelVer[a] = myLabelVer[b]; + myLabelVer[b] = temp; + a++; b--; + } + } + for (int i = 0; i < this.numVerMain; i++) + { + int myLabel=myLabelVer[i]; + if (i == 0) + switch (graphType) + { + case "wheel": + { + ret += "c: " + myLabel.ToString() + + sep + + "l: "; + break; + } + case "fan": + { + ret += "c: " + myLabel.ToString() + + sep + + "p: "; + break; + } + case "doublefan": + { + ret += "c: " + myLabel.ToString() + ","; + break; + } + } + else if (i == 1 && this.graphType == "doublefan") + { + ret += myLabel.ToString() + + sep + + "p: "; + } + else if (i == this.numVerMain-1) + ret += myLabel.ToString(); + else + ret += myLabel.ToString() + ","; + } + return ret; + } + private string printDef(int mode) + { + string ret = ""; + if (this.numVerDef > 0) + { + ret += "def: "; + bool[] labelVerUsed = new bool[this.numVerTotal + 1]; + for (int i = 0; i < this.numVerMain; i++) + labelVerUsed[this.labelVer[i]] = true; + int amountDef = 0; + for (int i = 1; i <= this.numVerTotal; i++) + { + int myDef; + if (!labelVerUsed[i]) + { + if (mode == 1) + myDef = this.numVerTotal + 1 - i; + else + myDef = i; + if (amountDef == this.numVerDef - 1) + { + ret += myDef.ToString(); + break; + } + else + { + ret += myDef.ToString() + ","; + amountDef++; + } + } + } + } + return ret; + } + private string printMisc(int mode) + { + string ret = ""; + if (this.graphType == "wheel" || this.graphType == "fan" || this.graphType == "doublefan") + { + int startPath, endPath; + startPath = 0; + switch (this.graphType) + { + case "fan": + { + startPath = 1; + break; + } + case "wheel": + case "doublefan": + { + startPath = 2; + break; + } + } + endPath = this.numVerMain-1; + bool isConstant = true; + for (int i = startPath; i < endPath; i++) + { + if (mode == 0) + { + if (this.labelVer[i] > this.labelVer[i + 1]) + { + isConstant = false; + break; + } + } + else if (mode == 1) + { + if (this.labelVer[i] < this.labelVer[i + 1]) + { + isConstant = false; + break; + } + } + } + if (isConstant) + ret += "constant"; + } + if (mode == 1) + ret += "dual"; + return ret; + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/defical-sharp/libsemtd/public.cs Fri Apr 02 23:11:57 2010 +0700 @@ -0,0 +1,20 @@ +namespace libsemtd +{ + public partial class Semtd + { + public int[] LabelVer { get { return this.labelVer; } } + public int NumVerTotal { get { return this.numVerTotal; } } + public int NumVerMain { get { return this.numVerMain; } } + public int NumVerDef { get { return this.numVerDef; } } + public string GraphType { get { return this.graphType; } } + public void LabelSetVer(int posVer, int labelVer) { labelSetVer(posVer, labelVer); } + public void LabelRemoveVer(int posVer) { labelRemoveVer(posVer); } + public bool IsSemt() { return isSemt(); } + public string Print(int mode) { return print(mode); } + public bool IsValidToLabel(int posVer, int labelVer) { return isValidToLabel(posVer, labelVer); } + public int MinDef() { return minDef(); } + /*public void GA_FixLabel() { ga_FixLabel(); } + public double GA_SemtScore() { return ga_SemtScore(); } + public void GA_SwapLabel() { ga_SwapLabel(); }*/ + } +} \ No newline at end of file