#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include <time.h> #include <unistd.h> #include <ctype.h> #ifndef __USE_POSIX #define __USE_POSIX #endif #include <signal.h> #include <time.h> #include "decompose.h" #include "graph.h" #include "lire.h" #include "lists.h" #include "main.h" #include "separator.h" #include "utils.h" volatile sig_atomic_t stopSearch = 0; char file_name[555], *last_name; FILE *fileSolution = NULL; #ifdef PACE_2020 int pace_2020 = 1; #else int pace_2020 = 0; #endif int nb_runs = 100000; int algo = SEPARE_AND_EXPLORE ; //SEPARE_AND_EXPLORE; GREEDY_ALGORITHM int noSwapsInFirstRuns = 0; // Do not improve for the first explorations int timeWithNoSwaps = 50; // proportion of the total time with no improvement int sizeSwitchToGreedy = 0; // switch to greedy algorithm when nb vertices is les than this. int preliminaryGreedyDecomposition = 0; // perform a preliminary greedy search, int maxSizePrelimGreedy = 350000; //350000; for instance heur_187 int maxDepthGreedy = 777; //25000; int depthThreshold = 1; // threshold above which the current run is abandoned, compared with the best first height int perForceChoiceNotInC = NONE; // Initialized before each separation if modeEvalAtRandom is true int perChooseInCAtRandom = 1; // Choice in C at random int nbRunsSeparation = 30; // 1 or 5 int nbFlushes = 101; // default is 100, int ratioMin = 5; // min=5 max=55 int ratioMax = 55; // too small ratioMax stops the flush (>50) int modeEvalSeparator = EVAL_CARD; // EVAL_SQRT_CARD EVAL_TREE_HEIGHT_COMPLETE_GRAPH EVAL_MINIMIZE_C EVAL_CARD EVAL_MIN_A_B double coeffHeightNbEdges = 2.0; // coefficient used to estimate the height for a given number of edges. Ponderates the evaluation against the cardinal of C. int modeEvalAtRandom = 1; int searchSwapsInCriticalBranch = 1; // improve version april 2020 int pullUpIndependentSubtrees = 1; // before swaps, pull up independent critical subtrees int maxMakeSwapsRestarts = 10; // the number of restarts of the improve process Without height decrease int printStats = 0; int compressTree = 0; // not used int trace = 0; clock_t startTime; int printSolution = 0; int printResult = 1; int time_limit = 30; void term(int signum) { stopSearch = 1; } /*********************************************** * Main * **********************************************/ int main (int nargs, char ** args) { Graph g; FILE *f = stdin; if (1) { struct sigaction action; memset(&action, 0, sizeof(struct sigaction)); action.sa_handler = term; sigaction(SIGTERM, &action, NULL); // signal(SIGTERM, sig_handler); // signal(SIGINT, sig_handler); } srand(time(NULL)); if (pace_2020) { nb_runs = 1000000; //100000; noSwapsInFirstRuns = 0; printSolution = 1; printResult = 0; time_limit = 1811; preliminaryGreedyDecomposition = 1; goto START_SOLVE; } for (int i = 1; i < nargs; i ++) { if (strcmp(args[i], "-file") == 0) { i ++; if (i == nargs) goto USAGE; strcpy(file_name, args[i]); f = fopen(file_name, "r"); if (f == NULL) { printf("unable to open file %s\n", file_name); goto USAGE; } } else if (strcmp(args[i], "-save_solution") == 0) { i ++; if (i == nargs) goto USAGE; fileSolution = fopen(args[i], "w"); if (fileSolution == NULL) { printf("Output abandoned :: unable to open file %s\n", args[i]); goto USAGE; } printSolution = 1; } else if (strcmp(args[i], "-auto") == 0) { noSwapsInFirstRuns = 1; nb_runs = 10000; } else if (strcmp(args[i], "-runs") == 0) { i ++; if (i == nargs) goto USAGE; nb_runs = atoi(args[i]); } else if (strcmp(args[i], "-s") == 0) { i ++; if (i == nargs) goto USAGE; srand(atoi(args[i])); } else if (strcmp(args[i], "-time") == 0) { i ++; if (i == nargs) goto USAGE; time_limit = atoi(args[i]); } else if (strcmp(args[i], "-trace") == 0) { trace = 1; } else if (strcmp(args[i], "-no_solution") == 0) { printSolution = 0; } else if (strcmp(args[i], "-no_improve") == 0) { searchSwapsInCriticalBranch = 0; pullUpIndependentSubtrees = 0; } else if (strcmp(args[i], "-no_pullup") == 0) { pullUpIndependentSubtrees = 0; } else if (strcmp(args[i], "-no_swaps") == 0) { searchSwapsInCriticalBranch = 0; } else if (strcmp(args[i], "-sep_runs") == 0) { i ++; if (i == nargs) goto USAGE; nbRunsSeparation = atoi(args[i]); } else if (strcmp(args[i], "-per_choice_AB") == 0) { i ++; if (i == nargs) goto USAGE; perForceChoiceNotInC = atoi(args[i]); } else if (strcmp(args[i], "-per_chrand_C") == 0) { i ++; if (i == nargs) goto USAGE; perChooseInCAtRandom = atoi(args[i]); } else if (strcmp(args[i], "-flushes") == 0) { i ++; if (i == nargs) goto USAGE; nbFlushes = atoi(args[i]); } else if (strcmp(args[i], "-ratios") == 0) { i ++; if (i == nargs) goto USAGE; ratioMin = atoi(args[i]); i ++; if (i == nargs) goto USAGE; ratioMax = atoi(args[i]); } else if (strcmp(args[i], "-threshold") == 0) { i ++; if (i == nargs) goto USAGE; depthThreshold = atoi(args[i]); } else if (strcmp(args[i], "-eval") == 0) { i ++; if (i == nargs) goto USAGE; modeEvalSeparator = atoi(args[i]); modeEvalAtRandom = 0; } else if (strcmp(args[i], "-tree_height_eval") == 0) { i ++; if (i == nargs) goto USAGE; modeEvalSeparator = EVAL_TREE_HEIGHT_COMPLETE_GRAPH; modeEvalAtRandom = 0; coeffHeightNbEdges = (double) (atoi(args[i])) / 100; } else if (strcmp(args[i], "-greedy") == 0) { algo = GREEDY_ALGORITHM; } else if (strcmp(args[i], "-separe") == 0) { // default algo = SEPARE_AND_EXPLORE; if ((i+1 < nargs) && (isdigit(args[i+1][0]))) { i ++; sizeSwitchToGreedy = atoi(args[i]); } } else goto USAGE; } if (f != stdin) { char *s = file_name; last_name = s; while (*s != '\0') { if (*s == '/') last_name = s+1; s ++; } } START_SOLVE: startTime = clock(); g = lireGraphe(f); if (trace) printf("n=%d m=%d\n", g->n, g->m); testDecompose(g, nb_runs, algo); return 0; USAGE: printf("Usage :: ./treedepth [-file <file name>] [-runs <nb runs>] [-s <number>] [-trace] \\" "[-save_solution <file name>] [-no_solution] [-improve] [-no_improve] [-no_pullup] [-no_swaps]\\" "[-flushes <nb flushes>] [-per_choice_AB <per>] [-per_chrand_C <per>] [-sep_runs <nb runs>] \\" "[-ratios <min> <max>] [-threshold <per>] [-eval <mode>] [-static_eval] [-dynamic_eval] \\" "[-greedy] [-separe [<size to greedy>]] <file name>\n"); return 0; }