Module org.cicirello.chips_n_salsa

Package org.cicirello.search.problems

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 G₁ and G₂. The problem is to find the largest graph G_c, measured in number of edges, that is isomorphic to a subgraph of G₁ and a subgraph of G₂.

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₁ and G₂ (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₁ is mapped to vertex j in G₂. This assumes that G₁ has at most the number of vertexes as G₂.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	LargestCommonSubgraph.Edge	This class is used to represent edges when specifying instances of the LargestCommonSubgraph problem.

Constructor Summary

Constructors

Constructor	Description
LargestCommonSubgraph(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 Type	Method	Description
int	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

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.