paal::ir::min_cut_finder Class Reference

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)

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 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.

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 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: