pgr_bipartite -Experimental¶
pgr_bipartite
— If graph is bipartite then function returns the vertex id along with color (0 and 1) else it will return an empty set.
In particular, the is_bipartite() algorithm implemented by Boost.Graph.
Warning
Possible server crash
- These functions might create a server crash
Warning
Experimental functions
- They are not officially of the current release.
- They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting
Availability
- Version 3.2.0
- New experimental function
Description¶
A bipartite graph is a graph with two sets of vertices which are connected to each other, but not within themselves. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.
The main Characteristics are:
- The algorithm works in undirected graph only.
- The returned values are not ordered.
- The algorithm checks graph is bipartite or not. If it is bipartite then it returns the node along with two colors 0 and 1 which represents two different sets.
- If graph is not bipartite then algorithm returns empty set.
- Running time: \(O(V + E)\)
Signatures¶
pgr_bipartite(Edges SQL)
RETURNS SET OF (vertex_id, color_id)
OR EMPTY SET
Example: | The pgr_bipartite algorithm with and edge_sql as a parameter when graph is bipartite: |
---|
SELECT * FROM pgr_bipartite(
$$SELECT id,source,target,cost,reverse_cost FROM edge_table$$
);
vertex_id | color_id
-----------+----------
1 | 0
2 | 1
3 | 0
4 | 1
5 | 0
6 | 1
7 | 0
8 | 1
9 | 0
10 | 1
11 | 0
12 | 1
13 | 0
14 | 0
15 | 1
16 | 0
17 | 1
(17 rows)
Parameters¶
Parameter | Type | Description |
---|---|---|
Edges SQL | TEXT |
Inner query as described below. |
Inner query¶
Edges SQL: | an SQL query of an undirected graph, which should return a set of rows with the following columns: |
---|
Column | Type | Default | Description |
---|---|---|---|
id | ANY-INTEGER |
Identifier of the edge. | |
source | ANY-INTEGER |
Identifier of the first end point vertex of the edge. | |
target | ANY-INTEGER |
Identifier of the second end point vertex of the edge. | |
cost | ANY-NUMERICAL |
|
|
reverse_cost | ANY-NUMERICAL |
-1 |
|
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 |
---|---|---|
vertex_id | BIGINT |
Identifier of the vertex. |
color_id | BIGINT |
Identifier of the color of the vertex.
|
Additional Example¶
Example: | The odd length cyclic graph can not be bipartite. |
---|
The following edge will make subgraph with vertices {1, 2, 5, 7, 8} an odd length cyclic graph.
INSERT INTO edge_table (source, target, cost, reverse_cost) VALUES
(1, 7, 1, 1);
INSERT 0 1
The new graph is not bipartite because it has a odd length cycle of 5 vertices. Edges in blue represent odd length cycle.

SELECT * FROM pgr_bipartite(
$$SELECT id,source,target,cost,reverse_cost FROM edge_table$$
);
vertex_id | color_id
-----------+----------
(0 rows)