An utility class to encapsulate the search for vertexes that satisfy constraints. More...

Collaboration diagram for denoptim.fragspace.GraphLinkFinder:

Public Member Functions
	GraphLinkFinder (FragmentSpace fragSpace, Vertex originalLink) throws DENOPTIMException
	Constructor that specifies which vertex has to be replaced. More...

	GraphLinkFinder (FragmentSpace fragSpace, Vertex originalLink, int newBuildingBlockID) throws DENOPTIMException
	Constructor that specifies which vertex has to be replaced and which building block ID to use as replacement. More...

	GraphLinkFinder (FragmentSpace fragSpace, Vertex originalLink, int newBuildingBlockID, boolean screenAll) throws DENOPTIMException
	Constructor that specifies which vertex has to be replaced. More...

	GraphLinkFinder (FragmentSpace fragSpace, Edge originalEdge) throws DENOPTIMException
	Constructor that specifies which edge has to be replaced with a vertex and two edges. More...

	GraphLinkFinder (FragmentSpace fragSpace, Edge originalEdge, int newBuildingBlockID) throws DENOPTIMException
	Constructor that specifies which edge has to be replaced with a vertex and two edges. More...

	GraphLinkFinder (FragmentSpace fragSpace, Edge originalEdge, int newBuildingBlockID, boolean screenAll) throws DENOPTIMException
	Constructor that specifies which edge has to be replaced with a vertex and two edges. More...

Vertex	getChosenAlternativeLink ()
	Returns the vertex chosen as alternative. More...

APMapping	getChosenAPMapping ()
	Returns the AP mapping that allows the usage of the vertex chosen either as alternative to be installed in the slot originally occupied by the original vertex, or to be inserted in between two vertexes. More...

LinkedHashMap< Vertex, List< APMapping > >	getAllAlternativesFound ()
	Returns all the AP mapping that were identified for any candidate vertex that could be used either as alternative to be installed in the slot originally occupied by the original vertex, or to be inserted in between two vertexes. More...

boolean	foundAlternativeLink ()

Private Member Functions
ArrayList< Vertex >	getCandidateBBs (BBType bbt, int bbId) throws DENOPTIMException

Private Attributes
Vertex	chosenNewLink
	The result of the search for a compatible building block, or null if no compatible link was found. More...

APMapping	chosenAPMap
	The mapping of attachment points between the original vertex/es and the chosen link. More...

LinkedHashMap< Vertex, List< APMapping > >	allCompatLinks
	The collection of all alternative vertex that can replace the original vertex, with the consistent mappings. More...

boolean	foundNewLink = false
	Flag recording if at least one alternative vertex was found. More...

FragmentSpace	fragmentSpace = null
	Parameter and reference to the fragment space. More...

Static Private Attributes
static int	maxCombs = 250
	Maximum number of combinations. More...

Detailed Description

An utility class to encapsulate the search for vertexes that satisfy constraints.

Typically, this class can be used to find building blocks that they replace other, non identical, building blocks in a graph while retaining the graph structure, i.e., the new building blocks offers at least enough APs (and APs that are compatible with the surrounding graph branches) to replace the original building block. Another example of use case, is the identification of a building block that can be inserted in between two connected vertexes of a graph.

Author: Marco Foscato

Definition at line 46 of file GraphLinkFinder.java.

Constructor & Destructor Documentation

◆ GraphLinkFinder() [1/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Vertex	originalLink
	)		throws DENOPTIMException

Constructor that specifies which vertex has to be replaced.

The search for an alternative building block takes place within this constructor.

Parameters

originalLink the vertex to replace.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 101 of file GraphLinkFinder.java.

◆ GraphLinkFinder() [2/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Vertex	originalLink,
		int	newBuildingBlockID
	)		throws DENOPTIMException

Constructor that specifies which vertex has to be replaced and which building block ID to use as replacement.

Parameters

originalLink	the vertex to replace.
newBuildingBlockID	the index specifying which building block to use as replacement. This can be -1, in which case, this method will search suitable building block candidates and choose randomly.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 119 of file GraphLinkFinder.java.

◆ GraphLinkFinder() [3/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Vertex	originalLink,
		int	newBuildingBlockID,
		boolean	screenAll
	)		throws DENOPTIMException

Constructor that specifies which vertex has to be replaced.

The search for an alternative building block takes place within this constructor.

Parameters

