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

   1 /* graph.h */\r
   2 /*\r
   3         This software library implements the maxflow algorithm\r
   4         described in\r
   5 \r
   6                 An Experimental Comparison of Min-Cut/Max-Flow Algorithms\r
   7                 for Energy Minimization in Vision.\r
   8                 Yuri Boykov and Vladimir Kolmogorov.\r
   9                 In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), \r
  10                 September 2004\r
  11 \r
  12         This algorithm was developed by Yuri Boykov and Vladimir Kolmogorov\r
  13         at Siemens Corporate Research. To make it available for public use,\r
  14         it was later reimplemented by Vladimir Kolmogorov based on open publications.\r
  15 \r
  16         If you use this software for research purposes, you should cite\r
  17         the aforementioned paper in any resulting publication.\r
  18 */\r
  19 \r
  20 /*\r
  21         Copyright 2001 Vladimir Kolmogorov (vnk@cs.cornell.edu), Yuri Boykov (yuri@csd.uwo.ca).\r
  22 \r
  23     This program is free software; you can redistribute it and/or modify\r
  24     it under the terms of the GNU General Public License as published by\r
  25     the Free Software Foundation; either version 2 of the License, or\r
  26     (at your option) any later version.\r
  27 \r
  28     This program is distributed in the hope that it will be useful,\r
  29     but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  30     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  31     GNU General Public License for more details.\r
  32 \r
  33     You should have received a copy of the GNU General Public License\r
  34     along with this program; if not, write to the Free Software\r
  35     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  36 */\r
  37 \r
  38 \r
  39 /*\r
  40         For description, example usage, discussion of graph representation\r
  41         and memory usage see README.TXT.\r
  42 */\r
  43 \r
  44 #ifndef __GRAPH_H__\r
  45 #define __GRAPH_H__\r
  46 \r
  47 #include <tmwtypes.h>\r
  48 #include "block.h"\r
  49 \r
  50 /*\r
  51         Nodes, arcs and pointers to nodes are\r
  52         added in blocks for memory and time efficiency.\r
  53         Below are numbers of items in blocks\r
  54 */\r
  55 #define NODE_BLOCK_SIZE 512\r
  56 #define ARC_BLOCK_SIZE 1024\r
  57 #define NODEPTR_BLOCK_SIZE 128\r
  58 \r
  59 \r
  60 class Graph\r
  61 {\r
  62 public:\r
  63         typedef enum\r
  64         {\r
  65                 SOURCE  = 0,\r
  66                 SINK    = 1\r
  67         } termtype; /* terminals */\r
  68 \r
  69     typedef void * node_id;\r
  70     \r
  71         /* Type of edge weights.\r
  72            Can be changed to char, int, float, double, ... */\r
  73     typedef float captype; /* bagon changed  from int to float */\r
  74 \r
  75     /* Type of total flow */\r
  76         typedef float flowtype; /* bagon changed  from int to float */\r
  77         \r
  78 \r
  79         /* interface functions */\r
  80 \r
  81         /* Constructor. Optional argument is the pointer to the\r
  82            function which will be called if an error occurs;\r
  83            an error message is passed to this function. If this\r
  84            argument is omitted, exit(1) will be called. */\r
  85         Graph(void (*err_function)(const char *) = NULL);\r
  86 \r
  87         /* Destructor */\r
  88         ~Graph();\r
  89 \r
  90         /* Adds a node to the graph */\r
  91         node_id add_node();\r
  92 \r
  93         /* Adds a bidirectional edge between 'from' and 'to'\r
  94            with the weights 'cap' and 'rev_cap' */\r
  95         void add_edge(node_id from, node_id to, captype cap, captype rev_cap);\r
  96 \r
  97         /* Sets the weights of the edges 'SOURCE->i' and 'i->SINK'\r
  98            Can be called at most once for each node before any call to 'add_tweights'.\r
  99            Weights can be negative */\r
 100         void set_tweights(node_id i, captype cap_source, captype cap_sink);\r
 101 \r
 102         /* Adds new edges 'SOURCE->i' and 'i->SINK' with corresponding weights\r
 103            Can be called multiple times for each node.\r
 104            Weights can be negative */\r
 105         void add_tweights(node_id i, captype cap_source, captype cap_sink);\r
 106 \r
 107         /* After the maxflow is computed, this function returns to which\r
 108            segment the node 'i' belongs (Graph::SOURCE or Graph::SINK) */\r
 109         termtype what_segment(node_id i);\r
 110 \r
 111         /* Computes the maxflow. Can be called only once. */\r
 112         flowtype maxflow();\r
 113 \r
 114 /***********************************************************************/\r
 115 /***********************************************************************/\r
 116 /***********************************************************************/\r
 117         \r
 118 private:\r
 119         /* internal variables and functions */\r
 120 \r
 121         struct arc_forward_st;\r
 122         struct arc_reverse_st;\r
 123 \r
 124 #ifdef A64BITS\r
 125 #define POINTER_CAST    int64_T\r
 126 #else\r
 127 #define POINTER_CAST    int\r
 128 #endif\r
 129 \r
 130 #define IS_ODD(a) ((POINTER_CAST)(a) & 1)\r
 131 #define MAKE_ODD(a)  ((arc_forward *) ((POINTER_CAST)(a) | 1))\r
 132 #define MAKE_EVEN(a) ((arc_forward *) ((POINTER_CAST)(a) & (~1)))\r
 133 #define MAKE_ODD_REV(a)  ((arc_reverse *) ((POINTER_CAST)(a) | 1))\r
 134 #define MAKE_EVEN_REV(a) ((arc_reverse *) ((POINTER_CAST)(a) & (~1)))\r
 135 \r
 136         /* node structure */\r
 137         typedef struct node_st\r
 138         {\r
 139                 /*\r
 140                         Usually i->first_out is the first outgoing\r
 141                         arc, and (i+1)->first_out-1 is the last outgoing arc.\r
 142                         However, it is not always possible, since\r
 143                         arcs are allocated in blocks, so arcs corresponding\r
 144                         to two consecutive nodes may be in different blocks.\r
 145 \r
 146                         If outgoing arcs for i are last in the arc block,\r
 147                         then a different mechanism is used. i->first_out\r
 148                         is odd in this case; the first outgoing arc\r
 149                         is (a+1), and the last outgoing arc is\r
 150                         ((arc_forward *)(a->shift))-1, where\r
 151                         a = (arc_forward *) (((char *)(i->first_out)) + 1);\r
 152 \r
 153                         Similar mechanism is used for incoming arcs.\r
 154                 */\r
 155                 arc_forward_st  *first_out;     /* first outcoming arc */\r
 156                 arc_reverse_st  *first_in;      /* first incoming arc */\r
 157 \r
 158                 arc_forward_st  *parent;        /* describes node's parent\r
 159                                                                            if IS_ODD(parent) then MAKE_EVEN(parent) points to 'arc_reverse',\r
 160                                                                            otherwise parent points to 'arc_forward' */\r
 161 \r
 162                 node_st                 *next;          /* pointer to the next active node\r
 163                                                                            (or to itself if it is the last node in the list) */\r
 164 \r
 165                 int                             TS;                     /* timestamp showing when DIST was computed */\r
 166                 int                             DIST;           /* distance to the terminal */\r
 167                 short                   is_sink;        /* flag showing whether the node is in the source or in the sink tree */\r
 168 \r
 169                 captype                 tr_cap;         /* if tr_cap > 0 then tr_cap is residual capacity of the arc SOURCE->node\r
 170                                                                            otherwise         -tr_cap is residual capacity of the arc node->SINK */\r
 171         } node;\r
 172 \r
 173         /* arc structures */\r
 174 #define NEIGHBOR_NODE(i, shift) ((node *) ((char *)(i) + (shift)))\r
 175 #define NEIGHBOR_NODE_REV(i, shift) ((node *) ((char *)(i) - (shift)))\r
 176         typedef struct arc_forward_st\r
 177         {\r
 178                 POINTER_CAST    shift;          /* node_to = NEIGHBOR_NODE(node_from, shift) */\r
 179                 captype                 r_cap;          /* residual capacity */\r
 180                 captype                 r_rev_cap;      /* residual capacity of the reverse arc*/\r
 181         } arc_forward;\r
 182 \r
 183         typedef struct arc_reverse_st\r
 184         {\r
 185                 arc_forward             *sister;        /* reverse arc */\r
 186         } arc_reverse;\r
 187 \r
 188         /* 'pointer to node' structure */\r
 189         typedef struct nodeptr_st\r
 190         {\r
 191                 node_st                 *ptr;\r
 192                 nodeptr_st              *next;\r
 193         } nodeptr;\r
 194 \r
 195         typedef struct node_block_st\r
 196         {\r
 197                 node                                    *current;\r
 198                 struct node_block_st    *next;\r
 199                 node                                    nodes[NODE_BLOCK_SIZE];\r
 200         } node_block;\r
 201 \r
 202 #define last_node LAST_NODE.LAST_NODE\r
 203 \r
 204         typedef struct arc_for_block_st\r
 205         {\r
 206                 char                                    *start;         /* the actual start address of this block.\r
 207                                                                                            May be different from 'this' since 'this'\r
 208                                                                                            must be at an even address. */\r
 209                 arc_forward                             *current;\r
 210                 struct arc_for_block_st *next;\r
 211                 arc_forward                             arcs_for[ARC_BLOCK_SIZE]; /* all arcs must be at even addresses */\r
 212                 union\r
 213                 {\r
 214                         arc_forward                     dummy;\r
 215                         node                            *LAST_NODE;     /* used in graph consruction */\r
 216                 }                                               LAST_NODE;\r
 217         } arc_for_block;\r
 218 \r
 219         typedef struct arc_rev_block_st\r
 220         {\r
 221                 char                                    *start;         /* the actual start address of this block.\r
 222                                                                                            May be different from 'this' since 'this'\r
 223                                                                                            must be at an even address. */\r
 224                 arc_reverse                             *current;\r
 225                 struct arc_rev_block_st *next;\r
 226                 arc_reverse                             arcs_rev[ARC_BLOCK_SIZE]; /* all arcs must be at even addresses */\r
 227                 union\r
 228                 {\r
 229                         arc_reverse                     dummy;\r
 230                         node                            *LAST_NODE;     /* used in graph consruction */\r
 231                 }                                               LAST_NODE;\r
 232         } arc_rev_block;\r
 233 \r
 234         node_block                      *node_block_first;\r
 235         arc_for_block           *arc_for_block_first;\r
 236         arc_rev_block           *arc_rev_block_first;\r
 237         DBlock<nodeptr>         *nodeptr_block;\r
 238 \r
 239         void    (*error_function)(const char *);        /* this function is called if a error occurs,\r
 240                                                                                    with a corresponding error message\r
 241                                                                                    (or exit(1) is called if it's NULL) */\r
 242 \r
 243         flowtype                        flow;           /* total flow */\r
 244 \r
 245 /***********************************************************************/\r
 246 \r
 247         node                            *queue_first[2], *queue_last[2];        /* list of active nodes */\r
 248         nodeptr                         *orphan_first, *orphan_last;            /* list of pointers to orphans */\r
 249         int                                     TIME;                                                           /* monotonically increasing global counter */\r
 250 \r
 251 /***********************************************************************/\r
 252 \r
 253         /* functions for processing active list */\r
 254         void set_active(node *i);\r
 255         node *next_active();\r
 256 \r
 257         void prepare_graph();\r
 258         void maxflow_init();\r
 259         void augment(node *s_start, node *t_start, captype *cap_middle, captype *rev_cap_middle);\r
 260         void process_source_orphan(node *i);\r
 261         void process_sink_orphan(node *i);\r
 262 };\r
 263 \r
 264 #endif\r