Graph< captype, tcaptype, flowtype > Class Template Reference

#include <graph.h>

Inheritance diagram for Graph< captype, tcaptype, flowtype >:

List of all members.

Classes
struct	arc
struct	node
struct	nodeptr
Public Types
typedef arc *	arc_id
typedef int	node_id
enum	termtype { SOURCE = 0, SINK = 1 }
Public Member Functions
void	add_edge (node_id i, node_id j, captype cap, captype rev_cap)
node_id	add_node (int num=1)
void	add_tweights (node_id i, tcaptype cap_source, tcaptype cap_sink)
void	Copy (Graph< captype, tcaptype, flowtype > *g0)
void	get_arc_ends (arc_id a, node_id &i, node_id &j)
int	get_arc_num ()
arc_id	get_first_arc ()
arc_id	get_next_arc (arc_id a)
int	get_node_num ()
captype	get_rcap (arc *a)
tcaptype	get_trcap (node_id i)
	Graph (int node_num_max, int edge_num_max, void(*err_function)(char *)=NULL)
void	mark_node (node_id i)
flowtype	maxflow (bool reuse_trees=false, Block< node_id > *changed_list=NULL)
void	remove_from_changed_list (node_id i)
void	reset ()
void	set_rcap (arc *a, captype rcap)
void	set_trcap (node_id i, tcaptype trcap)
termtype	what_segment (node_id i, termtype default_segm=SOURCE)
	~Graph ()
Private Member Functions
void	add_to_changed_list (node *i)
void	augment (arc *middle_arc)
void	maxflow_init ()
void	maxflow_reuse_trees_init ()
node *	next_active ()
void	process_sink_orphan (node *i)
void	process_source_orphan (node *i)
void	reallocate_arcs ()
void	reallocate_nodes (int num)
void	set_active (node *i)
void	set_orphan_front (node *i)
void	set_orphan_rear (node *i)
void	test_consistency (node *current_node=NULL)
Private Attributes
arc *	arc_last
arc *	arc_max
arc *	arcs
Block< node_id > *	changed_list
void(*	error_function )(char *)
flowtype	flow
int	maxflow_iteration
node *	node_last
node *	node_max
int	node_num
DBlock< nodeptr > *	nodeptr_block
node *	nodes
nodeptr *	orphan_first
nodeptr *	orphan_last
node *	queue_first [2]
node *	queue_last [2]
int	TIME
Static Private Attributes
static const int	NODEPTR_BLOCK_SIZE = 128

---

Detailed Description

template<typename captype, typename tcaptype, typename flowtype>
class Graph< captype, tcaptype, flowtype >

Definition at line 55 of file graph.h.

---

Member Typedef Documentation

template<typename captype, typename tcaptype, typename flowtype>

typedef arc* Graph< captype, tcaptype, flowtype >::arc_id

Definition at line 156 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

typedef int Graph< captype, tcaptype, flowtype >::node_id

Definition at line 63 of file graph.h.

---

Member Enumeration Documentation

template<typename captype, typename tcaptype, typename flowtype>

enum Graph::termtype

Enumerator:

SOURCE
SINK

Definition at line 58 of file graph.h.

---

Constructor & Destructor Documentation

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::Graph	(	int	node_num_max,
		int	edge_num_max,
		void(*)(char *)	err_function = NULL
	)

Definition at line 11 of file graph.cpp.

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::~Graph

(

)

Definition at line 33 of file graph.cpp.

---

Member Function Documentation

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::add_edge	(	node_id	i,
		node_id	j,
		captype	cap,
		captype	rev_cap
	)		[inline]

Definition at line 399 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::node_id Graph< captype, tcaptype, flowtype >::add_node

(

int

num = 1

)

[inline]

Definition at line 360 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::add_to_changed_list

(

node *

i

)

[inline, private]

Definition at line 106 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::add_tweights	(	node_id	i,
		tcaptype	cap_source,
		tcaptype	cap_sink
	)		[inline]

Definition at line 388 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::augment

(

arc *

middle_arc

)

[private]

Definition at line 244 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::Copy

(

Graph< captype, tcaptype, flowtype > *

g0

)

Definition at line 685 of file maxflow.cpp.

template<typename captype, typename tcaptype, typename flowtype>

void Graph< captype, tcaptype, flowtype >::get_arc_ends	(	arc_id	a,
		node_id &	i,
		node_id &	j
	)		[inline]

Definition at line 440 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

int Graph< captype, tcaptype, flowtype >::get_arc_num

(

)

[inline]

Definition at line 162 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::arc * Graph< captype, tcaptype, flowtype >::get_first_arc

(

)

[inline]

Definition at line 428 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

Graph< captype, tcaptype, flowtype >::arc * Graph< captype, tcaptype, flowtype >::get_next_arc

