class for graph cut algorithms on undirected graphs (a graph is represented by an adjacency matrix). More...

#include <GraphCutter.h>

Classes
struct	CutNode

Static Public Member Functions
static float	minCut (DynMatrix< float > &adjacencyMatrix, std::vector< int > &subset1, std::vector< int > &subset2)
	Applies a single minimum cut on a connected undirected graph. More...

static std::vector< std::vector< int > >	thresholdCut (DynMatrix< float > &adjacencyMatrix, float threshold)
	Applies minimum cut as long as a cut with costs smaller a given threshold exists and returns a list of subsets (for weighted graphs). More...

static std::vector< std::vector< int > >	thresholdCut (DynMatrix< bool > &adjacencyMatrix, float threshold)
	Applies minimum cut as long as a cut with costs smaller a given threshold exists and returns a list of subsets (unweighted graphs will be weighted). More...

static std::vector< CutNode >	hierarchicalCut (DynMatrix< float > &adjacencyMatrix)
	Applies hierarchical minimum cut and returns a list of nodes including subset, parent, children and weight representing a cut tree (for weighted graphs). More...

static std::vector< CutNode >	hierarchicalCut (DynMatrix< bool > &adjacencyMatrix)
	Applies hierarchical minimum cut and returns a list of nodes including subset, parent, children and weight representing a cut tree (unweighted graphs will be weighted). More...

static math::DynMatrix< float >	calculateProbabilityMatrix (math::DynMatrix< bool > &initialMatrix, bool symmetry=true)
	Creates a weighted matrix from an unweighted boolean matrix. More...

static std::vector< std::vector< int > >	findUnconnectedSubgraphs (DynMatrix< float > &adjacencyMatrix)
	Find all unconnected subgraphs and return a list of the subsets. More...

static DynMatrix< float >	createSubMatrix (DynMatrix< float > &adjacencyMatrix, std::vector< int > &subgraph)
	Creates a submatrix with a given subset. More...

static void	mergeMatrix (DynMatrix< bool > &dst, DynMatrix< bool > &src)
	Merges the src matrix into the dst matrix (dst is the maximum of both matrices). More...

static void	weightMatrix (DynMatrix< float > &dst, DynMatrix< bool > &featureMatrix, float weight)
	Weights the dst matrix (value*=weight) for all true cells in the featureMatrix. More...

Static Private Member Functions
static std::vector< float >	capforest (std::vector< utils::Point > &edgeList, std::vector< float > &edgeCosts, int subsetsSize)

static float	initialLambda (DynMatrix< float > &adjacencyMatrix, int &lambda_id)

static void	createEdgeList (DynMatrix< float > &adjacencyMatrix, std::vector< utils::Point > &edgeList, std::vector< float > &edgeCosts)

static std::vector< std::vector< int > >	createInitialNodes (DynMatrix< float > &adjacencyMatrix)

static float	merge (std::vector< utils::Point > &edgeList, std::vector< float > &edgeCosts, std::vector< float > &q, std::vector< std::vector< int > > &subsets, float lambda_score, int j, int &lambda_id)

Detailed Description

class for graph cut algorithms on undirected graphs (a graph is represented by an adjacency matrix).

The GraphCutter class implements the CONTRACT/CAP algorithm from H. Nagamochi, T. Ono, T. Ibaraki, "Implementing an efficient minimum capacity cut algorithm", Mathematical Programming 67 (1994).

Member Function Documentation

◆ calculateProbabilityMatrix()

static math::DynMatrix<float> icl::math::GraphCutter::calculateProbabilityMatrix	(	math::DynMatrix< bool > &	initialMatrix,
		bool	symmetry = `true`
	)

static

Creates a weighted matrix from an unweighted boolean matrix.

Parameters

initialMatrix the unweighted boolean matrix (0 for "no edge", 1 for "edge")

Returns: a weighted matrix.

◆ capforest()

static std::vector<float> icl::math::GraphCutter::capforest	(	std::vector< utils::Point > &	edgeList,
		std::vector< float > &	edgeCosts,
		int	subsetsSize
	)

staticprivate

◆ createEdgeList()

static void icl::math::GraphCutter::createEdgeList	(	DynMatrix< float > &	adjacencyMatrix,
		std::vector< utils::Point > &	edgeList,
		std::vector< float > &	edgeCosts
	)

staticprivate

◆ createInitialNodes()

static std::vector<std::vector<int> > icl::math::GraphCutter::createInitialNodes ( DynMatrix< float > & adjacencyMatrix )

staticprivate

◆ createSubMatrix()

static DynMatrix<float> icl::math::GraphCutter::createSubMatrix	(	DynMatrix< float > &	adjacencyMatrix,
		std::vector< int > &	subgraph
	)

static

Creates a submatrix with a given subset.

Parameters

