lgraph.h

动态场景中运动目标检测提取与跟踪 对新手很有用

/* graph.h */
/* Vladimir Kolmogorov ([e-mail]), 2001. */

#ifndef __GRAPH_H__
#define __GRAPH_H__

#include "block.h"
#define NODE_BLOCK_SIZE 512
#define ARC_BLOCK_SIZE 1024
#define NODEPTR_BLOCK_SIZE 128

#define TERMINAL ( (arc *) 1 )		/* to terminal */
#define ORPHAN   ( (arc *) 2 )		/* orphan */

class LGraph
{
	public:
	
		typedef enum { SOURCE	= 0, SINK	= 1} termtype; /* terminals */
		typedef float captype;	/* Type of edge weights. Can be changed to char, int, long, double, ... */
		typedef float flowtype; /* Type of total flow */
		typedef void * node_id;

		LGraph(void (*err_function)(char *) = NULL);
		~LGraph();

		node_id add_node();
		void add_edge(node_id from, node_id to, captype cap, captype rev_cap);
		void set_tweights(node_id i, captype cap_source, captype cap_sink);
		void add_tweights(node_id i, captype cap_source, captype cap_sink);
		
		void edit_tweights(node_id i, captype cap_source, captype cap_sink);
		void edit_edge(node_id from, node_id to, captype cap, captype rev_cap);
		void edit_tweights_tree(node_id i, captype cap_source, captype cap_sink);
		void edit_edge_tree(node_id from, node_id to, captype cap, captype rev_cap);

		termtype what_segment(node_id i);
		flowtype maxflow();
		flowtype revised_maxflow();

		flowtype getflow();


/***********************************************************************/
	
	private:
	
		struct arc_st;

		typedef struct node_st
		{
			arc_st			*first;		/* first outcoming arc */
			arc_st			*parent;	/* node's parent */
			node_st			*next;		/* pointer to the next active node(or to itself if it is the last node in the list) */
			int			TS;		/* timestamp showing when DIST was computed */
			int			DIST;		/* distance to the terminal */
			short			is_sink;	/* flag showing whether the node is in the source or in the sink tree */
			captype			tr_cap;		/* if tr_cap > 0 then tr_cap is residual capacity of the arc SOURCE->node
						   		otherwise         -tr_cap is residual capacity of the arc node->SINK */
			captype			t_cap;		/* orginal terminal capacity */
			captype			con_flow;
		} node;
		
		typedef struct arc_st
		{
			node_st			*head;		/* node the arc points to */
			arc_st			*next;		/* next arc with the same originating node */
			arc_st			*sister;	/* reverse arc */
			captype			r_cap;		/* residual capacity */
			captype			e_cap;		/* orignal edge capacity */
		} arc;

	
		typedef struct nodeptr_st
		{
			node_st			*ptr;
			nodeptr_st		*next;
		} nodeptr;

		Block<node>			*node_block;
		Block<arc>			*arc_block;
		DBlock<nodeptr>		*nodeptr_block;

		void	(*error_function)(char *);	

		flowtype flow;		/* total flow */

/***********************************************************************/

		node		*queue_first[2], *queue_last[2];	/* list of active nodes */
		nodeptr	*orphan_first, *orphan_last;		/* list of pointers to orphans */
		int		TIME;						/* monotonically increasing global counter */

/***********************************************************************/

		void set_active(node *i);
		void make_orphan(node *i);
		void settle_terminal(node *f_node);
		node* next_active();

		void maxflow_init();
		void augment(arc *middle_arc);
		void process_source_orphan(node *i);
		void process_sink_orphan(node *i);	
		void process_source_orphan_tree(node *i);
		void process_sink_orphan_tree(node *i);	
};
#endif