DGraph.java

Go to the documentation of this file.

/*
 *   DENOPTIM
 *   Copyright (C) 2019 Vishwesh Venkatraman <vishwesh.venkatraman@ntnu.no> and
 *   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.graph;
 
import java.io.File;
import java.io.Reader;
import java.lang.reflect.Type;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.stream.Collectors;
 
import org.jgrapht.alg.isomorphism.VF2GraphIsomorphismInspector;
import org.jgrapht.graph.DefaultUndirectedGraph;
import org.openscience.cdk.graph.ConnectivityChecker;
import org.openscience.cdk.interfaces.IAtom;
import org.openscience.cdk.interfaces.IAtomContainer;
 
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;
import com.google.gson.JsonArray;
import com.google.gson.JsonDeserializationContext;
import com.google.gson.JsonDeserializer;
import com.google.gson.JsonElement;
import com.google.gson.JsonObject;
import com.google.gson.JsonParseException;
import com.google.gson.JsonSerializationContext;
import com.google.gson.JsonSerializer;
 
import denoptim.constants.DENOPTIMConstants;
import denoptim.exception.DENOPTIMException;
import denoptim.fragspace.FragmentSpace;
import denoptim.fragspace.FragmentSpaceParameters;
import denoptim.graph.APClass.APClassDeserializer;
import denoptim.graph.Edge.BondType;
import denoptim.graph.Template.ContractLevel;
import denoptim.graph.Vertex.BBType;
import denoptim.graph.Vertex.DENOPTIMVertexDeserializer;
import denoptim.graph.Vertex.VertexType;
import denoptim.graph.rings.ClosableChain;
import denoptim.graph.rings.CyclicGraphHandler;
import denoptim.graph.rings.PathSubGraph;
import denoptim.graph.rings.RingClosingAttractor;
import denoptim.graph.rings.RingClosureParameters;
import denoptim.graph.simplified.Node;
import denoptim.graph.simplified.NodeConnection;
import denoptim.graph.simplified.UndirectedEdge;
import denoptim.io.DenoptimIO;
import denoptim.json.DENOPTIMgson;
import denoptim.json.DENOPTIMgson.DENOPTIMExclusionStrategyNoAPMap;
import denoptim.molecularmodeling.ThreeDimTreeBuilder;
import denoptim.programs.RunTimeParameters;
import denoptim.programs.RunTimeParameters.ParametersType;
import denoptim.utils.GeneralUtils;
import denoptim.utils.GraphConversionTool;
import denoptim.utils.GraphEdit;
import denoptim.utils.GraphUtils;
import denoptim.utils.MoleculeUtils;
import denoptim.utils.MutationType;
import denoptim.utils.ObjectPair;
import denoptim.utils.RotationalSpaceUtils;
 
 
public class DGraph implements Cloneable
{
    List<Vertex> gVertices;
 
    List<Edge> gEdges;
 
    List<Ring> gRings;
 
    List<ClosableChain> closableChains;
 
    /*
     * Unique graph id
     */
    int graphId;
 
    /*
     * store the set of symmetric vertex ids at each level. This is only
     * applicable for symmetric graphs
     */
    private List<SymmetricVertexes> symVertices;
 
    String localMsg;
 
    Candidate candidate;
    
    Template templateJacket;
    
    private DefaultUndirectedGraph<Vertex, UndirectedEdge> 
        jGraph = null;
    
    private DefaultUndirectedGraph<Node, NodeConnection> 
        jGraphKernel = null;
 
    public enum StringFormat {JSON, GRAPHENC}
    
    private AtomicInteger apCounter = new AtomicInteger(1);
 
 
//------------------------------------------------------------------------------
 
    public DGraph(List<Vertex> gVertices, List<Edge> gEdges)
    {
        this.gVertices = gVertices;
        for (Vertex v : this.gVertices)
            v.setGraphOwner(this);
        this.gEdges = gEdges;
        gRings = new ArrayList<>();
        closableChains = new ArrayList<>();
        symVertices = new ArrayList<>();
        localMsg = "";
    }
 
//------------------------------------------------------------------------------
 
    public DGraph(List<Vertex> gVertices, List<Edge> gEdges, List<Ring> gRings)
    {
        this(gVertices, gEdges);
        this.gRings = gRings;
        closableChains = new ArrayList<>();
        symVertices = new ArrayList<>();
        localMsg = "";
    }
 
//------------------------------------------------------------------------------
 
    public DGraph(List<Vertex> gVertices, List<Edge> gEdges, List<Ring> gRings,
            List<SymmetricVertexes> symSets)
    {
        this(gVertices, gEdges, gRings);
        closableChains = new ArrayList<>();
        this.symVertices = symSets;
        localMsg = "";
    }
 
//------------------------------------------------------------------------------
 
    public DGraph(List<Vertex> gVertices, List<Edge> gEdges, List<Ring> gRings,
            List<ClosableChain> closableChains, 
            List<SymmetricVertexes> symVertices)
    {
        this(gVertices, gEdges, gRings, symVertices);
        this.closableChains = closableChains;
        localMsg = "";
    }
 
//------------------------------------------------------------------------------
 
    public DGraph()
    {
        gVertices = new ArrayList<>();
        gEdges = new ArrayList<>();
        gRings = new ArrayList<>();
        closableChains = new ArrayList<>();
        symVertices = new ArrayList<>();
        localMsg = "";
    }
    
//------------------------------------------------------------------------------
    
    public void setCandidateOwner(Candidate candidate)
    {
        this.candidate = candidate;
    }
    
//------------------------------------------------------------------------------
    
    public Candidate getCandidateOwner()
    {
        return candidate;
    }
 
//------------------------------------------------------------------------------
 
    public void setGraphId(int id)
    {
        graphId = id;
    }
 
//------------------------------------------------------------------------------
 
    public int getGraphId()
    {
        return graphId;
    }
 
//------------------------------------------------------------------------------
 
    public void setLocalMsg(String msg)
    {
        localMsg = msg;
    }
 
//------------------------------------------------------------------------------
 
    public String getLocalMsg()
    {
        return localMsg;
    }
 
//------------------------------------------------------------------------------
 
    public boolean hasSymmetricAP()
    {
        return (!symVertices.isEmpty());
    }
 
//------------------------------------------------------------------------------
 
    public boolean hasSymmetryInvolvingVertex(Vertex v)
    {
        boolean res = false;
        for (SymmetricVertexes ss : symVertices)
        {
            if (ss.contains(v))
            {
                res = true;
                break;
            }
        }
        return res;
    }
 
//------------------------------------------------------------------------------
 
    public int getSymmetricSetCount()
    {
        return symVertices.size();
    }
 
//------------------------------------------------------------------------------
 
    public Iterator<SymmetricVertexes> getSymSetsIterator()
    {
        return symVertices.iterator();
    }
 
//------------------------------------------------------------------------------
 
    public List<Vertex> getSymVerticesForVertex(Vertex v)
    {
        List<Vertex> lst = new ArrayList<Vertex>();
        for (SymmetricVertexes ss : symVertices)
        {
            if (ss.contains(v))
            {
                ss.stream().forEach(i -> lst.add((Vertex) i));
            }
        }
        return lst;
    }
    
//------------------------------------------------------------------------------
    
    public boolean detectSymVertexSets() throws DENOPTIMException
    {
        int initialSize = symVertices.size();
        
        // This is do hold vertexes in a staging area (symVrtxsFromAnyBranch)
        // without adding them to a SymmetricVertexes right away. 
        Set<Vertex> alreadyAssignedVrtxs = new HashSet<Vertex>();
 
        // The sym vertexes on vrtx can have sym counterpart
        // that are attached to vertexes sym to vrtx. Prepare a storage to
        // collect all sym counterparts from any of vertexes sym to vrtx
        Map<SymmetricAPs,List<Vertex>> symVrtxsFromAnyBranch =
             new HashMap<SymmetricAPs,List<Vertex>>();
        for (Vertex vrtx : getVertexList())
        {
            // NB: if there is a symmetric relation involving vrtx, then 
            // vrtx is in the set returned by the following lines
            List<Vertex> vrtxsSymToVrtx = new ArrayList<Vertex>();
            for (List<Vertex> tmpSymSets : symVrtxsFromAnyBranch.values())
            {
                if (tmpSymSets.contains(vrtx))
                {
                    vrtxsSymToVrtx.addAll(tmpSymSets);
                }
            }
            if (vrtxsSymToVrtx.size()==0)
                vrtxsSymToVrtx.add(vrtx);
                
            for (Vertex symToVrtx : vrtxsSymToVrtx)
            {   
                Map<SymmetricAPs,List<Vertex>> symChildenSetsOnSymToVrtxs = 
                        findSymmetrySetsOfChildVertexes(symToVrtx, 
                                alreadyAssignedVrtxs);
                
                for (SymmetricAPs key : symChildenSetsOnSymToVrtxs.keySet())
                {
                    // Find any mapping with previously recorded SymmetricAPs
                    boolean foundSymmetricBranch = false;
                    for (SymmetricAPs keyOnMaster : key.getAllSameAs( 
                            symVrtxsFromAnyBranch.keySet()))
                    {
                        foundSymmetricBranch = true;
                        
                        // Here we must NOT consider the already assigned ones!
                        if (areApsUsedBySymmetricUsers(key.get(0),
                                keyOnMaster.get(0), new HashSet<Vertex>()))
                        {
                            // the previously recorded branch and 
                            // this one are consistent
                            symVrtxsFromAnyBranch.get(keyOnMaster).addAll(
                                    symChildenSetsOnSymToVrtxs.get(key));
                        } else {
                            // branches correspond to two different sets of
                            // symmetric vertexes. So, we treat the new branch
                            // independently
                            foundSymmetricBranch = false;
                        }
                    } 
                    if (!foundSymmetricBranch)
                    {
                        // Effectively, in the first iteration of the loop
                        // we will always end up here
                        List<Vertex> lst = new ArrayList<Vertex>();
                        lst.addAll(symChildenSetsOnSymToVrtxs.get(key));
                        symVrtxsFromAnyBranch.put(key, lst);
                    }
                }
            }
        }
        
        for (List<Vertex> symVertexes : symVrtxsFromAnyBranch.values())
        {
            if (symVertexes.size()<2)
            {
                // We get rid of placeholders for vertexes that use APs that 
                // are not part of a symmetriAPs, but could have been part 
                // of symmetric subgraphs
                continue;
            }
            alreadyAssignedVrtxs.addAll(symVertexes);
            addSymmetricSetOfVertices(new SymmetricVertexes(symVertexes));
        }
        
        return (symVertices.size()-initialSize)>0;
    }
 
//------------------------------------------------------------------------------
    
    Map<SymmetricAPs, List<Vertex>> findSymmetrySetsOfChildVertexes(
            Vertex vrtx, Set<Vertex> alreadyAssignedVrtxs)
    {
        Map<SymmetricAPs,List<Vertex>> symSetsOfChildVrtxs = 
                new HashMap<SymmetricAPs,List<Vertex>>();
        
        Set<AttachmentPoint> doneAPs = new HashSet<AttachmentPoint>();
        for (SymmetricAPs symAPs : vrtx.getSymmetricAPSets())
        {   
            // First condition: all symmetric APs must be in use
            boolean addSymAPsAreUsed = true;
            for (AttachmentPoint ap : symAPs)
            {
                if (ap.isAvailableThroughout())
                {
                    addSymAPsAreUsed = false;
                    break;
                }
            }
            if (!addSymAPsAreUsed)
                continue;
            
            // Now consider what vertex is attached to the symmetric APs
            AttachmentPoint firstAp = symAPs.get(0);
            
            boolean setSymmetryRelation = true;
            List<Vertex> symVertexes = new ArrayList<Vertex>();
            symVertexes.add(firstAp.getLinkedAPThroughout().getOwner());
            for (AttachmentPoint ap : symAPs)
            {
                doneAPs.add(ap);
                
                if (firstAp==ap)
                    continue;
                
                setSymmetryRelation = areApsUsedBySymmetricUsers(firstAp, ap,
                        alreadyAssignedVrtxs);
                if (!setSymmetryRelation)
                    break;
 
                // OK: this user of AP is symmetric to the user on firstAP
                symVertexes.add(ap.getLinkedAPThroughout().getOwner());
            }
            
            if (setSymmetryRelation)
            {
                symSetsOfChildVrtxs.put(symAPs,symVertexes);
                alreadyAssignedVrtxs.addAll(symVertexes);
            }
        }
        
        // Here we account for the possibility that  vertex without sym APs
        // is part of a subgraph the is symmetrically reproduced elsewhere.
        // This is a common pattern in chemistry.
        // To this end we create dummy symmetric sets of APs that contain 
        // only one APs, and use them as placeholder in case the same AP-user
        // is found on symmetric branches.
        for (AttachmentPoint ap : vrtx.getAttachmentPoints())
        {
            if (doneAPs.contains(ap) || ap.isAvailableThroughout())
                continue;            
         
            Vertex user = ap.getLinkedAPThroughout().getOwner();
            if (alreadyAssignedVrtxs.contains(user))
                continue;
            
            // Create an artifact of SymmetricAPs that contains one entry
            SymmetricAPs soloSymAps = new SymmetricAPs();
            soloSymAps.add(ap);
 
            // Well, this contains only one entry, but for consistency we still
            // use a list.
            List<Vertex> symVertexes = new ArrayList<Vertex>();
            symVertexes.add(user);
            
            symSetsOfChildVrtxs.put(soloSymAps,symVertexes);
            alreadyAssignedVrtxs.addAll(symVertexes);
        }
        return symSetsOfChildVrtxs;
    }
    
//------------------------------------------------------------------------------
 
    public static boolean areApsUsedBySymmetricUsers(AttachmentPoint apA,
            AttachmentPoint apB, Set<Vertex> alreadyAssignedVrtxs)
    {
        AttachmentPoint apUserOfApA = apA.getLinkedAPThroughout();
        Vertex userOfApA = apUserOfApA.getOwner();
        boolean userOfApAIsFragment = Fragment.class.isInstance(userOfApA);
        
        // 1st condition: (fast failing) the linked AP must have 
        // the same features. This is faster than checking vertex
        // isomorphism.
        AttachmentPoint apUserOfApB = apB.getLinkedAPThroughout();
        if (!apUserOfApA.sameAs(apUserOfApB))
        {
            return false;
        }
        
        // 2nd condition: (fast-failing) the linked vertexes
        // must be unassigned
        Vertex userOfApB = apUserOfApB.getOwner();
        if (alreadyAssignedVrtxs.contains(userOfApB))
        {
            return false;
        }
        
        // 3rd condition: (not fast, not too slow) the linked
        // vertexes must be have same features
        if (!userOfApB.sameAs(userOfApA))
        {
            return false;
        }
 
        // 4th condition: (slow) the linked vertexes
        // are fragments that have been generated on the fly, so 
        // they do not have an assigned building block ID. We must
        // therefore compare their internal structure.
        if (userOfApAIsFragment)
        {
            // At this point we know the two vertexes are instances 
            // of the same class. 
            Fragment frgUserOfApA = (Fragment) userOfApA;
            Fragment frgUserOfApB = (Fragment) userOfApB;
            if (!frgUserOfApA.isIsomorphicTo(frgUserOfApB))
            {
                return false;
            }
        }
        return true;
    }
 
//------------------------------------------------------------------------------
    
    public void removeSymmetrySet(SymmetricVertexes ss)
    {
        symVertices.remove(ss); 
    }
    
//------------------------------------------------------------------------------
 
    public SymmetricVertexes getSymSetForVertex(Vertex v)
    {
        for (SymmetricVertexes ss : symVertices)
        {
            if (ss.contains(v))
            {
                return ss;
            }
        }
        return new SymmetricVertexes();
    }
 
//------------------------------------------------------------------------------
 
    public void setSymmetricVertexSets(List<SymmetricVertexes> symVertices)
    {
        this.symVertices.clear();
        this.symVertices.addAll(symVertices);
    }
 
//------------------------------------------------------------------------------
 
    public void addSymmetricSetOfVertices(SymmetricVertexes symSet)
            throws DENOPTIMException
    {
        for (SymmetricVertexes oldSS : symVertices)
        {
            if (!Collections.disjoint(oldSS, symSet))
            {
                throw new DENOPTIMException("Adding " + symSet + " while "
                        + "there is already one that contains some of the same "
                        + "items");
            }
        }
        symVertices.add(symSet);
    }
 
