pgr_sequentialVertexColoring - Proposed - pgRouting Manual (3.4)
![Logo](images/pgrouting.png)
pgr_sequentialVertexColoring - Proposed
pgr_sequentialVertexColoring
- Returns the vertex coloring of an undirected
graph, using greedy approach.
![images/boost-inside.jpeg](images/boost-inside.jpeg)
Warning
Proposed functions for next mayor release.
-
They are not officially in the current release.
-
They will likely officially be part of the next mayor release:
-
The functions make use of ANY-INTEGER and ANY-NUMERICAL
-
Name might not change. (But still can)
-
Signature might not change. (But still can)
-
Functionality might not change. (But still can)
-
pgTap tests have being done. But might need more.
-
Documentation might need refinement.
-
Availability
-
Version 3.3.0
-
Promoted to proposed signature
-
-
Version 3.2.0
-
New experimental signature
-
Description
Sequential vertex coloring algorithm is a graph coloring algorithm in which color identifiers are assigned to the vertices of a graph in a sequential manner, such that no edge connects two identically colored vertices.
The main Characteristics are:
-
The implementation is applicable only for undirected graphs.
-
Provides the color to be assigned to all the vertices present in the graph.
-
Color identifiers values are in the Range \([1, V]\)
-
The algorithm tries to assign the least possible color to every vertex.
-
Efficient graph coloring is an NP-Hard problem, and therefore, this algorithm does not always produce optimal coloring. It follows a greedy strategy by iterating through all the vertices sequentially, and assigning the smallest possible color that is not used by its neighbors, to each vertex.
-
The returned rows are ordered in ascending order of the vertex value.
-
Sequential Vertex Coloring Running Time: \(O(V*(d + k))\)
-
where \(V\) is the number of vertices,
-
\(d\) is the maximum degree of the vertices in the graph,
-
\(k\) is the number of colors used.
-
Signatures
- Example :
-
Graph coloring of pgRouting Sample Data
SELECT * FROM pgr_sequentialVertexColoring(
'SELECT id, source, target, cost, reverse_cost FROM edges
ORDER BY id'
);
vertex_id color_id
-----------+----------
1 1
2 1
3 2
4 2
5 1
6 2
7 1
8 2
9 1
10 1
11 2
12 1
13 1
14 2
15 2
16 1
17 2
(17 rows)
Parameters
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Inner Queries
Edges SQL
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL :
-
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns
Returns SET OF
(vertex_id,
color_id)
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the vertex. |
|
|
Identifier of the color of the vertex.
|
See Also
-
The queries use the Sample Data network.
Indices and tables