Package org.graph4j.support

Class BipartiteGraphSupport

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.support.BipartiteGraphSupport
public class BipartiteGraphSupport extends SimpleGraphAlgorithm
Support class for bipartite graphs. A graph is bipartite if its vertices can be partitioned in two disjoint stable sets. A bipartite graph is 2-colorable. A graph is bipartite if and only if it has no odd-length cycle.
Author:
Cristian Frăsinaru

  • Constructor Details

    • BipartiteGraphSupport

      public BipartiteGraphSupport(Graph graph)
      Creates an instance of the support class.
      Parameters:
      graph - the input graph.

  • Method Details

    • isBipartite

      public boolean isBipartite()
      Returns:
      true if the graph is bipartite, false otherwise.

    • getLeftSide

      public StableSet getLeftSide()
      Returns the left side of the bipartition.
      Returns:
      the left side of the graph, if the graph is bipartite.
      Throws:
      NotBipartiteException - if the graph is not bipartite.

    • getRightSide

      public StableSet getRightSide()
      Returns the right side of the bipartition.
      Returns:
      the right side of the graph, if the graph is bipartite.
      Throws:
      NotBipartiteException - if the graph is not bipartite.

    • getSide

      public StableSet getSide(int v)
      Determines the stable set of the partition where a specified vertex belongs to.
      Parameters:
      v - a vertex number
      Returns:
      the partition set v belongs to, if the graph is bipartite.
      Throws:
      NotBipartiteException - if the graph is not bipartite.

    • findOddCycle

      public Cycle findOddCycle()
      Determines an odd cycle, if the graph is not bipartite.
      Returns:
      an odd cycle, if the graph is not bipartite, otherwise it returns null.

    • getColoring

      public Coloring getColoring()
      Created a 2-coloring of the bipartite graph.
      Returns:
      a 2-coloring of the bipartite graph.
      Throws:
      NotBipartiteException - if the graph is not bipartite.

    • getMaximumMatching

      public Matching getMaximumMatching()
      Determines a maximum matching in a bipartite graph, using HopcroftKarpMaximumMatching algorithm.
      Returns:
      a maximum stable set in a bipartite graph.
      Throws:
      NotBipartiteException - if the graph is not bipartite.
      See Also:

    • getMaximumStableSet

      public StableSet getMaximumStableSet()
      Determines a maximum stable set in a bipartite graph, using HopcroftKarpMaximumMatching algorithm.
      Returns:
      a maximum stable set in a bipartite graph.
      Throws:
      NotBipartiteException - if the graph is not bipartite.
      See Also:

    • getMinimumVertexCover

      public VertexSet getMinimumVertexCover()
      Determines a minimum vertex cover in a bipartite graph, using HopcroftKarpMaximumMatching algorithm.
      Returns:
      a maximum stable set in a bipartite graph.
      Throws:
      NotBipartiteException - if the graph is not bipartite.
      See Also: