APMapFinder.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.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Set;
 
import denoptim.graph.APClass;
import denoptim.graph.APMapping;
import denoptim.graph.AttachmentPoint;
import denoptim.graph.DGraph;
import denoptim.graph.Vertex;
 
public class APMapFinder
{   
    private APMapping chosenAPMap;
    
    private List<APMapping> allAPMappings = new ArrayList<APMapping>();
    
    public static final int DEFAULT_MAX_COMBS = 250;
 
    private int maxCombs = DEFAULT_MAX_COMBS;
    
    private FragmentSpace fragSpace = null;
    
//------------------------------------------------------------------------------
 
    public APMapFinder(FragmentSpace fragSpace,
            Vertex vA, Vertex vB, boolean screenAll)
    {
        this(fragSpace, vA, vB, null, screenAll, false, true);
    }
    
//------------------------------------------------------------------------------
 
    public APMapFinder(FragmentSpace fragSpace, 
            Vertex vA, Vertex vB, 
            APMapping fixedRootAPs, boolean screenAll,
            boolean onlyCompleteMappings, boolean compatibleIfFree) 
    {
        this(fragSpace, vA, vB, fixedRootAPs, screenAll, onlyCompleteMappings,
                compatibleIfFree, DEFAULT_MAX_COMBS);
    }
 
//------------------------------------------------------------------------------
 
    public APMapFinder(FragmentSpace fragSpace, 
            Vertex vA, Vertex vB, 
            APMapping fixedRootAPs, boolean screenAll,
            boolean onlyCompleteMappings, boolean compatibleIfFree,
            int maxCombs) 
    {
        this.fragSpace = fragSpace;
        this.maxCombs = maxCombs;
        List<AttachmentPoint> needyAPsA = new ArrayList<AttachmentPoint>();
        if (vA.getGraphOwner()!=null)
        {
            List<Vertex> subgraph = new ArrayList<Vertex>();
            subgraph.add(vA);
            needyAPsA = vA.getGraphOwner().getInterfaceAPs(subgraph);
        }
        List<AttachmentPoint> needyAPsB = 
                new ArrayList<AttachmentPoint>();
        if (vB.getGraphOwner()!=null)
        {
            List<Vertex> subgraph = new ArrayList<Vertex>();
            subgraph.add(vB);
            needyAPsB = vB.getGraphOwner().getInterfaceAPs(subgraph);
        }
        findAllMappings(vA.getAttachmentPoints(), needyAPsA, 
                vB.getAttachmentPoints(), needyAPsB,
                fixedRootAPs, screenAll, onlyCompleteMappings, compatibleIfFree);
    }
    
//------------------------------------------------------------------------------
 
    public APMapFinder(FragmentSpace fragSpace,
            List<AttachmentPoint> lstA, 
            List<AttachmentPoint> needyAPsA,
            List<AttachmentPoint> lstB, 
            List<AttachmentPoint> needyAPsB,
            APMapping fixedRootAPs, boolean screenAll,
            boolean onlyCompleteMappings, boolean compatibleIfFree) 
    {
        this(fragSpace, lstA, needyAPsA, lstB, needyAPsB, fixedRootAPs,
                screenAll, onlyCompleteMappings, compatibleIfFree,
                DEFAULT_MAX_COMBS);
    }
 
//------------------------------------------------------------------------------
 
    public APMapFinder(FragmentSpace fragSpace,
            List<AttachmentPoint> lstA, 
            List<AttachmentPoint> needyAPsA,
            List<AttachmentPoint> lstB, 
            List<AttachmentPoint> needyAPsB,
            APMapping fixedRootAPs, boolean screenAll,
            boolean onlyCompleteMappings, boolean compatibleIfFree,
            int maxCombs) 
    {
        this.fragSpace = fragSpace;
        this.maxCombs = maxCombs;
        findAllMappings(lstA, needyAPsA, lstB, needyAPsB,
                fixedRootAPs, screenAll, onlyCompleteMappings, compatibleIfFree);
    }
    
//------------------------------------------------------------------------------
 
