00001
00002 STATIC void phase2_down (void)
00003 { int i, j;
00004 int cross;
00005 gs_wait_message ('B');
00006 if (phase2_startlevel <= maxdepth)
00007 for (i = phase2_startlevel; i <= maxdepth; i++) {
00008 if (G_timelimit > 0) if (tesst_timelimit (60)) {gs_wait_message ('t'); break; }
00009 level_to_array (i, 'u');
00010 switch (crossing_heuristics)
00011 {
00012 case 0:for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = succbary (sort_array[j]); break;
00013 case 1:for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = succmedian (sort_array[j]); break;
00014 case 2:for (j = 0;j< ((layer[i]).anz); j++) ((sort_array[j])->bary) = succbary (sort_array[j]) + succmedian (sort_array[j]) / 10000.0; break;
00015 case 3:for (j = 0;j< ((layer[i]).anz); j++) ((sort_array[j])->bary) = succmedian (sort_array[j]) + succbary (sort_array[j]) / 10000.0; break;
00016 }
00017 if (((layer[i]).anz)) qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary);
00018
00019
00020 if (cycle_sort_array (((layer[i]).anz)))
00021 {
00022 array_to_level (i);
00023 if (((layer[i]).resort_necessary)) apply_horder (i);
00024 if (i > 0) ((tmp_layer[i - 1]).cross) = layer_crossing (i - 1);
00025 if (i <= maxdepth) ((tmp_layer[i]).cross) = layer_crossing (i);
00026 resort_up_down_layer (i);
00027 cross = graph_crossings ();
00028 if (cross < nr_crossings) {
00029 phase2_startlevel = i + 1;
00030 return;
00031 }
00032 }
00033 }
00034 for (i = 0; (i < phase2_startlevel) && (i <= maxdepth); i++) {
00035 if (G_timelimit > 0) if (test_timelimit (60)) { gs_wait_message ('t'); break; }
00036 level_to_array (i, 'u');
00037 switch (crossing_heuristics) {
00038 case 0:for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]); break;
00039 case 1:for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predmedian (sort_array[j]); break;
00040 case 2: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]) + predmedian (sort_array[j]) / 10000.0; break;
00041 case 3: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predmedian (sort_array[j]) + predbary (sort_array[j]) / 10000.0; break;
00042 }
00043 if (((layer[i]).anz)) qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary);
00044 if (cycle_sort_array (((layer[i]).anz))) {
00045 array_to_level (i);
00046 if (((layer[i]).resort_necessary)) apply_horder (i);
00047 if (i > 0) ((tmp_layer[i - 1]).cross) = layer_crossing (i - 1);
00048 if (i <= maxdepth) ((tmp_layer[i]).cross) = layer_crossing (i);
00049 resort_up_down_layer (i);
00050 cross = graph_crossings ();
00051 if (cross < nr_crossings)
00052 {
00053 phase2_startlevel = i + 1; return;
00054 }
00055 }
00056 }
00057 }
00058
00059 STATIC void phase2_up (void)
00060 {
00061 int i, j;
00062 int cross; ;
00063 gs_wait_message ('B');
00064 if (phase2_startlevel > 0) for (i = phase2_startlevel; i > 0; i--) {
00065 if (G_timelimit > 0) if (test_timelimit (60)) { gs_wait_message ('t'); break; }
00066 level_to_array (i, 'd');
00067 switch (crossing_heuristics)
00068 {
00069 case 0: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]); break;
00070 case 1: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predmedian (sort_array[j]); break;
00071 case 2: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]) + predmedian (sort_array[j]) / 10000.0; break;
00072 case 3: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = succmedian (sort_array[j]) + predbary (sort_array[j]) / 10000.0; break;
00073 }
00074 { if (((layer[i]).anz)) qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary); } ;
00075 if (cycle_sort_array (((layer[i]).anz)))
00076 {
00077 array_to_level (i);
00078 if (((layer[i]).resort_necessary)) apply_horder (i);
00079 if (i > 0) ((tmp_layer[i - 1]).cross) = layer_crossing (i - 1);
00080 if (i <= maxdepth) ((tmp_layer[i]).cross) = layer_crossing (i);
00081 resort_down_up_layer (i);
00082 cross = graph_crossings ();
00083 if (cross < nr_crossings)
00084 {
00085
00086 phase2_startlevel = i - 1; return;
00087 }
00088 }
00089 }
00090 for (i = maxdepth + 1; (i > phase2_startlevel) && (i > 0); i--)
00091 {
00092 if (G_timelimit > 0) if (test_timelimit (60)) { gs_wait_message ('t'); break; }
00093 level_to_array (i, 'd');
00094 switch (crossing_heuristics)
00095 {
00096 case 0: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]);
00097 break;
00098 case 1: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predmedian (sort_array[j]); break;
00099 case 2: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predbary (sort_array[j]) + predmedian (sort_array[j]) / 10000.0; break;
00100 case 3: for (j = 0; j < ((layer[i]).anz); j++) ((sort_array[j])->bary) = predmedian (sort_array[j]) + predbary (sort_array[j]) / 10000.0; break;
00101 }
00102 { if (((layer[i]).anz)) qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary); }
00103 ;
00104 if (cycle_sort_array (((layer[i]).anz))) {
00105 array_to_level (i);
00106 if (((layer[i]).resort_necessary))
00107 apply_horder (i);
00108 if (i > 0) ((tmp_layer[i - 1]).cross) = layer_crossing (i - 1);
00109 if (i <= maxdepth) ((tmp_layer[i]).cross) = layer_crossing (i);
00110 resort_down_up_layer (i);
00111 cross = graph_crossings ();
00112 if (cross < nr_crossings) {
00113 phase2_startlevel = i - 1;
00114 return;
00115 }
00116 }
00117 }
00118 }
