Class LargestCommonSubgraph

java.lang.Object
org.cicirello.search.problems.LargestCommonSubgraph
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>

public final class LargestCommonSubgraph extends Object implements IntegerCostOptimizationProblem<Permutation>

This class is an implementation of the Largest Common Subgraph problem, an NP-Hard combinatorial optimization problem. In the problem, we are given two graphs G1 and G2. The problem is to find the largest graph Gc, measured in number of edges, that is isomorphic to a subgraph of G1 and a subgraph of G2.

The value method computes the actual optimization objective, number of edges in common, which we must maximize. The cost method transforms this to a minimization problem by subtracting that count from the number of edges in the smaller of G1 and G2 (in terms of edges).

This implementation assumes representing solutions with a Permutation used to represent a mapping between the vertexes of the two graphs. Specifically, holding the vertexes of the graph with the fewer number of vertexes in a fixed order by their vertex id, a solution to the problem is represented with a Permutation of the vertex ids of the other graph. Position in the permutation corresponds to the mapping. For example, if p(i) = j, then vertex i in G1 is mapped to vertex j in G2. This assumes that G1 has at most the number of vertexes as G2.

  • Constructor Details

    • LargestCommonSubgraph

      public LargestCommonSubgraph(int v, double density, boolean isomorphic)
      Constructs a random instance of the largest common subgraph problem.
      Parameters:
      v - The number of vertexes of each graph.
      density - The density of each graph, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      isomorphic - If true, the two graphs will be isomorphic, which provides an easy way of generating instances with a known optimal solution.
      Throws:
      IllegalArgumentException - if v is less than 1.
      IllegalArgumentException - if density is less than 0.0 or greater than 1.0.
    • LargestCommonSubgraph

      public LargestCommonSubgraph(int v1, int v2, double density1, double density2)
      Constructs a random instance of the largest common subgraph problem.
      Parameters:
      v1 - The number of vertexes of graph 1.
      v2 - The number of vertexes of graph 2.
      density1 - The density of graph 1, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      density2 - The density of graph 2, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      Throws:
      IllegalArgumentException - if v1 and/or v2 is less than 1.
      IllegalArgumentException - if either density1 or density2 is less than 0.0 or greater than 1.0.
    • LargestCommonSubgraph

      public LargestCommonSubgraph(int v, double density, boolean isomorphic, long seed)
      Constructs a random instance of the largest common subgraph problem.
      Parameters:
      v - The number of vertexes of each graph.
      density - The density of each graph, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      isomorphic - If true, the two graphs will be isomorphic, which provides an easy way of generating instances with a known optimal solution.
      seed - The seed for the random number generator to enable replicating an instance.
      Throws:
      IllegalArgumentException - if v is less than 1.
      IllegalArgumentException - if density is less than 0.0 or greater than 1.0.
    • LargestCommonSubgraph

      public LargestCommonSubgraph(int v1, int v2, double density1, double density2, long seed)
      Constructs a random instance of the largest common subgraph problem.
      Parameters:
      v1 - The number of vertexes of graph 1.
      v2 - The number of vertexes of graph 2.
      density1 - The density of graph 1, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      density2 - The density of graph 2, which is the probability of an edge existing between a pair of vertexes. It must be in the interval [0.0, 1.0].
      seed - The seed for the random number generator to enable replicating an instance.
      Throws:
      IllegalArgumentException - if v1 and/or v2 is less than 1.
      IllegalArgumentException - if either density1 or density2 is less than 0.0 or greater than 1.0.
    • LargestCommonSubgraph

      public LargestCommonSubgraph(int v1, int v2, List<LargestCommonSubgraph.Edge> edges1, List<LargestCommonSubgraph.Edge> edges2)
      Constructs a random instance of the largest common subgraph problem.
      Parameters:
      v1 - The number of vertexes of graph 1.
      v2 - The number of vertexes of graph 2.
      edges1 - A list of the edges for graph 1. Each of the 2 endpoints of each edge in edges1 must be in the interval [0, v1). This list must not contain duplicate edges, and also must not contain both (a, b) and (b, a) since these are the same edge. The behavior of this class is undefined if either of these are violated.
      edges2 - A list of the edges for graph 2. Each of the 2 endpoints of each edge in edges2 must be in the interval [0, v2). This list must not contain duplicate edges, and also must not contain both (a, b) and (b, a) since these are the same edge. The behavior of this class is undefined if either of these are violated.
      Throws:
      IllegalArgumentException - if v1 and/or v2 is less than 1.
      IllegalArgumentException - if any of the endpoints of the edges in edges1 or edges2 are out of bounds for the corresponding graph.
  • Method Details

    • createInstanceGeneralizedPetersenGraph

      public static LargestCommonSubgraph createInstanceGeneralizedPetersenGraph(int n, int k)

      Creates an instance of the Largest Common Subgraph problem for a pair of isomorphic Generalized Petersen Graphs. One of the graphs for this LCS problem instance is the Generalized Petersen Graph G(n, k). The second is isomorphic to the first, formed by generating a random relabeling of the vertex indexes. The Generalized Petersen Graph G(n, k) consists of 2*n vertexes and 3*n edges.

      Parameters:
      n - The parameter n of the Generalized Petersen Graph G(n, k), which must be at least 1. The graph formed will have 2*n vertexes and 3*n edges.
      k - The parameter k of the Generalized Petersen Graph G(n, k), which must be less than n/2.
      Returns:
      An instance of the Largest Common Subgraph problem for a pair of isomorphic Generalized Petersen Graphs.
      Throws:
      IllegalArgumentException - if n is less than 1.
      IllegalArgumentException - if k is not less than n/2 or if k is negative.
    • createInstanceGeneralizedPetersenGraph

      public static LargestCommonSubgraph createInstanceGeneralizedPetersenGraph(int n, int k, long seed)

      Creates an instance of the Largest Common Subgraph problem for a pair of isomorphic Generalized Petersen Graphs. One of the graphs for this LCS problem instance is the Generalized Petersen Graph G(n, k). The second is isomorphic to the first, formed by generating a random relabeling of the vertex indexes. The Generalized Petersen Graph G(n, k) consists of 2*n vertexes and 3*n edges.

      Parameters:
      n - The parameter n of the Generalized Petersen Graph G(n, k), which must be at least 1. The graph formed will have 2*n vertexes and 3*n edges.
      k - The parameter k of the Generalized Petersen Graph G(n, k), which must be less than n/2.
      seed - The seed for the random number generator used in generating the randomized vertex index relabeling when generating the second graph of the pair.
      Returns:
      An instance of the Largest Common Subgraph problem for a pair of isomorphic Generalized Petersen Graphs.
      Throws:
      IllegalArgumentException - if n is less than 1.
      IllegalArgumentException - if k is not less than n/2 or if k is negative.
    • size

      public int size()
      Gets the size of the instance as the number of vertexes in the larger graph. This is the required permutation length.
      Returns:
      the number of vertexes in the larger of the two graphs.
    • cost

      public int cost(Permutation candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface IntegerCostOptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.
    • value

      public int value(Permutation candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface IntegerCostOptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.
    • minCost

      public int minCost()
      Description copied from interface: IntegerCostOptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Integer.MIN_VALUE.
      Specified by:
      minCost in interface IntegerCostOptimizationProblem<Permutation>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.
    • maxValue

      public int maxValue()
      Determines an upper bound on the possible size in number of edges of the largest common subgraph. This is simply the smaller of the number of edges of the two graphs. Note it may or may not be possible to actually find a common subgraph with this number of edges. It is simply an upper bound.
      Returns:
      the minimum of the number of edges in graph 1 and graph 2.