    private void findAllMappings(List<AttachmentPoint> lstA, 
            List<AttachmentPoint> needyAPsA,
            List<AttachmentPoint> lstB, 
            List<AttachmentPoint> needyAPsB,
            APMapping fixedRootAPs, boolean screenAll, 
            boolean onlyCompleteMappings, boolean compatibleIfFree) 
    {
        // Remove from the lists those APs that have already a mapping
        List<AttachmentPoint> purgedLstA = new ArrayList<AttachmentPoint>(lstA);
        if (fixedRootAPs!=null)
        {
            purgedLstA.removeAll(fixedRootAPs.keySet());
        }
        List<AttachmentPoint> purgedLstB = new ArrayList<AttachmentPoint>(lstB);
        if (fixedRootAPs!=null)
        {
            purgedLstB.removeAll(fixedRootAPs.values());
        }
        
        // Map all the compatibilities before choosing a specific mapping
        LinkedHashMap<AttachmentPoint,List<AttachmentPoint>> apCompatilities = 
                findMappingCompatibileAPs(purgedLstA, purgedLstB, 
                    compatibleIfFree, fragSpace);
        
        // The '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 (fixedRootAPs!=null)
        {
            // Since these are constrained we do not need them among the keys 
            // when looking over the combinations of keys
            keys.removeAll(fixedRootAPs.keySet());
        }
        
        // Test if we have enough AP compatibilities to satisfy the constraints
        Set<AttachmentPoint> doableAPsA = new HashSet<AttachmentPoint>(keys);
        if (fixedRootAPs!=null)
            doableAPsA.addAll(fixedRootAPs.keySet());
        Set<AttachmentPoint> doableAPsB = new HashSet<AttachmentPoint>();
        apCompatilities.values().stream().forEach(l -> doableAPsB.addAll(l));
        if (onlyCompleteMappings)
        {
            for (AttachmentPoint oldAp : lstA)
            {
                if (!needyAPsA.contains(oldAp))
                    needyAPsA.add(oldAp);
            }
            for (AttachmentPoint oldAp : lstB)
            {
                if (!needyAPsB.contains(oldAp))
                    needyAPsB.add(oldAp);
            }
        }
        Set<AttachmentPoint> mustBeDoableA = new HashSet<AttachmentPoint>(
                needyAPsA);
        Set<AttachmentPoint> mustBeDoableB = new HashSet<AttachmentPoint>(
                needyAPsB);
        if (fixedRootAPs!=null)
        {
            mustBeDoableA.removeAll(fixedRootAPs.keySet());
            mustBeDoableB.removeAll(fixedRootAPs.values());
        }
        if (!doableAPsA.containsAll(mustBeDoableA) 
                || !doableAPsB.containsAll(mustBeDoableB))
        {
            return;
        }
        
        if (!onlyCompleteMappings)
        {
            for (AttachmentPoint oldAp : lstA)
            {
                if (oldAp.isAvailableThroughout())
                {
                    // NB: adding 'null' will allow the presence of AP mappings
                    // where oldAP is intentionally left out of the mapping thus
                    // allowing to let it stay free.
                    if (apCompatilities.containsKey(oldAp))
                    {
                        apCompatilities.get(oldAp).add(null);
                    }
                }
            }
        }
        
        // Get all possible combinations of compatible AP pairs
        int currentKey = 0;
        APMapping currentMapping = new APMapping();
        if (fixedRootAPs!=null)
        {
            currentMapping = fixedRootAPs.clone(); //shallow
        }
        // We try the comprehensive approach, but if that is too demanding
        // and gets stopped, then we run a series of simplified attempts
        // to hit a decent combination with "lucky shots".
        Boolean stopped = false;
        if (keys.size()>0)
        {
            stopped = FragmentSpaceUtils.recursiveCombiner(keys, 
                    currentKey, apCompatilities, currentMapping, allAPMappings, 
                    screenAll, maxCombs);
        } else {
            // This would have been done by the recursive combiner
            allAPMappings.add(currentMapping);
        }
        
        // Purge according to lists of APs that needs a mapping
        List<APMapping> toRemove = new ArrayList<APMapping>();
        for (APMapping c : allAPMappings)
        {
            if (!c.containsAllKeys(needyAPsA))
            {
                toRemove.add(c);
            }
            if (!c.containsAllValues(needyAPsB))
            {
                toRemove.add(c);
            }
        }
        allAPMappings.removeAll(toRemove);
        
        // If we where interrupted, we try to get a proper mapping again.
        // This time we ignore all the possibilities and try a more direct 
        // approach, which, however, cannot account for all possible combs.
        if (stopped && allAPMappings.isEmpty())
        {
            for (int iTry = 0; iTry < maxCombs; iTry++)
            {
                APMapping apMap = new APMapping();
                List<AttachmentPoint> used = 
                        new ArrayList<AttachmentPoint>();
                List<AttachmentPoint> availKeys = 
                        new ArrayList<AttachmentPoint>();
                availKeys.addAll(needyAPsA);
                boolean abandon = false;
                for (int jj=0; jj<needyAPsA.size(); jj++)
                {
                    AttachmentPoint ap = 
                            fragSpace.getRandomizer().randomlyChooseOne(
                                    availKeys);
                    availKeys.remove(ap);
                    List<AttachmentPoint> availPartners = 
                            new ArrayList<AttachmentPoint>();
                    availPartners.addAll(apCompatilities.get(ap));
                    boolean done = false;
                    for (int j=0; j<apCompatilities.get(ap).size(); j++)
                    {
                        AttachmentPoint chosenAvail = 
                                fragSpace.getRandomizer().randomlyChooseOne(
                                        availPartners);
                        availPartners.remove(chosenAvail);
                        if (used.contains(chosenAvail))
                        {
                            continue;
                        }
                        used.add(chosenAvail);
                        apMap.put(ap,chosenAvail);
                        done = true;
                        break;
                    }
                    if (!done)
                    {
                        abandon = true;
                        break;
                    }
                }
                
                if (!abandon)
                {
                    allAPMappings.add(apMap);
                    break;
                }
            }
        }
        if (allAPMappings.size() > 0)
            chosenAPMap = fragSpace.getRandomizer().randomlyChooseOne(
                    allAPMappings);
    }
    
//------------------------------------------------------------------------------
    