originalLink	the vertex to replace.
newBuildingBlockID	the index specifying which building block to use as replacement. This can be -1, in which case, this method will search suitable building block candidates and choose randomly.
screenAll	use `true` to NOT stop at the first compatible vertex, but screen all the library of building blocks.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 141 of file GraphLinkFinder.java.

Here is the call graph for this function:

◆ GraphLinkFinder() [4/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Edge	originalEdge
	)		throws DENOPTIMException

Constructor that specifies which edge has to be replaced with a vertex and two edges.

The search for an alternative building block takes place within this constructor.

Parameters

originalEdge	the vertex to replace.
newBuildingBlockID	the index specifying which building block to use for the linking vertex. This can be -1, in which case, this method will search suitable building block candidates and choose randomly.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 245 of file GraphLinkFinder.java.

◆ GraphLinkFinder() [5/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Edge	originalEdge,
		int	newBuildingBlockID
	)		throws DENOPTIMException

Constructor that specifies which edge has to be replaced with a vertex and two edges.

The search for an alternative building block takes place within this constructor.

Parameters

originalEdge	the vertex to replace.
newBuildingBlockID	the index specifying which building block to use for the linking vertex. This can be -1, in which case, this method will search suitable building block candidates and choose randomly.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 265 of file GraphLinkFinder.java.

◆ GraphLinkFinder() [6/6]

denoptim.fragspace.GraphLinkFinder.GraphLinkFinder	(	FragmentSpace	fragSpace,
		Edge	originalEdge,
		int	newBuildingBlockID,
		boolean	screenAll
	)		throws DENOPTIMException

Constructor that specifies which edge has to be replaced with a vertex and two edges.

The search for an alternative building block takes place within this constructor.

Parameters

originalEdge	the vertex to replace.
newBuildingBlockID	the index specifying which building block to use for the linking vertex. This can be -1, in which case, this method will search suitable building block candidates and choose randomly.
screenAll	use `true` to NOT stop at the first compatible vertex, but screen all the library of building blocks.

Exceptions

DENOPTIMException if the required new building block ID cannot be used.

Definition at line 288 of file GraphLinkFinder.java.

Here is the call graph for this function:

Member Function Documentation

◆ foundAlternativeLink()

boolean denoptim.fragspace.GraphLinkFinder.foundAlternativeLink ( )

Definition at line 467 of file GraphLinkFinder.java.

References denoptim.fragspace.GraphLinkFinder.foundNewLink.

Referenced by denoptim.ga.GraphOperations.extendLink(), and denoptim.ga.GraphOperations.substituteLink().

Here is the caller graph for this function:

◆ getAllAlternativesFound()

LinkedHashMap< Vertex, List< APMapping > > denoptim.fragspace.GraphLinkFinder.getAllAlternativesFound ( )

Returns all the AP mapping that were identified for any candidate vertex that could be used either as alternative to be installed in the slot originally occupied by the original vertex, or to be inserted in between two vertexes.

The meaning of the mapping depends on how this GraphLinkFinder was constructed.

Returns: map of all AP mappings for each alternative vertex.

Definition at line 460 of file GraphLinkFinder.java.

References denoptim.fragspace.GraphLinkFinder.allCompatLinks.

Referenced by denoptim.fragspace.GraphLinkFinderTest.testLinkFromEdge(), denoptim.fragspace.GraphLinkFinderTest.testLinkFromEdgeNoMatch(), denoptim.fragspace.GraphLinkFinderTest.testLinkFromEdgeOneMatch(), and denoptim.fragspace.GraphLinkFinderTest.testLinkFromVertex().

Here is the caller graph for this function:

◆ getCandidateBBs()

ArrayList< Vertex > denoptim.fragspace.GraphLinkFinder.getCandidateBBs	(	BBType	bbt,
		int	bbId
	)		throws DENOPTIMException

private

Definition at line 206 of file GraphLinkFinder.java.

References denoptim.fragspace.GraphLinkFinder.fragmentSpace, denoptim.fragspace.FragmentSpace.getFragmentLibrary(), denoptim.fragspace.FragmentSpace.getScaffoldLibrary(), and denoptim.fragspace.FragmentSpace.getVertexFromLibrary().

Referenced by denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getChosenAlternativeLink()

Vertex denoptim.fragspace.GraphLinkFinder.getChosenAlternativeLink ( )

Returns the vertex chosen as alternative.

If more than one possibilities exist, then this will return a randomly chosen one. Consistency between the return value of this method and GraphLinkFinder#getChosenAPMapping() is guaranteed.

Returns: the chosen alternative or null is none was found.

Definition at line 410 of file GraphLinkFinder.java.