(

arc_id

a

)

[inline]

Definition at line 434 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

int Graph< captype, tcaptype, flowtype >::get_node_num

(

)

[inline]

Definition at line 161 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

captype Graph< captype, tcaptype, flowtype >::get_rcap

(

arc *

a

)

[inline]

Definition at line 455 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

tcaptype Graph< captype, tcaptype, flowtype >::get_trcap

(

node_id

i

)

[inline]

Definition at line 448 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::mark_node

(

node_id

i

)

[inline]

Definition at line 490 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

flowtype Graph< captype, tcaptype, flowtype >::maxflow	(	bool	reuse_trees = false,
		Block< node_id > *	changed_list = NULL
	)

Definition at line 472 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::maxflow_init

(

)

[private]

Definition at line 119 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::maxflow_reuse_trees_init

(

)

[private]

Definition at line 159 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::node * Graph< captype, tcaptype, flowtype >::next_active

(

)

[inline, private]

Definition at line 52 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::process_sink_orphan

(

node *

i

)

[private]

Definition at line 393 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::process_source_orphan

(

node *

i

)

[private]

Definition at line 316 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::reallocate_arcs

(

)

[private]

Definition at line 86 of file graph.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::reallocate_nodes

(

int

num

)

[private]

Definition at line 62 of file graph.cpp.

template<typename captype, typename tcaptype, typename flowtype>

void Graph< captype, tcaptype, flowtype >::remove_from_changed_list

(

node_id

i

)

[inline]

Definition at line 244 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::reset

(

)

Definition at line 45 of file graph.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::set_active

(

node *

i

)

[inline, private]

Definition at line 34 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::set_orphan_front

(

node *

i

)

[inline, private]

Definition at line 80 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::set_orphan_rear

(

node *

i

)

[inline, private]

Definition at line 91 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::set_rcap	(	arc *	a,
		captype	rcap
	)		[inline]

Definition at line 469 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::set_trcap	(	node_id	i,
		tcaptype	trcap
	)		[inline]

Definition at line 462 of file graph.h.

template<typename captype , typename tcaptype , typename flowtype >

void Graph< captype, tcaptype, flowtype >::test_consistency

(

node *

current_node = NULL

)

[private]

Definition at line 610 of file maxflow.cpp.

template<typename captype , typename tcaptype , typename flowtype >

Graph< captype, tcaptype, flowtype >::termtype Graph< captype, tcaptype, flowtype >::what_segment	(	node_id	i,
		termtype	default_segm = SOURCE
	)		[inline]

Definition at line 477 of file graph.h.

---

Member Data Documentation

template<typename captype, typename tcaptype, typename flowtype>

arc * Graph< captype, tcaptype, flowtype >::arc_last [private]

Definition at line 297 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

arc * Graph< captype, tcaptype, flowtype >::arc_max [private]

Definition at line 297 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

arc* Graph< captype, tcaptype, flowtype >::arcs [private]

Definition at line 297 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

Block<node_id>* Graph< captype, tcaptype, flowtype >::changed_list [private]

Definition at line 311 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

void(* Graph< captype, tcaptype, flowtype >::error_function)(char *) [private]

Reimplemented in Energy< captype, tcaptype, flowtype >.

Definition at line 303 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

flowtype Graph< captype, tcaptype, flowtype >::flow [private]

Definition at line 307 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

int Graph< captype, tcaptype, flowtype >::maxflow_iteration [private]

Definition at line 310 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

node * Graph< captype, tcaptype, flowtype >::node_last [private]

Definition at line 296 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

node * Graph< captype, tcaptype, flowtype >::node_max [private]

Definition at line 296 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

int Graph< captype, tcaptype, flowtype >::node_num [private]

Definition at line 299 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

DBlock<nodeptr>* Graph< captype, tcaptype, flowtype >::nodeptr_block [private]

Definition at line 301 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

const int Graph< captype, tcaptype, flowtype >::NODEPTR_BLOCK_SIZE = 128 [static, private]

Definition at line 294 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

node* Graph< captype, tcaptype, flowtype >::nodes [private]

Definition at line 296 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

nodeptr* Graph< captype, tcaptype, flowtype >::orphan_first [private]

Definition at line 316 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

nodeptr * Graph< captype, tcaptype, flowtype >::orphan_last [private]

Definition at line 316 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

node* Graph< captype, tcaptype, flowtype >::queue_first[2] [private]

Definition at line 315 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

node * Graph< captype, tcaptype, flowtype >::queue_last[2] [private]

Definition at line 315 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>

int Graph< captype, tcaptype, flowtype >::TIME [private]

Definition at line 317 of file graph.h.

---

The documentation for this class was generated from the following files:

• graph.h
• graph.cpp
• maxflow.cpp