Given (sparse?) graph eliminate invalid arcs and nodes until a kernel of arc-consistent nodes and arcs remains. More...

#include <mmn_csp_solver.h>

Public Types
typedef vcl_set< unsigned >	label_subset_t
	Subset of labels present for each node.
typedef vcl_set< vcl_pair < unsigned,unsigned > , mbl_stl_pred_pair_order < unsigned,unsigned > >	arc_labels_subset_t
	Define the subset of labels linked.
typedef vcl_multiset< vcl_pair < unsigned,unsigned > , mbl_stl_pred_pair_key_order < vcl_pair< unsigned,unsigned > > >	arc_labels_subset_t1
typedef vcl_multiset< vcl_pair < unsigned,unsigned > , mbl_stl_pred_pair_value_order < vcl_pair< unsigned,unsigned > > >	arc_labels_subset_t2
Public Member Functions
	mmn_csp_solver ()
	Default constructor.
	mmn_csp_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.
bool	operator() (const vcl_vector< mmn_csp_solver::label_subset_t > &node_labels_subset, const vcl_vector< mmn_csp_solver::arc_labels_subset_t > &links_subset)
	Run the algorithm.
void	set_verbose (bool verbose)
const vcl_vector < label_subset_t > &	kernel_node_labels () const
Private Member Functions
bool	check_for_node_deletions ()
	delete any node labels not linked by any current arcs.
bool	check_for_arc_deletions ()
	delete any arcs with either target node label not present.
void	initialise_arc_labels_linked (const vcl_vector< mmn_csp_solver::arc_labels_subset_t > &links_subset)
void	init ()
Private Attributes
unsigned	nnodes_
bool	verbose_
vcl_vector< label_subset_t >	node_labels_present_
	Vector of nodes, defining which labels are present for each node.
vcl_vector< arc_labels_subset_t1 >	arc_labels_linked1_
	Define the subset of labels linked.
vcl_vector< arc_labels_subset_t2 >	arc_labels_linked2_
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.

Detailed Description

Given (sparse?) graph eliminate invalid arcs and nodes until a kernel of arc-consistent nodes and arcs remains.

See Werner 2007 paper in IEEE Trans on Pattern Recognition and Machine Intelligence Can be used to see if Max Sum problem has been reduced to "trivial" form i.e. if the maximal nodes are joined up via maximal arcs We successively delete a) nodes not linked with some neighbour by any edge b) edges lacking an end node

Definition at line 23 of file mmn_csp_solver.h.

Member Typedef Documentation

typedef vcl_set<vcl_pair<unsigned ,unsigned >, mbl_stl_pred_pair_order<unsigned ,unsigned > > mmn_csp_solver::arc_labels_subset_t

Define the subset of labels linked.

For each original arc (outer vector), the inner set gives all the corresponding node labels actually linked Note the first in the pair corresponds always to the lower node ID in the arc (i.e. as for arc pair costs

Definition at line 33 of file mmn_csp_solver.h.

typedef vcl_multiset<vcl_pair<unsigned ,unsigned >, mbl_stl_pred_pair_key_order<vcl_pair<unsigned ,unsigned > > > mmn_csp_solver::arc_labels_subset_t1

Definition at line 36 of file mmn_csp_solver.h.

typedef vcl_multiset<vcl_pair<unsigned ,unsigned >, mbl_stl_pred_pair_value_order<vcl_pair<unsigned ,unsigned > > > mmn_csp_solver::arc_labels_subset_t2

Definition at line 39 of file mmn_csp_solver.h.

typedef vcl_set<unsigned> mmn_csp_solver::label_subset_t

Subset of labels present for each node.

Definition at line 27 of file mmn_csp_solver.h.

Constructor & Destructor Documentation

mmn_csp_solver::mmn_csp_solver ( )

Default constructor.

Definition at line 11 of file mmn_csp_solver.cxx.

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

Construct with arcs.

Definition at line 17 of file mmn_csp_solver.cxx.

Member Function Documentation

bool mmn_csp_solver::check_for_arc_deletions ( ) [private]

delete any arcs with either target node label not present.

Return true if any deletions occur

Definition at line 181 of file mmn_csp_solver.cxx.

bool mmn_csp_solver::check_for_node_deletions ( ) [private]

delete any node labels not linked by any current arcs.

Return true if any deletions occur

Definition at line 103 of file mmn_csp_solver.cxx.

void mmn_csp_solver::init ( ) [private]

Definition at line 24 of file mmn_csp_solver.cxx.

void mmn_csp_solver::initialise_arc_labels_linked ( const vcl_vector< mmn_csp_solver::arc_labels_subset_t > & links_subset ) [private]

Definition at line 79 of file mmn_csp_solver.cxx.

const vcl_vector<label_subset_t >& mmn_csp_solver::kernel_node_labels ( ) const [inline]

Definition at line 86 of file mmn_csp_solver.h.

bool mmn_csp_solver::operator()	(	const vcl_vector< mmn_csp_solver::label_subset_t > &	node_labels_subset,
		const vcl_vector< mmn_csp_solver::arc_labels_subset_t > &	links_subset
	)

Run the algorithm.

Definition at line 50 of file mmn_csp_solver.cxx.

void mmn_csp_solver::set_arcs	(	unsigned	num_nodes,
		const vcl_vector< mmn_arc > &	arcs
	)

Input the arcs that define the graph.

Pass in the arcs, which are then used to build the graph object.

Definition at line 29 of file mmn_csp_solver.cxx.

void mmn_csp_solver::set_verbose ( bool verbose ) [inline]

Definition at line 85 of file mmn_csp_solver.h.

Member Data Documentation

vcl_vector<arc_labels_subset_t1 > mmn_csp_solver::arc_labels_linked1_ [private]

Define the subset of labels linked.

For each original arc (outer vector), the inner set gives all the corresponding node labels actually linked Note the first in the pair corresponds always to the lower node ID in the arc (i.e. as for arc pair costs

Definition at line 53 of file mmn_csp_solver.h.

vcl_vector<arc_labels_subset_t2 > mmn_csp_solver::arc_labels_linked2_ [private]

Definition at line 54 of file mmn_csp_solver.h.

vcl_vector<mmn_arc> mmn_csp_solver::arcs_ [private]

The arcs from which graph was generated.

Definition at line 59 of file mmn_csp_solver.h.

mmn_graph_rep1 mmn_csp_solver::graph_ [private]

Store in graph form (so each node's neighbours are conveniently to hand).

Definition at line 56 of file mmn_csp_solver.h.

unsigned mmn_csp_solver::nnodes_ [private]

Definition at line 42 of file mmn_csp_solver.h.

vcl_vector<label_subset_t > mmn_csp_solver::node_labels_present_ [private]