001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021package org.biojava.nbio.structure.symmetry.internal;
022
023import java.util.HashMap;
024import java.util.List;
025import java.util.Map;
026import java.util.Set;
027
028import org.biojava.nbio.structure.Atom;
029import org.biojava.nbio.structure.align.model.AFPChain;
030import org.biojava.nbio.structure.symmetry.utils.SymmetryTools;
031import org.jgrapht.Graph;
032import org.jgrapht.alg.connectivity.ConnectivityInspector;
033import org.jgrapht.graph.DefaultEdge;
034
035/**
036 * The GraphOrderDetector transforms the self-alignment into a Graph and
037 * extracts its maximally connected Components.
038 * <p>
039 * The order reported is the one that maximizes the number of residues aligned,
040 * i.e. the highest order (component size) times the frequency of the Component.
041 *
042 * @author Aleix Lafita
043 * @since 4.2.0
044 *
045 */
046public class GraphComponentOrderDetector implements OrderDetector {
047
048        @Override
049        public int calculateOrder(AFPChain selfAlignment, Atom[] ca)
050                        throws RefinerFailedException {
051
052                // Construct the alignment graph with jgrapht
053                Graph<Integer, DefaultEdge> graph = SymmetryTools
054                                .buildSymmetryGraph(selfAlignment);
055
056                // Find the maximally connected components of the graph
057                ConnectivityInspector<Integer, DefaultEdge> inspector =
058                                new ConnectivityInspector<Integer, DefaultEdge>(graph);
059                List<Set<Integer>> components = inspector.connectedSets();
060
061                // The order maximizes the residues aligned
062                Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
063                for (Set<Integer> c : components) {
064                        if (counts.containsKey(c.size()))
065                                counts.put(c.size(), counts.get(c.size()) + c.size());
066                        else
067                                counts.put(c.size(), c.size());
068                }
069                int maxCounts = 0;
070                int order = 1;
071                for (Integer ord : counts.keySet()) {
072                        if (counts.get(ord) > maxCounts) {
073                                order = ord;
074                                maxCounts = counts.get(ord);
075                        }
076                }
077                return order;
078        }
079
080}