SCIL::StronglyConnected< Graph > Class Template Reference
The symbolic constraint for strongly connected graphs. More...
#include <stronglyconnected.h>
Public Member Functions | |
| StronglyConnected (Graph &G_, var_map< edge_descriptor > &VM_) | |
| void | min_cut (vertex_descriptor u, map< edge_descriptor, int > &C, map< edge_descriptor, int > &F, map< vertex_descriptor, bool > &R, int &k) |
| status | standard_separation (subproblem &S) |
| status | feasible (solution &S) |
| void | info () |
Detailed Description
template<typename Graph>
class SCIL::StronglyConnected< Graph >
This symbolic constraints takes as agruments an directed graph G and a var_map<edge> X. X has to map every edge of the graph to a binary variable.
The feasible assignments of the symbolic constraint are those where the vector of the variables associated with the edges of the graph is an incidencevector of a strongly connected subgraph of G.
The symbolic constraint uses the cutting plane method.
Definition at line 29 of file stronglyconnected.h.
Constructor & Destructor Documentation
| StronglyConnected::StronglyConnected | ( | Graph & | G_, | |
| var_map< edge_descriptor > & | VM_ | |||
| ) | [inline] |
Ensures that the edges in X form a strongly connected subgraph.
Preconditions:
- The variables associated to the edges are binary.
For a demo, see: asym_connect.c .
Definition at line 13 of file stronglyconnected.cc.
Member Function Documentation
| StronglyConnected< Graph >::status StronglyConnected::feasible | ( | solution & | S | ) | [inline, virtual] |
Tests if the subgraph induced by the edges with value one is strongly connected.
Reimplemented from SCIL::sym_constraint.
Definition at line 144 of file stronglyconnected.cc.
References SCIL::subproblem::configuration(), and SCIL::solution::value().
| void StronglyConnected::info | ( | ) | [inline, virtual] |
Returns information on the symbolic constraints.
Reimplemented from SCIL::sym_constraint.
Definition at line 167 of file stronglyconnected.cc.
| void StronglyConnected::min_cut | ( | vertex_descriptor | u, | |
| map< edge_descriptor, int > & | C, | |||
| map< edge_descriptor, int > & | F, | |||
| map< vertex_descriptor, bool > & | R, | |||
| int & | k | |||
| ) | [inline] |
Computes Minimum Cut
Definition at line 48 of file stronglyconnected.cc.
References SCIL::StronglyConnected< Graph >::min_cut().
Referenced by SCIL::StronglyConnected< Graph >::min_cut(), and SCIL::StronglyConnected< Graph >::standard_separation().
| StronglyConnected< Graph >::status StronglyConnected::standard_separation | ( | subproblem & | S | ) | [inline, virtual] |
Separates the constraints
Reimplemented from SCIL::sym_constraint.
Definition at line 65 of file stronglyconnected.cc.
References SCIL::subproblem::add_basic_constraint(), SCIL::subproblem::configuration(), SCIL::StronglyConnected< Graph >::min_cut(), SCIL::row::size(), and SCIL::subproblem::value().
The documentation for this class was generated from the following files:
