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 typeE
- 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
All Methods Instance Methods Concrete Methods 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.
-
-
-
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 interfacePartitioningAlgorithm<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 interfacePartitioningAlgorithm<V>
- Parameters:
partitioning
- the input vertex partitioning- Returns:
- true if the input partitioning is valid, false otherwise
-
-