GraphLinkFinder.java

Go to the documentation of this file.

/*
 *   DENOPTIM
 *   Copyright (C) 2022 Marco Foscato <marco.foscato@uib.no>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU Affero General Public License as published
 *   by the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU Affero General Public License for more details.
 *
 *   You should have received a copy of the GNU Affero General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
package denoptim.fragspace;
 
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
 
import denoptim.exception.DENOPTIMException;
import denoptim.graph.APClass;
import denoptim.graph.APMapping;
import denoptim.graph.AttachmentPoint;
import denoptim.graph.Edge;
import denoptim.graph.Vertex;
import denoptim.graph.Vertex.BBType;
 
public class GraphLinkFinder
{
    private Vertex chosenNewLink;
 
    private APMapping chosenAPMap;
    
    private LinkedHashMap<Vertex,List<APMapping>> allCompatLinks = 
            new LinkedHashMap<Vertex,List<APMapping>>();
    
    private static int maxCombs = 250;
    
    private boolean foundNewLink = false;
    
    private FragmentSpace fragmentSpace = null;
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace, Vertex originalLink) 
            throws DENOPTIMException
    {  
        this(fragSpace, originalLink, -1, false);
    }
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace,
            Vertex originalLink, int newBuildingBlockID) 
            throws DENOPTIMException
    {  
        this(fragSpace, originalLink, newBuildingBlockID, false);
    }
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace,
            Vertex originalLink, int newBuildingBlockID,
            boolean screenAll) throws DENOPTIMException 
    {   
        this.fragmentSpace = fragSpace;
        
        ArrayList<Vertex> candidates = getCandidateBBs(
                originalLink.getBuildingBlockType(), newBuildingBlockID);
        
        int candidatesOrigSize = candidates.size();
        for (int i=0; i<candidatesOrigSize; i++)
        {
            if (foundNewLink && !screenAll)
                break;
            
            Vertex originalBB = fragSpace.getRandomizer().randomlyChooseOne(
                    candidates);
            candidates.remove(originalBB);
            try
            {
                chosenNewLink = fragmentSpace.getVertexFromLibrary(
                        originalBB.getBuildingBlockType(), 
                        originalBB.getBuildingBlockId());
            } catch (DENOPTIMException e)
            {
                e.printStackTrace();
                continue;
            }
            
            // NB: the new link cannot be the same building block as the old one
            if (chosenNewLink.getBuildingBlockId() == 
                    originalLink.getBuildingBlockId())
            {
                continue;
            }
            
            if (chosenNewLink.getNumberOfAPs() < (originalLink.getNumberOfAPs() -
                    originalLink.getFreeAPCountThroughout()))
            {
                continue;
            }
            
            // We map all the compatibilities before choosing a specific mapping
            APMapFinder apmf = new APMapFinder(fragSpace, originalLink, 
                    chosenNewLink, screenAll);
            
            if (!apmf.foundMapping())
            {
                this.chosenNewLink = null;
                continue;
            } else {
                this.foundNewLink = true;
            }
            
            chosenAPMap = apmf.getChosenAPMapping();
            
            if (screenAll)
            {
                allCompatLinks.put(chosenNewLink, apmf.getAllAPMappings());
            }
        }
    }
    
//------------------------------------------------------------------------------
    
    private ArrayList<Vertex> getCandidateBBs(BBType bbt, int bbId) 
            throws DENOPTIMException 
    {
        ArrayList<Vertex> candidates = new ArrayList<Vertex>();
        if (bbId<0)
        {
            switch (bbt)
            {
                case FRAGMENT:
                    candidates.addAll(fragmentSpace.getFragmentLibrary());
                    break;
                case SCAFFOLD:
                    candidates.addAll(fragmentSpace.getScaffoldLibrary());
                case CAP:
                    break;
                default:
                    break;
            }
        } else {
            Vertex chosenOne =  fragmentSpace.getVertexFromLibrary(bbt, bbId);
            candidates.add(chosenOne);
        }
        return candidates;
    }
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace, Edge originalEdge) 
            throws DENOPTIMException
    {  
        this(fragSpace, originalEdge,-1,false);
    }
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace, Edge originalEdge, 
            int newBuildingBlockID) throws DENOPTIMException
    {  
        this(fragSpace, originalEdge,newBuildingBlockID,false);
    }
    
//------------------------------------------------------------------------------
 
    public GraphLinkFinder(FragmentSpace fragSpace,
            Edge originalEdge, int newBuildingBlockID,
            boolean screenAll) throws DENOPTIMException 
    {
        this.fragmentSpace = fragSpace;
        ArrayList<Vertex> candidates = getCandidateBBs(
                originalEdge.getTrgAP().getOwner().getBuildingBlockType(), 
                newBuildingBlockID);
 
        int candidatesOrigSize = candidates.size();
        for (int i=0; i<candidatesOrigSize; i++)
        {
            if (foundNewLink && !screenAll)
                break;
            
            Vertex originalBB = fragSpace.getRandomizer().randomlyChooseOne(
                    candidates);
            candidates.remove(originalBB);
            try
            {
                chosenNewLink = fragmentSpace.getVertexFromLibrary(
                        originalBB.getBuildingBlockType(), 
                        originalBB.getBuildingBlockId());
            } catch (DENOPTIMException e)
            {
                e.printStackTrace();
                continue;
            }
            
            if (chosenNewLink.getNumberOfAPs() < 2)
            {
                continue;
            }
            
            // We map all the compatibilities before choosing a specific mapping
            LinkedHashMap<AttachmentPoint,List<AttachmentPoint>> apCompatilities =
                    new LinkedHashMap<AttachmentPoint,List<AttachmentPoint>>();
            
            List<AttachmentPoint> needeAPs = new ArrayList<AttachmentPoint>();
            needeAPs.add(originalEdge.getSrcAP());
            needeAPs.add(originalEdge.getTrgAP());
            for (int j=0; j<2;j++)
            {
                AttachmentPoint oAP = needeAPs.get(j);
                APClass oriAPC = oAP.getAPClass();
                for (AttachmentPoint cAP : chosenNewLink.getAttachmentPoints())
                {  
                    boolean compatible = false;
                    if (fragmentSpace.useAPclassBasedApproach())
                    {
                        if (j==0 
                                && oriAPC.isCPMapCompatibleWith(
                                        cAP.getAPClass(),
                                        fragmentSpace))
                            compatible = true;
                        else if (j==1 
                                && cAP.getAPClass().isCPMapCompatibleWith(
                                        oriAPC, fragmentSpace))
                            compatible = true;
                    } else {
                        compatible = true;
                    }
                    if (compatible)
                    {
                        if (apCompatilities.containsKey(oAP))
                        {
                            apCompatilities.get(oAP).add(cAP);
                        } else {
                            List<AttachmentPoint> lst = 
                                    new ArrayList<AttachmentPoint>();
                            lst.add(cAP);
                            apCompatilities.put(oAP,lst);
                        }
                    }
                }
            }
            // keys is used just to keep the map keys sorted in a separate list
            // so that the order is randomized only once, then it is retained.
            List<AttachmentPoint> keys = 
                    new ArrayList<AttachmentPoint>(
                            apCompatilities.keySet());
            if (keys.size() < 2)
            {
                continue;
            }
            
            // Get all possible combinations of compatible AP pairs
            List<APMapping> apMappings = new ArrayList<APMapping>();
            int currentKey = 0;
            APMapping currentMapping = new APMapping();
            // yes, a nested loop would do it, but for now I use the same code
            // as for when there is no limit to the number of keys (here, always 2)
            FragmentSpaceUtils.recursiveCombiner(keys, 
                    currentKey, apCompatilities, currentMapping, apMappings, 
                    screenAll, maxCombs);
            
            if (apMappings.isEmpty())
            {
                this.chosenNewLink = null;
                continue;
            } else {
                this.foundNewLink = true;
            }
            
            this.chosenAPMap = fragSpace.getRandomizer().randomlyChooseOne(
                    apMappings);
            if (screenAll)
            {
                allCompatLinks.put(chosenNewLink, apMappings);
            }
        }
    }
    
//------------------------------------------------------------------------------
    
    public Vertex getChosenAlternativeLink()
    {
        return chosenNewLink;
    }
    
//------------------------------------------------------------------------------
    
    public APMapping getChosenAPMapping()
    {
        return chosenAPMap;
    }
    
//------------------------------------------------------------------------------
    
    public LinkedHashMap<Vertex, List<APMapping>> getAllAlternativesFound()
    {
        return allCompatLinks;
    }
    
//------------------------------------------------------------------------------
    
    public boolean foundAlternativeLink()
    {
        return foundNewLink;
    }
    
//------------------------------------------------------------------------------
 
}