    public static LinkedHashMap<AttachmentPoint,List<AttachmentPoint>> 
        findMappingCompatibileAPs(List<AttachmentPoint> lstA, 
            List<AttachmentPoint> lstB, boolean compatibleIfFree,
            FragmentSpace fragSpace)
    {
        LinkedHashMap<AttachmentPoint,List<AttachmentPoint>> 
        apCompatilities = new LinkedHashMap<AttachmentPoint,
        List<AttachmentPoint>>();
    
        for (AttachmentPoint oAP : lstA)
        {
            for (AttachmentPoint cAP : lstB)
            {  
                boolean compatible = false;
                if (fragSpace.useAPclassBasedApproach())
                {
                    // Addressing the cases where the APs are used/free
                    // and have src/trg role
                    
                    boolean oAPInUse = !oAP.isAvailableThroughout();
                    boolean oAPIsSrc = oAP.isSrcInUserThroughout();
                    boolean oAPIsTrg = oAPInUse && !oAP.isSrcInUserThroughout();
 
                    boolean cAPInUse = !cAP.isAvailableThroughout();
                    boolean cAPIsSrc = cAP.isSrcInUserThroughout();
                    boolean cAPIsTrg = cAPInUse && !cAP.isSrcInUserThroughout();
                    
                    // These can be null if AP is not in use!
                    AttachmentPoint loAP = oAP.getLinkedAPThroughout();
                    AttachmentPoint lcAP = cAP.getLinkedAPThroughout();
                    
                    APClass oAPcl = oAP.getAPClass();
                    APClass cAPcl = cAP.getAPClass();
                    APClass loAPcl = null;
                    if (loAP!=null)
                        loAPcl = loAP.getAPClass();
                    APClass lcAPcl = null;
                    if (lcAP!=null)
                        lcAPcl = lcAP.getAPClass();
                    
                    // TODO: if the vertex is a template, we should
                    // consider the required APs.
                    
                    if (oAP.getAPClass().equals(cAP.getAPClass()))
                    {
                        compatible = true;
                    } else {
                        if (!oAPInUse && !cAPInUse && compatibleIfFree)
                        {
                            compatible = true;
                        } else if (!oAPInUse && cAPInUse && compatibleIfFree)
                        {
                            if (cAPIsSrc && oAPcl.isCPMapCompatibleWith(lcAPcl, 
                                    fragSpace))
                            {
                                compatible = true;
                            } else if (cAPIsTrg && lcAPcl.isCPMapCompatibleWith(
                                    oAPcl, fragSpace))
                            {
                                compatible = true;
                            }
                        } else if (oAPInUse && !cAPInUse && compatibleIfFree)
                        {
                            if (oAPIsSrc && cAPcl.isCPMapCompatibleWith(loAPcl, 
                                    fragSpace))
                            {
                                compatible = true;
                            } else if (oAPIsTrg && loAPcl.isCPMapCompatibleWith(
                                    cAPcl, fragSpace))
                            {
                                compatible = true;
                            }
                        } else if (oAPInUse && cAPInUse) 
                        {
                            if (oAPIsSrc && cAPIsSrc)
                            {
                                // both are SRC
                                if (oAPcl.isCPMapCompatibleWith(lcAPcl, 
                                        fragSpace) 
                                    && cAPcl.isCPMapCompatibleWith(loAPcl,
                                        fragSpace))
                                {
                                    compatible = true;
                                }
                            } else if ((!oAPIsSrc && cAPIsSrc)
                                || (oAPIsSrc && !cAPIsSrc))
                            {
                                // Since directions will have to be inverted, we
                                // want the APClass compatibility to exists in
                                // both directions on each connection.
                                if (oAPcl.isCPMapCompatibleWith(lcAPcl, 
                                        fragSpace) 
                                    && lcAPcl.isCPMapCompatibleWith(oAPcl,
                                            fragSpace)
                                    && cAPcl.isCPMapCompatibleWith(loAPcl,
                                        fragSpace)
                                    && loAPcl.isCPMapCompatibleWith(cAPcl,
                                            fragSpace))
                                {
                                    compatible = true;
                                }
                            } else {
                                // both oAP and cAP are TRG
                                if (lcAPcl.isCPMapCompatibleWith(oAPcl,
                                            fragSpace)
                                    && loAPcl.isCPMapCompatibleWith(cAPcl,
                                            fragSpace))
                                {
                                    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);
                    }
                }
            }
        }
        return apCompatilities;
    }
    
//------------------------------------------------------------------------------
    
    public boolean foundMapping()
    {
        return !allAPMappings.isEmpty();
    }
    
//------------------------------------------------------------------------------
    
    public APMapping getChosenAPMapping()
    {
        return chosenAPMap;
    }
    
//------------------------------------------------------------------------------
    
    public List<APMapping> getAllAPMappings()
    {
        return allAPMappings;
    }
    
//------------------------------------------------------------------------------
 
}