com.yworks.yfiles.algorithms

Class Bipartitions

java.lang.Object

com.yworks.yfiles.algorithms.Bipartitions

public final class Bipartitions
extends Object

This class provides methods to determine whether a graph is bipartite and to obtain the corresponding partitions.

A bipartite graph is a graph whose nodes can be partitioned into two sets such that each edges connects two nodes of different sets. In other words, there are no edges connecting nodes that belong to the same partition.

The two sets/partitions are represented by two Object constants i.e., RED or BLUE.

Example of a bipartite graph. Circular and rectangular nodes represent the two partitions.

Field Summary

Fields

Modifier and Type	Field and Description
static Object	BLUE A constant for marking a node that belongs to the blue partition.
static Object	RED A constant for marking a node that belongs to the red partition.

Method Summary

Modifier and Type	Method and Description
static boolean	getBipartition(Graph graph, INodeMap markMap) Calculates a bipartition of the given graph, if one exists.
static boolean	isBipartite(Graph graph) Determines whether or not the given graph is bipartite.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

BLUE

public static final Object BLUE

A constant for marking a node that belongs to the blue partition.

RED

public static final Object RED

A constant for marking a node that belongs to the red partition.

Method Detail

getBipartition

public static final boolean getBipartition(Graph graph,
                                           INodeMap markMap)

Calculates a bipartition of the given graph, if one exists.

If the graph is bipartite, then for all nodes of the given graph either RED or BLUE objects will be set in the given INodeMap, depending on the partition to which each node belongs.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the given graph

markMap - the INodeMap that will be filled during the BFS execution and returns the partition (either RED or BLUE) to which each node belongs

Returns:

true if the graph is bipartite, false otherwise

isBipartite

public static final boolean isBipartite(Graph graph)

Determines whether or not the given graph is bipartite.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the given graph

Returns:

true if the graph is bipartite, false otherwise