Run diffusion algorithm to solve max sum problem. More...

#include <mmn_diffusion_solver.h>

Public Member Functions
	mmn_diffusion_solver ()
	Default constructor.
	mmn_diffusion_solver (unsigned num_nodes, const vcl_vector< mmn_arc > &arcs)
	Construct with arcs.
void	set_arcs (unsigned num_nodes, const vcl_vector< mmn_arc > &arcs)
	Input the arcs that define the graph.
vcl_pair< bool, double >	operator() (const vcl_vector< vnl_vector< double > > &node_cost, const vcl_vector< vnl_matrix< double > > &arc_cost, vcl_vector< unsigned > &x)
	Find values for each node with minimise the total cost.
unsigned	count () const
	final iteration count.
void	set_verbose (bool verbose)
	Produce shed loads of debug output.
Private Types
typedef vcl_map< unsigned, vnl_vector< double > >	potential_set_t
	in below the map is indexed by the neighbour's node id.
typedef vcl_map< unsigned, vnl_matrix< double > >	neigh_arc_cost_t
	Matrix referenced by [source node state ID][target node state ID].
Private Member Functions
bool	continue_diffusion ()
	Check if we carry on.
void	update_potentials_to_neighbours (unsigned inode, const vnl_vector< double > &node_cost)
	Update all messages from input node to its neighbours.
void	transform_costs ()
	Update all node and arc costs (equivalent transform) given phi (potentials).
void	transform_costs (unsigned inode)
	Update node and arc costs (equivalent transform) given phi (potentials) for given node.
bool	arc_consistent_solution (vcl_vector< unsigned > &x)
	Find maximal nodes and arcs and check if arc consistent.
void	init ()
	Reset iteration counters.
double	solution_cost (vcl_vector< unsigned > &x)
	Calculate final sum of node and arc values.
Private Attributes
mmn_graph_rep1	graph_
	Store in graph form (so each node's neighbours are conveniently to hand).
vcl_vector< mmn_arc >	arcs_
	The arcs from which graph was generated.
unsigned	nnodes_
	Total number of nodes.
vcl_vector< neigh_arc_cost_t >	arc_costs_
	Workspace for costs of each arc.
vcl_vector< neigh_arc_cost_t >	arc_costs_phi_
	Workspace for transformed costs of each arc.
vcl_vector< potential_set_t >	phi_
	All the potentials at previous iteration (vector index is source node).
vcl_vector< potential_set_t >	phi_upd_
	Update potentials calculated during this iteration (vector index is source node).
vcl_vector< vnl_vector< double > >	node_costs_
	Node costs (outer vector is node ID, inner vnl_vector is by state value).
vcl_vector< vnl_vector< double > >	node_costs_phi_
	Node costs after phi transform (outer vector is node ID, inner vnl_vector is by state value).
vcl_vector< vcl_map< unsigned, vnl_vector< double > > >	u_
	Workspace for adjustment to potential.
unsigned	count_
	Current iteration count.
double	max_delta_
	Max change in any potential value over this iteration.
unsigned	max_iterations_
	max number of iterations allowed.
unsigned	min_iterations_
	min iterations allowed before additional convergence checks.
double	epsilon_
	Convergence criterion on max_delta_.
bool	verbose_
	verbose debug output.
double	soln_val_prev_
	Previous solution value at arc consistency check.
unsigned	nConverging_
	Count of number of times solution value was unchanged.
Static Private Attributes
static unsigned	gNCONVERGED = 3
	Max count of nConverging_.
static unsigned	gACS_CHECK_PERIOD = 10
	Period at which arc consistency of solution is checked for.

Detailed Description

Run diffusion algorithm to solve max sum problem.

See T Werner. A Linear Programming Approach to Max-sum problem: A review; IEEE Trans on Pattern Recog & Machine Intell, July 2007 Try and solve the max-sum problem by performing node-pencil averaging over the graph I.e. transform to equivalent problem by adding "potentials" to nodes and subtracting them from arcs. This is done to equalise node costs and the cost of the maximal connecting arcs If this converges the solution is to take the maximal nodes (which will then be arc-consistent).

Definition at line 23 of file mmn_diffusion_solver.h.

Member Typedef Documentation

typedef vcl_map<unsigned, vnl_matrix<double > > mmn_diffusion_solver::neigh_arc_cost_t [private]

Matrix referenced by [source node state ID][target node state ID].

Map ID is target node ID

Definition at line 33 of file mmn_diffusion_solver.h.

typedef vcl_map<unsigned,vnl_vector<double > > mmn_diffusion_solver::potential_set_t [private]

in below the map is indexed by the neighbour's node id.

Inner vector indexed by source node state ID, map by neighbour node (t').

Definition at line 29 of file mmn_diffusion_solver.h.

Constructor & Destructor Documentation

mmn_diffusion_solver::mmn_diffusion_solver ( )

Default constructor.

Definition at line 25 of file mmn_diffusion_solver.cxx.

mmn_diffusion_solver::mmn_diffusion_solver	(	unsigned	num_nodes,
		const vcl_vector< mmn_arc > &	arcs
	)

Construct with arcs.

Definition at line 33 of file mmn_diffusion_solver.cxx.

Member Function Documentation

bool mmn_diffusion_solver::arc_consistent_solution ( vcl_vector< unsigned > & x ) [private]

Find maximal nodes and arcs and check if arc consistent.

Find (possibly non-unique) maximal label value.

Then compile vector of all node indices with label value "near" this.

Definition at line 292 of file mmn_diffusion_solver.cxx.

bool mmn_diffusion_solver::continue_diffusion ( ) [private]

Check if we carry on.

Definition at line 389 of file mmn_diffusion_solver.cxx.

unsigned mmn_diffusion_solver::count ( ) const [inline]

final iteration count.

Definition at line 147 of file mmn_diffusion_solver.h.

void mmn_diffusion_solver::init ( ) [private]

Reset iteration counters.

Definition at line 40 of file mmn_diffusion_solver.cxx.

vcl_pair< bool, double > mmn_diffusion_solver::operator()	(	const vcl_vector< vnl_vector< double > > &	node_cost,
		const vcl_vector< vnl_matrix< double > > &	arc_cost,
		vcl_vector< unsigned > &	x
	)

Find values for each node with minimise the total cost.

Run the algorithm.

Parameters:

node_cost,:	node_cost[i][j] is cost of selecting value j for node i
pair_cost,:	pair_cost[a](i,j) is cost of selecting values (i,j) for nodes at end of arc a.
x,:	On exit, x[i] gives choice for node i NOTE: If arc a connects nodes v1,v2, the associated pair_cost is ordered with the node with the lowest index being the first parameter. Thus if v1 has value i1, v2 has value i2, then the cost of this choice is (v1<v2?pair_cost(i1,i2):pair_cost(i2,i1))

Returns the minimum cost. Note that internally we deal with a maximisation after negating the input costs, which are assumed to represent -log probabilities In the return the boolean returns whether the algorithm was successful in converging to an arc-consistent solution, and the double is the cost (negative minimum, i.e. -internal max) Even if the solution is not arc-consistent a solution is still returned given by the local node first maxima, but this may not then be optimal.

Negate costs to convert to log prob (i.e. internally we do maximisation).

Definition at line 86 of file mmn_diffusion_solver.cxx.