Class LargestCommonSubgraph
 All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>
,Problem<Permutation>
This class is an implementation of the Largest Common Subgraph problem, an NPHard combinatorial optimization problem. In the problem, we are given two graphs G_{1} and G_{2}. The problem is to find the largest graph G_{c}, measured in number of edges, that is isomorphic to a subgraph of G_{1} and a subgraph of G_{2}.
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 G_{1} and G_{2} (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 G_{1} is mapped to vertex j in G_{2}. This assumes that G_{1} has at most the number of vertexes as G_{2}.

Nested Class Summary
Modifier and TypeClassDescriptionstatic final class
This class is used to represent edges when specifying instances of theLargestCommonSubgraph
problem. 
Constructor Summary
ConstructorDescriptionLargestCommonSubgraph
(int v, double density, boolean isomorphic) Constructs a random instance of the largest common subgraph problem.LargestCommonSubgraph
(int v, double density, boolean isomorphic, long seed) Constructs a random instance of the largest common subgraph problem.LargestCommonSubgraph
(int v1, int v2, double density1, double density2) Constructs a random instance of the largest common subgraph problem.LargestCommonSubgraph
(int v1, int v2, double density1, double density2, long seed) Constructs a random instance of the largest common subgraph problem.LargestCommonSubgraph
(int v1, int v2, List<LargestCommonSubgraph.Edge> edges1, List<LargestCommonSubgraph.Edge> edges2) Constructs a random instance of the largest common subgraph problem. 
Method Summary
Modifier and TypeMethodDescriptionint
cost
(Permutation candidate) Computes the cost of a candidate solution to the problem instance.static LargestCommonSubgraph
createInstanceGeneralizedPetersenGraph
(int n, int k) Creates an instance of the Largest Common Subgraph problem for a pair of isomorphic Generalized Petersen Graphs.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.int
maxValue()
Determines an upper bound on the possible size in number of edges of the largest common subgraph.int
minCost()
A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.int
size()
Gets the size of the instance as the number of vertexes in the larger graph.int
value
(Permutation candidate) Computes the value of the candidate solution within the usual constraints and interpretation of the problem.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.cicirello.search.problems.IntegerCostOptimizationProblem
costAsDouble, getSolutionCostPair, isMinCost

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
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
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
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 interfaceIntegerCostOptimizationProblem<Permutation>
 Parameters:
candidate
 The candidate solution to evaluate. Returns:
 The cost of the candidate solution. Lower cost means better solution.

value
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 interfaceIntegerCostOptimizationProblem<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 interfaceIntegerCostOptimizationProblem<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.
