OKlibrary  0.2.1.6
OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph > Class Template Reference

Evaluation of greedy colouring for a graph. More...

#include <GreedyColouring.hpp>

List of all members.

Public Types

typedef UndirectedGraph graph_type
typedef boost::graph_traits
< graph_type >
::vertex_descriptor 
vertex_descriptor
typedef boost::graph_traits
< graph_type >
::vertices_size_type 
vertices_size_type
typedef boost::graph_traits
< graph_type >
::vertex_iterator 
vertex_iterator
typedef boost::property_map
< graph_type,
boost::vertex_index_t >
::const_type 
vertex_index_map
 property map type from vertex_descriptor to vertex_index_type
typedef boost::property_traits
< vertex_index_map >
::value_type 
vertex_index_type
typedef std::vector
< vertex_descriptor
VertexVector
typedef std::pair
< vertex_iterator,
vertex_iterator
VertexRange
typedef
::OKlib::HypergraphColouring::Out_degree_order
< graph_type
sort_type
typedef unsigned long int count_type
typedef std::vector< count_typehash_vector_type
typedef vertices_size_type colour_type
typedef
boost::iterator_property_map
< colour_type
*, vertex_index_map
colour_map_type
 property map for mapping vertex_descriptor to colour_type
typedef std::vector< colour_typecolour_vector_type
 the colour for vertex-indices
typedef VertexVector::size_type order_index_type
 index-type for the vertices in given_order
typedef std::vector
< order_index_type
permutation_type
 permutations of given_order

Public Member Functions

 Greedy_colouring (const graph_type &g)
 fills hash_orders and optimal_order, worst_order together with associated optimal_colouring, worst_colouring
void evaluation ()
void set_order (const permutation_type &p)
void colouring ()

Public Attributes

const graph_typeg
const vertices_size_type n
sort_type sort
hash_vector_type hash_orders
 hash_orders[i] = number of vertex-orders using (exactly) i colours
const VertexVector given_order
 from indices to vertex_descriptor: given_order[i] is the vertex-descriptor with index i
VertexVector optimal_order
VertexVector worst_order
colour_vector_type colour_vec
 underlying store for the colour-map "colour"; colour_vec[i] is the current colour of the vertex with index i
colour_map_type running_colour
 running colouring-map for g
colour_type num_colours
colour_vector_type optimal_colouring
 the maps from vertex indices to colours representing optimal resp. worst colourings
colour_vector_type worst_colouring
colour_type min_colours
colour_type max_colours
VertexVector running_order
 running order, associated with running_colour

Detailed Description

template<class UndirectedGraph>
class OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >

Evaluation of greedy colouring for a graph.

Definition at line 68 of file GreedyColouring.hpp.


Member Typedef Documentation

template<class UndirectedGraph>
typedef boost::iterator_property_map<colour_type*, vertex_index_map> OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::colour_map_type

property map for mapping vertex_descriptor to colour_type

Definition at line 101 of file GreedyColouring.hpp.

Definition at line 99 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef std::vector<colour_type> OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::colour_vector_type

the colour for vertex-indices

Definition at line 104 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef unsigned long int OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::count_type

Definition at line 89 of file GreedyColouring.hpp.

Definition at line 70 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef std::vector<count_type> OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::hash_vector_type

Definition at line 90 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef VertexVector::size_type OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::order_index_type

index-type for the vertices in given_order

Definition at line 121 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef std::vector<order_index_type> OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::permutation_type

permutations of given_order

Definition at line 123 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef boost::graph_traits<graph_type>::vertex_descriptor OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::vertex_descriptor

Definition at line 72 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef boost::property_map<graph_type, boost::vertex_index_t>::const_type OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::vertex_index_map

property map type from vertex_descriptor to vertex_index_type

Definition at line 77 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef boost::property_traits<vertex_index_map>::value_type OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::vertex_index_type

Definition at line 78 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef boost::graph_traits<graph_type>::vertex_iterator OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::vertex_iterator

Definition at line 74 of file GreedyColouring.hpp.

Definition at line 81 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef std::vector<vertex_descriptor> OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::VertexVector

Definition at line 80 of file GreedyColouring.hpp.

template<class UndirectedGraph>
typedef boost::graph_traits<graph_type>::vertices_size_type OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::vertices_size_type

Definition at line 73 of file GreedyColouring.hpp.


Constructor & Destructor Documentation

template<class UndirectedGraph>
OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::Greedy_colouring ( const graph_type g) [inline, explicit]

fills hash_orders and optimal_order, worst_order together with associated optimal_colouring, worst_colouring

Definition at line 128 of file GreedyColouring.hpp.


Member Function Documentation


Member Data Documentation

underlying store for the colour-map "colour"; colour_vec[i] is the current colour of the vertex with index i

Definition at line 107 of file GreedyColouring.hpp.

Referenced by OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::evaluation(), and main().

from indices to vertex_descriptor: given_order[i] is the vertex-descriptor with index i

Definition at line 95 of file GreedyColouring.hpp.

Referenced by main(), and OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::set_order().

hash_orders[i] = number of vertex-orders using (exactly) i colours

Definition at line 92 of file GreedyColouring.hpp.

Referenced by OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::evaluation(), and main().

the maps from vertex indices to colours representing optimal resp. worst colourings

Definition at line 114 of file GreedyColouring.hpp.

Referenced by OKlib::HypergraphColouring::Greedy_colouring< UndirectedGraph >::evaluation(), and main().

Definition at line 87 of file GreedyColouring.hpp.

Referenced by main().


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