Class for creating and modifying directed graphs with edge capacities and finding directed minimum cuts between given vertices. More...

#include <min_cut.hpp>

Public Types
using	Edge = Traits::edge_descriptor

using	Vertex = Traits::vertex_descriptor

Public Member Functions
	min_cut_finder ()
	Constructor.

void	init (int vertices_num)

Vertex	add_vertex_to_graph ()

std::pair< Edge, Edge >	add_edge_to_graph (Vertex src, Vertex trg, double cap, double rev_cap=0.)

double	find_min_cut (Vertex src, Vertex trg)

bool	is_in_source_set (Vertex v) const

int	source_set_size () const

std::pair< Vertex, Vertex >	get_last_cut () const

double	get_capacity (Edge e) const

void	set_capacity (Edge e, double cap)

void	set_capacity (Vertex src, Vertex trg, double cap)

Detailed Description

Class for creating and modifying directed graphs with edge capacities and finding directed minimum cuts between given vertices.

Definition at line 31 of file min_cut.hpp.

Member Function Documentation

std::pair<Edge, Edge> paal::ir::min_cut_finder::add_edge_to_graph	(	Vertex	src,
		Vertex	trg,
		double	cap,
		double	rev_cap = `0.`
	)

inline

Adds an edge to the graph.

Parameters

src	source vertex of for the added edge
trg	target vertex of for the added edge
cap	capacity of the added edge
rev_cap	capacity of the reverse edge

Returns: created edge of the graph and the created reverse edge

Definition at line 70 of file min_cut.hpp.

Vertex paal::ir::min_cut_finder::add_vertex_to_graph ( )

inline

Adds a new vertex to the graph.

Definition at line 58 of file min_cut.hpp.

double paal::ir::min_cut_finder::find_min_cut	(	Vertex	src,
		Vertex	trg
	)

inline

Finds the min cut between src and trg.

Parameters

src	source vertex (belongs to the cut set)
trg	target vertex (does not belong to the cut set)

Returns: min cut value

Definition at line 95 of file min_cut.hpp.

double paal::ir::min_cut_finder::get_capacity ( Edge e ) const

inline

Returns the capacity of a given edge.

Definition at line 133 of file min_cut.hpp.

std::pair<Vertex, Vertex> paal::ir::min_cut_finder::get_last_cut ( ) const

inline

Returns the pair of vertices defining the last checked cut.

Definition at line 128 of file min_cut.hpp.

void paal::ir::min_cut_finder::init ( int vertices_num )

inline

(Re)Initializes the graph.

Definition at line 46 of file min_cut.hpp.

bool paal::ir::min_cut_finder::is_in_source_set ( Vertex v ) const

inline

Checks if the given vertex belongs to the source side of the last checked cut.

Definition at line 109 of file min_cut.hpp.

void paal::ir::min_cut_finder::set_capacity	(	Edge	e,
		double	cap
	)

inline

Sets the capacity of a given edge.

Definition at line 138 of file min_cut.hpp.

void paal::ir::min_cut_finder::set_capacity	(	Vertex	src,
		Vertex	trg,
		double	cap
	)

inline

Sets the capacity of a given edge.

Definition at line 145 of file min_cut.hpp.

int paal::ir::min_cut_finder::source_set_size ( ) const

inline

Returns the number of vertices in the source size of the last checked cut.

Definition at line 117 of file min_cut.hpp.

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

include/paal/iterative_rounding/min_cut.hpp

Public Types

Public Member Functions

Detailed Description

Member Function Documentation