//------------------------------------------------------------------------------
 
    public void setVertexList(ArrayList<Vertex> vertices)
    {
        gVertices = vertices;
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void setEdgeList(ArrayList<Edge> edges)
    {
        gEdges = edges;
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void setRings(ArrayList<Ring> rings)
    {
        gRings = rings;
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void setCandidateClosableChains(ArrayList<ClosableChain> closableChains)
    {
        this.closableChains = closableChains;
    }
 
//------------------------------------------------------------------------------
 
    public List<ClosableChain> getClosableChains()
    {
        return closableChains;
    }
 
//------------------------------------------------------------------------------
 
    public List<Vertex> getVertexList()
    {
        return gVertices;
    }
    
//------------------------------------------------------------------------------
    
    public Vertex getSourceVertex()
    {
        switch (gVertices.size())
        {
            case 0:
                return null;
            case 1:
                return getVertexAtPosition(0);
        }
        Vertex v0 = getVertexAtPosition(0);
        for (Edge e : this.getEdgeList())
        {
            if (e.getTrgAP().getOwner() == v0)
            {
                ArrayList<Vertex> parentTree = new ArrayList<>();
                getParentTree(v0,parentTree);
                return parentTree.get(parentTree.size()-1);
            }
        }
        return v0;
    }
 
//------------------------------------------------------------------------------
 
    public List<Edge> getEdgeList()
    {
        return gEdges;
    }
 
//------------------------------------------------------------------------------
 
    public List<Ring> getRings()
    {
        return gRings;
    }
 
//------------------------------------------------------------------------------
 
    public List<Edge> getEdgesWithSrc(Vertex v)
    {
        List<Edge> edges = new ArrayList<Edge>();
        for (Edge e : this.getEdgeList())
        {
            if (e.getSrcAP().getOwner() == v)
            {
                edges.add(e);
            }
        }
        return edges;
    }
    
//------------------------------------------------------------------------------
 
    public List<Edge> getEdgesWithTrg(Vertex v)
    {
        List<Edge> edges = new ArrayList<Edge>();
        for (Edge e : this.getEdgeList())
        {
            if (e.getTrgAP().getOwner() == v)
            {
                edges.add(e);
            }
        }
        return edges;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Ring> getRingsInvolvingVertex(Vertex v)
    {
        ArrayList<Ring> rings = new ArrayList<Ring>();
        for (Ring r : gRings)
        {
            if (r.contains(v))
            {
                rings.add(r);
            }
        }
        return rings;
    }
    
//------------------------------------------------------------------------------
 
    public ArrayList<Ring> getRingsInvolvingVertex(Vertex[] vs)
    {
        ArrayList<Ring> rings = new ArrayList<Ring>();
        for (Ring r : gRings)
        {
            boolean matchesAll = true;
            for (int i=0; i<vs.length; i++)
            {
                if (!r.contains(vs[i]))
                {
                    matchesAll = false;
                    break;
                }
            }
            if (matchesAll)
            {
                rings.add(r);
            }
        }
        return rings;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Ring> getRingsInvolvingVertexID(int vid)
    {
        ArrayList<Ring> rings = new ArrayList<Ring>();
        for (Ring r : gRings)
        {
            if (r.containsID(vid))
            {
                rings.add(r);
            }
        }
        return rings;
    }
 
//------------------------------------------------------------------------------
 
    public boolean hasRings()
    {
        return gRings.size() > 0;
    }
    
//------------------------------------------------------------------------------
    
    public boolean hasOrEmbedsRings()
    {
        if (gRings.size() > 0)
            return true;
        for (Vertex v : gVertices)
        {
            if (!(v instanceof Template))
                continue;
            
            Template t = (Template) v;
            if (t.getInnerGraph().hasOrEmbedsRings())
                return true;
        }
        return false;
    }
 
//------------------------------------------------------------------------------
 
    public boolean isVertexIDInRing(int vid)
    {
        boolean result = false;
        for (Ring  r : gRings)
        {
            if (r.containsID(vid))
            {
                result = true;
                break;
            }
        }
        return result;
    }
 
//------------------------------------------------------------------------------
 
    public boolean isVertexInRing(Vertex v)
    {
        boolean result = false;
        for (Ring  r : gRings)
        {
            if (r.contains(v))
            {
                result = true;
                break;
            }
        }
        return result;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Vertex> getRCVertices()
    {
        ArrayList<Vertex> rcvLst = new ArrayList<Vertex>();
        for (Vertex v : gVertices)
        {
            if (v.isRCV())
            {
                rcvLst.add(v);
            }
        }
        return rcvLst;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Vertex> getFreeRCVertices()
    {
        ArrayList<Vertex> rcvLst = getRCVertices();
        ArrayList<Vertex> free = new ArrayList<Vertex>();
        for (Vertex v : rcvLst)
        {
            if (!isVertexInRing(v))
            {
                free.add(v);
            }
        }
        return free;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Vertex> getUsedRCVertices()
    {
        ArrayList<Vertex> used = new ArrayList<Vertex>();
        used.addAll(getRCVertices());
        used.removeAll(getFreeRCVertices());
        return used;
    }
 
//------------------------------------------------------------------------------
 
    public void addEdge(Edge edge)
    {
        gEdges.add(edge);
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void addRing(Ring ring)
    {
        gRings.add(ring);
        jGraph = null;
        jGraphKernel = null;
    }
    
//------------------------------------------------------------------------------
    
    public void addRing(Vertex vI, Vertex vJ) 
            throws DENOPTIMException
    {
        BondType bndTypI = vI.getEdgeToParent().getBondType();
        BondType bndTypJ = vJ.getEdgeToParent().getBondType();
        if (bndTypI != bndTypJ)
        {
            String s = "Attempt to close rings is not compatible "
            + "to the different bond type specified by the "
            + "head and tail APs: (" + bndTypI + "!=" 
            + bndTypJ + " for vertices " + vI + " " 
            + vJ + ")";
            throw new DENOPTIMException(s);
        }
        addRing(vI,vJ,bndTypI);
        jGraph = null;
        jGraphKernel = null;
    }
    
//------------------------------------------------------------------------------
    
    public void addRing(Vertex vI, Vertex vJ, BondType bndTyp)
    {
        PathSubGraph path = new PathSubGraph(vI,vJ,this);
        ArrayList<Vertex> arrLst = new ArrayList<Vertex>();
        arrLst.addAll(path.getVertecesPath());                    
        Ring ring = new Ring(arrLst);
        ring.setBondType(bndTyp);
        this.addRing(ring);
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void addVertex(Vertex vertex) throws DENOPTIMException
    {
        if (containsVertexID(vertex.getVertexId()))
            throw new DENOPTIMException("Vertex must have a VertexID that is "
                    + "unique within the graph. VertexID '" 
                    + vertex.getVertexId()+ "' already present in graph " 
                    + getGraphId());
        vertex.setGraphOwner(this);
        gVertices.add(vertex);
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void removeVertex(Vertex vertex)
    {
        if (!gVertices.contains(vertex))
        {
            return;
        }
 
        vertex.resetGraphOwner();
        long vid = vertex.getVertexId();
 
        // delete also any ring involving the removed vertex
        if (isVertexInRing(vertex))
        {
            ArrayList<Ring> rToRm = getRingsInvolvingVertex(vertex);
            for (Ring r : rToRm)
            {
                removeRing(r);
            }
        }
 
        // remove edges involving the removed vertex
        ArrayList<Edge> eToDel = new ArrayList<>();
        for (int i=0; i<gEdges.size(); i++)
        {
            Edge edge = gEdges.get(i);
            if (vid == edge.getTrgVertex())
            {
                eToDel.add(edge);
            }
            // NB: the following allows to break the spanning tree
            if (vid == edge.getSrcVertex())
            {
                eToDel.add(edge);
            }
        }
        for (Edge e : eToDel)
        {
            this.removeEdge(e);
        }
 
        //delete the removed vertex from symmetric sets, but leave other vertices
        List<SymmetricVertexes> ssToRemove = new ArrayList<SymmetricVertexes>();
        for (SymmetricVertexes ss : symVertices)
        {
            if (ss.contains(vertex))
            {
                if (ss.size() < 3)
                {
                    ssToRemove.add(ss);
                }
                else
                {
                    ss.remove(vertex);
                }
            }
        }
        symVertices.removeAll(ssToRemove);
 
        // remove the vertex from the graph
        gVertices.remove(vertex);
        
        jGraph = null;
        jGraphKernel = null;
    }
    
//------------------------------------------------------------------------------
    
    public boolean removeVertexAndWeld(Vertex vertex,
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        if (!gVertices.contains(vertex))
        {
            return false;
        }
        
        List<Vertex> symSites = getSymVerticesForVertex(vertex);
        if (symSites.size() == 0)
        {
            symSites.add(vertex);
        } else {
            //TODO-V3 flip coin to decide if this should be a symmetric operation or not
        }
        for (Vertex oldLink : symSites)
        {
            GraphUtils.ensureVertexIDConsistency(this.getMaxVertexId());
            if (!removeSingleVertexAndWeld(oldLink, fragSpace))
            {
                return false;
            }
        }
        // Reject deletions that cause the collapse of a 3-atom ring into a
        // loop (i.e., 1-atom ring) or multiple connection (i.e., a 3-atom ring)
        for (Ring r : gRings)
        {
            // 3 = 1 actual vertex + 2 RCVs
            if (r.getSize()!=3)
                continue;
            
            AttachmentPoint apH = r.getHeadVertex().getEdgeToParent()
                    .getSrcAPThroughout();
            AttachmentPoint apT = r.getTailVertex().getEdgeToParent()
                    .getSrcAPThroughout();
            
            if (apH.hasSameSrcAtom(apT) || apH.hasConnectedSrcAtom(apT))
                return false;
        }
        return true;
    }
  
//------------------------------------------------------------------------------
    
    public boolean removeSingleVertexAndWeld(Vertex vertex, 
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        if (!gVertices.contains(vertex))
        {
            return false;
        }
        if (vertex == getSourceVertex())
        {
            // Make sure there is something to weld, or give up. This to avoid
            // trying to remove the scaffold vertex (i.e., a vertex that has no
            // parents in this graph and the APs of which are only user as 
            // source APs)
            boolean foundLinkToParent = false;
            for (AttachmentPoint ap : vertex.getAttachmentPoints())
            {
                if (ap.isAvailable() && !ap.isAvailableThroughout())
                {
                    if (!ap.isSrcInUserThroughout())
                        foundLinkToParent = true;
                }
            }
            if (!foundLinkToParent)
                return false;
            
            // When we try to remove the only vertex inside a template, we
            // are removing the template itself
            if (gVertices.size()==1 && templateJacket!=null)
            {
                return templateJacket.getGraphOwner().removeSingleVertexAndWeld(
                        templateJacket, fragSpace);
            }
        }
        
        // Get all APs that we'll try to weld into the parent
        ArrayList<AttachmentPoint> needyAPsOnChildren = 
                new ArrayList<AttachmentPoint>();
        // And all APs where we could weld onto
        ArrayList<AttachmentPoint> freeAPsOnParent = 
                new ArrayList<AttachmentPoint>();
        //        vertex.getAPsFromChilddren(); //No, because it enter templates
        Map<AttachmentPoint,AttachmentPoint> apOnOldToNeedyAP = 
                new HashMap<AttachmentPoint,AttachmentPoint>();
        for (AttachmentPoint apOnOld : vertex.getAttachmentPoints())
        {
            if (!apOnOld.isAvailableThroughout())
            {
                if (apOnOld.isSrcInUserThroughout())
                {
                    // Links that depart from vertex
                    AttachmentPoint needyAP = 
                            apOnOld.getLinkedAPThroughout();
                    // NB: here do not use getSrcThroughout because it would 
                    // enter trg templates rather than staying on their surface.
                    needyAPsOnChildren.add(needyAP);
                    apOnOldToNeedyAP.put(apOnOld, needyAP);
                } else {
                    AttachmentPoint apOnParent = 
                            apOnOld.getLinkedAPThroughout();
                    // NB: here do not use getSrcThroughout because it would 
                    // enter src templates rather than staying on their surface.
                    freeAPsOnParent.add(apOnParent);
                    freeAPsOnParent.addAll(apOnParent.getOwner()
                            .getFreeAPThroughout());
                }
            }
        }
        
        // Get all possible parentAPs-childAPs mappings
        List<APMapping> mappings = fragSpace.mapAPClassCompatibilities(
                freeAPsOnParent, needyAPsOnChildren, 500);
        if (mappings.size() == 0)
        {
            // No APClass-compatible possibility of removing the link.
            return false;
        }
        
        // Score mapping to prioritise those that preserve rings.
        // This to differentiate from the combination of DELETE+EXTEND operation
        // which cannot preserve rings.
        List<Integer> preferences = new ArrayList<Integer>();
        // Score rings in this level's graph
        for (int i=0; i<needyAPsOnChildren.size(); i++)
        {
            AttachmentPoint needyAP = needyAPsOnChildren.get(i);
            preferences.add(0);
            
            Vertex ownerOfNeedy = needyAP.getOwner();
            for (Ring r : ownerOfNeedy.getGraphOwner()
                    .getRingsInvolvingVertex(ownerOfNeedy))
            {
                // NB: here we stay at the level of the graph owning ownerOfNeedy
                Vertex lastBeforeOwnerOfNeedy = 
                        needyAP.getLinkedAP().getOwner();
                if (r.contains(lastBeforeOwnerOfNeedy))
                {
                    preferences.set(i, preferences.get(i) + 1); 
                }
            }
        }
        
        // Choose best scoring mapping
        int maxScore = Integer.MIN_VALUE;
        APMapping bestScoringMapping = null;
        for (APMapping apm : mappings)
        {
            int score = 0;
            for (AttachmentPoint ap : apm.values())
            {
                score = score + preferences.get(needyAPsOnChildren.indexOf(ap));
            }
            if (score > maxScore)
            {
                maxScore = score;
                bestScoringMapping = apm;
            }
        }
        
        APMapping bestScoringMappingReverse = new APMapping();
        for (Entry<AttachmentPoint, AttachmentPoint> e : 
            bestScoringMapping.entrySet())
        {
            bestScoringMappingReverse.put(e.getValue(), e.getKey());
        }
        
        // Update rings involving vertex directly (i.e., in this graph)
        ArrayList<Ring> rToEdit = getRingsInvolvingVertex(vertex);
        ArrayList<Ring> ringsToRemove = new ArrayList<Ring>();
        for (Ring r : rToEdit)
        {
            r.removeVertex(vertex);
            if (r.getSize() < 3)
                ringsToRemove.add(r);
        }
        for (Ring r : ringsToRemove)
        {
            removeRing(r);
        }
        
        // Remove edges to/from old vertex, while keeping track of edits to do
        // in a hypothetical jacket template (if such template exists)
        LinkedHashMap<AttachmentPoint,AttachmentPoint> newInReplaceOldInInTmpl = 
                new LinkedHashMap<AttachmentPoint,AttachmentPoint>();
        List<AttachmentPoint> oldAPToRemoveFromTmpl = 
                new ArrayList<AttachmentPoint>();
        for (AttachmentPoint oldAP : vertex.getAttachmentPoints())
        {
            if (oldAP.isAvailable())
            {
                // NB: if this graph is embedded in a template, free/available 
                // APs at this level (and sources at the vertex we are removing) 
                // are mapped on the jacket templates' surface, and must be 
                // removed.
                if (templateJacket!=null)
                {
                    if (!oldAP.isAvailableThroughout())
                    {
                        AttachmentPoint lAP = 
                                oldAP.getLinkedAPThroughout();
                        if (bestScoringMapping.keySet().contains(lAP))
                        {
                            newInReplaceOldInInTmpl.put(
                                    bestScoringMapping.get(lAP), oldAP);
                        } else if (bestScoringMapping.values().contains(lAP))
                        {
                            newInReplaceOldInInTmpl.put(
                                    bestScoringMappingReverse.get(lAP), oldAP);
                        } else {
                            oldAPToRemoveFromTmpl.add(oldAP);
                        }
                    } else {
                        oldAPToRemoveFromTmpl.add(oldAP);
                    }
                }
            } else {
                removeEdge(oldAP.getEdgeUser());
            }
        }
        
        // Update pointers in symmetric sets in this graph level
        // NB: this deals only with the symmetric relations of the removed vertex
        // The symm. relations of other removed child vertices are dealt with
        // when removing those vertices.
        List<SymmetricVertexes> ssToRemove = new ArrayList<SymmetricVertexes>();
        Iterator<SymmetricVertexes> ssIter = getSymSetsIterator();
        while (ssIter.hasNext())
        {
            SymmetricVertexes ss = ssIter.next();
            if (ss.contains(vertex))
            {
                ss.remove(vertex);
            }
            if (ss.size() < 2)
                ssToRemove.add(ss);
        }
        symVertices.removeAll(ssToRemove);
        
        // Remove the vertex
        getVertexList().remove(vertex);
        vertex.resetGraphOwner();
        
        // Add new edges (within the graph owning the removed vertex) 
        List<AttachmentPoint> reconnettedApsOnChilds = 
                new ArrayList<AttachmentPoint>();
        for (Entry<AttachmentPoint,AttachmentPoint> e : 
            bestScoringMapping.entrySet())
        {
            AttachmentPoint apOnParent = e.getKey();
            AttachmentPoint apOnChild = e.getValue();
            if (containsVertex(apOnChild.getOwner()) 
                    && containsVertex(apOnParent.getOwner()))
            {
                Edge edge = new Edge(apOnParent,apOnChild,
                        apOnParent.getAPClass().getBondType());
                addEdge(edge);
                reconnettedApsOnChilds.add(apOnChild);
            } else {
                if (templateJacket!=null)
                {
                    if (containsVertex(apOnParent.getOwner()))
                    {
                        templateJacket.updateInnerApID(
                                newInReplaceOldInInTmpl.get(apOnParent), //AP on old vertex
                                apOnParent);
                        reconnettedApsOnChilds.add(apOnChild);
                    }
                    if (containsVertex(apOnChild.getOwner()))
                    {
                        templateJacket.updateInnerApID(
                                newInReplaceOldInInTmpl.get(apOnChild), //AP on old vertex
                                apOnChild);
                        reconnettedApsOnChilds.add(apOnChild);
                    }
                    // The case where neither is contained in 'this' cannot
                    // occur because of the initial checks that identify 
                    // attempts to remove the only vertex inside a template.
                } else {
                    DENOPTIMException de = new DENOPTIMException("AP '"
                            + apOnChild + "' seems connected to a template, "
                            + "no template was found. Possible bug!");
                    throw de;
                }
            }
        }
        
        // update the mapping of this vertex's APs in the jacket template
        if (templateJacket!=null)
        {   
            // Remove all APs that existed only in the old vertex
            for (AttachmentPoint apOnOld : oldAPToRemoveFromTmpl)
            {
                templateJacket.removeProjectionOfInnerAP(apOnOld);
            }
        }
        
        // Remove branches of child-APs that were not mapped/done
        for (AttachmentPoint apOnChild : needyAPsOnChildren)
        {
            if (!reconnettedApsOnChilds.contains(apOnChild))
            {
                removeOrphanBranchStartingAt(apOnChild.getOwner());
            }
        }
 
        jGraph = null;
        jGraphKernel = null;
        
        return !this.containsVertex(vertex);
    }
    
//------------------------------------------------------------------------------
    
    public void replaceUnusedRCVsWithCapps(FragmentSpace fragSpace) 
            throws DENOPTIMException 
    {
        List<Vertex> rcvToReplace = new ArrayList<Vertex>();
        List<AttachmentPoint> apToCap = new ArrayList<AttachmentPoint>();
        for (Vertex v : getRCVertices())
        {
            if (getRingsInvolvingVertex(v).size()==0 
                    && v.getEdgeToParent()!=null)
            {
                rcvToReplace.add(v);
                apToCap.add(v.getEdgeToParent().getSrcAP());
            }
        }
        for (int i=0; i<rcvToReplace.size(); i++)
        {
            Vertex v = rcvToReplace.get(i);
            removeVertex(v);
            
            AttachmentPoint apOnParent = apToCap.get(i);
            APClass cappAPClass = fragSpace.getAPClassOfCappingVertex(
                    apOnParent.getAPClass());
            
            if (cappAPClass != null)
            {
                Vertex capVrt = fragSpace.getCappingVertexWithAPClass(
                        cappAPClass);
                capVrt.setVertexId(v.getVertexId());
                appendVertexOnAP(apOnParent, capVrt.getAP(0));
            }
        }
    }
    
//------------------------------------------------------------------------------
    
    protected void reassignSymmetricLabels()
    {
        //Remove previous labeling
        for (Vertex v : gVertices)
            v.removeProperty(DENOPTIMConstants.VRTSYMMSETID);
        
        Iterator<SymmetricVertexes> ssIter = getSymSetsIterator();
        int i = 0;
        while (ssIter.hasNext())
        {
            SymmetricVertexes ss = ssIter.next();
            String symmLabel = ss.hashCode() + "-" + i;
            for (Vertex v : ss)
            {
                v.setProperty(DENOPTIMConstants.VRTSYMMSETID, symmLabel);
            }
            i++;
        }
        for (Vertex v : gVertices)
        {
            i++;
            if (!v.hasProperty(DENOPTIMConstants.VRTSYMMSETID))
                v.setProperty(DENOPTIMConstants.VRTSYMMSETID, v.hashCode()+"-"+i);
        }
    }
    
//------------------------------------------------------------------------------
    
    protected void convertSymmetricLabelsToSymmetricSets()
    {
        Map<String,List<Vertex>> collectedLabels = new HashMap<>();
        for (Vertex v : gVertices)
        {
            if (v.hasProperty(DENOPTIMConstants.VRTSYMMSETID))
            {
                String label = v.getProperty(
                        DENOPTIMConstants.VRTSYMMSETID).toString();
                if (collectedLabels.containsKey(label))
                {
                    collectedLabels.get(label).add(v);
                } else {
                    List<Vertex> lst = new ArrayList<Vertex>();
                    lst.add(v);
                    collectedLabels.put(label, lst);
                }
                v.removeProperty(DENOPTIMConstants.VRTSYMMSETID);
            }
        }
        
        for (String label : collectedLabels.keySet())
        {
            List<Vertex> symmvertices = collectedLabels.get(label);
            
            if (symmvertices.size()>1)
            {
                SymmetricVertexes ss = null;
                for (Vertex v : symmvertices)
                {
                    if (hasSymmetryInvolvingVertex(v))
                    {
                        ss = getSymSetForVertex(v);
                        break;
                    }
                }
                
                if (ss != null)
                {
                    for (Vertex v : symmvertices)
                        ss.add(v);
                    
                } else {
                    ss = new SymmetricVertexes();
                    for (Vertex v : symmvertices)
                        ss.add(v);
                    try
                    {
                        addSymmetricSetOfVertices(ss);
                    } catch (DENOPTIMException e)
                    {
                        //this can never happen because we are testing for
                        // preliminary existence of an id in the existing sets.
                    }
                }
            }
        }
    }
        
//------------------------------------------------------------------------------
    
    public boolean replaceSubGraph(List<Vertex> subGrpVrtxs, 
            DGraph incomingGraph, 
            LinkedHashMap<AttachmentPoint,AttachmentPoint> apMap,
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        for (Vertex vToRemove : subGrpVrtxs)
        {
            if (!gVertices.contains(vToRemove))
            {
                return false;
            }
        }
        
        // Capping groups are removed and, if needed, re-added back
        subGrpVrtxs.stream().filter(v -> v.getBuildingBlockType()==BBType.CAP)
            .forEach(v -> this.removeVertex(v));
        subGrpVrtxs.removeIf(v -> v.getBuildingBlockType()==BBType.CAP);
        if (subGrpVrtxs.size() == 0)
        {
            throw new DENOPTIMException("Capping groups cannot be the only "
                    + "vertex in a subgraph to replace.");   
        }
        
        // Refresh the symmetry set labels so that clones of the branch inherit
        // the same symmetry set labels.
        incomingGraph.reassignSymmetricLabels();
        
        GraphUtils.ensureVertexIDConsistency(this.getMaxVertexId());
        
        // Verify that also the surrounding of vertices in the lists is 
        // consistent between subGrpVrtxs and verticesToRemove. Even if the
        // two are consistent, there can still be differences in the childs.
        List<List<Vertex>> compatibleSymSubGrps = new ArrayList<List<Vertex>>();
        for (List<Vertex> symmetricSubGrpVrtx : getSymmetricSubGraphs(subGrpVrtxs))
        {
            boolean skip = false;
            for (int iv=0; iv<subGrpVrtxs.size(); iv++)
            {
                if (skip)
                    break;
                Vertex oriVs = subGrpVrtxs.get(iv);
                Vertex symVs = symmetricSubGrpVrtx.get(iv);
                List<Vertex> oriVsChildren = oriVs.getChilddren();
                List<Vertex> symVsChildren = symVs.getChilddren();
                
                // NB: oriVsChildren does not include CAPs from the 
                // initial subgraph, while symVsChildren does include the 
                // corresponding CAPs.
                oriVsChildren.removeIf(v -> v.getBuildingBlockType()==BBType.CAP);
                symVsChildren.removeIf(v -> v.getBuildingBlockType()==BBType.CAP);
                if (oriVsChildren.size()!=symVsChildren.size())
                {
                    // we continue in the outer loop
                    skip = true;
                    continue;
                }
                for (int ic=0; ic<oriVsChildren.size(); ic++)
                {
                    if (skip)
                        break;
                    // We have already checked those in the subgraph
                    if (subGrpVrtxs.contains(oriVsChildren.get(ic)))
                        continue;
                    // We do allow the two child to be different vertices, but
                    // we avoid having one CAP and one not. this because it will
                    // lead to having free APs on the parent of the first and
                    // busy APs on the parent of the second. This prevents 
                    // finding a mapping of the free APs.
                    if (oriVsChildren.get(ic).getBuildingBlockType()
                            != symVsChildren.get(ic).getBuildingBlockType())
                    {
                        skip = true;
                        continue;
                    }
                }
            }
            if (!skip)
                compatibleSymSubGrps.add(symmetricSubGrpVrtx);
        }
        if (compatibleSymSubGrps.size()==0)
            throw new DENOPTIMException("Failed to detect autosymmetry.");
        
        for (List<Vertex> verticesToRemove : compatibleSymSubGrps)
        {
            // Prepare incoming graph
            DGraph graphToAdd = incomingGraph.clone();
            graphToAdd.renumberGraphVertices();
            List<Vertex> vertexAddedToThis = new ArrayList<Vertex>(
                    graphToAdd.gVertices);
            
            // Prepare subgraph (it already does not contain caps)
            removeCappingGroupsFromChilds(verticesToRemove);
            
            // Prepare AP mapping projecting the one for subGrpVrtxs
            LinkedHashMap<AttachmentPoint,AttachmentPoint> localApMap = 
                    new LinkedHashMap<AttachmentPoint,AttachmentPoint>();
            for (Map.Entry<AttachmentPoint,AttachmentPoint> e : apMap.entrySet())
            {
                // WARNING! Assumption that subGrpVrtxs and verticesToRemove
                // are sorted accordingly to symmetry, which should be the case.
                int vrtPosOnOld = subGrpVrtxs.indexOf(e.getKey().getOwner());
                int apPosOnOld = e.getKey().getIndexInOwner();
                AttachmentPoint apOnOld = verticesToRemove.get(
                        vrtPosOnOld).getAP(apPosOnOld); 
                
                int vrtPosOnNew = incomingGraph.indexOf(e.getValue().getOwner());
                int apPosOnNew = e.getValue().getIndexInOwner();
                AttachmentPoint apOnNew = graphToAdd.getVertexAtPosition(
                        vrtPosOnNew).getAP(apPosOnNew); 
                localApMap.put(apOnOld,apOnNew);
            }
            
            if (!replaceSingleSubGraph(verticesToRemove, graphToAdd, localApMap))
            {
                return false;
            }
            addCappingGroups(vertexAddedToThis, fragSpace);
        }
        convertSymmetricLabelsToSymmetricSets();
        return true;
    }
    
//------------------------------------------------------------------------------
    
    public List<List<Vertex>> getSymmetricSubGraphs(
            List<Vertex> subGrpVrtxs) throws DENOPTIMException
    {
        if (subGrpVrtxs.stream().anyMatch(v -> v.getBuildingBlockType()==BBType.CAP))
            throw new DENOPTIMException("Capping groups must not be part of "
                    + "symmetric subgraphs");
 
        List<List<Vertex>> symSites = new ArrayList<List<Vertex>>();
        
        if (subGrpVrtxs.size()==1)
        {
            for (Vertex sv : getSymVerticesForVertex(subGrpVrtxs.get(0)))
            {
                ArrayList<Vertex> lst = new ArrayList<Vertex>();
                lst.add(sv);
                symSites.add(lst);
            }
            if (symSites.size()==0)
            {
                symSites.add(subGrpVrtxs);
            }
            return symSites;
        }
        
        // Identify the (sole) grand parent.
        List<Vertex> thoseWithoutParent = new ArrayList<Vertex>();
        for (Vertex v : subGrpVrtxs)
        {
            if (!subGrpVrtxs.contains(v.getParent()))
                thoseWithoutParent.add(v);
        }
        if (thoseWithoutParent.size()!=1)
        {
            throw new DENOPTIMException("SubGraph has more than one grand "
                    + "parent.");
        }
        Vertex sourceOfSubGraph = thoseWithoutParent.get(0);
        int numSymmetricSubGraphs = getSymVerticesForVertex(sourceOfSubGraph).size();
        if (numSymmetricSubGraphs==0)
        {
            symSites.add(subGrpVrtxs);
            return symSites;
        }
        
        // Identify the ends of the subgraph's spanning tree
        List<Vertex> thoseWithoutChildren = new ArrayList<Vertex>();
        for (Vertex v : subGrpVrtxs)
        {
            if (Collections.disjoint(v.getChilddren(),subGrpVrtxs))
                thoseWithoutChildren.add(v);
        }
        
        // We want to verify that all the ends of the subgraph's spanning tree
        // have the same number of symmetric partners. This, while collecting
        // all ends that are outside the subgraph and are symmetric to any of
        // the ends belonging to the subgraph. The first, in fact, are the ends
        // of the symmetric subgraphs.
        Set<Vertex> upperLimits = new HashSet<Vertex>();
        Set<Vertex> doneBySymmetry = new HashSet<Vertex>();
        for (Vertex upperLimit : thoseWithoutChildren)
        {
            // We need to understand how many symmetric vertices are already
            // within the subgraph
            int numInSubGraphReplicas = 1;
            
            if (doneBySymmetry.contains(upperLimit))
                continue;
            
            // These are symmetric vertices that do belong to the subgraph
            Set<Vertex> symmSitesOnBranch = new HashSet<Vertex>(
                    getSymVerticesForVertex(upperLimit));
            symmSitesOnBranch.retainAll(subGrpVrtxs);
            if (symmSitesOnBranch.size()>0)
            {
                numInSubGraphReplicas = symmSitesOnBranch.size();
                doneBySymmetry.addAll(symmSitesOnBranch);
            }
            
            List<Vertex> lst = getSymVerticesForVertex(upperLimit);
            if (lst.size() != numInSubGraphReplicas*numSymmetricSubGraphs)
            {
                // The subgraph is not symmetrically reproduced.
                symSites.add(subGrpVrtxs);
                return symSites;
            }
            upperLimits.addAll(lst);
        }
        
        for (Vertex symSources : getSymVerticesForVertex(sourceOfSubGraph))
        {
            List<Vertex> symSubGraph = new ArrayList<Vertex>();
            // The source of the symmetric subgraph is always the first!
            symSubGraph.add(symSources);
            getChildTreeLimited(symSources, symSubGraph, upperLimits);
            //NB: Capping groups are not supposed to be in the list.
            symSubGraph.removeIf(v -> v.getBuildingBlockType()==BBType.CAP);
            if (symSubGraph.size()!=subGrpVrtxs.size())
            {
                symSites = new ArrayList<List<Vertex>>();
                symSites.add(subGrpVrtxs);
                return symSites;
            }
            symSites.add(symSubGraph);
        }
 
        return symSites;
    }
    
//------------------------------------------------------------------------------
    
    public boolean replaceSingleSubGraph(List<Vertex> subGrpVrtxs, 
            DGraph newSubGraph, 
            LinkedHashMap<AttachmentPoint,AttachmentPoint> apMap) 
                    throws DENOPTIMException
    {
        if (!gVertices.containsAll(subGrpVrtxs) 
                || gVertices.contains(newSubGraph.getVertexAtPosition(0)))
        {
            return false;
        }
        
        // Identify vertex that will be added
        ArrayList<Vertex> newvertices = new ArrayList<Vertex>();
        newvertices.addAll(newSubGraph.getVertexList());
        
        // Collect APs from the vertices that will be removed, and that might
        // be reflected onto the jacket template or used to make links to the 
        // rest of the graph.
        List<AttachmentPoint> interfaceApsOnOldBranch = 
                new ArrayList<AttachmentPoint>();
        for (Vertex vToDel : subGrpVrtxs)
        {
            for (AttachmentPoint ap : vToDel.getAttachmentPoints())
            {
                if (ap.isAvailable())
                {
                    // being available, this AP might be reflected onto 
                    // jacket template
                    interfaceApsOnOldBranch.add(ap);
                } else {
                    Vertex user = ap.getLinkedAP().getOwner();
                    if (!subGrpVrtxs.contains(user))
                    {
                        interfaceApsOnOldBranch.add(ap);
                    }
                }
            }
        }
        
        List<AttachmentPoint> interfaceApsOnNewBranch = 
                new ArrayList<AttachmentPoint>();
        for (Vertex v : newSubGraph.getVertexList())
        {
            for (AttachmentPoint ap : v.getAttachmentPoints())
            {
                if (ap.isAvailable())
                {
                    // being available, this AP will have to be reflected onto 
                    // jacket template
                    interfaceApsOnNewBranch.add(ap);
                }
            }
        }
        
        // Keep track of the links that will be broken and re-created,
        // and also of the relation free APs may have with a possible template
        // that embeds this graph.
        LinkedHashMap<AttachmentPoint,AttachmentPoint> 
            linksToRecreate = new LinkedHashMap<>();
        LinkedHashMap<AttachmentPoint,BondType> 
            linkTypesToRecreate = new LinkedHashMap<>();
        LinkedHashMap<AttachmentPoint,AttachmentPoint> 
            inToOutAPForTemplate = new LinkedHashMap<>();
        List<AttachmentPoint> oldAPToRemoveFromTmpl = new ArrayList<>();
        AttachmentPoint trgAPOnNewLink = null;
        for (AttachmentPoint oldAP : interfaceApsOnOldBranch)
        {
            if (oldAP.isAvailable())
            {
                // NB: if this graph is embedded in a template, free/available 
                // APs at this level (and from the old link) 
                // are mapped on the templates' surface
                if (templateJacket!=null)
                {
                    if (oldAP.isAvailableThroughout())
                    {
                        if (!apMap.containsKey(oldAP))
                        {
                            // An AP of the old link is going to be removed from the
                            // template-jacket's list of APs
                            oldAPToRemoveFromTmpl.add(oldAP);
                        } else {
                            // This AP is not used, not even outside of the template
                            // but for some reason the apMapping wants to keep it
                            inToOutAPForTemplate.put(apMap.get(oldAP),oldAP);
                        }
                    } else {
                        if (!apMap.containsKey(oldAP))
                        {
                            throw new DENOPTIMException("Cannot replace subgraph "
                                    + "if a used AP has no mapping.");
                        } else {
                            // This AP is not used, not even outside of the template
                            // but for some reason the apMapping wants to keep it
                            inToOutAPForTemplate.put(apMap.get(oldAP),oldAP);
                        }
                    }
                }
                continue;
            }
            
            if (!apMap.containsKey(oldAP))
            {
                throw new DENOPTIMException("Cannot replace subgraph if a used "
                        + "AP has no mapping. Missing mapping for AP "
                        + oldAP.getIndexInOwner() + " in " 
                        + oldAP.getOwner().getVertexId());
            }
            AttachmentPoint newAP = apMap.get(oldAP);
            linksToRecreate.put(newAP, oldAP.getLinkedAP());
            linkTypesToRecreate.put(newAP, oldAP.getEdgeUser().getBondType());
            
            // This is were we identify the edge/ap to the parent of the oldLink
            if (!oldAP.isSrcInUser())
            {
                trgAPOnNewLink = newAP;
            }
        }
        
        // Identify rings that are affected by the change of vertices
        Map<Ring,List<Vertex>> ringsOverSubGraph = 
                new HashMap<Ring,List<Vertex>>();
        for (int iA=0; iA<interfaceApsOnOldBranch.size(); iA++)
        {
            AttachmentPoint apA = interfaceApsOnOldBranch.get(iA);
        
            if (apA.isAvailable())
                continue;
            
            for (int iB=(iA+1); iB<interfaceApsOnOldBranch.size(); iB++)
            {
                AttachmentPoint apB = interfaceApsOnOldBranch.get(iB);
            
                if (apB.isAvailable())
                    continue;
                
                Vertex vLinkedOnA = apA.getLinkedAP().getOwner();
                Vertex vLinkedOnB = apB.getLinkedAP().getOwner();
                for (Ring r : getRingsInvolvingVertex(
                        new Vertex[] {
                                apA.getOwner(), vLinkedOnA,
                                apB.getOwner(), vLinkedOnB}))
                {
                    List<Vertex> vPair = new ArrayList<Vertex>();
                    vPair.add(r.getCloserToHead(vLinkedOnA, vLinkedOnB));
                    vPair.add(r.getCloserToTail(vLinkedOnA, vLinkedOnB));
                    ringsOverSubGraph.put(r, vPair);
                }
            }
        }
        
        // remove the vertex-to-delete from the rings where they participate
        for (Ring r : ringsOverSubGraph.keySet())
        {
            List<Vertex> vPair = ringsOverSubGraph.get(r);
            PathSubGraph path = new PathSubGraph(vPair.get(0),vPair.get(1),this);
            List<Vertex> verticesInPath = path.getVertecesPath();
            for (int i=1; i<(verticesInPath.size()-1); i++)
            {
                r.removeVertex(verticesInPath.get(i));
            }
        }
        
        // remove edges with old vertex
        for (AttachmentPoint oldAP : interfaceApsOnOldBranch)
        {
            if (!oldAP.isAvailable())
                removeEdge(oldAP.getEdgeUser());
        }
 
        // remove the vertex from the graph
        for (Vertex vToDel : subGrpVrtxs)
        {
            // WARNING! This removes rings involving these vertices. 
            removeVertex(vToDel);
        }
        
        // finally introduce the new vertices from incoming graph into this graph
        for (Vertex incomingVrtx : newSubGraph.getVertexList())
        {
            addVertex(incomingVrtx);
        }
        
        // import edges from incoming graph 
        for (Edge incomingEdge : newSubGraph.getEdgeList())
        {
            addEdge(incomingEdge);
        }
        
        // import rings from incoming graph
        for (Ring incomingRing : newSubGraph.getRings())
        {
            addRing(incomingRing);
        }
        
        // import symmetric sets from incoming graph? No, this method doesn't do
        // it because we want to use it in situations where we have to perform 
        // multiple replaceSubGraph operations and, afterwards, use the 
        // symmetric labels to create symmetric sets that might span across
        // more than one of the subgraphs that were added.
        
        // We keep track of the APs on the new link that have been dealt with
        List<AttachmentPoint> doneApsOnNew = 
                new ArrayList<AttachmentPoint>();
        
        // Connect the incoming subgraph to the rest of the graph
        if (trgAPOnNewLink != null)
        {
            // the incoming graph has a parent vertex, and the edge should be  
            // directed accordingly
            Edge edge = new Edge(
                    linksToRecreate.get(trgAPOnNewLink),
                    trgAPOnNewLink, 
                    linkTypesToRecreate.get(trgAPOnNewLink));
            addEdge(edge);
            doneApsOnNew.add(trgAPOnNewLink);
        } else {
            // newLink does NOT have a parent vertex, so all the
            // edges see newLink as target vertex. Such links are dealt with
            // in the loop below. So, there is nothing special to do, here.
        }
        for (AttachmentPoint apOnNew : linksToRecreate.keySet())
        {
            if (apOnNew == trgAPOnNewLink)
            {
                continue; //done just before this loop
            }
            AttachmentPoint trgOnChild = linksToRecreate.get(apOnNew);
            Edge edge = new Edge(apOnNew,trgOnChild, 
                    linkTypesToRecreate.get(apOnNew));
            addEdge(edge);
            doneApsOnNew.add(apOnNew);
        }
        
        // redefine rings that spanned over the removed subgraph
        for (Ring r : ringsOverSubGraph.keySet())
        {
            List<Vertex> vPair = ringsOverSubGraph.get(r);
            PathSubGraph path = new PathSubGraph(vPair.get(0),vPair.get(1),this);
            int initialInsertPoint = r.getPositionOf(vPair.get(0));
            List<Vertex> verticesInPath = path.getVertecesPath();
            for (int i=1; i<(verticesInPath.size()-1); i++)
            {
                r.insertVertex(initialInsertPoint+i, verticesInPath.get(i));
            }
        }
        
        // update the mapping of this vertices' APs in the jacket template
        if (templateJacket != null)
        {
            templateJacket.clearIAtomContainer();
            for (AttachmentPoint apOnNew : inToOutAPForTemplate.keySet())
            {
                templateJacket.updateInnerApID(
                        inToOutAPForTemplate.get(apOnNew),apOnNew);
                doneApsOnNew.add(apOnNew);
            }
            
            // Project all remaining APs of new branch on the surface of template
            for (AttachmentPoint apOnNew : interfaceApsOnNewBranch)
            {
                if (!doneApsOnNew.contains(apOnNew))
                {
                    templateJacket.addInnerToOuterAPMapping(apOnNew);
                }
            }
            
            // Remove all APs that existed only in the old branch
            for (AttachmentPoint apOnOld : oldAPToRemoveFromTmpl)
            {
                templateJacket.removeProjectionOfInnerAP(apOnOld);
            }
        }
        
        jGraph = null;
        jGraphKernel = null;
        
        for (Vertex vOld : subGrpVrtxs)
            if (this.containsVertex(vOld))
                return false;
        for (Vertex vNew : newvertices)
            if (!this.containsVertex(vNew))
                return false;
        return true;
    }
    
//------------------------------------------------------------------------------
    
    public boolean replaceVertex(Vertex vertex, int bbId, BBType bbt,
            LinkedHashMap<Integer, Integer> apIdMap, FragmentSpace fragSpace)
                    throws DENOPTIMException
    {
        return replaceVertex(vertex, bbId, bbt, apIdMap, true, fragSpace);
    }
    
//------------------------------------------------------------------------------
    
    public boolean replaceVertex(Vertex vertex, int bbId, BBType bbt,
            LinkedHashMap<Integer, Integer> apIdMap, boolean symmetry,
            FragmentSpace fragSpace)
                    throws DENOPTIMException
    {
        if (!gVertices.contains(vertex))
        {
            return false;
        }
        
        List<Vertex> symSites = new ArrayList<Vertex>();
        if (symmetry)
        {
            symSites = getSymVerticesForVertex(vertex);
        }
        if (symSites.size() == 0)
        {
            symSites.add(vertex);
        }
        
        GraphUtils.ensureVertexIDConsistency(this.getMaxVertexId());
        Vertex newLink = Vertex.newVertexFromLibrary(
                GraphUtils.getUniqueVertexIndex(), bbId, bbt, fragSpace);
        DGraph incomingGraph = new DGraph();
        incomingGraph.addVertex(newLink);
        incomingGraph.reassignSymmetricLabels();
        
        for (Vertex oldLink : symSites)
        {
            DGraph graphAdded = incomingGraph.clone();
            graphAdded.getVertexAtPosition(0).setMutationTypes(
                    oldLink.getUnfilteredMutationTypes());
            graphAdded.renumberGraphVertices();
            
            ArrayList<Vertex> oldVertex = new ArrayList<Vertex>();
            oldVertex.add(oldLink);
            LinkedHashMap<AttachmentPoint,AttachmentPoint> apMap =
                    new LinkedHashMap<AttachmentPoint,AttachmentPoint>();
            for (Map.Entry<Integer,Integer> e : apIdMap.entrySet())
            {
                apMap.put(oldLink.getAP(e.getKey()), 
                        graphAdded.getVertexAtPosition(0).getAP(e.getValue()));
            }
            
            if (!replaceSingleSubGraph(oldVertex, graphAdded, apMap))
            {
                return false;
            }
        }
        convertSymmetricLabelsToSymmetricSets();
        return true;
    }
    
//------------------------------------------------------------------------------
    
    //NB: LinkedHashMap is used to retain reproducibility between runs.
    
    public boolean insertVertex(Edge edge, int bbId, BBType bbt,
            LinkedHashMap<AttachmentPoint,Integer> apMap, 
            FragmentSpace fragSpace) 
                    throws DENOPTIMException
    {
        if (!gEdges.contains(edge))
        {
            return false;
        }
        
        List<Edge> symSites = new ArrayList<Edge> ();
        List<LinkedHashMap<AttachmentPoint,Integer>> symApMaps = 
                new ArrayList<LinkedHashMap<AttachmentPoint,Integer>>();
        List<Vertex> symTrgvertices = getSymVerticesForVertex(
                edge.getTrgAP().getOwner());
        if (symTrgvertices.size() == 0)
        {
            symSites.add(edge);
            symApMaps.add(apMap);
        } else {
            for (Vertex trgVrtx : symTrgvertices)
            {
                Edge symEdge = trgVrtx.getEdgeToParent();
                symSites.add(symEdge);
                
                LinkedHashMap<AttachmentPoint,Integer> locApMap = new
                        LinkedHashMap<AttachmentPoint,Integer>();
                locApMap.put(symEdge.getSrcAP(), apMap.get(edge.getSrcAP()));
                locApMap.put(symEdge.getTrgAP(), apMap.get(edge.getTrgAP()));
                symApMaps.add(locApMap);
            }
        }
        
        SymmetricVertexes newSS = new SymmetricVertexes();
        for (int i=0; i<symSites.size(); i++)
        {
            Edge symEdge = symSites.get(i);
            LinkedHashMap<AttachmentPoint,Integer> locApMap = symApMaps.get(i);
            
            GraphUtils.ensureVertexIDConsistency(this.getMaxVertexId());
            Vertex newLink = Vertex.newVertexFromLibrary(
                    GraphUtils.getUniqueVertexIndex(), bbId, bbt, fragSpace);
            newSS.add(newLink);
            LinkedHashMap<AttachmentPoint,AttachmentPoint> apToApMap =
                    new LinkedHashMap<AttachmentPoint,AttachmentPoint>();
            for (AttachmentPoint apOnGraph : locApMap.keySet())
            {
                apToApMap.put(apOnGraph, newLink.getAP(locApMap.get(apOnGraph)));
            }
            if (!insertSingleVertex(symEdge, newLink, apToApMap))
            {
                return false;
            }
        }
        if (newSS.size()>1)
        {
            addSymmetricSetOfVertices(newSS);
        }
        return true;
    }
    
//------------------------------------------------------------------------------
    
    public boolean insertSingleVertex(Edge edge, Vertex newLink,
            LinkedHashMap<AttachmentPoint,AttachmentPoint> apMap) 
                    throws DENOPTIMException
    {
        //TODO: for reproducibility the AP mapping should become an optional
        // parameter: if given we try to use it, if not given we GraphLinkFinder
        // will try to find a suitable mapping.
        
        if (!gEdges.contains(edge) || gVertices.contains(newLink))
        {
            return false;
        }
        
        // First keep track of the links that will be broken and re-created,
        // and also of the relation free APs may have with a possible template
        // that embeds this graph.
        AttachmentPoint orisEdgeSrc = edge.getSrcAP();
        AttachmentPoint orisEdgeTrg = edge.getTrgAP();
        Vertex srcVrtx = orisEdgeSrc.getOwner();
        Vertex trgVrtx = orisEdgeTrg.getOwner();
        
        removeEdge(edge);
        
        // Introduce the new vertex in the graph
        addVertex(newLink);
        
        // Connect the new vertex to the graph
        Edge eSrcToLink = new Edge(orisEdgeSrc,
                apMap.get(orisEdgeSrc), edge.getBondType());
        addEdge(eSrcToLink);
        Edge eLinkToTrg = new Edge(apMap.get(orisEdgeTrg),
                orisEdgeTrg, edge.getBondType());
        addEdge(eLinkToTrg);
        
        // update any affected ring
        if (isVertexInRing(srcVrtx) && isVertexInRing(trgVrtx))
        {
            ArrayList<Ring> rToEdit = new ArrayList<Ring>();
            rToEdit.addAll(getRingsInvolvingVertex(srcVrtx));
            rToEdit.retainAll(getRingsInvolvingVertex(trgVrtx));
            for (Ring r : rToEdit)
            {
                r.insertVertex(newLink,srcVrtx,trgVrtx);
            }
        }
    
        // NB: if this graph is embedded in a template, new free/available 
        // APs introduced with the new link need to be mapped on the surface of
        // the template
        if (templateJacket != null)
        {
            for (AttachmentPoint ap : newLink.getAttachmentPoints())
            {
                if (ap.isAvailable())
                {
                    templateJacket.addInnerToOuterAPMapping(ap);
                }
            }
        } 
        
        jGraph = null;
        jGraphKernel = null;
        
        return !gEdges.contains(edge) && this.containsVertex(newLink);
    }
 
//------------------------------------------------------------------------------
 
    public Vertex getVertexAtPosition(int pos)
    {
        return ((pos >= gVertices.size()) || pos < 0) ? null :
                gVertices.get(pos);
    }
    
//------------------------------------------------------------------------------
    
    public boolean containsOrEmbedsVertex(Vertex v)
    {
        if (gVertices.contains(v))
            return true;
           
        for (Vertex vrt : gVertices)
        {
            if (vrt instanceof Template)
            {
                Template t = (Template) vrt;
                if (t.getInnerGraph().containsOrEmbedsVertex(v))
                    return true;
            }
        }
        return false;
    }
    
 
//------------------------------------------------------------------------------
 
    public boolean containsVertex(Vertex v)
    {
        return gVertices.contains(v);
    }
    
//------------------------------------------------------------------------------
 
    public int indexOf(Vertex v)
    {
        return gVertices.indexOf(v);
    }
 
//------------------------------------------------------------------------------
 
    public Vertex getVertexWithId(long vid)
    {
        Vertex v = null;
        int idx = indexOfVertexWithID(vid);
        if (idx != -1)
            v = gVertices.get(idx);
        return v;
    }
 
//------------------------------------------------------------------------------
 
    public int indexOfVertexWithID(long vid)
    {
        int idx = -1;
        for (int i=0; i<gVertices.size(); i++)
        {
            Vertex v = gVertices.get(i);
            if (v.getVertexId() == vid)
            {
                idx = i;
                break;
            }
        }
        return idx;
    }
 
//------------------------------------------------------------------------------
 
    public void removeEdge(Edge edge)
    {
        if (gEdges.contains(edge))
        {
            AttachmentPoint srcAP = edge.getSrcAP();
            AttachmentPoint trgAP = edge.getTrgAP();
            srcAP.setUser(null);
            trgAP.setUser(null);
 
            gEdges.remove(edge);
        }
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public void removeRing(Ring ring)
    {
        if (gRings.contains(ring))
        {
            gRings.remove(ring);
        }
        jGraph = null;
        jGraphKernel = null;
    }
 
//------------------------------------------------------------------------------
 
    public Edge getEdgeAtPosition(int pos)
    {
        if ((pos >= gEdges.size()) || pos < 0)
            return null;
        return gEdges.get(pos);
    }
 
//------------------------------------------------------------------------------
 
    public int getEdgeCount()
    {
        return gEdges.size();
    }
 
//------------------------------------------------------------------------------
 
    public int getRingCount()
    {
        return gRings.size();
    }
 
//------------------------------------------------------------------------------
 
    public int getVertexCount()
    {
        return gVertices.size();
    }
 
//------------------------------------------------------------------------------
 
    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder(512);
 
        sb.append(graphId).append(" ");
 
        for (int i=0; i<gVertices.size(); i++)
        {
            sb.append(gVertices.get(i).toString()).append(",");
        }
 
        sb.append(" ");
 
        for (int i=0; i<gEdges.size(); i++)
        {
            sb.append(gEdges.get(i).toString()).append(",");
        }
 
        sb.append(" ");
 
        for (int i=0; i<gRings.size(); i++)
        {
            sb.append(gRings.get(i).toString()).append(" ");
        }
 
        for (int i=0; i<symVertices.size(); i++)
        {
            sb.append(symVertices.get(i).toString()).append(" ");
        }
 
        return sb.toString();
    }
 
//------------------------------------------------------------------------------
 
    @Deprecated
    public int getBondingAPIndex(Vertex srcVert, int dapidx,
                                    Vertex dstVert)
    {
        int n = getEdgeCount();
        for (int i = 0; i < n; i++)
        {
            Edge edge = getEdgeList().get(i);
 
            // get the vertex ids
            long v1_id = edge.getSrcVertex();
            long v2_id = edge.getTrgVertex();
 
            int dap_idx_v1 = edge.getSrcAPID();
 
            if (srcVert.getVertexId() == v1_id && v2_id == dstVert.getVertexId()
                                && dap_idx_v1 == dapidx)
            {
                return edge.getTrgAPID();
            }
        }
 
        return -1;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Vertex> getChildVertices(Vertex vertex)
    {
        return vertex.getChilddren();
    }
 
//------------------------------------------------------------------------------
 
    public void getChildrenTree(Vertex vertex, List<Vertex> children) 
    {
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst) 
        {
            if (!children.contains(child)) 
            {
                children.add(child);
                getChildrenTree(child, children);
            }
        }
    }
    
//------------------------------------------------------------------------------
 
    public void getChildrenTree(Vertex vertex, List<Vertex> children, 
            boolean markBranches) 
    {
        if (!markBranches)
        {
            getChildrenTree(vertex, children);
            return;
        }
        
        AtomicInteger branchIdGenerator = new AtomicInteger(0);
        List<Integer> thisBranchId = new ArrayList<Integer>();
        thisBranchId.add(branchIdGenerator.getAndIncrement());
        
        vertex.setProperty(DENOPTIMConstants.GRAPHBRANCHID, thisBranchId);
        
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst)
        {
            if (!children.contains(child)) 
            {
                children.add(child);
                if (lst.size()==1)
                {
                    child.setProperty(DENOPTIMConstants.GRAPHBRANCHID, 
                            thisBranchId);
                    getChildrenTree(child, children, branchIdGenerator, 
                            thisBranchId);
                } else {
                    List<Integer> newBranchId = new ArrayList<>(thisBranchId);
                    newBranchId.add(branchIdGenerator.getAndIncrement());
                    child.setProperty(DENOPTIMConstants.GRAPHBRANCHID, 
                            newBranchId);
                    getChildrenTree(child, children, branchIdGenerator, 
                            newBranchId);
                }
            }
        }
    }
    
//------------------------------------------------------------------------------
 
    public void getChildrenTree(Vertex vertex, List<Vertex> children, 
            AtomicInteger branchIdGenerator, List<Integer> prevBranchId) 
    {
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst)
        {
            if (!children.contains(child)) 
            {
                children.add(child);
                if (lst.size()==1)
                {
                    child.setProperty(DENOPTIMConstants.GRAPHBRANCHID, 
                            prevBranchId);
                    getChildrenTree(child, children, branchIdGenerator, 
                            prevBranchId);
                } else {
                    List<Integer> newBranchId = new ArrayList<>(prevBranchId);
                    newBranchId.add(branchIdGenerator.getAndIncrement());
                    child.setProperty(DENOPTIMConstants.GRAPHBRANCHID, 
                            newBranchId);
                    getChildrenTree(child, children, branchIdGenerator, 
                            newBranchId);
                }
            }
        }
    }
    
//------------------------------------------------------------------------------
 
    public void getChildrenTree(Vertex vertex,
            List<Vertex> children, int numLayers, boolean stopBeforeRCVs) 
    {
        if (numLayers==0)
        {
            return;
        }
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst) 
        {
            if (children.contains(child)) 
                continue;
            
            if (stopBeforeRCVs && child.isRCV())
                continue;
                
            children.add(child);
            getChildrenTree(child, children, numLayers-1, stopBeforeRCVs);
        }
    }
    
//------------------------------------------------------------------------------
    
    public List<Integer> getBranchIdOfVertexAtPosition(int i)
    {
        return getBranchIdOfVertex(getVertexAtPosition(i));
    }
    
//------------------------------------------------------------------------------
    
    @SuppressWarnings("unchecked")
    public List<Integer> getBranchIdOfVertex(Vertex v)
    {
        if (!gVertices.contains(v))
            return null;
        
        return (List<Integer>) v.getProperty(DENOPTIMConstants.GRAPHBRANCHID);
    }
    
//------------------------------------------------------------------------------
    
    public String getBranchIdOfVertexAsStr(Vertex v)
    {
        List<Integer> lst = getBranchIdOfVertex(v);
        String s = "";
        for (Integer i : lst)
            s = s + i + "_";
        return s;
    }
    
//------------------------------------------------------------------------------
    
    public boolean directedPathExists(Vertex src, Vertex trg)
    {
        List<Integer> bIdSrc = getBranchIdOfVertex(src);
        List<Integer> bIdTrg = getBranchIdOfVertex(trg);
        if (bIdSrc==null || bIdTrg==null)
            return false;
        if (bIdSrc.size()>bIdTrg.size())
            return false;
        int sharedSubBranches = 0;
        for (int i=0; i<bIdSrc.size(); i++)
        {
            if (bIdSrc.get(i)==bIdTrg.get(i))
                sharedSubBranches++;
        }
        return sharedSubBranches==bIdSrc.size();
    }
    
//------------------------------------------------------------------------------
 
    public void getChildTreeLimited(Vertex vertex,
            List<Vertex> children, boolean stopBeforeRCVs) 
    {
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst) 
        {   
            if (children.contains(child)) 
                continue;
              
            if (stopBeforeRCVs && child.isRCV())
                continue;
                  
            children.add(child);
            getChildTreeLimited(child, children, stopBeforeRCVs);
        }
    }
    
//------------------------------------------------------------------------------
    
    public void getChildTreeLimited(Vertex vertex,
            List<Vertex> children, Set<Vertex> limits)
    {
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst) 
        {
            if (!children.contains(child)) 
            {
                children.add(child);
                if (!limits.contains(child))
                    getChildTreeLimited(child, children, limits);
            }
        }
    }
   
//------------------------------------------------------------------------------
 
    public void getChildTreeLimited(Vertex vertex,
            List<Vertex> children, List<Vertex> limitsInClone, 
            boolean stopBeforeRCVs) 
    {
        List<Vertex> lst = getChildVertices(vertex);
        if (lst.isEmpty()) 
        {
            return;
        }
        for (Vertex child : lst) 
        {   
            if (children.contains(child)) 
                continue;
            
            if (stopBeforeRCVs && child.isRCV())
                continue;
                
            children.add(child);
            if (!limitsInClone.contains(child))
                getChildTreeLimited(child, children, limitsInClone, stopBeforeRCVs);
        }
    }
    
//------------------------------------------------------------------------------
    
    public Vertex getDeepestAmongThese(List<Vertex> list)
    {
        Vertex deepest = null;
        int shortest = Integer.MAX_VALUE;
        for (Vertex vertex : list)
        {
            List<Vertex> parentTree = new ArrayList<Vertex>();
            getParentTree(vertex, parentTree);
            if (parentTree.size()<shortest)
            {
                shortest = parentTree.size();
                deepest = vertex;
            }
        }
        return deepest;
    }
    
//------------------------------------------------------------------------------
 
    public void getParentTree(Vertex vertex,
            List<Vertex> parentTree) 
    {
        Vertex parent = getParent(vertex);
        if (parent == null) 
        {
            return;
        }
        if (parentTree.contains(parent))
        {
            // Cyclic graphs are not allowed!
            throw new IllegalArgumentException();
        }
        parentTree.add(parent);
        getParentTree(parent, parentTree);
    }
    
//------------------------------------------------------------------------------
 
    public Vertex getParent(Vertex v)
    {
        Edge edge = v.getEdgeToParent();
        if (edge != null)
        {
            return edge.getSrcAP().getOwner();
        }
        return null;
    }
 
//------------------------------------------------------------------------------
 
    @Override
    public DGraph clone()
    {   
        // When cloning, the VertexID remains the same so we'll have two
        // deep-copies of the same vertex having the same VertexID
        ArrayList<Vertex> cListVrtx = new ArrayList<>();
        Map<Long, Vertex> vidsInClone = new HashMap<Long, Vertex>();
        for (Vertex vOrig : gVertices)
        {
            Vertex vClone = vOrig.clone();
            cListVrtx.add(vClone);
            vidsInClone.put(vClone.getVertexId(), vClone);
        }
 
        ArrayList<Edge> cListEdges = new ArrayList<>();
        for (Edge e : gEdges)
        {
            long srcVrtxId = e.getSrcVertex();
            int srcApId = this.getVertexWithId(srcVrtxId).getIndexOfAP(
                    e.getSrcAP());
 
            long trgVrtxId = e.getTrgVertex();
            int trgApId = this.getVertexWithId(trgVrtxId).getIndexOfAP(
                    e.getTrgAP());
 
            AttachmentPoint srcAPClone = vidsInClone.get(
                    srcVrtxId).getAP(srcApId);
            AttachmentPoint trgAPClone = vidsInClone.get(
                    trgVrtxId).getAP(trgApId);
 
            cListEdges.add(new Edge(srcAPClone, trgAPClone,
                    e.getBondType()));
        }
 
        DGraph clone = new DGraph(cListVrtx, cListEdges);
 
        // Copy the list but using the references to the cloned vertices
        ArrayList<Ring> cListRings = new ArrayList<>();
        for (Ring ring : gRings)
        {
            Ring cRing = new Ring();
            for (int iv=0; iv<ring.getSize(); iv++)
            {
                Vertex origVrtx = ring.getVertexAtPosition(iv);
                cRing.addVertex(
                        clone.getVertexWithId(origVrtx.getVertexId()));
            }
            cRing.setBondType(ring.getBondType());
            cListRings.add(cRing);
        }
        clone.setRings(cListRings);
 
        // The chainLinks are made of primitives, so it's just fine
        ArrayList<ClosableChain> cListClosableChains =
                new ArrayList<>();
        for (ClosableChain cc : closableChains)
        {
            cListClosableChains.add(cc.clone());
        }
        clone.setCandidateClosableChains(cListClosableChains);
 
        
        List<SymmetricVertexes> cSymVertices = new ArrayList<>();
        for (SymmetricVertexes ss : symVertices)
        {
            SymmetricVertexes clonedSS = new SymmetricVertexes();
            for (Vertex origVrt : ss)
            {
                clonedSS.add(clone.gVertices.get(gVertices.indexOf(origVrt)));
            }
            cSymVertices.add(clonedSS);
        }
        clone.setSymmetricVertexSets(cSymVertices);
        
        clone.setGraphId(graphId);
        clone.setLocalMsg(localMsg);
 
        return clone;
    }
 
//------------------------------------------------------------------------------
 
    public Edge getEdgeWithParent(long l)
    {
        Vertex v = getVertexWithId(l);
        if (v == null)
        {
            return null;
        }
        return v.getEdgeToParent();
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Integer> getIndexOfEdgesWithChild(int vid)
    {
        ArrayList<Integer> lstEdges = new ArrayList<>();
        for (int j=0; j<getEdgeCount(); j++)
        {
            Edge edge = getEdgeAtPosition(j);
 
            if (edge.getSrcVertex() == vid)
            {
                lstEdges.add(j);
            }
        }
        return lstEdges;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<Edge> getEdgesWithChild(int vid)
    {
        ArrayList<Edge> lstEdges = new ArrayList<>();
        for (int j=0; j<getEdgeCount(); j++)
        {
            Edge edge = getEdgeAtPosition(j);
 
            if (edge.getSrcVertex() == vid)
            {
                lstEdges.add(edge);
            }
        }
        return lstEdges;
    }
 
//------------------------------------------------------------------------------
 
    public long getMaxVertexId()
    {
        long mval = Long.MIN_VALUE;
        for (Vertex v : gVertices) {
            mval = Math.max(mval, v.getVertexId());
        }
        return mval;
    }
    
//------------------------------------------------------------------------------
    
    public boolean containsVertexID(long l)
    {
        boolean result = false;
        for (Vertex v : gVertices) 
        {
            if (l == v.getVertexId())
            {
                result = true;
                break;
            }
        }
        return result;
    }
 
//------------------------------------------------------------------------------
 
    public void cleanup()
    {
        if (gVertices != null)
        {
            gVertices.clear();
        }
        if (gEdges != null)
        {
            gEdges.clear();
        }
        if (gRings != null)
        {
            gRings.clear();
        }
        if (symVertices != null)
        {
            symVertices.clear();
        }
        if (closableChains != null)
        {
            closableChains.clear();
        }
        jGraph = null;
        jGraphKernel = null;
    }
    
//------------------------------------------------------------------------------
    
    /*
     * NB: this javadoc string is reproduced in the user manual HTML file.
     * In case of modifications, please keep the two sources compatible by
     * reproducing the modification on both sites.
     */
    
    public boolean isIsomorphicTo(DGraph other) {
        if (this.jGraph == null)
        {
            this.jGraph = GraphConversionTool.getJGraphFromGraph(this);
        }
        if (other.jGraph == null)
        {
            other.jGraph = GraphConversionTool.getJGraphFromGraph(other);
        }
        
        // Simple but slow because it ignores symmetry
        /*
        Comparator<DENOPTIMVertex> vComp = (v1, v2) -> {
            // Vertex.sameAs returns boolean, so we need to produce
            // an int to allow comparison.
            StringBuilder sb = new StringBuilder();
            boolean areSame = v1.sameAs(v2, sb);
            
            if (areSame) {
                return 0;
            } else {
                return Integer.compare(v1.getBuildingBlockId(),
                        v2.getBuildingBlockId());
            }
        };
        */
        
        Comparator<Vertex> vComp = new Comparator<Vertex>() {
            
            Map<Vertex,Set<Vertex>> symmetryShortCuts = 
                    new HashMap<Vertex,Set<Vertex>>();
            
            @Override
            public int compare(Vertex v1, Vertex v2) {
                
                // exploit symmetric relations between vertices
                if (symmetryShortCuts.containsKey(v1) 
                        && symmetryShortCuts.get(v1).contains(v2))
                {
                    return 0;
                }
 
                // Vertex.sameAs returns boolean, so we need to produce
                // an int to allow comparison.
                StringBuilder sb = new StringBuilder();
                if (v1.sameAs(v2, sb)) 
                {
                    Set<Vertex> symToV2 = new HashSet<Vertex>();
                    symToV2.addAll(v2.getGraphOwner().getSymSetForVertex(v2));
                    Set<Vertex> symToV1 = new HashSet<Vertex>();
                    symToV1.addAll(v1.getGraphOwner().getSymSetForVertex(v1));
                    for (Vertex v1s : symToV1)
                    {
                        if (symmetryShortCuts.containsKey(v1s))
                        {
                            symmetryShortCuts.get(v1s).addAll(symToV2);
                        } else {
                            symmetryShortCuts.put(v1s,symToV2);
                        }
                    }
                    return 0;
                } else {
                    // We must return something different than zero
                    if (Integer.compare(v1.getBuildingBlockId(),
                            v2.getBuildingBlockId())!=0)
                        return Integer.compare(v1.getBuildingBlockId(),
                                v2.getBuildingBlockId());
                    if (Integer.compare(v1.hashCode(),
                            v2.hashCode())!=0)
                        return Integer.compare(v1.hashCode(),
                                v2.hashCode());
                    return Integer.compare(v1.getBuildingBlockId()+v1.hashCode(),
                            v2.getBuildingBlockId()+v2.hashCode());
                }
            }
        };
        
        Comparator<UndirectedEdge> eComp =
                UndirectedEdge::compare;
        
        // NB: these two were created to evaluate the simplest and fasted 
        // possible scenario. It turns out that for a graph like the following
        // one the time spent to do automorphism (i.e., isomorphism with itself)
        // can only be improved by 20% when using these two simplest and 
        // useless (i.e., inaccurate) comparators. Instead the above, and useful
        // comparators do introduce some computational demands, but are less 
        // detrimental than having to address a wide multitude of possible 
        // mappings: this seems to be the liming factor, rather than the
        // implementation of the comparators.
        
        // Example of challenging, yet simple graph:
        //29 853_1_0_-1,855_2_1_0,857_1_1_0,858_1_1_0,859_1_1_0,861_2_1_1,862_2_1_1,863_2_1_1,864_2_1_1,865_2_1_1,866_2_1_1,867_2_1_1,868_2_1_1,869_2_1_1, 853_1_855_0_1_c:0_ATneutral:0,853_0_857_1_1_c:0_c:0,853_2_858_1_1_c:0_c:0,853_3_859_1_1_c:0_c:0,857_0_861_0_1_c:0_ATneutral:0,857_2_862_0_1_c:0_ATneutral:0,857_3_863_0_1_c:0_ATneutral:0,858_0_864_0_1_c:0_ATneutral:0,858_2_865_0_1_c:0_ATneutral:0,858_3_866_0_1_c:0_ATneutral:0,859_0_867_0_1_c:0_ATneutral:0,859_2_868_0_1_c:0_ATneutral:0,859_3_869_0_1_c:0_ATneutral:0, SymmetricSet [symIds=[857, 858, 859]] SymmetricSet [symIds=[861, 862, 863, 864, 865, 866, 867, 868, 869]]
        
        /*
        Comparator<UndirectedEdgeRelation> eCompDummy = (e1, e2) -> {
            return Integer.compare(e1.hashCode(),e2.hashCode());
        };
        Comparator<DENOPTIMVertex> vCompDummy = (v1, v2) -> {
            return Integer.compare(v1.getBuildingBlockId(),
                        v2.getBuildingBlockId());
        };
        */
        
        VF2GraphIsomorphismInspector<Vertex, UndirectedEdge> vf2 =
                new VF2GraphIsomorphismInspector<>(this.jGraph, other.jGraph, 
                        vComp, eComp);
 
        return vf2.isomorphismExists();
    }
    
//------------------------------------------------------------------------------
 
    public boolean isIsostructuralTo(DGraph other) {
        if (this.jGraphKernel == null)
        {
            this.jGraphKernel = GraphConversionTool.getJGraphKernelFromGraph(this);
        }
        if (other.jGraphKernel == null)
        {
            other.jGraphKernel = GraphConversionTool.getJGraphKernelFromGraph(other);
        }
        
        Comparator<Node> vComp = new Comparator<Node>() {
            
            Map<Node,Set<Node>> symmetryShortCuts = 
                    new HashMap<Node,Set<Node>>();
            
            @Override
            public int compare(Node v1, Node v2) {
                
                // exploit symmetric relations between vertices
                if (symmetryShortCuts.containsKey(v1) 
                        && symmetryShortCuts.get(v1).contains(v2))
                {
                    return 0;
                }
                
                int result = v1.compare(v2);
                if (result==0) 
                {
                    Vertex dv1 = v1.getDNPVertex();
                    Vertex dv2 = v2.getDNPVertex();
                    if (dv1==null && dv2==null)
                    {
                        return result;
                    }
                    
                    Set<Node> symToV2 = new HashSet<Node>();
                    for (Vertex sv : dv2.getGraphOwner().getSymSetForVertex(dv2))
                    {
                        symToV2.add((Node) sv.getProperty(
                                Node.REFTOVERTEXKERNEL));
                    }
                    
                    Set<Node> symToV1 = new HashSet<Node>();
                    for (Vertex sv :  dv1.getGraphOwner().getSymSetForVertex(dv1))
                    {
                        symToV1.add((Node) sv.getProperty(
                                Node.REFTOVERTEXKERNEL));
                    }
                    
                    for (Node v1s : symToV1)
                    {
                        if (symmetryShortCuts.containsKey(v1s))
                        {
                            symmetryShortCuts.get(v1s).addAll(symToV2);
                        } else {
                            symmetryShortCuts.put(v1s,symToV2);
                        }
                    }
                    return 0;
                }
                return result;
            }
        };
        
        Comparator<NodeConnection> eComp = NodeConnection::compare;
        
        VF2GraphIsomorphismInspector<Node, NodeConnection> vf2 =
                new VF2GraphIsomorphismInspector<>(this.jGraphKernel, 
                        other.jGraphKernel, vComp, eComp);
 
        return vf2.isomorphismExists();
    }
 
//------------------------------------------------------------------------------
 
    public boolean sameAs(DGraph other, StringBuilder reason)
    {
        if (this.getEdgeCount() != other.getEdgeCount())
        {
            reason.append("Different number of edges ("+this.getEdgeCount()+":"
                        +other.getEdgeCount()+")");
            return false;
        }
 
        if (this.getVertexCount() != other.getVertexCount())
        {
            reason.append("Different number of vertices ("+this.getVertexCount()+":"
                        +other.getVertexCount()+")");
            return false;
        }
 
        if (this.getSymmetricSetCount() != other.getSymmetricSetCount())
        {
            reason.append("Different number of symmetric sets ("
                        + this.getSymmetricSetCount() + ":"
                        + other.getSymmetricSetCount() + ")");
            return false;
        }
 
        if (this.getRingCount() != other.getRingCount())
        {
            reason.append("Different number of Rings ("+this.getRingCount()+":"
                        +other.getRingCount()+")");
            return false;
        }
 
        //Pairwise correspondence of vertices
        Map<Vertex,Vertex> vertexMap =
                new HashMap<Vertex,Vertex>();
 
        vertexMap.put(this.getVertexAtPosition(0),other.getVertexAtPosition(0));
 
        //WARNING: assuming that the first vertex in the vertex list is the root
        // and also that there are no disconnections. Both assumptions are
        // reasonable for graphs.
        try {
            if (!compareGraphNodes(this.getVertexAtPosition(0), this,
                                            other.getVertexAtPosition(0), other,
                                            vertexMap,reason))
            {
                return false;
            }
        } catch (DENOPTIMException e) {
            e.printStackTrace();
            reason.append("Exception");
            return false;
        }
 
        //Check Symmetric sets
        Iterator<SymmetricVertexes> ssIter = this.getSymSetsIterator();
        while (ssIter.hasNext())
        {
            SymmetricVertexes ssT = ssIter.next();
 
            SymmetricVertexes ssO = other.getSymSetForVertex(
                    vertexMap.get(ssT.get(0)));
            if (ssO.size() == 0)
            {
                // ssO is empty because no SymmetricSet was found that
                // contains the given vertex. This means the two graphs
                // are different
                reason.append("Symmetric set not found for vertex (" 
                        + ssT.get(0) + ")");
                return false;
            }
 
            if (ssT.size() != ssO.size())
            {
                reason.append("Different number of symmetric sets on vertex " 
                        + ssT.get(0) + "("+ssT.size()+":"+ssO.size()+")");
                return false;
            }
 
            Set<Vertex> mappedVrtxFromThis = new HashSet<>();
            ssT.stream().forEach(v -> mappedVrtxFromThis.add(vertexMap.get(v)));
 
            Set<Vertex> vrtxFromOther = new HashSet<>();
            ssO.stream().forEach(v -> vrtxFromOther.add(v));
            if (!vrtxFromOther.equals(mappedVrtxFromThis))
            {
                reason.append("Difference in symmetric set " + ssT + " vs " + ssO);
                return false;
            }
        }
 
        //Check Rings
        for (Ring rT : this.getRings())
        {
            Vertex vhT = rT.getHeadVertex();
            Vertex vtT = rT.getTailVertex();
            boolean hasRing = other
                    .getRingsInvolvingVertex(vertexMap.get(vhT))
                    .stream()
                    .anyMatch(rO -> sameAsRings(reason, vertexMap, rT, vhT,
                            vtT, rO));
            if (!hasRing) {
                return false;
            }
        }
 
        return true;
    }
 
//------------------------------------------------------------------------------
 
    private boolean sameAsRings(StringBuilder reason, Map<Vertex,
            Vertex> vertexMap, Ring rT, Vertex vhT,
                                Vertex vtT, Ring rO) {
        if (rT.getSize() != rO.getSize()) {
            reason.append("Different ring size (").append(rT.getSize())
                    .append(":").append(rO.getSize()).append(")");
            return false;
        }
 
        if (rO.getHeadVertex() == vertexMap.get(vhT)
                && rO.getTailVertex() == vertexMap.get(vtT)) {
            for (int i = 1; i < rT.getSize(); i++) {
                if (vertexMap.get(rT.getVertexAtPosition(i))
                        != rO.getVertexAtPosition(i)) {
                    reason.append("Rings differ (A) (").append(rT).append(":")
                            .append(rO).append(")");
                    return false;
                }
            }
        } else if (rO.getHeadVertex() == vertexMap.get(vtT)
                && rO.getTailVertex() == vertexMap.get(vhT)) {
            for (int i = 1; i < rT.getSize(); i++) {
                int j = rO.getSize() - i - 1;
                if (vertexMap.get(rT.getVertexAtPosition(i))
                        != rO.getVertexAtPosition(j)) {
                    reason.append("Rings differ (B) (").append(rT).append(":")
                            .append(rO).append(")");
                    return false;
                }
            }
        } else {
            reason.append("Rings differ (C) (").append(rT).append(":")
                    .append(rO).append(")");
            return false;
        }
        return true;
    }
 
//------------------------------------------------------------------------------
 
    public static boolean compareGraphNodes(Vertex thisV,
                                            DGraph thisG,
                                            Vertex otherV,
                                            DGraph otherG) throws DENOPTIMException
    {
        Map<Vertex, Vertex> map = new HashMap<>();
        map.put(thisV, otherV);
        return compareGraphNodes(thisV, thisG, otherV, otherG, map,
                new StringBuilder());
    }
 
//------------------------------------------------------------------------------
 
    private static boolean compareGraphNodes(Vertex seedOnA,
            DGraph gA, Vertex seedOnB, DGraph gB, 
            Map<Vertex,Vertex> vertexMap, StringBuilder reason) 
                    throws DENOPTIMException
    {
        if (!seedOnA.sameAs(seedOnB, reason))
        {
            reason.append("Different vertex ("+seedOnA+":"+seedOnB+")");
            return false;
        }
 
        List<Edge> edgesFromThis = gA.getEdgesWithSrc(seedOnA);
        List<Edge> edgesFromOther = gB.getEdgesWithSrc(seedOnB);
        if (edgesFromThis.size() != edgesFromOther.size())
        {
            reason.append("Different number of edges from vertex "+seedOnA+" ("
                        +edgesFromThis.size()+":"
                        +edgesFromOther.size()+")");
            return false;
        }
 
        // pairwise correspondence between child vertices
        ArrayList<Vertex[]> pairs = new ArrayList<Vertex[]>();
 
        for (Edge et : edgesFromThis)
        {
            boolean found = false;
            Edge eo = null;
            StringBuilder innerSb = new StringBuilder();
            int otherEdgeI = 0;
            for (Edge e : edgesFromOther)
            {
                innerSb.append(" Edge"+otherEdgeI+":");
                if (et.sameAs(e,innerSb))
                {
                    found = true;
                    eo = e;
                    break;
                }
            }
            if (!found)
            {
                reason.append("Edge not found in other("+et+"). "
                        + "Edges in othes: "+innerSb.toString());
                return false;
            }
 
            //Check: this should never be true
            if (vertexMap.keySet().contains(
                    gA.getVertexWithId(et.getTrgVertex())))
            {
                throw new DENOPTIMException("More than one attempt to set vertex map.");
            }
            vertexMap.put(gA.getVertexWithId(et.getTrgVertex()),
                    gB.getVertexWithId(eo.getTrgVertex()));
 
            Vertex[] pair = new Vertex[]{
                    gA.getVertexWithId(et.getTrgVertex()),
                    gB.getVertexWithId(eo.getTrgVertex())};
            pairs.add(pair);
        }
 
        //Recursion on child vertices
        for (Vertex[] pair : pairs)
        {
            Vertex v = pair[0];
            Vertex o = pair[1];
            boolean localRes = compareGraphNodes(v, gA, o, gB,vertexMap,
                    reason);
            if (!localRes)
            {
                return false;
            }
        }
 
        return true;
    }
 
//------------------------------------------------------------------------------
 
    public boolean containsAtoms()
    {
        for (Vertex v : getVertexList())
        {
            if (v.containsAtoms())
            {
                return true;
            }
        }
        return false;
    }
 
//------------------------------------------------------------------------------
 
    public int getHeavyAtomsCount()
    {
        int n = 0;
        for (Vertex v : getVertexList())
        {
            n += v.getHeavyAtomsCount();
        }
        return n;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<AttachmentPoint> getAttachmentPoints()
    {
        ArrayList<AttachmentPoint> lstAPs =
                new ArrayList<AttachmentPoint>();
        for (Vertex v : gVertices)
        {
            lstAPs.addAll(v.getAttachmentPoints());
        }
        return lstAPs;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<AttachmentPoint> getAvailableAPs()
    {
        ArrayList<AttachmentPoint> lstFreeAPs =
                new ArrayList<AttachmentPoint>();
        for (AttachmentPoint ap : getAttachmentPoints())
        {
            if (ap.isAvailable())
            {
                lstFreeAPs.add(ap);
            }
        }
        return lstFreeAPs;
    }
    
//------------------------------------------------------------------------------
 
    public List<AttachmentPoint> getAvailableAPsThroughout()
    {
        ArrayList<AttachmentPoint> lstFreeAPs =
                new ArrayList<AttachmentPoint>();
        for (AttachmentPoint ap : getAttachmentPoints())
        {
            if (ap.isAvailableThroughout())
            {
                lstFreeAPs.add(ap);
            }
        }
        return lstFreeAPs;
    }
 
//------------------------------------------------------------------------------
 
    public AttachmentPoint getAPWithId(int id)
    {
        AttachmentPoint ap = null;
        for (AttachmentPoint apCand : getAttachmentPoints())
        {
            if (apCand.getID() == id)
            {
                ap = apCand;
                break;
            }
        }
        return ap;
    }
    
//------------------------------------------------------------------------------
    
    protected int getUniqueAPIndex()
    {
        return apCounter.getAndIncrement();
    }
 
//------------------------------------------------------------------------------
 
    public boolean graphNeedsCappingGroups(FragmentSpace fragSpace)
    {
        for (Vertex v : getVertexList()) {
            for (AttachmentPoint ap : v.getAttachmentPoints()) {
                if (ap.isAvailable()  && fragSpace.getAPClassOfCappingVertex(
                        ap.getAPClass()) !=null
                ) {
                    return true;
                }
            }
        }
        return false;
    }
 
//------------------------------------------------------------------------------
 
    public void removeCappingGroupsOn(Vertex vertex)
    {
        ArrayList<Vertex> toDel = new ArrayList<Vertex>();
        for (Vertex vtx : this.getChildVertices(vertex))
        {
            if (vtx instanceof Fragment == false)
            {
                continue;
            }
            // capping groups have fragment type 2
            if (((Fragment) vtx).getBuildingBlockType() == BBType.CAP
                    && !isVertexInRing(vtx))
            {
                toDel.add(vtx);
            }
        }
 
        for (Vertex v : toDel)
        {
            removeVertex(v);
        }
    }
 
//------------------------------------------------------------------------------
 
    public void removeCappingGroups(List<Vertex> lstVerts)
    {
        List<Long> rvids = new ArrayList<>();
        for (int i=0; i<lstVerts.size(); i++)
        {
            Vertex vtx = lstVerts.get(i);
            if (vtx instanceof Fragment == false)
            {
                continue;
            }
            
            if (((Fragment) vtx).getBuildingBlockType() == BBType.CAP
                    && !isVertexInRing(vtx))
            {
                rvids.add(vtx.getVertexId());
            }
        }
 
        // remove the vids from the vertex lst
        for (int i=0; i<rvids.size(); i++)
        {
            long vid = rvids.get(i);
            removeVertex(getVertexWithId(vid));
        }
    }
    
//------------------------------------------------------------------------------
    
    public void removeCappingGroupsFromChilds(List<Vertex> lstVerts)
    {
        for (Vertex v : lstVerts)
        {
            removeCappingGroups(getChildVertices(v));
        }
    }
    
//------------------------------------------------------------------------------
 
    public void removeCappingGroups()
    {
        removeCappingGroups(new ArrayList<Vertex>(gVertices));
    }
    
//------------------------------------------------------------------------------
 
    public void addCappingGroups(FragmentSpace fragSpace) throws DENOPTIMException
    {
        if (!fragSpace.useAPclassBasedApproach())
            return;
        addCappingGroups(new ArrayList<Vertex>(gVertices), fragSpace);
    }
    
//------------------------------------------------------------------------------
 
    public void addCappingGroups(List<Vertex> vertexAddedToThis, 
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        if (!fragSpace.useAPclassBasedApproach())
            return;
 
        for (Vertex curVertex : vertexAddedToThis)
        {
            // no capping of a capping group. Since capping groups are expected
            // to have only one AP, there should never be a capping group with 
            // a free AP.
            if (curVertex.getBuildingBlockType() == Vertex.BBType.CAP)
            {
                continue;
            }
 
            for (AttachmentPoint curDap : curVertex.getAttachmentPoints())
            {
                if (curDap.isAvailableThroughout())
                {
                    APClass apcCap = fragSpace.getAPClassOfCappingVertex(
                            curDap.getAPClass());
                    if (apcCap != null)
                    {
                        int bbIdCap = fragSpace.getCappingFragment(apcCap);
 
                        if (bbIdCap != -1)
                        {
                            Vertex capVrtx = Vertex.newVertexFromLibrary(
                                        GraphUtils.getUniqueVertexIndex(), 
                                        bbIdCap, BBType.CAP, fragSpace);
                            DGraph molGraph = curDap.getOwner()
                                    .getGraphOwner();
                            if (molGraph == null)
                                throw new Error("Cannot add capping "
                                        + "groups to a vertex that does not "
                                        + "belong to a graph.");
                            molGraph.appendVertexOnAP(curDap, capVrtx.getAP(0));
                        }
                        else
                        {
                            String msg = "Capping is required but no proper "
                                    + "capping fragment found with APCalss " 
                                    + apcCap;
                            throw new Error(msg);
                        }
                    }
                }
            }
        }
    }
    
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(int index)
            throws DENOPTIMException
    {
        return extractSubgraph(this.getVertexAtPosition(index));
    }
 
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Vertex seed)
            throws DENOPTIMException
    {
        return extractSubgraph(seed, Integer.MAX_VALUE, false);
    }
    
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Vertex seed, int numLayers, 
            boolean stopBeforeRCVs) throws DENOPTIMException
    {
        if (!this.gVertices.contains(seed))
        {
            throw new DENOPTIMException("Attempt to extract a subgraph giving "
                    + "a seed vertex that is not contained in this graph.");
        }
        DGraph subGraph = this.clone();
        Vertex seedClone = subGraph.getVertexAtPosition(
                this.indexOf(seed));
        
        ArrayList<Vertex> subGrpVrtxs = new ArrayList<Vertex>();
        subGrpVrtxs.add(seedClone);
        subGraph.getChildrenTree(seedClone, subGrpVrtxs, numLayers, stopBeforeRCVs);
        ArrayList<Vertex> toRemove = new ArrayList<Vertex>();
        for (Vertex v : subGraph.gVertices)
        {
            if (!subGrpVrtxs.contains(v))
            {
                toRemove.add(v);
            }
        }
        
        for (Vertex v : toRemove)
        {
            subGraph.removeVertex(v);
        }
        
        return subGraph;
    }
    
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Vertex seed, 
            List<Vertex> limits, boolean stopBeforeRCVs) 
                    throws DENOPTIMException
    {
        if (!this.gVertices.contains(seed))
        {
            throw new DENOPTIMException("Attempt to extract a subgraph giving "
                    + "a seed vertex that is not contained in this graph.");
        }
        
        if (limits.size()==0)
        {
            return extractSubgraph(seed, stopBeforeRCVs);
        }
        
        DGraph subGraph = this.clone();
        Vertex seedClone = subGraph.getVertexAtPosition(
                this.indexOf(seed));
        
        List<Vertex> limitsInClone =  new ArrayList<Vertex>();
        for (Vertex v : limits)
            limitsInClone.add(subGraph.getVertexAtPosition(this.indexOf(v)));
        
        ArrayList<Vertex> subGrpVrtxs = new ArrayList<Vertex>();
        subGrpVrtxs.add(seedClone);
        subGraph.getChildTreeLimited(seedClone, subGrpVrtxs, limitsInClone, 
                stopBeforeRCVs);
        
        ArrayList<Vertex> toRemove = new ArrayList<Vertex>();
        for (Vertex v : subGraph.gVertices)
        {
            if (!subGrpVrtxs.contains(v))
            {
                toRemove.add(v);
            }
        }
        for (Vertex v : toRemove)
        {
            subGraph.removeVertex(v);
        }
        
        return subGraph;
    }
    
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Vertex seed, boolean stopBeforeRCVs) 
                    throws DENOPTIMException
    {
        if (!this.gVertices.contains(seed))
        {
            throw new DENOPTIMException("Attempt to extract a subgraph giving "
                    + "a seed vertex that is not contained in this graph.");
        }
        
        DGraph subGraph = this.clone();
        Vertex seedClone = subGraph.getVertexAtPosition(
                this.indexOf(seed));
        
        ArrayList<Vertex> subGrpVrtxs = new ArrayList<Vertex>();
        subGrpVrtxs.add(seedClone);
        subGraph.getChildTreeLimited(seedClone, subGrpVrtxs, stopBeforeRCVs);
        
        ArrayList<Vertex> toRemove = new ArrayList<Vertex>();
        for (Vertex v : subGraph.gVertices)
        {
            if (!subGrpVrtxs.contains(v))
            {
                toRemove.add(v);
            }
        }
        for (Vertex v : toRemove)
        {
            subGraph.removeVertex(v);
        }
        
        return subGraph;
    }
  
//------------------------------------------------------------------------------
 
    public List<DGraph> extractPattern(GraphPattern pattern) 
            throws DENOPTIMException 
    {
        return extractPattern(pattern, false).keySet().stream().collect(
                Collectors.toList());
    }
    
//------------------------------------------------------------------------------
 
    public Map<DGraph,ObjectPair> extractPattern(GraphPattern pattern, 
            boolean recordConnectivity) throws DENOPTIMException 
    {
        if (pattern != GraphPattern.RING) {
            throw new IllegalArgumentException("Graph pattern " + pattern +
                    " not supported.");
        }
 
        List<Set<Vertex>> disjointMultiCycleVertices = this
                  .getRings()
                  .stream()
                  .map(Ring::getVertices)
                  .map(HashSet::new)
                  .collect(Collectors.toList());
 
        GeneralUtils.unionOfIntersectingSets(disjointMultiCycleVertices);
 
        Map<DGraph,ObjectPair> subGraphsAndConnections = new LinkedHashMap<>();
        for (Set<Vertex> fusedRing : disjointMultiCycleVertices) {
            if (recordConnectivity)
            {
                Set<Edge> connectionToSubgraph = new HashSet<Edge>();
                Set<Edge> connectionFromSubgraph = new HashSet<Edge>();
                DGraph subGraph = extractSubgraph(fusedRing, connectionToSubgraph, 
                        connectionFromSubgraph);
                ObjectPair connections = new ObjectPair(connectionToSubgraph, 
                        connectionFromSubgraph);
                subGraphsAndConnections.put(subGraph, connections);
            } else {
                DGraph subGraph = extractSubgraph(fusedRing);
                subGraphsAndConnections.put(subGraph, null);
            }
        }
          
        for (DGraph g : subGraphsAndConnections.keySet()) {
            g.storeCurrentVertexIDs();
            g.renumberGraphVertices();
            reorderVertexList(g);
        }
 
        return subGraphsAndConnections;
    }
 
  //------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Collection<Vertex> definedOn) 
    {
        DGraph subgraph = extractSubgraph(definedOn, null, null);
        return subgraph;
    }
    
//------------------------------------------------------------------------------
 
    public DGraph extractSubgraph(Collection<Vertex> definedOn, 
            Set<Edge> connectionToSubgraph, 
            Set<Edge> connectionFromSubgraph) 
    {
        
        DGraph subgraph = this.clone();
 
        Set<Vertex> complement = subgraph
                .getVertexList()
                .stream()
                .filter(u -> definedOn
                        .stream()
                        .allMatch(v -> v.getVertexId() != u.getVertexId())
                ).collect(Collectors.toSet());
        
        Set<Long> vrtxIDsInComplement = complement.stream()
                .map(v -> v.getVertexId())
                .collect(Collectors.toSet());
        
        if (connectionToSubgraph!=null && connectionFromSubgraph!=null)
        {
            for (Vertex v : definedOn) 
            {
                for (Edge e : this.getEdgeList())
                {
                    if (e.getSrcAP().getOwner() == v && 
                            vrtxIDsInComplement.contains(e.getTrgVertex()))
                    {
                        connectionFromSubgraph.add(e);
                    }
                    
                    if (e.getTrgAP().getOwner() == v && 
                            vrtxIDsInComplement.contains(e.getSrcVertex()))
                    {
                        connectionToSubgraph.add(e);
                    }
                }
            }
        }
        
        for (Vertex v : complement) {
            subgraph.removeVertex(v);
        }
        
        return subgraph;
    }
 
//------------------------------------------------------------------------------
    
    public DGraph embedPatternsInTemplates(GraphPattern pattern, 
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        return embedPatternsInTemplates(pattern, fragSpace, ContractLevel.FREE);
    }
    
//------------------------------------------------------------------------------
    
    public DGraph embedPatternsInTemplates(GraphPattern pattern, 
            FragmentSpace fragSpace, ContractLevel contract) 
                    throws DENOPTIMException
    {
        // We will return a modified clone of this graph
        DGraph graph = this.clone();
        // We use IDs to find the mapping of APs between cloned graphs. So, must
        // ensure the IDs of APs are unique within the graph.
        graph.ensureUniqueApIDs();
        
        // Identify the subgraphs to be replaced by templates
        Map<DGraph,ObjectPair> subGraphsAndLinks = graph.extractPattern(
                pattern, true);
        
        // Replace the subgraphs with the templates
        for (Map.Entry<DGraph,ObjectPair> entry : subGraphsAndLinks.entrySet())
        {
            // WARNING: while the subgraph is a clone of 'graph', the sets
            // contain referenced to the edges of 'graph'.
            DGraph subGraph = entry.getKey();
            
            // Make template
            BBType tmplType = subGraph.hasScaffoldTypeVertex() ? 
                    BBType.SCAFFOLD :
                        BBType.FRAGMENT;
            Template tmpl = new Template(tmplType);
            tmpl.setInnerGraph(subGraph);
            tmpl.setContractLevel(contract);
 
            // Recover info on which APs of the original subgraph (i.e., APs in
            // 'graph') correspond to APs on the template.
            LinkedHashMap<AttachmentPoint, AttachmentPoint> apMapOrigToTmpl = 
                    new LinkedHashMap<AttachmentPoint, AttachmentPoint>();
            @SuppressWarnings("unchecked")
            Set<Edge> edsToSubgrph = (Set<Edge>) entry.getValue().getFirst();
            for (Edge e : edsToSubgrph)
            {
                AttachmentPoint apOnOrig = e.getTrgAP();
                AttachmentPoint apOnTmpl = tmpl.getOuterAPFromInnerAP(
                       subGraph.getAPWithId(apOnOrig.getID()));
                apMapOrigToTmpl.put(apOnOrig, apOnTmpl);
            }
            @SuppressWarnings("unchecked")
            Set<Edge> edsFromSubGrph = (Set<Edge>) entry.getValue().getSecond();
            for (Edge e : edsFromSubGrph)
            {
                AttachmentPoint apOnOrig = e.getSrcAP();
                AttachmentPoint apOnTmpl = tmpl.getOuterAPFromInnerAP(
                        subGraph.getAPWithId(apOnOrig.getID()));
                apMapOrigToTmpl.put(apOnOrig, apOnTmpl);
            }
            
            // Identify the vertexes in the subgraph replaced by the template
            List<Vertex> toReplaceByTemplate = new ArrayList<>();
            for (Vertex embeddedVrtx : subGraph.gVertices)
            {
                long vIdInThis = (long) embeddedVrtx.getProperty(
                        DENOPTIMConstants.STOREDVID);
                toReplaceByTemplate.add(graph.getVertexWithId(vIdInThis));
            }
            
            // Do the actual replacement of original subgraph with the template
            DGraph singleVertedGraph = new DGraph();
            singleVertedGraph.addVertex(tmpl);
            graph.replaceSubGraph(toReplaceByTemplate, singleVertedGraph, 
                    apMapOrigToTmpl, fragSpace);
        }
        
        return graph;
    }
    
//------------------------------------------------------------------------------
 
      private static void reorderVertexList(DGraph g) 
      {
          Vertex newScaffold = g.getSourceVertex();
          if (newScaffold == null) {
              return;
          }
          DGraph.setScaffold(newScaffold);
          fixEdgeDirections(g);
      }
 
//------------------------------------------------------------------------------
 
    private static void fixEdgeDirections(DGraph graph) 
    {
        Vertex src = graph.getSourceVertex();
        fixEdgeDirections(src, new HashSet<>());
    }
 
//------------------------------------------------------------------------------
 
    private static void fixEdgeDirections(Vertex v, 
            Set<Long> visited) 
    {
        visited.add(v.getVertexId());
        int visitedVertexEncounters = 0;
        for (int i = 0; i < v.getNumberOfAPs(); i++) {
            AttachmentPoint ap = v.getAP(i);
            Edge edge = ap.getEdgeUser();
            if (edge != null) {
                long srcVertex = edge.getSrcVertex();
                boolean srcIsVisited = srcVertex != v.getVertexId() 
                        && visited.contains(srcVertex);
 
                visitedVertexEncounters += srcIsVisited ? 1 : 0;
                if (visitedVertexEncounters >= 2) {
                    throw new IllegalArgumentException("Invalid graph. "
                            + "Contains a cycle.");
                }
 
                boolean edgeIsWrongWay = edge.getTrgVertex() 
                        == v.getVertexId() && !srcIsVisited;
                if (edgeIsWrongWay) {
                    edge.flipEdge();
                }
                if (!srcIsVisited) {
                    fixEdgeDirections(edge.getTrgAP().getOwner(), visited);
                }
            }
        }
    }
 
//------------------------------------------------------------------------------
 
    public boolean removeBranchStartingAt(Vertex v, boolean symmetry)
            throws DENOPTIMException
    {
        boolean res = true;
        if (hasSymmetryInvolvingVertex(v) && symmetry)
        {
            for (Vertex sv : getSymSetForVertex(v))
            {
                boolean res2 = removeBranchStartingAt(sv);
                if (!res2)
                {
                    res = res2;
                }
            }
        }
        else
        {
            res = removeBranchStartingAt(v);
        }
        return res;
    }
    
//------------------------------------------------------------------------------
 
    public boolean removeBranchStartingAt(Vertex v)
            throws DENOPTIMException
    {
        Edge edgeToParent = v.getEdgeToParent();
        if (edgeToParent != null)
        {
            removeEdge(edgeToParent);
        }
        return removeOrphanBranchStartingAt(v);
    }
 
//------------------------------------------------------------------------------
 
    public boolean removeOrphanBranchStartingAt(Vertex v)
            throws DENOPTIMException
    {
        // now get the vertices attached to v
        ArrayList<Vertex> children = new ArrayList<Vertex>();
        getChildrenTree(v, children);
 
        // delete the children vertices and associated edges
        for (Vertex c : children) {
            removeVertex(c);
        }
 
        // finally delete the vertex and associated edges
        removeVertex(v);
 
        return getVertexWithId(v.getVertexId()) == null;
    }
    
//------------------------------------------------------------------------------
    
    public boolean removeChainUpToBranching(Vertex v, 
            FragmentSpace fragSpace) throws DENOPTIMException
    {
        List<Ring> rings = getRingsInvolvingVertex(v);
        if (rings.isEmpty())
        {
            return false;
        }
        
        // Identify the RCVs defining the chord that might become an edge
        // The corresponding ring is the "frame" we'll use throughout this 
        // operation, and is the smallest ring that is closest to the appointed
        // vertex.
        Ring frame = null;
        Vertex[] replacedByEdge = new Vertex[2];
        int minDist = Integer.MAX_VALUE;
        BondType bt = null;
        for (Ring r : rings)
        {
            int dist = Math.min(r.getDistance(r.getHeadVertex(),v),
                    r.getDistance(r.getTailVertex(),v));
            if (dist < minDist)
            {
                minDist = dist;
                frame = r;
                replacedByEdge[0] = r.getHeadVertex();
                replacedByEdge[1] = r.getTailVertex();
                bt = r.getBondType();
            }
        }
        
        // Find out where branching vertices are along the frame ring
        boolean frameHasBranching = false;
        List<Integer> branchingPositions = new ArrayList<Integer>();
        int posOfFocusVrtInRing = frame.getPositionOf(v);
        for (int i=0; i<frame.getSize(); i++)
        {
            Vertex vi = frame.getVertexAtPosition(i);
            // We consider the scaffold as a branching point, i.e., it will never be removed
            if (vi.getBuildingBlockType() == BBType.SCAFFOLD)
            {
                branchingPositions.add(i);
                continue;
            }
            long oNonCap = vi.getAttachmentPoints().size() 
                    - vi.getCappedAPCountThroughout()
                    - vi.getFreeAPCountThroughout();
            if (oNonCap > 2)
            {
                branchingPositions.add(i);
                frameHasBranching = true;
            }
        }
        
        // Make sure this ring is not all there is in this graph.
        if (rings.size()==1 && !frameHasBranching) 
        {
            return false;
        }
        
        // Identify the end points of chain that gets removed, i.e., the chain
        // containing V and is between branchingDownstreamId and 
        // branchingUpstreamId gets removed.
        int branchingDownstreamId = -1;
        for (int i=0; i<frame.getSize(); i++)
        {
            int iTranslated = i + posOfFocusVrtInRing;
            if (iTranslated >= frame.getSize())
                iTranslated = iTranslated - frame.getSize();
            if (branchingPositions.contains(iTranslated))
            {
                branchingDownstreamId = iTranslated;
                break;
            }
        }
        int branchingUpstreamId = -1;
        for (int i=(frame.getSize()-1); i>-1; i--)
        {
            int iTranslated = i + posOfFocusVrtInRing;
            if (iTranslated >= frame.getSize())
                iTranslated = iTranslated - frame.getSize();
            if (branchingPositions.contains(iTranslated))
            {
                branchingUpstreamId = iTranslated;
                break;
            }
        }
        
        // Now, collect the vertices along the ring based on whether they
        // will be removed or remain (possible with a change of edge direction
        // and replacement of an RCV pair by edge)
        List<Vertex> remainingChain = new ArrayList<Vertex>();
        for (int i=0; i<frame.getSize(); i++)
        {
            int iTranslated = i + branchingDownstreamId;
            if (iTranslated >= frame.getSize())
                iTranslated = iTranslated - frame.getSize();
            remainingChain.add(frame.getVertexAtPosition(iTranslated));
            if (iTranslated == branchingUpstreamId)
            {
                break;
            }
        }
        List<Vertex> toRemoveChain = new ArrayList<Vertex>();
        for (int i=0; i<frame.getSize(); i++)
        {
            int iTranslated = i + branchingUpstreamId + 1; //exclude branch point
            if (iTranslated >= frame.getSize())
                iTranslated = iTranslated - frame.getSize();
            toRemoveChain.add(frame.getVertexAtPosition(iTranslated));
            if (iTranslated == (branchingDownstreamId - 1)) //exclude branch point
            {
                break;
            }
        }
        
        // Need to exclude the case where the chain to remove consists only of
        // the RCVs because it would lead to loss of the chord and creation of
        // cyclic graph. Also, proceeding without making the edge would simply
        // correspond to removing the chord.
        if (toRemoveChain.size() == 2)
        {
            int countOrRCVs = 0;
            for (Vertex vtr : toRemoveChain)
            {
                if (vtr.isRCV())
                    countOrRCVs++;
            }
            if (countOrRCVs == 2)
            {
                return false;
            }
        }
        
        // To understand if we need to reverse some edges, we identify the
        // deepest vertex level-wise. It may or may not be a scaffold!!!
        int deepestLevel = Integer.MAX_VALUE;
        Vertex deepestVrtRemainingChain = null;
        for (Vertex vint : remainingChain)
        {
            int lvl = getLevel(vint);
            if (lvl < deepestLevel)
            {
                deepestLevel = lvl;
                deepestVrtRemainingChain = vint;
            }
        }
        
        // Check if we need to transform a pair of RCVs into an edge, and 
        // identify APs used by the edge that replaces the to-be-removed RCVs.
        // I do not see how the chain can possibly contain only one of the 
        // RCVs, so I assume that if one RCV is there, then the other is too.
        if (remainingChain.contains(replacedByEdge[0]))
        {
            AttachmentPoint apSrcOfNewEdge = replacedByEdge[0]
                    .getEdgeToParent().getSrcAP();
            AttachmentPoint apTrgOfNewEdge = replacedByEdge[1]
                    .getEdgeToParent().getSrcAP();
            
            // Remove the RCVs that will be replaced by an edge
            removeVertex(replacedByEdge[0]);
            remainingChain.remove(replacedByEdge[0]);
            removeVertex(replacedByEdge[1]);
            remainingChain.remove(replacedByEdge[1]);
            
            // And make the new edge. The direction can be anything. Later, we
            // decide if we need to reverse it.
            //NB: the compatibility between the APs should be granted by the 
            // previous existence of the chord. so no need to check 
            // apSrcOfNewEdge.getAPClass().isCPMapCompatibleWith(
            //        apTrgOfNewEdge.getAPClass()))
            addEdge(new Edge(apSrcOfNewEdge, apTrgOfNewEdge, bt));
        } else {
            // We remove the frame already, otherwise we will try to recreate 
            // such ring from RCVs and waste time with it.
            removeRing(frame);
        }
        
        // Now, inspect the paths from the deepest vertex and outwards, to
        // find out where to start reversing edges.
        List<Vertex> chainToReverseA = new ArrayList<Vertex>();
        List<Vertex> chainToReverseB = new ArrayList<Vertex>();
        for (int i=(remainingChain.indexOf(deepestVrtRemainingChain)+1); 
                i<remainingChain.size(); i++)
        {
            Vertex vPrev = remainingChain.get(i-1);
            Vertex vHere = remainingChain.get(i);
            if (!vPrev.getChilddren().contains(vHere))
            {
                // in an healthy spanning tree, once we find the first reversed
                // edge, all the following edges will also have to be reversed.
                if (chainToReverseA.size()==0)
                    chainToReverseA.add(vPrev);
                chainToReverseA.add(vHere);
            }
        }
        for (int i=(remainingChain.indexOf(deepestVrtRemainingChain)-1);i>-1;i--)
        {
            Vertex vPrev = remainingChain.get(i+1);
            Vertex vHere = remainingChain.get(i);
            if (!vPrev.getChilddren().contains(vHere))
            {
                if (chainToReverseB.size()==0)
                    chainToReverseB.add(vPrev);
                chainToReverseB.add(vHere);
            }
        }
        
        // These are to remember all chords that will have to be recreated
        LinkedHashMap<Vertex,Vertex> chordsToRecreate = 
                new LinkedHashMap<Vertex,Vertex>();
        LinkedHashMap<Vertex,BondType> chordsToRecreateBB = 
                new LinkedHashMap<Vertex,BondType>();
        
        // Change direction of those edges that have to be reversed as a 
        // consequence of the change in the spanning tree.
        if (chainToReverseA.size()+chainToReverseB.size() > 1)
        {
            List<Vertex> chainToWorkOn = null;
            for (int ic=0; ic<2; ic++)
            {
                if (ic == 1)
                    chainToWorkOn = chainToReverseA;
                else
                    chainToWorkOn = chainToReverseB;
            
                for (int i=1; i<chainToWorkOn.size(); i++)
                {
                    Vertex vHere = chainToWorkOn.get(i);
                    Vertex vPrev = chainToWorkOn.get(i-1);
                    List<Ring> ringsToRecreate = new ArrayList<>();
                    for (Ring r : getRingsInvolvingVertex(vHere))
                    {
                        ringsToRecreate.add(r);
                        chordsToRecreate.put(r.getHeadVertex(), 
                                r.getTailVertex());
                        chordsToRecreateBB.put(r.getHeadVertex(), 
                                r.getBondType());
                    }
                    for (Ring r : ringsToRecreate)
                    {
                        removeRing(r);
                    }
                    
                    Edge edgeToPrevious = vHere.getEdgeWith(vPrev);
                    if (edgeToPrevious == null) 
                    {
                        // Since we have already made the new edge this should 
                        // never happen.
                        String debugFile = "debug_"+v.getVertexId()+".json";
                        DenoptimIO.writeGraphToJSON(new File(debugFile), this);
                        throw new DENOPTIMException("Unconnected vertices "  
                                + vHere.getVertexId() + " and "
                                + vPrev.getVertexId() + ". Unable to deal with "
                                + "removal of " + v + " from ring " + frame 
                                + " in graph " + this.getGraphId() 
                                + ". See graph in " + debugFile);
                    } else {
                        if (edgeToPrevious.getSrcAP().getOwner() == vHere) 
                        {
                            // This is an edge that has to be reversed.
                            AttachmentPoint newSrcAP = 
                                    edgeToPrevious.getTrgAP();
                            AttachmentPoint newTrgAP = 
                                    edgeToPrevious.getSrcAP();
                            if (newSrcAP.getAPClass().isCPMapCompatibleWith(
                                    newTrgAP.getAPClass(), fragSpace))
                            {
                                BondType oldBt = edgeToPrevious.getBondType();
                                removeEdge(edgeToPrevious);
                                addEdge(new Edge(newSrcAP, newTrgAP, 
                                        oldBt));
                            } else {
                                // There is a non-reversible connection along 
                                // the way, therefore we cannot do this 
                                // specific mutation.
                                return false;
                            }
                        }
                    }
                }
            }
        }
           
        // Delete the chain to be removed
        for (Vertex vtr : toRemoveChain) 
        {
            // This works across template boundaries!
            for (Vertex child : vtr.getChildrenThroughout())
            {
                if (remainingChain.contains(child)
                        || toRemoveChain.contains(child))
                    continue;
                DGraph ownerOfChild = child.getGraphOwner();
                ownerOfChild.removeVertex(child);
            }
            if (templateJacket!= null)
            {
                List<AttachmentPoint> apProjectionsToRemove = 
                        new ArrayList<AttachmentPoint>();
                for (AttachmentPoint outerAP : 
                    templateJacket.getAttachmentPoints())
                {
                    AttachmentPoint innerAP = 
                            templateJacket.getInnerAPFromOuterAP(outerAP);
                    if (innerAP.getOwner() == vtr)
                    {
                        apProjectionsToRemove.add(innerAP);
                    }
                }
                for (AttachmentPoint apToRemove : apProjectionsToRemove)
                    templateJacket.removeProjectionOfInnerAP(apToRemove);
            }
            removeVertex(vtr);
        }
        
        // Regenerate the rings that have been affected
        for (Vertex h : chordsToRecreate.keySet())
        {
            addRing(h, chordsToRecreate.get(h), chordsToRecreateBB.get(h));
        }
        
        // Symmetry relation need to be compared with the change of topology.
        // The worst that can happen is that two vertices that are
        // listed as symmetric are, instead, one the (grand)parent of 
        // the other. This is inconsistent with the expectations when
        // dealing with any operation with symmetric vertices.
        // A different level does NOT imply a parent-child relation,
        // but is a sign that the topology has changed substantially,
        // and that the symmetric relation is, most likely, not sensible
        // anymore.
        List<SymmetricVertexes> ssToRemove = new ArrayList<SymmetricVertexes>();
        Iterator<SymmetricVertexes> ssIter = getSymSetsIterator();
        while (ssIter.hasNext())
        {
            SymmetricVertexes ss = ssIter.next();
            int level = -2;
            for (Vertex vrt : ss)
            {
                if (level==-2)
                {
                    level = getLevel(vrt);
                } else {
                    if (level != getLevel(vrt))
                    {
                        ssToRemove.add(ss);
                        break;
                    }
                }
            }
        }
        for (SymmetricVertexes ss : ssToRemove)
            removeSymmetrySet(ss);
        
        // The free-ed up APs need to be projected to template's surface
        if (templateJacket!= null)
        {
            for (AttachmentPoint innerAP : getAvailableAPs())
            {
                templateJacket.addInnerToOuterAPMapping(innerAP);
            }
        }
        
        return true;
    }
 
//------------------------------------------------------------------------------
 
    @Deprecated
    public void changeSignOfVertexID()
    {
        HashMap<Long, Long> nmap = new HashMap<>();
        for (int i=0; i<getVertexCount(); i++)
        {
            long vid = getVertexList().get(i).getVertexId();
            long nvid = -vid;
            nmap.put(vid, nvid);
 
            getVertexList().get(i).setVertexId(nvid);
 
            for (int j=0; j<getEdgeCount(); j++)
            {
                Edge e = getEdgeList().get(j);
                if (e.getSrcVertex() == vid) {
                    e.getSrcAP().getOwner().setVertexId(nvid);
                }
                if (e.getTrgVertex() == vid) {
                    e.getTrgAP().getOwner().setVertexId(nvid);
                }
            }
        }
    }
 
//------------------------------------------------------------------------------
 
    public void renumberGraphVertices()
    {
        renumberVerticesGetMap();
    }
 
//------------------------------------------------------------------------------
 
    public Map<Long,Long> renumberVerticesGetMap()
    {
        Map<Long, Long> nmap = new HashMap<>();
 
        // for the vertices in the graph, get new vertex ids
        for (int i=0; i<getVertexCount(); i++)
        {
            Vertex v = getVertexList().get(i);
            long vid = v.getVertexId();
            long nvid = GraphUtils.getUniqueVertexIndex();
 
            nmap.put(vid, nvid);
 
            v.setVertexId(nvid);
            v.setProperty(DENOPTIMConstants.STOREDVID, vid);
        }
        
        return nmap;
    }
    
//------------------------------------------------------------------------------
    
    public int getLevel(Vertex v)
    {
        ArrayList<Vertex> parentTree = new ArrayList<>();
        getParentTree(v,parentTree);
        return parentTree.size() - 1;
    }
 
//------------------------------------------------------------------------------
 
    public Object[] checkConsistency(RunTimeParameters settings)
            throws DENOPTIMException
    {
        return checkConsistency(settings, false);
    }
    
//------------------------------------------------------------------------------
 
    public Object[] checkConsistency(RunTimeParameters settings, boolean permissive)
            throws DENOPTIMException
    {
        RingClosureParameters rcSettings = new RingClosureParameters();
        if (settings.containsParameters(ParametersType.RC_PARAMS))
        {
            rcSettings = (RingClosureParameters)settings.getParameters(
                    ParametersType.RC_PARAMS);
        }
        FragmentSpaceParameters fsSettings = new FragmentSpaceParameters();
        if (settings.containsParameters(ParametersType.FS_PARAMS))
        {
            fsSettings = (FragmentSpaceParameters)settings.getParameters(
                    ParametersType.FS_PARAMS);
        }
        
        // calculate the molecule representation
        ThreeDimTreeBuilder t3d = new ThreeDimTreeBuilder(settings.getLogger(),
                settings.getRandomizer());
        t3d.setAlignBBsIn3D(false);
        IAtomContainer mol = t3d.convertGraphTo3DAtomContainer(this,true);
        if (mol == null)
        {
            String msg ="Evaluation of graph: graph-to-mol returned null!"
                    + toString();
            settings.getLogger().log(Level.FINE, msg);
            return null;
        }
 
        // check if the molecule is connected
        boolean isConnected = ConnectivityChecker.isConnected(mol);
        if (!isConnected)
        {
            String msg = "Evaluation of graph: Not all connected"
                    + toString();
            settings.getLogger().log(Level.FINE, msg);
            return null;
        }
 
        // SMILES
        String smiles = null;
        smiles = MoleculeUtils.getSMILESForMolecule(mol,settings.getLogger());
        if (smiles == null)
        {
            String msg = "Evaluation of graph: SMILES is null! "
                    + toString();
            settings.getLogger().log(Level.FINE, msg);
            smiles = "FAIL: NO SMILES GENERATED";
        }
        // if by chance the smiles indicates a disconnected molecule
        if (smiles.contains(".") && !permissive)
        {
            String msg = "Evaluation of graph: SMILES contains \".\"" + smiles;
            settings.getLogger().log(Level.FINE, msg);
            return null;
        }
 
        // criteria from definition of Fragment space
        // 1A) number of heavy atoms
        if (fsSettings.getMaxHeavyAtom()>0 && !permissive)
        {
            if (MoleculeUtils.getHeavyAtomCount(mol) >
                fsSettings.getMaxHeavyAtom())
            {
                String msg = "Evaluation of graph: Max atoms constraint "
                        + " violated: " + smiles;
                settings.getLogger().log(Level.FINE, msg);
                return null;
            }
        }
 
        // 1B) molecular weight
        double mw = MoleculeUtils.getMolecularWeight(mol);
        if (fsSettings.getMaxMW()>0 && !permissive)
        {
            if (mw > fsSettings.getMaxMW())
            {
                String msg = "Evaluation of graph: Molecular weight "
                        + "constraint violated: " + smiles + " | MW: " + mw;
                settings.getLogger().log(Level.FINE, msg);
                return null;
            }
        }
        mol.setProperty("MOL_WT", mw);
 
        // 1C) number of rotatable bonds
        int nrot = MoleculeUtils.getNumberOfRotatableBonds(mol);
        if (fsSettings.getMaxRotatableBond()>0 && !permissive)
        {
            if (nrot > fsSettings.getMaxRotatableBond())
            {
                String msg = "Evaluation of graph: Max rotatable bonds "
                        + "constraint violated: "+ smiles;
                settings.getLogger().log(Level.FINE, msg);
                return null;
            }
        }
        mol.setProperty("ROT_BND", nrot);
 
        // 1D) unacceptable free APs
        if (fsSettings.getFragmentSpace().useAPclassBasedApproach())
        {
            if (hasForbiddenEnd(fsSettings))
            {
                String msg = "Evaluation of graph: forbidden end in graph!";
                settings.getLogger().log(Level.FINE, msg);
                return null;
            }
        }
 
        // criteria from settings of ring closures
        if (rcSettings.allowRingClosures() && !permissive)
        {
            // Count rings and RCAs
            int nPossRings = 0;
            Set<String> doneType = new HashSet<>();
            Map<String,String> rcaTypes = RingClosingAttractor.RCATYPEMAP;
            for (String rcaTyp : rcaTypes.keySet())
            {
                if (doneType.contains(rcaTyp))
                {
                    continue;
                }
 
                int nThisType = 0;
                int nCompType = 0;
                for (Vertex v : getRCVertices())
                {
                    if (v.containsAtoms())
                    {
                        IAtom atm = v.getIAtomContainer().getAtom(0);
                        if (MoleculeUtils.getSymbolOrLabel(atm).equals(rcaTyp))
                        {
                            nThisType++;
                        } else if (MoleculeUtils.getSymbolOrLabel(atm).equals(
                                rcaTypes.get(rcaTyp)))
                        {
                            nCompType++;
                        } 
                        if (rcaTyp.equals(rcaTypes.get(rcaTyp)))
                        {
                            nCompType++;
                        }
                    }
                }
 
                // check number of rca per type
                if (nThisType > rcSettings.getMaxRcaPerType(rcaTyp) ||
                        nCompType > rcSettings.getMaxRcaPerType(rcaTyp))
                {
                    String msg = "Evaluation of graph: too many RCAs! "
                            + rcaTyp + ":" + nThisType + " "
                            + rcaTypes.get(rcaTyp) + ":" + nCompType;
                    settings.getLogger().log(Level.FINE, msg);
                    return null;
                }
                if (nThisType < rcSettings.getMinRcaPerType(rcaTyp) ||
                        nCompType < rcSettings.getMinRcaPerType(rcaTyp))
                {
                    String msg = "Evaluation of graph: too few RCAs! "
                            + rcaTyp + ":" + nThisType + " "
                            + rcaTypes.get(rcaTyp) + ":" + nCompType;
                    settings.getLogger().log(Level.FINE, msg);
                    return null;
                }
 
                nPossRings = nPossRings + Math.min(nThisType, nCompType);
                doneType.add(rcaTyp);
                doneType.add(rcaTypes.get(rcaTyp));
            }
            if (nPossRings < rcSettings.getMinRingClosures())
            {
                String msg = "Evaluation of graph: too few ring candidates";
                settings.getLogger().log(Level.FINE, msg);
                return null;
            }
        }
 
        // get the smiles/Inchi representation
        String inchiKey = MoleculeUtils.getInChIKeyForMolecule(mol, 
                settings.getLogger());
        if (inchiKey == null)
        {
            String msg = "Evaluation of graph: InChI Key is null!";
            settings.getLogger().log(Level.WARNING, msg);
            inchiKey = "UNDEFINED_INCHI";
        }
 
        Object[] res = new Object[3];
        res[0] = inchiKey; 
        res[1] = smiles; 
        res[2] = mol;
 
        return res;
    }
 
//------------------------------------------------------------------------------
 
    public ArrayList<DGraph> makeAllGraphsWithDifferentRingSets(
            RunTimeParameters settings)
            throws DENOPTIMException 
    {
        RingClosureParameters rcSettings = new RingClosureParameters();
        if (settings.containsParameters(ParametersType.RC_PARAMS))
        {
            rcSettings = (RingClosureParameters)settings.getParameters(
                    ParametersType.RC_PARAMS);
        }
        FragmentSpaceParameters fsSettings = new FragmentSpaceParameters();
        if (settings.containsParameters(ParametersType.FS_PARAMS))
        {
            fsSettings = (FragmentSpaceParameters)settings.getParameters(
                    ParametersType.FS_PARAMS);
        }
        ArrayList<DGraph> lstGraphs = new ArrayList<>();
 
        boolean rcnEnabled = fsSettings.getFragmentSpace()
                .useAPclassBasedApproach();
        if (!rcnEnabled)
            return lstGraphs;
 
        boolean evaluateRings = rcSettings.allowRingClosures();
        if (!evaluateRings)
            return lstGraphs;
 
        // get a atoms/bonds molecular representation (no 3D needed)
        ThreeDimTreeBuilder t3d = new ThreeDimTreeBuilder(settings.getLogger(),
                settings.getRandomizer());
        t3d.setAlignBBsIn3D(false);
        IAtomContainer mol = t3d.convertGraphTo3DAtomContainer(this,false);
 
        // Set rotatable property as property of IBond
        RotationalSpaceUtils.defineRotatableBonds(mol,
                fsSettings.getRotSpaceDefFile(), true, true,
                settings.getLogger());
 
        // get the set of possible RCA combinations = ring closures
        CyclicGraphHandler cgh = new CyclicGraphHandler(rcSettings,
                fsSettings.getFragmentSpace());
        ArrayList<List<Ring>> allCombsOfRings =
                cgh.getPossibleCombinationOfRings(mol, this);
 
        // Keep closable chains that are relevant for chelate formation
        if (rcSettings.buildChelatesMode())
        {
            ArrayList<List<Ring>> toRemove = new ArrayList<>();
            for (List<Ring> setRings : allCombsOfRings)
            {
                if (!cgh.checkChelatesGraph(this,setRings))
                {
                    toRemove.add(setRings);
                }
            }
            allCombsOfRings.removeAll(toRemove);
        }
 
        // prepare output graphs
        for (List<Ring> ringSet : allCombsOfRings)
        {
            // clone root graph
            DGraph newGraph = this.clone();
 
            Map<Long,Long> vRenum = newGraph.renumberVerticesGetMap();
            newGraph.setGraphId(GraphUtils.getUniqueGraphIndex());
 
            // add rings
            for (Ring oldRing : ringSet)
            {
                Ring newRing = new Ring();
                for (int i=0; i<oldRing.getSize(); i++)
                {
                    long oldVId = oldRing.getVertexAtPosition(i).getVertexId();
                    long newVId = vRenum.get(oldVId);
                    newRing.addVertex(newGraph.getVertexWithId(newVId));
                }
                newRing.setBondType(oldRing.getBondType());
                newGraph.addRing(newRing);
            }
 
            // store
            lstGraphs.add(newGraph);
        }
 
        return lstGraphs;
    }
 
//------------------------------------------------------------------------------
 
    public boolean hasForbiddenEnd(FragmentSpaceParameters fsSettings)
    {
        List<Vertex> vertices = getVertexList();
        Set<APClass> classOfForbEnds = 
                fsSettings.getFragmentSpace().getForbiddenEndList();
        boolean found = false;
        for (Vertex vtx : vertices)
        {
            List<AttachmentPoint> daps = vtx.getAttachmentPoints();
            for (AttachmentPoint dp : daps)
            {
                if (dp.isAvailable())
                {
                    APClass apClass = dp.getAPClass();
                    if (classOfForbEnds.contains(apClass))
                    {
                        found = true;
                        String msg = "Forbidden free AP for Vertex: "
                                + vtx.getVertexId() + " "
                                + vtx.toString()
                                + "\n"+ this +" \n "
                                + " AP class: " + apClass;
                        fsSettings.getLogger().log(Level.WARNING, msg);
                        break;
                    }
                }
            }
            if (found)
            {
                break;
            }
        }
 
        return found;
    }
 
//------------------------------------------------------------------------------
 
    public void appendGraphOnGraph(List<Vertex> parentVertices,
                                   List<Integer> parentAPIdx,
                                   DGraph subGraph,
                                   Vertex childVertex, int childAPIdx,
                                   BondType bndType, boolean onAllSymmAPs) 
                                           throws DENOPTIMException
    {
        // Collector for symmetries created by appending copies of subGraph
        Map<Vertex, SymmetricVertexes> newSymSets = new HashMap<>();
 
        // Repeat append for each parent vertex while collecting symmetries
        for (int i=0; i<parentVertices.size(); i++)
        {
            appendGraphOnGraph(parentVertices.get(i), parentAPIdx.get(i),
                    subGraph, childVertex, childAPIdx, bndType,
                    newSymSets, onAllSymmAPs);
        }
    }
    
//------------------------------------------------------------------------------
 
    public void appendVertexOnAP(AttachmentPoint srcAP, 
            AttachmentPoint trgAP) throws DENOPTIMException 
    {
        if (!srcAP.isAvailable())
        {
            throw new DENOPTIMException("Attempt to use unavailable attachment "
                    + "point " + srcAP + " on vertex " 
                    + srcAP.getOwner().getVertexId());
        }
        if ( !trgAP.isAvailable())
        {
            throw new DENOPTIMException("Attempt to use unavailable attachment "
                    + "point " + trgAP + " on vertex " 
                    + trgAP.getOwner().getVertexId());
        }
        
        BondType btSrc = srcAP.getBondType();
        BondType btTrg = trgAP.getBondType();
        BondType bndTyp = btSrc;
        if (btSrc != btTrg)
        {
            if (btSrc == BondType.ANY && btTrg != BondType.ANY)
            {
                bndTyp = btTrg;
            } else {
                if (btSrc != BondType.ANY && btTrg == BondType.ANY)
                {
                    bndTyp = btSrc;
                } else {
                    bndTyp = BondType.UNDEFINED;
                }
            }
        }
 
        this.addVertex(trgAP.getOwner());
        Edge edge = new Edge(srcAP,trgAP, bndTyp);
        addEdge(edge);
    }
    
//------------------------------------------------------------------------------
 
    public void appendGraphOnAP(AttachmentPoint apOnThisGraph,
            AttachmentPoint apOnIncomingGraph, BondType bndType)
                                        throws DENOPTIMException
    {
        DGraph incomingGraph = apOnIncomingGraph.getOwner().getGraphOwner();
        incomingGraph.renumberGraphVertices();
 
        Edge edge = new Edge(apOnThisGraph, apOnIncomingGraph, 
                bndType);
        addEdge(edge);
        
        //Import vertices
        for (Vertex incomingVrtx : incomingGraph.getVertexList())
        {
            addVertex(incomingVrtx);
        }
        
        //Import edges
        for (Edge incomingEdge : incomingGraph.getEdgeList())
        {
            addEdge(incomingEdge);
        }
        
        //Import rings
        for (Ring incomingRing : incomingGraph.getRings())
        {
            addRing(incomingRing);
        }
        
        incomingGraph.cleanup();
    }
 
//------------------------------------------------------------------------------
 
    public void appendGraphOnAP(Vertex parentVertex, int parentAPIdx,
                                DGraph subGraph,
                                Vertex childVertex, int childAPIdx,
                                BondType bndType,
                                Map<Vertex, SymmetricVertexes> newSymSets)
                                        throws DENOPTIMException
    {
        // Clone and renumber the subgraph to ensure uniqueness
        DGraph sgClone = subGraph.clone();
        // The clones have the same vertex IDs before renumbering vertices
        Vertex cvClone = sgClone.getVertexWithId(
                childVertex.getVertexId());
        sgClone.renumberGraphVertices();
 
        Edge edge = new Edge(parentVertex.getAP(parentAPIdx),
                cvClone.getAP(childAPIdx), bndType);
        addEdge(edge);
 
        // Import all vertices from cloned subgraph, i.e., sgClone
        for (int i=0; i<sgClone.getVertexList().size(); i++)
        {
            Vertex clonV = sgClone.getVertexList().get(i);
            Vertex origV = subGraph.getVertexList().get(i);
 
            addVertex(sgClone.getVertexList().get(i));
 
            // also need to tmp store pointers to symmetric vertices
            // Why is this working on subGraph and not on sgClone?
            // Since we are only checking is there is symmetry, there should be
            // no difference between doing it on sgClone or subGraph.
            if (subGraph.hasSymmetryInvolvingVertex(origV))
            {
                if (newSymSets.containsKey(origV))
                {
                    newSymSets.get(origV).add(clonV);
                }
                else
                {
                    newSymSets.put(origV, sgClone.getSymSetForVertex(clonV));
                }
            }
            else
            {
                if (newSymSets.containsKey(origV))
                {
                    newSymSets.get(origV).add(clonV);
                }
                else
                {
                    SymmetricVertexes ss = new SymmetricVertexes();
                    ss.add(clonV);
                    newSymSets.put(origV, ss);
                }
            }
        }
        // Import all edges from cloned subgraph
        for (int i=0; i<sgClone.getEdgeList().size(); i++)
        {
            addEdge(sgClone.getEdgeList().get(i));
        }
        // Import all rings from cloned subgraph
        for (int i=0; i<sgClone.getRings().size(); i++)
        {
            addRing(sgClone.getRings().get(i));
        }
 
        // project tmp symmetric set into final symmetric sets
        Set<SymmetricVertexes> doneTmpSymSets = new HashSet<SymmetricVertexes>();
        for (Map.Entry<Vertex, SymmetricVertexes> e : newSymSets.entrySet())
        {
            SymmetricVertexes tmpSS = e.getValue();
            if (doneTmpSymSets.contains(tmpSS))
            {
                continue;
            }
            doneTmpSymSets.add(tmpSS);
            boolean done = false;
            // NB: no need to check all entries of tmpSS: the first is enough
            SymmetricVertexes oldSS;
            Iterator<SymmetricVertexes> iter = getSymSetsIterator();
            while (iter.hasNext())
            {
                oldSS = iter.next();
                if (oldSS.contains(tmpSS.get(0)))
                {
                    oldSS.addAll(tmpSS);
                    done = true;
                    break;
                }
            }
            if (!done)
            {
                if (tmpSS.size() <= 1)
                {
                    // tmpSS has always at least one entry: the initial vrtx
                    continue;
                }
                //Move tmpSS into a new SS on molGraph
                SymmetricVertexes newSS = new SymmetricVertexes();
                newSS.addAll(tmpSS);
                addSymmetricSetOfVertices(newSS);
            }
        }
    }
 
//------------------------------------------------------------------------------
 
    public void appendGraphOnGraph(Vertex parentVertex,
                                   int parentAPIdx, DGraph subGraph,
                                   Vertex childVertex, int childAPIdx,
                                   BondType bndType,
                                   Map<Vertex, SymmetricVertexes> newSymSets,
                                   boolean onAllSymmAPs)
                                           throws DENOPTIMException
    {
        SymmetricAPs symAPs = parentVertex.getSymmetricAPs(
                parentVertex.getAP(parentAPIdx));
        if (symAPs.size()!=0 && onAllSymmAPs)
        {
            for (AttachmentPoint symAP : symAPs) 
            {
                if (!symAP.isAvailable())
                {
                    continue;
                }
                appendGraphOnAP(parentVertex, symAP.getIndexInOwner(), 
                        subGraph, childVertex,
                        childAPIdx, bndType, newSymSets);
            }
        } else {
            appendGraphOnAP(parentVertex, parentAPIdx, subGraph, childVertex,
                    childAPIdx, bndType, newSymSets);
        }
    }
 
//-----------------------------------------------------------------------------
 
    public List<Long> findVerticesIds(VertexQuery query, Logger logger)
    {
        List<Long> matches = new ArrayList<>();
        for (Vertex v : findVertices(query, logger))
        {
            matches.add(v.getVertexId());
        }
        return matches;
    }
 
//-----------------------------------------------------------------------------
 
    public ArrayList<Vertex> findVertices(VertexQuery vrtxQuery, Logger logger)
    {
        return findVertices(vrtxQuery, true,logger);
    }
    
//-----------------------------------------------------------------------------
 
    public ArrayList<Vertex> findVertices(VertexQuery vrtxQuery, 
            boolean purgeSym, Logger logger)
    {
        ArrayList<Vertex> matches = new ArrayList<>(getVertexList());
 
        logger.log(Level.FINE, "Candidates: " + matches);
 
        //Check condition vertex ID
        Long vidQuery = vrtxQuery.getVertexIDQuery();
        if (vidQuery != null)
        {
            ArrayList<Vertex> newLst = new ArrayList<>();
            for (Vertex v : matches)
            {
                if (v.getVertexId() == vidQuery.intValue())
                {
                    newLst.add(v);
                }
            }
            matches = newLst;
        }
        logger.log(Level.FINE,"  After filtering by vertex ID: " + matches);
        
        //Check condition vertex type (NB: essentially the vertex implementation
        VertexType vtQuery = vrtxQuery.getVertexTypeQuery();
        if (vtQuery != null)
        {
            ArrayList<Vertex> newLst = new ArrayList<>();
            for (Vertex v : matches)
            {
                if (v.getVertexType() == vtQuery)
                {
                    newLst.add(v);
                }
            }
            matches = newLst;
            logger.log(Level.FINER, "  After filtering by vertex type: "
                    + matches);
        }
        
        //Check condition building block Type
        BBType bbtQuery = vrtxQuery.getVertexBBTypeQuery();
        if (bbtQuery != null)
        {
            ArrayList<Vertex> newLst = new ArrayList<>();
            for (Vertex v : matches)
            {
                if (v.getBuildingBlockType() == bbtQuery)
                {
                    newLst.add(v);
                }
            }
            matches = newLst;
            logger.log(Level.FINER, "  After filtering by building block "
                        + "type: " + matches);
        }
        
        //Check condition building block ID
        Integer bbID = vrtxQuery.getVertexBBIDQuery();
        if (bbID != null)
        {
            ArrayList<Vertex> newLst = new ArrayList<>();
            for (Vertex v : matches)
            {   
                if (v.getBuildingBlockId() == bbID.intValue())
                {
                    newLst.add(v);
                }
            }
            matches = newLst;
            logger.log(Level.FINER, "  After filtering by building block ID: " 
                        + matches);
        } 
 
        //Check condition: level of vertex
        Integer levelQuery = vrtxQuery.getVertexLevelQuery();
        if (levelQuery != null)
        {
            ArrayList<Vertex> newLst = new ArrayList<Vertex>();
            for (Vertex v : matches)
            {
                if (getLevel(v) == levelQuery)
                {
                    newLst.add(v);
                }
            }
            matches = newLst;
            logger.log(Level.FINER, "  After filtering by level: " + matches);
        }
        
        logger.log(Level.FINE, "After all vertex-based filters: " + matches);
        
        List<EdgeQuery> inAndOutEdgeQueries = new ArrayList<>();
        inAndOutEdgeQueries.add(vrtxQuery.getInEdgeQuery());
        inAndOutEdgeQueries.add(vrtxQuery.getOutEdgeQuery());
        for (int i=0; i<2; i++) 
        {
            String inOrOut = "";
            if (i==0)
                inOrOut = "incoming";
            else 
                inOrOut = "ourgoing";
            
            EdgeQuery edgeQuery = inAndOutEdgeQueries.get(i);
            if (edgeQuery == null)
            {
                continue;
            }
            
            EdgeFinder edgeFinder = new EdgeFinder(i-1);
            
            Integer eTrgApIDx = edgeQuery.getTargetAPIdx();
            if (eTrgApIDx != null)
            {
                ArrayList<Vertex> newLst = new ArrayList<>();
                for (Vertex v : matches)
                {
                    for (Edge e : edgeFinder.apply(v))
                    {
                        if (e.getTrgAPID() == eTrgApIDx)
                        {
                            newLst.add(v);
                            break;
                        }
                    }
                }
                matches = newLst;
                logger.log(Level.FINER, "  After " + inOrOut 
                            + " edge trgAPID filter: " + matches);
            }
            
            Integer eInSrcApIDx = edgeQuery.getSourceAPIdx();
            if (eInSrcApIDx != null)
            {
                ArrayList<Vertex> newLst = new ArrayList<>();
                for (Vertex v : matches)
                {
                    for (Edge e : edgeFinder.apply(v))
                    {
                        if (e != null && e.getSrcAPID() == eInSrcApIDx)
                        {
                            newLst.add(v);
                            break;
                        }
                    }
                }
                matches = newLst;
                logger.log(Level.FINER, "  After " + inOrOut 
                            + " edge srcAPID filter: " + matches);
            }
            
            if (i==0)
            {
                Long eSrcVrtID = edgeQuery.getSourceVertexId();
                if (eSrcVrtID != null)
                {
                    ArrayList<Vertex> newLst = new ArrayList<>();
                    for (Vertex v : matches)
                    {
                        for (Edge e : edgeFinder.apply(v))
                        {
                            if(e.getSrcAP().getOwner().getVertexId()==eSrcVrtID)
                            {
                                newLst.add(v);
                                break;
                            }
                        }
                    }
                    matches = newLst;
                    logger.log(Level.FINER, "  After " + inOrOut 
                                + " edge src VertexID filter: " + matches);
                }
            } else if (i==1) {
                Long eTrgVrtID = edgeQuery.getTargetVertexId();
                if (eTrgVrtID != null)
                {
                    ArrayList<Vertex> newLst = new ArrayList<>();
                    for (Vertex v : matches)
                    {
                        for (Edge e : edgeFinder.apply(v))
                        {
                            if(e.getTrgAP().getOwner().getVertexId()==eTrgVrtID)
                            {
                                newLst.add(v);
                                break;
                            }
                        }
                    }
                    matches = newLst;
                    logger.log(Level.FINER, "  After " + inOrOut 
                                + " edge trg VertexID filter: " + matches);
                }
            }
 
            BondType btQuery = edgeQuery.getBondType();
            if (btQuery != null)
            {
                ArrayList<Vertex> newLst = new ArrayList<>();
                for (Vertex v : matches)
                {
                    for (Edge e : edgeFinder.apply(v))
                    {
                        if (e.getBondType() == btQuery)
                        {
                            newLst.add(v);
                            break;
                        }
                    }
                }
                matches = newLst;
                logger.log(Level.FINER, "  After " + inOrOut 
                            + " edge bond type filter: " + matches);
            }
 
            APClass srcAPC = edgeQuery.getSourceAPClass();
            if (srcAPC != null)
            {
                ArrayList<Vertex> newLst = new ArrayList<>();
                for (Vertex v : matches)
                {
                    for (Edge e : edgeFinder.apply(v))
                    {
                        if (e.getSrcAPClass().equals(srcAPC))
                        {
                            newLst.add(v);
                            break;
                        }
                    }
                }
                matches = newLst;
            }
            
            APClass trgAPC = edgeQuery.getTargetAPClass();
            if (trgAPC != null)
            {
                ArrayList<Vertex> newLst = new ArrayList<>();
                for (Vertex v : matches)
                {
                    for (Edge e : edgeFinder.apply(v))
                    {
                        if (e.getTrgAPClass().equals(trgAPC))
                        {
                            newLst.add(v);
                            break;
                        }
                    }
                }
                matches = newLst;
            }
            logger.log(Level.FINER, "After all " + inOrOut 
                        + " edge-based filters: " + matches);
        }
    
        // Identify symmetric sets and keep only one member
        if (purgeSym)
            removeSymmetryRedundance(matches);
 
        logger.log(Level.FINE, "Final Matches (after symmetry): " + matches);
 
        return matches;
    }
    
//-----------------------------------------------------------------------------
    
    private class EdgeFinder implements Function<Vertex,List<Edge>> 
    {
        private int mode = 0;
        
        public EdgeFinder(int i)
        {
            mode = i;   
        }
        
        @Override
        public List<Edge> apply(Vertex v)
        {
            List<Edge> edges = new ArrayList<Edge>();
            if (mode < 0)
            {
                Edge eToParent = v.getEdgeToParent();
                if (eToParent != null)
                    edges.add(eToParent);
            } else {
                for (AttachmentPoint ap : v.getAttachmentPoints())
                {
                    if (!ap.isAvailable() && ap.isSrcInUser())
                    {
                        edges.add(ap.getEdgeUser());
                    }
                }
            }
            return edges;
        }
    }
    
//-----------------------------------------------------------------------------
 
    public void removeSymmetryRedundance(List<Vertex> list) 
    {
        List<Vertex> symRedundant = new ArrayList<>();
        Iterator<SymmetricVertexes> itSymm = getSymSetsIterator();
        while (itSymm.hasNext())
        {
            SymmetricVertexes ss = itSymm.next();
            for (Vertex v : list)
            {
                if (symRedundant.contains(v))
                {
                    continue;
                }
                if (ss.contains(v))
                {
                    symRedundant.addAll(ss);
                    symRedundant.remove(v);
                }
            }
        }
        for (Vertex v : symRedundant)
        {
            list.remove(v);
        }
    }
 
//-----------------------------------------------------------------------------
 
    public void removeSymmetryRedundantIds(ArrayList<Long> list) {
        ArrayList<Vertex> vList = new ArrayList<>();
        for (long vid : list) {
            vList.add(getVertexWithId(vid));
        }
        removeSymmetryRedundance(vList);
        list.clear();
        for (Vertex v : vList) {
            list.add(v.getVertexId());
        }
    }
 
//------------------------------------------------------------------------------
 
    public DGraph editGraph(ArrayList<GraphEdit> edits,
            boolean symmetry, FragmentSpace fragSpace, Logger logger) 
                    throws DENOPTIMException
    {
        DGraph modGraph = this.clone();
 
        for (GraphEdit edit : edits)
        {
            logger.log(Level.FINE, "Graph edit task: " + edit.getType());
 
            switch (edit.getType())
            {
                case REPLACECHILD:
                {
                    DGraph inGraph = edit.getIncomingGraph();
                    VertexQuery query = edit.getVertexQuery();
                    int idAPOnInGraph = -1; // Initialization to invalid value
                    Vertex rootOfInGraph = null;
                    if (edit.getIncomingAPId() != null)
                    {
                        AttachmentPoint ap = inGraph.getAPWithId(
                                edit.getIncomingAPId().intValue());
                        if (ap == null)
                        {
                            String msg = "Skipping " + edit.getType() + " on "
                                    + "graph " + getGraphId() + ". The incoming"
                                    + " graph has no AP with ID = " 
                                    + edit.getIncomingAPId() + ". The IDs of "
                                    + "free APs are:";
                            for (AttachmentPoint freeAP : inGraph.getAvailableAPs())
                            {
                                msg = msg + " " + freeAP.getID();
                            }
                            msg = msg + ". "
                                    + "Please, use one of those values in "
                                    + "'idAPOnIncomingGraph'.";
                            logger.log(Level.WARNING, msg);
                        }
                        idAPOnInGraph = ap.getIndexInOwner();
                        rootOfInGraph = ap.getOwner();
                    } else {
                        ArrayList<AttachmentPoint> freeAPs = 
                                inGraph.getAvailableAPs();
                        if (freeAPs.size()==1)
                        {
                            AttachmentPoint ap = freeAPs.get(0);
                            idAPOnInGraph = ap.getIndexInOwner();
                            rootOfInGraph = ap.getOwner();
                        } else {
                            String geClsName = GraphEdit.class.getSimpleName();
                            String msg = "Skipping " + edit.getType() + " on "
                                    + "graph " + getGraphId() + ". The incoming"
                                    + " graph has more than one free AP ("
                                    + freeAPs.size() + ") and "
                                    + "the " + geClsName + " "
                                    + "does not provide sufficient information "
                                    + "to unambiguously choose one AP. "
                                    + "Please, add 'idAPOnIncomingGraph' in "
                                    + "the definition of " + geClsName + ".";
                            logger.log(Level.WARNING, msg);
                        }
                    }
                    
                    ArrayList<Vertex> matches = modGraph.findVertices(query, 
                            false, logger);
                    for (Vertex vertexToReplace : matches)
                    {
                        Edge edgeToParent = vertexToReplace.getEdgeToParent();
                        if (edgeToParent == null)
                        {
                            //The matched vertex has no parent, therefore
                            // the change would correspond to changing the graph 
                            // completely. This is unlikely the desired effect, 
                            // so we do not do anything.
                            continue;
                        }
                        Vertex parent = vertexToReplace.getParent();
                        int srcApId = edgeToParent.getSrcAPID();
                        
                        BondType bondType = edgeToParent.getBondType();
                        
                        modGraph.removeBranchStartingAt(vertexToReplace,symmetry);
                        
                        modGraph.appendGraphOnGraph(parent, srcApId, inGraph,
                                rootOfInGraph, idAPOnInGraph, bondType, 
                                new HashMap<Vertex, SymmetricVertexes>(), symmetry);
                    }
                    break;
                }
                case CHANGEVERTEX:
                {   
                    // One of the ways to provide the incoming vertex/subgraph
                    if (edit.getIncomingBBId() > -1 
                            && edit.getIncomingBBType() != null
                            && edit.getIncomingGraph() == null)
                    {
                        ArrayList<Vertex> matches = modGraph.findVertices(
                                edit.getVertexQuery(), false, logger);
                        for (Vertex vertexToChange : matches)
                        {
                            if (modGraph.containsVertex(vertexToChange))
                            {
                                DGraph graph = vertexToChange.getGraphOwner();
                                graph.replaceVertex(vertexToChange,
                                        edit.getIncomingBBId(),
                                        edit.getIncomingBBType(),
                                        edit.getAPMappig(),
                                        symmetry,
                                        fragSpace);
                            }
                        }
                    }
                    // Another of the ways to provide the incoming vertex/subgraph
                    if (edit.getIncomingGraph() != null
                            && edit.getIncomingBBType() == null)
                    {
                        // Since the replaceSingleSubGraph method below does not
                        // deal with symmetry, we keep symmetrically-redundant
                        // matches
                        ArrayList<Vertex> matches = modGraph.findVertices(
                                edit.getVertexQuery(), false, logger);
                        
                        for (Vertex vertexToChange : matches)
                        {
                            DGraph graph = vertexToChange.getGraphOwner();
                            DGraph newSubG = edit.getIncomingGraph().clone();
                            newSubG.renumberGraphVertices();
                            
                            LinkedHashMap<AttachmentPoint,AttachmentPoint> apMap =
                                    new LinkedHashMap<AttachmentPoint,AttachmentPoint>();
                            for (Map.Entry<Integer,Integer> e : 
                                edit.getAPMappig().entrySet())
                            {
                                apMap.put(vertexToChange.getAP(e.getKey()), 
                                        newSubG.getAvailableAPs().get(
                                                e.getValue()));
                            }
                            
                            List<Vertex> oldSubG = new ArrayList<Vertex>();
                            oldSubG.add(vertexToChange);
                            graph.replaceSingleSubGraph(oldSubG, newSubG, apMap);
                        }
                    }
                    
                    break;
                }
                case DELETEVERTEX:
                {
                    ArrayList<Vertex> matches = modGraph.findVertices(
                            edit.getVertexQuery(), false, logger);
                    for (Vertex vertexToRemove : matches)
                    {
                        if (modGraph.containsVertex(vertexToRemove))
                            modGraph.removeBranchStartingAt(vertexToRemove,
                                    symmetry);
                    }
                    break;
                }
            }
        }
        return modGraph;
    }
 
//------------------------------------------------------------------------------
 
    public List<Vertex> getMutableSites()
    {
        List<Vertex> mutableSites = new ArrayList<Vertex>();
        for (Vertex v : gVertices)
        {
            mutableSites.addAll(v.getMutationSites(
                    new ArrayList<MutationType>()));
        }
        return mutableSites;
    }
    
//------------------------------------------------------------------------------
 
    public List<Vertex> getMutableSites(List<MutationType> ignoredTypes)
    {
        List<Vertex> mutableSites = new ArrayList<Vertex>();
        for (Vertex v : gVertices)
        {
            mutableSites.addAll(v.getMutationSites(ignoredTypes));
        }
        return mutableSites;
    }
 
//------------------------------------------------------------------------------
 
    public String toJson()
    {
        Gson gson = DENOPTIMgson.getWriter();
        String jsonOutput = gson.toJson(this);
        return jsonOutput;
    }
    
//------------------------------------------------------------------------------
    
    protected void ensureUniqueApIDs()
    {
        for (AttachmentPoint ap : getAttachmentPoints())
        {
            ap.setID(apCounter.getAndIncrement());
        }
    }
 
//------------------------------------------------------------------------------
 
    public static DGraph fromJson(String json)
    {
        Gson gson = DENOPTIMgson.getReader();
        DGraph graph = gson.fromJson(json, DGraph.class);
        return graph;
    }
 
//------------------------------------------------------------------------------
 
    public static DGraph fromJson(Reader reader)
    {
        Gson gson = DENOPTIMgson.getReader();
        DGraph graph = gson.fromJson(reader, DGraph.class);
        return graph;
    }
 
//------------------------------------------------------------------------------
 
    public static class DENOPTIMGraphSerializer
    implements JsonSerializer<DGraph>
    {
        @Override
        public JsonElement serialize(DGraph g, Type typeOfSrc,
                JsonSerializationContext context) 
        {
            boolean regenerateVrtxID = false;
            boolean regenerateAP = false;
            Set<Long> unqVrtxIDs = new HashSet<Long>();
            Set<Integer> unqApIDs = new HashSet<Integer>();
            for (Vertex v : g.getVertexList())
            {
                if (!unqVrtxIDs.add(v.getVertexId()))
                {
                    regenerateVrtxID = true;
                }
                for (AttachmentPoint ap : v.getAttachmentPoints())
                {
                    if (!unqApIDs.add(ap.getID()))
                    {
                        regenerateAP = true;
                        break;
                    }
                }
            }
            if (regenerateVrtxID)
            {
                g.renumberGraphVertices();
            }
            if (regenerateAP)
            {
                g.ensureUniqueApIDs();
            }
            
            JsonObject jsonObject = new JsonObject();
            jsonObject.addProperty("graphId", g.graphId);
            jsonObject.add("gVertices", context.serialize(g.gVertices));
            jsonObject.add("gEdges", context.serialize(g.gEdges));
            jsonObject.add("gRings", context.serialize(g.gRings));
            jsonObject.add("symVertices", context.serialize(g.symVertices));
            return jsonObject;
        }
    }
 
    //--------------------------------------------------------------------------
 
    public static class DENOPTIMGraphDeserializer
    implements JsonDeserializer<DGraph>
    {
        @Override
        public DGraph deserialize(JsonElement json, Type typeOfT,
                JsonDeserializationContext context) throws JsonParseException
        {
            JsonObject jsonObject = json.getAsJsonObject();
 
            // First, build a graph with a graph ID and a list of vertices
            JsonObject partialJsonObj = new JsonObject();
            partialJsonObj.add("graphId", jsonObject.get("graphId"));
            partialJsonObj.add("gVertices", jsonObject.get("gVertices"));
 
            Gson gson = new GsonBuilder()
                .setExclusionStrategies(new DENOPTIMExclusionStrategyNoAPMap())
                .registerTypeAdapter(Vertex.class,
                      new DENOPTIMVertexDeserializer())
                .registerTypeAdapter(APClass.class, new APClassDeserializer())
                .setPrettyPrinting()
                .create();
 
            DGraph graph = gson.fromJson(partialJsonObj, DGraph.class);
 
            // Refresh APs
            for (Vertex v : graph.getVertexList())
            {
                // Regenerate reference to fragment owner
                v.setGraphOwner(graph);
 
                for (AttachmentPoint ap : v.getAttachmentPoints())
                {
                    // Regenerate reference to AP owner
                    ap.setOwner(v);
                }
            }
 
            // Then, recover those members that are heavily based on references:
            // edges, rings.
            JsonArray edgeArr = jsonObject.get("gEdges").getAsJsonArray();
            for (JsonElement e : edgeArr)
            {
                JsonObject o = e.getAsJsonObject();
                AttachmentPoint srcAP = graph.getAPWithId(
                        o.get("srcAPID").getAsInt());
                AttachmentPoint trgAP = graph.getAPWithId(
                        o.get("trgAPID").getAsInt());
 
                Edge edge = new Edge(srcAP, trgAP,
                        context.deserialize(o.get("bondType"),BondType.class));
                graph.addEdge(edge);
            }
 
            // Now, recover the rings
            JsonArray ringArr = jsonObject.get("gRings").getAsJsonArray();
            for (JsonElement e : ringArr)
            {
                JsonObject o = e.getAsJsonObject();
                Ring ring = new Ring();
                for (JsonElement re : o.get("vertices").getAsJsonArray())
                {
                    ring.addVertex(graph.getVertexWithId(re.getAsInt()));
                }
                ring.setBondType(context.deserialize(o.get("bndTyp"),
                        BondType.class));
                graph.addRing(ring);
            }
            
            //and symmetry relations between vertexes
            if (jsonObject.has("symVertices"))
            {
                for (JsonElement elSet : jsonObject.get("symVertices").getAsJsonArray())
                {
                    SymmetricVertexes ss = new SymmetricVertexes();
                    for (JsonElement elId : elSet.getAsJsonArray())
                    {
                        int id = context.deserialize(elId, Integer.class);
                        ss.add(graph.getVertexWithId(id));
                    }
                    try
                    {
                        graph.addSymmetricSetOfVertices(ss);
                    } catch (DENOPTIMException e1)
                    {
                        e1.printStackTrace();
                        throw new Error("Vertex listed in multiple symmetric "
                                + "sets. Check this: " + elSet);
                    }
                }                
            }
 
            return graph;
        }
    }
 
//------------------------------------------------------------------------------
 
    public static void setScaffold(Vertex v) {
        ArrayList<Vertex> newVertexList = new ArrayList<>();
 
        Set<Long> visited = new HashSet<>();
        Queue<Vertex> currLevel = new ArrayDeque<>();
        Queue<Vertex> nextLevel = new ArrayDeque<>();
        currLevel.add(v);
 
        while (!currLevel.isEmpty()) {
            Vertex currVertex = currLevel.poll();
 
            long currId = currVertex.getVertexId();
            if (!visited.contains(currId)) {
                visited.add(currId);
 
                newVertexList.add(currVertex);
 
                Iterable<Vertex> neighbors = currVertex
                        .getAttachmentPoints()
                        .stream()
                        .map(AttachmentPoint::getEdgeUser)
                        .filter(e -> e != null)
                        .map(e -> e.getSrcVertex() == currId ?
                                e.getTrgAP() : e.getSrcAP())
                        .map(AttachmentPoint::getOwner)
                        .collect(Collectors.toList());
                for (Vertex adj : neighbors) {
                    nextLevel.add(adj);
                }
            }
 
            if (currLevel.isEmpty()) {
                currLevel = nextLevel;
                nextLevel = new ArrayDeque<>();
            }
        }
 
        v.getGraphOwner().setVertexList(newVertexList);
    }
 
//------------------------------------------------------------------------------
 
    public boolean hasScaffoldTypeVertex() {
        return getVertexList()
                .stream()
                .anyMatch(v -> v.getBuildingBlockType() == BBType.SCAFFOLD);
    }
    
//------------------------------------------------------------------------------
    
    public void setTemplateJacket(Template template)
    {
        this.templateJacket = template;
    }
    
//------------------------------------------------------------------------------
    
    public Template getTemplateJacket()
    {
        return templateJacket;
    }
    
//------------------------------------------------------------------------------
    
    public DGraph getOutermostGraphOwner()
    {
        if (templateJacket == null)
            return this;
        else
            return templateJacket.getGraphOwner().getOutermostGraphOwner();
    }
    
//------------------------------------------------------------------------------
    
    public List<Template> getEmbeddingPath()
    {
        List<Template> path = new ArrayList<Template>();
        if (templateJacket==null)
            return path;
        if (templateJacket.getGraphOwner()!=null)
            path.addAll(templateJacket.getGraphOwner().getEmbeddingPath());
        path.add(templateJacket);
        return path;
    }
 
//------------------------------------------------------------------------------    
    
    public void storeCurrentVertexIDs()
    {
        for (Vertex v : gVertices)
        {
            v.setProperty(DENOPTIMConstants.STOREDVID, v.getVertexId());
        }
    }
 
//------------------------------------------------------------------------------        
    
    public AttachmentPoint getAPOnLeftVertexID(long nbrVid, long vid)
    {
        Vertex v1 = getVertexWithId(nbrVid);
        Vertex v2 = getVertexWithId(vid);
        if ( v1== null || v2 == null)
            return null;
        
        if (getChildVertices(v1).contains(v2))
        {
            return v2.getEdgeToParent().getSrcAP();
        } else if (getChildVertices(v2).contains(v1))
        {
            return v1.getEdgeToParent().getTrgAP();
        }
        
        // At this point the two vertices are not directly connected, but there 
        // could still be a chord between them. Here, we check for chords:
        /*
        for (DENOPTIMRing r : getRingsInvolvingVertex(v1))
        {
            if (r.contains(v2))
            {
                int lstId = r.getSize()-1;
                // Position 0 and lstId are where the RCVs sit
                if (r.getPositionOf(v1)==1 && r.getPositionOf(v2)==lstId)
                {
                    return r.getHeadVertex().getEdgeToParent().getSrcAP();
                }
                if (r.getPositionOf(v1)==lstId && r.getPositionOf(v2)==1)
                {
                    return r.getTailVertex().getEdgeToParent().getSrcAP();
                }
            }
        }
        */
        return null;
    }
 
//------------------------------------------------------------------------------    
    
    public boolean isReversible(FragmentSpace fragSpace)
    {
        for (Edge e : gEdges)
        {
            if (!e.getTrgAPClass().isCPMapCompatibleWith(e.getSrcAPClass(),
                    fragSpace))
            {
                return false;
            }
        }
        return true;
    }
    
//------------------------------------------------------------------------------
 
    public static DGraph getEmbeddedGraphInClone(DGraph graphY, 
            DGraph graphB, List<Template> path) 
    {
        if (path.isEmpty())
            return graphY;
        Template currentLevelVertex = null;
        DGraph currentLevelGraphEmdInB = graphB;
        DGraph currentLevelGraphEmbInY = graphY;
        for (Template t : path)
        {
            currentLevelVertex = (Template) currentLevelGraphEmbInY
                    .getVertexAtPosition(currentLevelGraphEmdInB.indexOf(t));
            currentLevelGraphEmdInB = t.getInnerGraph();
            currentLevelGraphEmbInY = currentLevelVertex.getInnerGraph();
        }
        return currentLevelVertex.getInnerGraph();
    }
    
//------------------------------------------------------------------------------    
 
    public List<AttachmentPoint> getInterfaceAPs(List<Vertex> subGraphB)
    {
        List<AttachmentPoint> interfaceAPs = new ArrayList<AttachmentPoint>();
        for (Vertex v : subGraphB)
        {
            for (AttachmentPoint ap : v.getAttachmentPoints())
            {
                if (ap.isAvailableThroughout())
                    continue;
                if (ap.isAvailable())
                {
                    // This AP is used across the template boundary
                    interfaceAPs.add(ap);
                } else {
                    Vertex user = ap.getLinkedAP().getOwner();
                    if (!subGraphB.contains(user))
                    {
                        // AP used to make a connection to outside subgraph
                        interfaceAPs.add(ap);
                    }
                }    
            }      
        }
        return interfaceAPs;
    }
 
//------------------------------------------------------------------------------
 
    public List<AttachmentPoint> getSubgraphAPs(
            List<Vertex> subGraphB)
    {
        List<AttachmentPoint> aps = new ArrayList<AttachmentPoint>();
        for (Vertex v : subGraphB)
        {
            for (AttachmentPoint ap : v.getAttachmentPoints())
            {
                if (ap.isAvailable())
                {
                    aps.add(ap);
                    continue;
                } 
                Vertex user = ap.getLinkedAP().getOwner();
                if (!subGraphB.contains(user))
                {
                    // AP used to make a connection to outside subgraph
                    aps.add(ap);
                }    
            }      
        }
        return aps;
    }
    
//------------------------------------------------------------------------------    
    
}