This class provides methods to determine whether a graph is bipartite and to obtain the corresponding partitions.
Remarks
Note: Methods of this class work with instances of Graph. To determine a bipartition of an IGraph use Bipartition instead.
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.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.Bipartitions
Constants
A constant for marking a node that belongs to the blue partition.
A constant for marking a node that belongs to the red partition.
Static Methods
Calculates a bipartition of the given graph, if one exists.
Remarks
Note: This method works with instances of Graph. To determine a bipartition of an IGraph use Bipartition instead.
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
A map of options to pass to the method.
- graph - Graph
- the given graph
- markMap - INodeMap
- the INodeMap that will be filled during the BFS execution and returns the partition (either RED or BLUE) to which each node belongs
Domain YNode Values Object an value (either or ) representing the partition to which the given node belongs
Returns
- ↪boolean
trueif the graph is bipartite,falseotherwise
Determines whether or not the given graph is bipartite.
Remarks
Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
Returns
- ↪boolean
trueif the graph is bipartite,falseotherwise