THESE/codes/graphe/GCmex1.9/graph.cpp

   1 /* graph.cpp */\r
   2 /*\r
   3     Copyright 2001 Vladimir Kolmogorov (vnk@cs.cornell.edu), Yuri Boykov (yuri@csd.uwo.ca).\r
   4 \r
   5     This program is free software; you can redistribute it and/or modify\r
   6     it under the terms of the GNU General Public License as published by\r
   7     the Free Software Foundation; either version 2 of the License, or\r
   8     (at your option) any later version.\r
   9 \r
  10     This program is distributed in the hope that it will be useful,\r
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13     GNU General Public License for more details.\r
  14 \r
  15     You should have received a copy of the GNU General Public License\r
  16     along with this program; if not, write to the Free Software\r
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  18 */\r
  19 \r
  20 \r
  21 #include <stdio.h>\r
  22 #include "graph.h"\r
  23 \r
  24 Graph::Graph(void (*err_function)(const char *))\r
  25 {\r
  26         error_function = err_function;\r
  27         node_block_first = NULL;\r
  28         arc_for_block_first = NULL;\r
  29         arc_rev_block_first = NULL;\r
  30         flow = 0;\r
  31 }\r
  32 \r
  33 Graph::~Graph()\r
  34 {\r
  35         while (node_block_first)\r
  36         {\r
  37                 node_block *next = node_block_first -> next;\r
  38                 delete node_block_first;\r
  39                 node_block_first = next;\r
  40         }\r
  41 \r
  42         while (arc_for_block_first)\r
  43         {\r
  44                 arc_for_block *next = arc_for_block_first -> next;\r
  45                 delete arc_for_block_first -> start;\r
  46                 arc_for_block_first = next;\r
  47         }\r
  48 \r
  49         while (arc_rev_block_first)\r
  50         {\r
  51                 arc_rev_block *next = arc_rev_block_first -> next;\r
  52                 delete arc_rev_block_first -> start;\r
  53                 arc_rev_block_first = next;\r
  54         }\r
  55 }\r
  56 \r
  57 Graph::node_id Graph::add_node()\r
  58 {\r
  59         node *i;\r
  60 \r
  61         if (!node_block_first || node_block_first->current+1 > &node_block_first->nodes[NODE_BLOCK_SIZE-1])\r
  62         {\r
  63                 node_block *next = node_block_first;\r
  64                 node_block_first = (node_block *) new node_block;\r
  65                 if (!node_block_first) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
  66                 node_block_first -> current = & ( node_block_first -> nodes[0] );\r
  67                 node_block_first -> next = next;\r
  68         }\r
  69 \r
  70         i = node_block_first -> current ++;\r
  71         i -> first_out = (arc_forward *) 0;\r
  72         i -> first_in = (arc_reverse *) 0;\r
  73 \r
  74         i -> tr_cap = 0;\r
  75 \r
  76         return (node_id) i;\r
  77 }\r
  78 \r
  79 void Graph::add_edge(node_id from, node_id to, captype cap, captype rev_cap)\r
  80 {\r
  81         arc_forward *a_for;\r
  82         arc_reverse *a_rev;\r
  83 \r
  84         if (!arc_for_block_first || arc_for_block_first->current+1 > &arc_for_block_first->arcs_for[ARC_BLOCK_SIZE])\r
  85         {\r
  86                 arc_for_block *next = arc_for_block_first;\r
  87                 char *ptr = new char[sizeof(arc_for_block)+1];\r
  88                 if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
  89                 if ((POINTER_CAST)ptr & 1) arc_for_block_first = (arc_for_block *) (ptr + 1);\r
  90                 else              arc_for_block_first = (arc_for_block *) ptr;\r
  91                 arc_for_block_first -> start = ptr;\r
  92                 arc_for_block_first -> current = & ( arc_for_block_first -> arcs_for[0] );\r
  93                 arc_for_block_first -> next = next;\r
  94         }\r
  95 \r
  96         if (!arc_rev_block_first || arc_rev_block_first->current+1 > &arc_rev_block_first->arcs_rev[ARC_BLOCK_SIZE])\r
  97         {\r
  98                 arc_rev_block *next = arc_rev_block_first;\r
  99                 char *ptr = new char[sizeof(arc_rev_block)+1];\r
 100                 if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
 101                 if ((POINTER_CAST)ptr & 1) arc_rev_block_first = (arc_rev_block *) (ptr + 1);\r
 102                 else              arc_rev_block_first = (arc_rev_block *) ptr;\r
 103                 arc_rev_block_first -> start = ptr;\r
 104                 arc_rev_block_first -> current = & ( arc_rev_block_first -> arcs_rev[0] );\r
 105                 arc_rev_block_first -> next = next;\r
 106         }\r
 107 \r
 108         a_for = arc_for_block_first -> current ++;\r
 109         a_rev = arc_rev_block_first -> current ++;\r
 110 \r
 111         a_rev -> sister = (arc_forward *) from;\r
 112         a_for -> shift  = (POINTER_CAST) to;\r
 113         a_for -> r_cap = cap;\r
 114         a_for -> r_rev_cap = rev_cap;\r
 115 \r
 116         ((node *)from) -> first_out =\r
 117                 (arc_forward *) ((POINTER_CAST)(((node *)from) -> first_out) + 1);\r
 118         ((node *)to) -> first_in =\r
 119                 (arc_reverse *) ((POINTER_CAST)(((node *)to) -> first_in) + 1);\r
 120 }\r
 121 \r
 122 void Graph::set_tweights(node_id i, captype cap_source, captype cap_sink)\r
 123 {\r
 124         flow += (cap_source < cap_sink) ? cap_source : cap_sink;\r
 125         ((node*)i) -> tr_cap = cap_source - cap_sink;\r
 126 }\r
 127 \r
 128 void Graph::add_tweights(node_id i, captype cap_source, captype cap_sink)\r
 129 {\r
 130         register captype delta = ((node*)i) -> tr_cap;\r
 131         if (delta > 0) cap_source += delta;\r
 132         else           cap_sink   -= delta;\r
 133         flow += (cap_source < cap_sink) ? cap_source : cap_sink;\r
 134         ((node*)i) -> tr_cap = cap_source - cap_sink;\r
 135 }\r
 136 \r
 137 /*\r
 138         Converts arcs added by 'add_edge()' calls\r
 139         to a forward star graph representation.\r
 140 \r
 141         Linear time algorithm.\r
 142         No or little additional memory is allocated\r
 143         during this process\r
 144         (it may be necessary to allocate additional\r
 145         arc blocks, since arcs corresponding to the\r
 146         same node must be contiguous, i.e. be in one\r
 147         arc block.)\r
 148 */\r
 149 void Graph::prepare_graph()\r
 150 {\r
 151         node *i;\r
 152         arc_for_block *ab_for, *ab_for_first;\r
 153         arc_rev_block *ab_rev, *ab_rev_first, *ab_rev_scan;\r
 154         arc_forward *a_for;\r
 155         arc_reverse *a_rev, *a_rev_scan, a_rev_tmp;\r
 156         node_block *nb;\r
 157         bool for_flag = false, rev_flag = false;\r
 158         int k;\r
 159 \r
 160         if (!arc_rev_block_first)\r
 161         {\r
 162                 node_id from = add_node(), to = add_node();\r
 163                 add_edge(from, to, 1, 0);\r
 164         }\r
 165 \r
 166         /* FIRST STAGE */\r
 167         a_rev_tmp.sister = NULL;\r
 168         for (a_rev=arc_rev_block_first->current; a_rev<&arc_rev_block_first->arcs_rev[ARC_BLOCK_SIZE]; a_rev++)\r
 169         {\r
 170                 a_rev -> sister = NULL;\r
 171         }\r
 172 \r
 173         ab_for = ab_for_first = arc_for_block_first;\r
 174         ab_rev = ab_rev_first = ab_rev_scan = arc_rev_block_first;\r
 175         a_for = &ab_for->arcs_for[0];\r
 176         a_rev = a_rev_scan = &ab_rev->arcs_rev[0];\r
 177 \r
 178         for (nb=node_block_first; nb; nb=nb->next)\r
 179         {\r
 180                 for (i=&nb->nodes[0]; i<nb->current; i++)\r
 181                 {\r
 182                         /* outgoing arcs */\r
 183                         k = (POINTER_CAST) i -> first_out;\r
 184                         if (a_for + k > &ab_for->arcs_for[ARC_BLOCK_SIZE])\r
 185                         {\r
 186                                 if (k > ARC_BLOCK_SIZE) { if (error_function) (*error_function)("# of arcs per node exceeds block size!"); exit(1); }\r
 187                                 if (for_flag) ab_for = NULL;\r
 188                                 else          { ab_for = ab_for -> next; ab_rev_scan = ab_rev_scan -> next; }\r
 189                                 if (ab_for == NULL)\r
 190                                 {\r
 191                                         arc_for_block *next = arc_for_block_first;\r
 192                                         char *ptr = new char[sizeof(arc_for_block)+1];\r
 193                                         if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
 194                                         if ((POINTER_CAST)ptr & 1) arc_for_block_first = (arc_for_block *) (ptr + 1);\r
 195                                         else              arc_for_block_first = (arc_for_block *) ptr;\r
 196                                         arc_for_block_first -> start = ptr;\r
 197                                         arc_for_block_first -> current = & ( arc_for_block_first -> arcs_for[0] );\r
 198                                         arc_for_block_first -> next = next;\r
 199                                         ab_for = arc_for_block_first;\r
 200                                         for_flag = true;\r
 201                                 }\r
 202                                 else a_rev_scan = &ab_rev_scan->arcs_rev[0];\r
 203                                 a_for = &ab_for->arcs_for[0];\r
 204                         }\r
 205                         if (ab_rev_scan)\r
 206                         {\r
 207                                 a_rev_scan += k;\r
 208                                 i -> parent = (arc_forward *) a_rev_scan;\r
 209                         }\r
 210                         else i -> parent = (arc_forward *) &a_rev_tmp;\r
 211                         a_for += k;\r
 212                         i -> first_out = a_for;\r
 213                         ab_for -> last_node = i;\r
 214 \r
 215                         /* incoming arcs */\r
 216                         k = (POINTER_CAST) i -> first_in;\r
 217                         if (a_rev + k > &ab_rev->arcs_rev[ARC_BLOCK_SIZE])\r
 218                         {\r
 219                                 if (k > ARC_BLOCK_SIZE) { if (error_function) (*error_function)("# of arcs per node exceeds block size!"); exit(1); }\r
 220                                 if (rev_flag) ab_rev = NULL;\r
 221                                 else          ab_rev = ab_rev -> next;\r
 222                                 if (ab_rev == NULL)\r
 223                                 {\r
 224                                         arc_rev_block *next = arc_rev_block_first;\r
 225                                         char *ptr = new char[sizeof(arc_rev_block)+1];\r
 226                                         if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
 227                                         if ((POINTER_CAST)ptr & 1) arc_rev_block_first = (arc_rev_block *) (ptr + 1);\r
 228                                         else              arc_rev_block_first = (arc_rev_block *) ptr;\r
 229                                         arc_rev_block_first -> start = ptr;\r
 230                                         arc_rev_block_first -> current = & ( arc_rev_block_first -> arcs_rev[0] );\r
 231                                         arc_rev_block_first -> next = next;\r
 232                                         ab_rev = arc_rev_block_first;\r
 233                                         rev_flag = true;\r
 234                                 }\r
 235                                 a_rev = &ab_rev->arcs_rev[0];\r
 236                         }\r
 237                         a_rev += k;\r
 238                         i -> first_in = a_rev;\r
 239                         ab_rev -> last_node = i;\r
 240                 }\r
 241                 /* i is the last node in block */\r
 242                 i -> first_out = a_for;\r
 243                 i -> first_in  = a_rev;\r
 244         }\r
 245 \r
 246         /* SECOND STAGE */\r
 247         for (ab_for=arc_for_block_first; ab_for; ab_for=ab_for->next)\r
 248         {\r
 249                 ab_for -> current = ab_for -> last_node -> first_out;\r
 250         }\r
 251 \r
 252         for ( ab_for=ab_for_first, ab_rev=ab_rev_first;\r
 253                   ab_for;\r
 254                   ab_for=ab_for->next, ab_rev=ab_rev->next )\r
 255         for ( a_for=&ab_for->arcs_for[0], a_rev=&ab_rev->arcs_rev[0];\r
 256                   a_for<&ab_for->arcs_for[ARC_BLOCK_SIZE];\r
 257                   a_for++, a_rev++ )\r
 258         {\r
 259                 arc_forward *af;\r
 260                 arc_reverse *ar;\r
 261                 node *from;\r
 262                 POINTER_CAST shift = 0, shift_new;\r
 263                 captype r_cap, r_rev_cap, r_cap_new, r_rev_cap_new;\r
 264 \r
 265                 if (!(from=(node *)(a_rev->sister))) continue;\r
 266                 af = a_for;\r
 267                 ar = a_rev;\r
 268 \r
 269                 do\r
 270                 {\r
 271                         ar -> sister = NULL;\r
 272 \r
 273                         shift_new = ((char *)(af->shift)) - (char *)from;\r
 274                         r_cap_new = af -> r_cap;\r
 275                         r_rev_cap_new = af -> r_rev_cap;\r
 276                         if (shift)\r
 277                         {\r
 278                                 af -> shift = shift;\r
 279                                 af -> r_cap = r_cap;\r
 280                                 af -> r_rev_cap = r_rev_cap;\r
 281                         }\r
 282                         shift = shift_new;\r
 283                         r_cap = r_cap_new;\r
 284                         r_rev_cap = r_rev_cap_new;\r
 285 \r
 286                         af = -- from -> first_out;\r
 287                         if ((arc_reverse *)(from->parent) != &a_rev_tmp)\r
 288                         {\r
 289                                 from -> parent = (arc_forward *)(((arc_reverse *)(from -> parent)) - 1);\r
 290                                 ar = (arc_reverse *)(from -> parent);\r
 291                         }\r
 292                 } while (from=(node *)(ar->sister));\r
 293 \r
 294                 af -> shift = shift;\r
 295                 af -> r_cap = r_cap;\r
 296                 af -> r_rev_cap = r_rev_cap;\r
 297         }\r
 298 \r
 299         for (ab_for=arc_for_block_first; ab_for; ab_for=ab_for->next)\r
 300         {\r
 301                 i = ab_for -> last_node;\r
 302                 a_for = i -> first_out;\r
 303                 ab_for -> current -> shift     = a_for -> shift;\r
 304                 ab_for -> current -> r_cap     = a_for -> r_cap;\r
 305                 ab_for -> current -> r_rev_cap = a_for -> r_rev_cap;\r
 306                 a_for -> shift = (POINTER_CAST) (ab_for -> current + 1);\r
 307                 i -> first_out = (arc_forward *) (((char *)a_for) - 1);\r
 308         }\r
 309 \r
 310         /* THIRD STAGE */\r
 311         for (ab_rev=arc_rev_block_first; ab_rev; ab_rev=ab_rev->next)\r
 312         {\r
 313                 ab_rev -> current = ab_rev -> last_node -> first_in;\r
 314         }\r
 315 \r
 316         for (nb=node_block_first; nb; nb=nb->next)\r
 317         for (i=&nb->nodes[0]; i<nb->current; i++)\r
 318         {\r
 319                 arc_forward *a_for_first, *a_for_last;\r
 320 \r
 321                 a_for_first = i -> first_out;\r
 322                 if (IS_ODD(a_for_first))\r
 323                 {\r
 324                         a_for_first = (arc_forward *) (((char *)a_for_first) + 1);\r
 325                         a_for_last = (arc_forward *) ((a_for_first ++) -> shift);\r
 326                 }\r
 327                 else a_for_last = (i + 1) -> first_out;\r
 328 \r
 329                 for (a_for=a_for_first; a_for<a_for_last; a_for++)\r
 330                 {\r
 331                         node *to = NEIGHBOR_NODE(i, a_for -> shift);\r
 332                         a_rev = -- to -> first_in;\r
 333                         a_rev -> sister = a_for;\r
 334                 }\r
 335         }\r
 336 \r
 337         for (ab_rev=arc_rev_block_first; ab_rev; ab_rev=ab_rev->next)\r
 338         {\r
 339                 i = ab_rev -> last_node;\r
 340                 a_rev = i -> first_in;\r
 341                 ab_rev -> current -> sister = a_rev -> sister;\r
 342                 a_rev -> sister = (arc_forward *) (ab_rev -> current + 1);\r
 343                 i -> first_in = (arc_reverse *) (((char *)a_rev) - 1);\r
 344         }\r
 345 }\r