adjacencyMatrix	the input matrix
subgraph	the subset of nodes in the matrix

Returns: a matrix from the subset.

◆ findUnconnectedSubgraphs()

static std::vector<std::vector<int> > icl::math::GraphCutter::findUnconnectedSubgraphs ( DynMatrix< float > & adjacencyMatrix )

static

Find all unconnected subgraphs and return a list of the subsets.

Parameters

adjacencyMatrix the input matrix (0 for "no edge", >0 for edge weights)

Returns: a list of subsets.

◆ hierarchicalCut() [1/2]

static std::vector<CutNode> icl::math::GraphCutter::hierarchicalCut ( DynMatrix< float > & adjacencyMatrix )

static

Applies hierarchical minimum cut and returns a list of nodes including subset, parent, children and weight representing a cut tree (for weighted graphs).

Parameters

adjacencyMatrix the input symmetric adjacency matrix (0 for "no edge", >0 for edge weights)

Returns: a list of tree-nodes.

◆ hierarchicalCut() [2/2]

static std::vector<CutNode> icl::math::GraphCutter::hierarchicalCut ( DynMatrix< bool > & adjacencyMatrix )

static

Applies hierarchical minimum cut and returns a list of nodes including subset, parent, children and weight representing a cut tree (unweighted graphs will be weighted).

Parameters

adjacencyMatrix the input symmetric adjacency matrix (0 for "no edge", 1 for "edge")

Returns: a list of tree-nodes.

◆ initialLambda()

static float icl::math::GraphCutter::initialLambda	(	DynMatrix< float > &	adjacencyMatrix,
		int &	lambda_id
	)

staticprivate

◆ merge()

static float icl::math::GraphCutter::merge	(	std::vector< utils::Point > &	edgeList,
		std::vector< float > &	edgeCosts,
		std::vector< float > &	q,
		std::vector< std::vector< int > > &	subsets,
		float	lambda_score,
		int	j,
		int &	lambda_id
	)

staticprivate

◆ mergeMatrix()

static void icl::math::GraphCutter::mergeMatrix	(	DynMatrix< bool > &	dst,
		DynMatrix< bool > &	src
	)

static

Merges the src matrix into the dst matrix (dst is the maximum of both matrices).

Parameters

dst	the destination matrix
src	the source matrix

◆ minCut()

static float icl::math::GraphCutter::minCut	(	DynMatrix< float > &	adjacencyMatrix,
		std::vector< int > &	subset1,
		std::vector< int > &	subset2
	)

static

Applies a single minimum cut on a connected undirected graph.

Parameters

adjacencyMatrix	the input symmetric adjacency matrix (0 for "no edge", >0 for edge capacity)
subset1	pointer to the first subset result
subset2	pointer to the second subset result

Returns: the cut cost.

◆ thresholdCut() [1/2]

static std::vector<std::vector<int> > icl::math::GraphCutter::thresholdCut	(	DynMatrix< float > &	adjacencyMatrix,
		float	threshold
	)

static

Applies minimum cut as long as a cut with costs smaller a given threshold exists and returns a list of subsets (for weighted graphs).

Parameters

adjacencyMatrix	the input symmetric adjacency matrix (0 for "no edge", >0 for edge capacity)
threshold	the maximum cut cost

Returns: a list of subsets.

◆ thresholdCut() [2/2]

static std::vector<std::vector<int> > icl::math::GraphCutter::thresholdCut	(	DynMatrix< bool > &	adjacencyMatrix,
		float	threshold
	)

static

Applies minimum cut as long as a cut with costs smaller a given threshold exists and returns a list of subsets (unweighted graphs will be weighted).

Parameters

adjacencyMatrix	the input symmetric adjacency matrix (0 for "no edge", 1 for "edge")
threshold	the maximum cut cost

Returns: a list of subsets.

◆ weightMatrix()

static void icl::math::GraphCutter::weightMatrix	(	DynMatrix< float > &	dst,
		DynMatrix< bool > &	featureMatrix,
		float	weight
	)

static

Weights the dst matrix (value*=weight) for all true cells in the featureMatrix.

Parameters

dst	the destination matrix
featureMatrix	the boolean feature matrix (indicates where to weight)
weight	the weight

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

/Users/alneuman/vm/icl/ICLMath/src/ICLMath/GraphCutter.h

Classes

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation

◆ calculateProbabilityMatrix()

◆ capforest()

◆ createEdgeList()

◆ createInitialNodes()

◆ createSubMatrix()

◆ findUnconnectedSubgraphs()

◆ hierarchicalCut() [1/2]

◆ hierarchicalCut() [2/2]

◆ initialLambda()

◆ merge()

◆ mergeMatrix()

◆ minCut()

◆ thresholdCut() [1/2]

◆ thresholdCut() [2/2]

◆ weightMatrix()