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 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 and Description
BipartitePartitioning(Graph<V,E> graph) Constructs a new bipartite partitioning.

Method Summary

Modifier and Type	Method and 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 Detail

BipartitePartitioning

public BipartitePartitioning(Graph<V,E> graph)

Constructs a new bipartite partitioning.

Parameters:

graph - the input graph;

Method Detail

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