Edge Coloring
Computes an edge coloring for the edges of an undirected, loop-free graph.
Complexity: O(|E| |V|)
Defined in: <boost/graph/edge_coloring.hpp>
Example
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edge_coloring.hpp>
int main() {
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property, boost::property<boost::edge_color_t, int>>;
Graph g(4);
boost::add_edge(0, 1, g); boost::add_edge(0, 2, g);
boost::add_edge(0, 3, g); boost::add_edge(1, 2, g);
boost::add_edge(2, 3, g);
auto color_map = get(boost::edge_color, g);
auto num_colors = boost::edge_coloring(g, color_map);
std::cout << "Edge coloring uses " << num_colors << " colors:\n";
for (auto ep = edges(g); ep.first != ep.second; ++ep.first) {
auto e = *ep.first;
std::cout << " " << source(e, g) << "-" << target(e, g)
<< " : color " << get(color_map, e) << "\n";
}
}Edge coloring uses 4 colors:
0-1 : color 2
0-2 : color 3
0-3 : color 0
1-2 : color 0
2-3 : color 1(1) Edge coloring
template <class Graph, class ColorMap>
typename boost::property_traits<ColorMap>::value_type
edge_coloring(
const Graph& g,
ColorMap color);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
OUT |
|
This property map records the colors of each edge. 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. |
Description
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 assigns 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.