Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library

Edge Coloring is an algorithm used for coloring of the edges for the vertices in the graph. It is an assignment of colors to the edges of the graph so that no two adjacent edges have the same color.

If edges are ordered as e1, e2, ..., en it assigns colors c1, c2, ..., cn in such a way that no vertex connects with 2 edges of the same color. Furthermore, at most Δ + 1 colors are used, where Δ is the degree of the graph.

It is used in several representations of real-world systems like traffic signalling, bi-processors, fiber-optic communication, etc. It can also tell us if a graph is Bipartite. It is implemented in Boost Graph Library (BGL) as Boost::Edge Coloring. It is applicable for undirected and loop-free (i.e no self-loops and no parallel edges) graph. It has a polynomial-time complexity of O(|E | |V |).