Package org.graph4j.util

Class Matching

java.lang.Object
org.graph4j.util.Matching
public class Matching extends Object
A matching or independent edge set is a set of edges without common vertices.
Author:
Cristian Frăsinaru

  • Constructor Summary

    Constructors
    Constructor
    Description
    Matching(Graph graph)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(int v, int u)
     
    boolean
    contains(int v, int u)
     
    boolean
    covers(int v)
    Returns true if there is an edge in the matching incident to the given vertex.
    Set<Edge>
    edges()
     
    boolean
    equals(Object obj)
     
    int
    hashCode()
     
    boolean
    isPerfect()
    A perfect matching of a graph is a matching in which every vertex of the graph is incident to exactly one edge of the matching.
    boolean
    isValid()
    A matching is valid if each vertex of the graph appears in at most one edge of that matching.
    int
    mate(int v)
    The mate of a vertex v is a vertex u such that the edge vu belongs to the matching.
    protected boolean
    remove(int v, int u)
     
    int
    size()
    Returns the number of edges in the matching.
    String
    toString()
     
    double
    weight()
    Computes the sum of the weights associated with each edge in the matching.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • Matching

      public Matching(Graph graph)

  • Method Details

    • add

      public boolean add(int v, int u)

    • remove

      protected boolean remove(int v, int u)

    • contains

      public boolean contains(int v, int u)

    • size

      public int size()
      Returns the number of edges in the matching.
      Returns:
      the number of edges in the matching.

    • edges

      public Set<Edge> edges()

    • covers

      public boolean covers(int v)
      Returns true if there is an edge in the matching incident to the given vertex.
      Parameters:
      v - a vertex number.
      Returns:
      true if the matching covers the given vertex.

    • mate

      public int mate(int v)
      The mate of a vertex v is a vertex u such that the edge vu belongs to the matching.
      Parameters:
      v - a vertex number.
      Returns:
      the mate of v in the matching, or -1 if it has no mate.

    • isPerfect

      public boolean isPerfect()
      A perfect matching of a graph is a matching in which every vertex of the graph is incident to exactly one edge of the matching.
      Returns:
      true if the matching is perfect.

    • weight

      public double weight()
      Computes the sum of the weights associated with each edge in the matching.
      Returns:
      the sum of all weights of the edges in the collection, including duplicates.

    • isValid

      public boolean isValid()
      A matching is valid if each vertex of the graph appears in at most one edge of that matching.
      Returns:
      true if the matching is valid, false otherwise.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object