00001
00002
00003 #define C_WEIGHT 256.0
00004 #define BARYTYPE float
00005 #define BARYTYPECAST (float)
00006
00007
00008 #define EVAL_BARY(CASEID,VALUE_EXPR) case CASEID: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = (VALUE_EXPR);break;
00009
00010 #define DEFINE_CASES(DIR) \
00011 switch(crossing_heuristics) { \
00012 EVAL_BARY(CROSSING_BARY ,DIR ## bary (sort_array[j]))\
00013 EVAL_BARY(CROSSING_MEDIAN ,DIR ##median (sort_array[j]))\
00014 EVAL_BARY(CROSSING_BARYMEDIAN ,DIR ##bary (sort_array[j])+DIR ##median (sort_array[j])/10000.0)\
00015 EVAL_BARY(CROSSING_MEDIANBARY ,DIR ##median (sort_array[j])+DIR##bary (sort_array[j])/10000.0) }
00016
00017 #define PREBLOCK if (G_timelimit > 0)if (test_timelimit (60)){gs_wait_message ('t');} \
00018 level_to_array (i, 'u');
00019
00020 #define QSORTLAYER() \
00021 if (((layer[i]).anz)) qsort ( \
00022 sort_array, ((layer[i]).anz), sizeof (GNODE), \
00023 (int (*)(const void *, const void *)) compare_bary);
00024
00025 #define POST(PHASE,SORT_DIR) \
00026 QSORTLAYER() \
00027 if (cycle_sort_array (((layer[i]).anz))) { \
00028 array_to_level (i); \
00029 if (((layer[i]).resort_necessary)) apply_horder (i); \
00030 if (i > 0) ((tmp_layer[i - 1]).cross) = layer_crossing (i - 1); \
00031 if (i <= maxdepth) ((tmp_layer[i]).cross) = layer_crossing (i); \
00032 \
00033 resort_## SORT_DIR ## _layer (i); \
00034 \
00035 cross = graph_crossings (); \
00036 if (cross < nr_crossings){ \
00037 phase## PHASE ##_startlevel \
00038 = i + 1;checkcrossing (cross);return;} \
00039 }
00040
00041 #define apply_eval_crossing_to_levels(BARYCASE) { \
00042 for (i = phase2_startlevel; i > 0; i--) { \
00043 PREBLOCK \
00044 BARYCASE \
00045 check_for_cycles(i); \
00046 POST(2,down_up) \
00047 } \
00048 }
00049
00050 #define PTR2(X,Y) (X -> Y)
00051 #define GETDIR(X) (node-> X)
00052
00053 #define GENERICBARY(NAME,DEGREEDIR,NEXTDIR,ANCHOR) \
00054 STATIC BARYTYPE NAME (GNODE node){ \
00055 int Sum; \
00056 ADJEDGE w; \
00057 if (GETDIR(DEGREEDIR) == 0) return (0.0); \
00058 Sum = 0; \
00059 w = GETDIR(NEXTDIR); \
00060 while (w) \
00061 { \
00062 Sum += (C_WEIGHT * (PTR2(w->kante,ANCHOR)->position)); \
00063 Sum += (w->kante->anchor); w = w->next; \
00064 } \
00065 return ((BARYTYPECAST Sum) / (BARYTYPECAST (C_WEIGHT * GETDIR(DEGREEDIR)))); \
00066 }
00067
00068 #define GENERICMEDIAN(NAME,DEGREEDIR,NEXTDIR,ANCHOR,OPERATOR) STATIC BARYTYPE NAME (GNODE node) \
00069 { \
00070 int i, leftpart, rightpart; ADJEDGE w; ; ; \
00071 switch (( GETDIR(DEGREEDIR) )) { \
00072 case 0: return (0.0); \
00073 break; \
00074 case 1: return ((BARYTYPECAST(node->NEXTDIR->kante->ANCHOR->position) ) \
00075 OPERATOR \
00076 (BARYTYPECAST(node->NEXTDIR->kante->anchor)) / C_WEIGHT); \
00077 break; \
00078 case 2: \
00079
00080
00081
00082
00083 \
00084 break; \
00085 return ((BARYTYPECAST \
00086 (node->NEXTDIR->kante->ANCHOR->position) + \
00087 (node->NEXTDIR->next->kante->ANCHOR->position)) / 2.0); \
00088 } \
00089 i = 0; w = ((node)->NEXTDIR); \
00090 while (w) { save_array[i++] = (((((w)->kante))->ANCHOR)); w = ((w)->next); } \
00091 if (i) qsort (save_array, i, sizeof (GNODE), (int (*)(const void *, const void *)) compare_pos); \
00092 if (i % 2) return (BARYTYPECAST ((save_array[i / 2])->position)); \
00093 leftpart = ((save_array[i / 2 - 1])->position) - ((save_array[0])->position); \
00094 rightpart = ((save_array[i - 1])->position) - ((save_array[i / 2])->position); \
00095 return ((BARYTYPECAST (((save_array[i / 2 - 1])->position) * \
00096 rightpart + ((save_array[i / 2])->position) \
00097 * leftpart)) \
00098 / (BARYTYPECAST (leftpart + rightpart))); \
00099 }
00100
00101
00102 #define PHASE(NUMBER,DIR,FIRST,SECOND,POSTDATA) \
00103 void STATIC phase ## NUMBER ## _ ## DIR () { \
00104 int i, j; \
00105 int cross; \
00106 gs_wait_message ('B'); \
00107 if (phase2_startlevel <= maxdepth)for (i = phase2_startlevel; i <= maxdepth; i++) { \
00108 PREBLOCK; \
00109 FIRST \
00110 POSTDATA \
00111 } \
00112 for (i = 0; (i < phase2_startlevel) && (i <= maxdepth); i++) { \
00113 PREBLOCK; \
00114 SECOND \
00115 POSTDATA \
00116 } \
00117 }
00118 #define BARY_CASE(X) DEFINE_CASES(X)
00119 #define RESORT_DOWN_LAYER DEFINE_CASES(pred)
00120 #define RESORT_UP_LAYER DEFINE_CASES(succ)
00121
00122
00123
00124
00125 #define RESORT_FUNCTION(DIR,DIRECTIONL,DIRECTION2,INDEX,INDEX2) \
00126 STATIC int resort_## DIR ##_layer (int i){ \
00127 int c; int j; \
00128 level_to_array (INDEX, DIRECTIONL); \
00129 BARY_CASE(DIRECTION2) \
00130 QSORTLAYER() \
00131 save_level (INDEX); \
00132 array_to_level (INDEX); \
00133 if (((layer[INDEX]).resort_necessary)) apply_horder (INDEX); \
00134 c = layer_crossing (i); \
00135 if (c <= ((tmp_layer[i]).cross)) { \
00136 ((tmp_layer[i]).cross) = c; \
00137 if (i > 0) ((tmp_layer[INDEX2]).cross) = layer_crossing (INDEX2); \
00138 return (1); \
00139 } \
00140 restore_level (INDEX); \
00141 return (0); \
00142 }
00143
