Module org.jgrapht.core

Package org.jgrapht.alg.partition

Class BipartitePartitioning<V,E>

java.lang.Object

org.jgrapht.alg.partition.BipartitePartitioning<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

PartitioningAlgorithm<V>

public class BipartitePartitioning<V,E>
extends java.lang.Object
implements PartitioningAlgorithm<V>

Algorithm for computing bipartite partitions thus checking whether a graph is bipartite or not.

The algorithm runs in linear time in the number of vertices and edges.

Author:

Dimitrios Michail, Alexandru Valeanu

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.PartitioningAlgorithm

PartitioningAlgorithm.Partitioning<V>, PartitioningAlgorithm.PartitioningImpl<V>

Constructor Summary

Constructors

Constructor	Description
BipartitePartitioning(Graph<V,E> graph)	Constructs a new bipartite partitioning.

Method Summary

Modifier and Type	Method	Description
PartitioningAlgorithm.Partitioning<V>	getPartitioning()	Computes a vertex partitioning.
boolean	isBipartite()	Test whether the input graph is bipartite.
boolean	isValidPartitioning(PartitioningAlgorithm.Partitioning<V> partitioning)	Check if the given vertex partitioning is valid.

Methods inherited from class java.lang.Object

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

Constructor Details

BipartitePartitioning

public BipartitePartitioning(Graph<V,E> graph)

Constructs a new bipartite partitioning.

Parameters:

graph - the input graph;

Method Details

isBipartite

public boolean isBipartite()

Test whether the input graph is bipartite.

Returns:

true if the input graph is bipartite, false otherwise

getPartitioning

public PartitioningAlgorithm.Partitioning<V> getPartitioning()

Computes a vertex partitioning.

Specified by:

getPartitioning in interface PartitioningAlgorithm<V>

Returns:

a vertex partitioning

isValidPartitioning

public boolean isValidPartitioning(PartitioningAlgorithm.Partitioning<V> partitioning)

Check if the given vertex partitioning is valid.

Specified by:

isValidPartitioning in interface PartitioningAlgorithm<V>

Parameters:

partitioning - the input vertex partitioning

Returns:

true if the input partitioning is valid, false otherwise