C++ Boost

edge_coloring

Graphs: undirected, loop-free
Properties: color
Complexity: time: O(|E| |V|)
  template <class Graph, class ColorMap>
  typename boost::property_traits::value_type
  edge_coloring(const Graph &g, ColorMap color);

Computes an edge coloring for the vertices in the graph, using an algorithm proposed by Misra et al. []. Given edges ordered e1, e2, ..., en it assignes a colors c1, c2, ..., cn in a way that no vertex connects with 2 edges of the same color. Furthermore at most m + 1 colors are used.

Where defined

boost/graph/edge_coloring.hpp

Parameters

IN: const Graph& g
The graph object on which the algorithm will be applied. The type Graph must be a model of Edge List Graph and Incidence Graph.
OUT: ColorMap color
This property map records the colors of each edges. It must be a model of Read/Write Property Map whose key type is the same as the edge descriptor type of the graph and whose value type is an integral type that can store all values smaller or equal to m.

Example

See example/king_ordering.cpp.

See Also

sequential vertex ordering.

Copyright © 2013 Maciej Piechotka (uzytkownik2@gmail.com)