PGX 20.2.2
Documentation

## Bipartite Check

##### Categorystructure evaluationAlgorithm IDpgx_builtin_s10_bipartite_checkTime ComplexityO(E) with E = number of edgesSpace RequirementO(2 * V) with V = number of verticesJavadocAnalyst#bipartiteCheck(PgxGraph graph, VertexProperty isLeft)

This algorithm checks whether the given directed graph is bipartite. It assumes that all the edges are going in the same direction since the method relies on BFS traversals of the graph. If the graph is bipartite the algorithm will return the side of each vertex in the graph with the is_left vertex property.

## Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
is_left vertexProp vertex property holding the side of each vertex in a bipartite graph (true for left, false for right).
Return Value Type Comment
bool true if the graph is bipartite, false otherwise.

## Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class BipartiteCheck {
public boolean bipartiteCheck(PgxGraph g, @Out VertexProperty<Boolean> isLeft) {
VertexProperty<Boolean> visited = VertexProperty.create(false);
isLeft.setAll(false);

Scalar<Boolean> isBipartiteGraph = Scalar.create(true);

// assumption: edges only go from left to right
g.getVertices().filter(root_node -> !visited.get(root_node) && root_node.getOutDegree() > 0)
.forSequential(root_node -> {
isLeft.set(root_node, true);

inBFS(g, root_node).forward(n -> {
boolean levelIsLeft = currentLevel() % 2 == 0;
visited.set(n, true);
isLeft.set(n, levelIsLeft);

if (levelIsLeft && n.getInDegree() > 0) {
isBipartiteGraph.set(false);
} else if (!levelIsLeft && n.getOutDegree() > 0) {
isBipartiteGraph.set(false);
}
});
});

return isBipartiteGraph.get();
}
}
```
```/*
*/

procedure bipartite_check(graph G; vertexProp<bool> is_left) : bool {

vertexProp<bool> visited;
G.is_left = false;
G.visited = false;

bool is_bipartite_graph = true;
// assumption: edges only go from left to right
for (root_node: G.nodes) (root_node.visited == false && root_node.outDegree() > 0) {

root_node.is_left = true;

inBFS (n: G.nodes from root_node) [is_bipartite_graph] {

bool level_is_left = currentBFSLevel() % 2 == 0;
n.visited = true;
n.is_left = level_is_left;

if (level_is_left == true && n.numInNbrs() > 0) {
is_bipartite_graph = false;
} else if (level_is_left == false && n.numNbrs() > 0) {
is_bipartite_graph = false;
}
}
}
return is_bipartite_graph;
}
```