www.pudn.com > maxflow_fast2.rar > graph.cpp
/* graph.cpp */
/*
Copyright 2001 Vladimir Kolmogorov (vnk@cs.cornell.edu), Yuri Boykov (yuri@csd.uwo.ca).
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include
#include "graph.h"
Graph::Graph(void (*err_function)(char *))
{
error_function = err_function;
node_block_first = NULL;
arc_for_block_first = NULL;
arc_rev_block_first = NULL;
flow = 0;
}
Graph::~Graph()
{
while (node_block_first)
{
node_block *next = node_block_first -> next;
delete node_block_first;
node_block_first = next;
}
while (arc_for_block_first)
{
arc_for_block *next = arc_for_block_first -> next;
delete arc_for_block_first -> start;
arc_for_block_first = next;
}
while (arc_rev_block_first)
{
arc_rev_block *next = arc_rev_block_first -> next;
delete arc_rev_block_first -> start;
arc_rev_block_first = next;
}
}
Graph::node_id Graph::add_node()
{
node *i;
if (!node_block_first || node_block_first->current+1 > &node_block_first->nodes[NODE_BLOCK_SIZE-1])
{
node_block *next = node_block_first;
node_block_first = (node_block *) new node_block;
if (!node_block_first) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
node_block_first -> current = & ( node_block_first -> nodes[0] );
node_block_first -> next = next;
}
i = node_block_first -> current ++;
i -> first_out = (arc_forward *) 0;
i -> first_in = (arc_reverse *) 0;
i -> tr_cap = 0;
return (node_id) i;
}
void Graph::add_edge(node_id from, node_id to, captype cap, captype rev_cap)
{
arc_forward *a_for;
arc_reverse *a_rev;
if (!arc_for_block_first || arc_for_block_first->current+1 > &arc_for_block_first->arcs_for[ARC_BLOCK_SIZE])
{
arc_for_block *next = arc_for_block_first;
char *ptr = new char[sizeof(arc_for_block)+1];
if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
if ((int)ptr & 1) arc_for_block_first = (arc_for_block *) (ptr + 1);
else arc_for_block_first = (arc_for_block *) ptr;
arc_for_block_first -> start = ptr;
arc_for_block_first -> current = & ( arc_for_block_first -> arcs_for[0] );
arc_for_block_first -> next = next;
}
if (!arc_rev_block_first || arc_rev_block_first->current+1 > &arc_rev_block_first->arcs_rev[ARC_BLOCK_SIZE])
{
arc_rev_block *next = arc_rev_block_first;
char *ptr = new char[sizeof(arc_rev_block)+1];
if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
if ((int)ptr & 1) arc_rev_block_first = (arc_rev_block *) (ptr + 1);
else arc_rev_block_first = (arc_rev_block *) ptr;
arc_rev_block_first -> start = ptr;
arc_rev_block_first -> current = & ( arc_rev_block_first -> arcs_rev[0] );
arc_rev_block_first -> next = next;
}
a_for = arc_for_block_first -> current ++;
a_rev = arc_rev_block_first -> current ++;
a_rev -> sister = (arc_forward *) from;
a_for -> shift = (int) to;
a_for -> r_cap = cap;
a_for -> r_rev_cap = rev_cap;
((node *)from) -> first_out =
(arc_forward *) ((int)(((node *)from) -> first_out) + 1);
((node *)to) -> first_in =
(arc_reverse *) ((int)(((node *)to) -> first_in) + 1);
}
void Graph::set_tweights(node_id i, captype cap_source, captype cap_sink)
{
flow += (cap_source < cap_sink) ? cap_source : cap_sink;
((node*)i) -> tr_cap = cap_source - cap_sink;
}
void Graph::add_tweights(node_id i, captype cap_source, captype cap_sink)
{
register captype delta = ((node*)i) -> tr_cap;
if (delta > 0) cap_source += delta;
else cap_sink -= delta;
flow += (cap_source < cap_sink) ? cap_source : cap_sink;
((node*)i) -> tr_cap = cap_source - cap_sink;
}
/*
Converts arcs added by 'add_edge()' calls
to a forward star graph representation.
Linear time algorithm.
No or little additional memory is allocated
during this process
(it may be necessary to allocate additional
arc blocks, since arcs corresponding to the
same node must be contiguous, i.e. be in one
arc block.)
*/
void Graph::prepare_graph()
{
node *i;
arc_for_block *ab_for, *ab_for_first;
arc_rev_block *ab_rev, *ab_rev_first, *ab_rev_scan;
arc_forward *a_for;
arc_reverse *a_rev, *a_rev_scan, a_rev_tmp;
node_block *nb;
bool for_flag = false, rev_flag = false;
int k;
if (!arc_rev_block_first)
{
node_id from = add_node(), to = add_node();
add_edge(from, to, 1, 0);
}
/* FIRST STAGE */
a_rev_tmp.sister = NULL;
for (a_rev=arc_rev_block_first->current; a_rev<&arc_rev_block_first->arcs_rev[ARC_BLOCK_SIZE]; a_rev++)
{
a_rev -> sister = NULL;
}
ab_for = ab_for_first = arc_for_block_first;
ab_rev = ab_rev_first = ab_rev_scan = arc_rev_block_first;
a_for = &ab_for->arcs_for[0];
a_rev = a_rev_scan = &ab_rev->arcs_rev[0];
for (nb=node_block_first; nb; nb=nb->next)
{
for (i=&nb->nodes[0]; icurrent; i++)
{
/* outgoing arcs */
k = (int) i -> first_out;
if (a_for + k > &ab_for->arcs_for[ARC_BLOCK_SIZE])
{
if (k > ARC_BLOCK_SIZE) { if (error_function) (*error_function)("# of arcs per node exceeds block size!"); exit(1); }
if (for_flag) ab_for = NULL;
else { ab_for = ab_for -> next; ab_rev_scan = ab_rev_scan -> next; }
if (ab_for == NULL)
{
arc_for_block *next = arc_for_block_first;
char *ptr = new char[sizeof(arc_for_block)+1];
if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
if ((int)ptr & 1) arc_for_block_first = (arc_for_block *) (ptr + 1);
else arc_for_block_first = (arc_for_block *) ptr;
arc_for_block_first -> start = ptr;
arc_for_block_first -> current = & ( arc_for_block_first -> arcs_for[0] );
arc_for_block_first -> next = next;
ab_for = arc_for_block_first;
for_flag = true;
}
else a_rev_scan = &ab_rev_scan->arcs_rev[0];
a_for = &ab_for->arcs_for[0];
}
if (ab_rev_scan)
{
a_rev_scan += k;
i -> parent = (arc_forward *) a_rev_scan;
}
else i -> parent = (arc_forward *) &a_rev_tmp;
a_for += k;
i -> first_out = a_for;
ab_for -> last_node = i;
/* incoming arcs */
k = (int) i -> first_in;
if (a_rev + k > &ab_rev->arcs_rev[ARC_BLOCK_SIZE])
{
if (k > ARC_BLOCK_SIZE) { if (error_function) (*error_function)("# of arcs per node exceeds block size!"); exit(1); }
if (rev_flag) ab_rev = NULL;
else ab_rev = ab_rev -> next;
if (ab_rev == NULL)
{
arc_rev_block *next = arc_rev_block_first;
char *ptr = new char[sizeof(arc_rev_block)+1];
if (!ptr) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
if ((int)ptr & 1) arc_rev_block_first = (arc_rev_block *) (ptr + 1);
else arc_rev_block_first = (arc_rev_block *) ptr;
arc_rev_block_first -> start = ptr;
arc_rev_block_first -> current = & ( arc_rev_block_first -> arcs_rev[0] );
arc_rev_block_first -> next = next;
ab_rev = arc_rev_block_first;
rev_flag = true;
}
a_rev = &ab_rev->arcs_rev[0];
}
a_rev += k;
i -> first_in = a_rev;
ab_rev -> last_node = i;
}
/* i is the last node in block */
i -> first_out = a_for;
i -> first_in = a_rev;
}
/* SECOND STAGE */
for (ab_for=arc_for_block_first; ab_for; ab_for=ab_for->next)
{
ab_for -> current = ab_for -> last_node -> first_out;
}
for ( ab_for=ab_for_first, ab_rev=ab_rev_first;
ab_for;
ab_for=ab_for->next, ab_rev=ab_rev->next )
for ( a_for=&ab_for->arcs_for[0], a_rev=&ab_rev->arcs_rev[0];
a_for<&ab_for->arcs_for[ARC_BLOCK_SIZE];
a_for++, a_rev++ )
{
arc_forward *af;
arc_reverse *ar;
node *from;
int shift = 0, shift_new;
captype r_cap, r_rev_cap, r_cap_new, r_rev_cap_new;
if (!(from=(node *)(a_rev->sister))) continue;
af = a_for;
ar = a_rev;
do
{
ar -> sister = NULL;
shift_new = ((char *)(af->shift)) - (char *)from;
r_cap_new = af -> r_cap;
r_rev_cap_new = af -> r_rev_cap;
if (shift)
{
af -> shift = shift;
af -> r_cap = r_cap;
af -> r_rev_cap = r_rev_cap;
}
shift = shift_new;
r_cap = r_cap_new;
r_rev_cap = r_rev_cap_new;
af = -- from -> first_out;
if ((arc_reverse *)(from->parent) != &a_rev_tmp)
{
from -> parent = (arc_forward *)(((arc_reverse *)(from -> parent)) - 1);
ar = (arc_reverse *)(from -> parent);
}
} while (from=(node *)(ar->sister));
af -> shift = shift;
af -> r_cap = r_cap;
af -> r_rev_cap = r_rev_cap;
}
for (ab_for=arc_for_block_first; ab_for; ab_for=ab_for->next)
{
i = ab_for -> last_node;
a_for = i -> first_out;
ab_for -> current -> shift = a_for -> shift;
ab_for -> current -> r_cap = a_for -> r_cap;
ab_for -> current -> r_rev_cap = a_for -> r_rev_cap;
a_for -> shift = (int) (ab_for -> current + 1);
i -> first_out = (arc_forward *) (((char *)a_for) - 1);
}
/* THIRD STAGE */
for (ab_rev=arc_rev_block_first; ab_rev; ab_rev=ab_rev->next)
{
ab_rev -> current = ab_rev -> last_node -> first_in;
}
for (nb=node_block_first; nb; nb=nb->next)
for (i=&nb->nodes[0]; icurrent; i++)
{
arc_forward *a_for_first, *a_for_last;
a_for_first = i -> first_out;
if (IS_ODD(a_for_first))
{
a_for_first = (arc_forward *) (((char *)a_for_first) + 1);
a_for_last = (arc_forward *) ((a_for_first ++) -> shift);
}
else a_for_last = (i + 1) -> first_out;
for (a_for=a_for_first; a_for shift);
a_rev = -- to -> first_in;
a_rev -> sister = a_for;
}
}
for (ab_rev=arc_rev_block_first; ab_rev; ab_rev=ab_rev->next)
{
i = ab_rev -> last_node;
a_rev = i -> first_in;
ab_rev -> current -> sister = a_rev -> sister;
a_rev -> sister = (arc_forward *) (ab_rev -> current + 1);
i -> first_in = (arc_reverse *) (((char *)a_rev) - 1);
}
}