References denoptim.fragspace.GraphLinkFinder.chosenNewLink.

Referenced by denoptim.ga.GraphOperations.extendLink(), and denoptim.ga.GraphOperations.substituteLink().

Here is the caller graph for this function:

◆ getChosenAPMapping()

APMapping denoptim.fragspace.GraphLinkFinder.getChosenAPMapping ( )

Returns the AP mapping that allows the usage of the vertex chosen either as alternative to be installed in the slot originally occupied by the original vertex, or to be inserted in between two vertexes.

The meaning of the mapping depends on how this GraphLinkFinder was constructed. In particular, when this instance is constructed from an Vertex, the syntax of the AP mapping is:

keys: the APs of the original vertex from which we seek replacement.
values: the APs that belong on the new vertex returned by GraphLinkFinder#getChosenAlternativeLink().

Otherwise, when this instance if constructed from an Edge, the AP mapping's syntax is:

keys: the APs originally involved in making that edge,
values: the APs that belong on the new vertex returned by GraphLinkFinder#getChosenAlternativeLink() and that can be connected to the corresponding AP in the key.

If more than one possible mapping exist, then this will return a randomly chosen one. Consistency between the return value of this method and GraphLinkFinder#getChosenAlternativeLink() is guaranteed.

Returns: the chosen AP mapping or null is none was found.

Definition at line 443 of file GraphLinkFinder.java.

References denoptim.fragspace.GraphLinkFinder.chosenAPMap.

Referenced by denoptim.ga.GraphOperations.extendLink(), and denoptim.ga.GraphOperations.substituteLink().

Here is the caller graph for this function:

Member Data Documentation

◆ allCompatLinks

LinkedHashMap<Vertex,List<APMapping> > denoptim.fragspace.GraphLinkFinder.allCompatLinks

private

Initial value:

=

new LinkedHashMap<Vertex,List<APMapping>>()

The collection of all alternative vertex that can replace the original vertex, with the consistent mappings.

This field is null in case the constructor was asked to work on an edge rather than a vertex.

Definition at line 70 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.getAllAlternativesFound(), and denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

◆ chosenAPMap

APMapping denoptim.fragspace.GraphLinkFinder.chosenAPMap

private

The mapping of attachment points between the original vertex/es and the chosen link.

In case of multiple possible AP mappings, the result reported here is randomly chosen among the possible ones.

Definition at line 61 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.getChosenAPMapping(), and denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

◆ chosenNewLink

Vertex denoptim.fragspace.GraphLinkFinder.chosenNewLink

private

The result of the search for a compatible building block, or null if no compatible link was found.

In case of multiple possibilities, the result reported here is chosen randomly among the possible ones.

Definition at line 53 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.getChosenAlternativeLink(), and denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

◆ foundNewLink

boolean denoptim.fragspace.GraphLinkFinder.foundNewLink = false

private

Flag recording if at least one alternative vertex was found.

Definition at line 85 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.foundAlternativeLink(), and denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

◆ fragmentSpace

FragmentSpace denoptim.fragspace.GraphLinkFinder.fragmentSpace = null

private

Parameter and reference to the fragment space.

Definition at line 90 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.getCandidateBBs(), and denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

◆ maxCombs

int denoptim.fragspace.GraphLinkFinder.maxCombs = 250

staticprivate

Maximum number of combinations.

This prevents combinatorial explosion, but it is ignored if the constructor is required to screen all. Remember that the combinations are anyway randomized, so even with the maximum limit on the number of combination to consider, there is no systematic exclusion of specific combinations.

Definition at line 80 of file GraphLinkFinder.java.

Referenced by denoptim.fragspace.GraphLinkFinder.GraphLinkFinder().

The documentation for this class was generated from the following file:

/github/workspace/src/main/java/denoptim/fragspace/GraphLinkFinder.java

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GraphLinkFinder() [1/6]

◆ GraphLinkFinder() [2/6]

◆ GraphLinkFinder() [3/6]

◆ GraphLinkFinder() [4/6]

◆ GraphLinkFinder() [5/6]

◆ GraphLinkFinder() [6/6]

Member Function Documentation

◆ foundAlternativeLink()

◆ getAllAlternativesFound()

◆ getCandidateBBs()

◆ getChosenAlternativeLink()

◆ getChosenAPMapping()

Member Data Documentation

◆ allCompatLinks

◆ chosenAPMap

◆ chosenNewLink

◆ foundNewLink

◆ fragmentSpace

◆ maxCombs