mincut.h File Reference

Go to the source code of this file.

Typedefs
typedef struct _MinCut	MinCut

Functions
MinCut *	minc_create (int nArcs, const int tail[], const int head[], const int _cap[], int s, int t)
	creates a min cut solver More...
int	minc_optimize (MinCut *minc)
	solves the min cut problem More...
int	minc_n (MinCut *minc)
	number of nodes in graph More...
int	minc_n_cut (MinCut *minc)
	number of arcs in minimum cut More...
int	minc_cut_arc_source (MinCut *minc, int i)
	returns the i-th arc source in the cut More...
int	minc_cut_arc_destination (MinCut *minc, int i)
	returns the i-th arc destination in the cut More...
char	minc_in_s (MinCut *minc, int i)
	checks if a node is in the subset of the source node or not More...
void	minc_free (MinCut **_minc)
	frees memory of mincut solver

Detailed Description

Author

Haroldo Gambini Santos

Date

15 Aug 2019

A self-contained, C99 compatible minimum cut implementation

See also

https://en.wikipedia.org/wiki/Minimum_cut

Definition in file mincut.h.

Function Documentation

minc_create()

MinCut* minc_create	(	int	nArcs,
		const int	tail[],
		const int	head[],
		const int	_cap[],
		int	s,
		int	t
	)

creates a min cut solver

Parameters

nArcs	number of arcs
tail	vector with arc sources
head	vector with arc destinations
_cap	vector with arc capacities
s	source
t	destination

Returns

minimum cut solver

minc_cut_arc_destination()

int minc_cut_arc_destination	(	MinCut *	minc,
		int	i
	)

returns the i-th arc destination in the cut

Parameters

minc	mincut solver object
i	index of the destination arc

Returns

source of the i-th arc in the cut

minc_cut_arc_source()

int minc_cut_arc_source	(	MinCut *	minc,
		int	i
	)

returns the i-th arc source in the cut

Parameters

minc	mincut solver object
i	index of the arc

Returns

source of the i-th arc in the cut

minc_in_s()

char minc_in_s	(	MinCut *	minc,
		int	i
	)

checks if a node is in the subset of the source node or not

Parameters

minc	mincut solver object
i	node to be checked

Returns

1 is node i is in subset S, 0 otherwise

minc_n()

int minc_n

(

MinCut *

minc

)

number of nodes in graph

Parameters

minc	mincut solver object

Returns

number of nodes in the graph

minc_n_cut()

int minc_n_cut

(

MinCut *

minc

)

number of arcs in minimum cut

Parameters

minc	mincut solver object

Returns

number of arcs in minimum cut

minc_optimize()

int minc_optimize

(

MinCut *

minc

)

solves the min cut problem

Parameters

minc	mincut solver object

Returns

capacity of of min cut (max flow)