OKlibrary  0.2.1.6
OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph > Class Template Reference

Functor computing the width induced by an elimination sequence. More...

#include <EliminationSequences.hpp>

Inheritance diagram for OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph >:
binary_function

List of all members.

Public Types

typedef EliminationSequence elimination_sequence_type
typedef Graph graph_type

Public Member Functions

degree_size_type operator() (const elimination_sequence_type &elim, graph_type &g) const

Detailed Description

template<class EliminationSequence, class Graph>
class OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph >

Functor computing the width induced by an elimination sequence.

"Width_elimination_sequence<C,G>()(elimination_sequence, g)" returns the width associated with the elimination sequence (which must be non-empty, since the graph with no vertices has tree width -1, while the return degree_size_type is unsigned). g is changed by the procedure.

C is a single pass range of vertex descriptors. The graph class G must fulfil the following concepts:

  • boost::AdjacencyGraphConcept (see BOOST_CLASS_REQUIRE below)
  • boost::MutableGraphConcept (see BOOST_CLASS_REQUIRE below)
  • has boost::graph_traits<G>::degree_size_type
  • undirected (see BOOST_STATIC_ASSERT below)
  • no parallel edges (see BOOST_STATIC_ASSERT below)
  • no loops
  • applying add_edge(u,v,g) does not invalidate (or change in any way) adjacency_iterator's in the range adjacent_vertices(w,g) for w different from u and v, and neither does it invalidate vertex descriptors
  • applying clear_vertex(v,g) does not invalidate other vertex descriptors
  • applying remove_vertex(v,g) does not invalidate other vertex descriptors

Definition at line 65 of file EliminationSequences.hpp.


Member Typedef Documentation

template<class EliminationSequence , class Graph >
typedef EliminationSequence OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph >::elimination_sequence_type

Definition at line 78 of file EliminationSequences.hpp.

template<class EliminationSequence , class Graph >
typedef Graph OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph >::graph_type

Definition at line 79 of file EliminationSequences.hpp.


Member Function Documentation

template<class EliminationSequence , class Graph >
degree_size_type OKlib::GraphDecomposition::Width_elimination_sequence< EliminationSequence, Graph >::operator() ( const elimination_sequence_type elim,
graph_type g 
) const [inline]

Definition at line 89 of file EliminationSequences.hpp.

References Latex_Handler::begin(), and end.


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