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.
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. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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(); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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; }