001package org.biopax.paxtools.query.algorithm;
002
003
004import org.biopax.paxtools.query.model.GraphObject;
005import org.biopax.paxtools.query.model.Node;
006
007import java.util.*;
008
009/**
010 * Finds the paths between the specified source set of states within the boundaries of a
011 * specified length limit.
012 *
013 * @author Ozgun Babur
014 */
015public class PathsBetweenQuery
016{
017        /**
018         * The set of nodes from which the paths of interests should start.
019         */
020        private Collection<Set<Node>> sourceSet;
021
022        /**
023         * Based on the limitType, given integer may be used directly as stop
024         * distance or may be added up with the shortest path's length and used as
025         * stop distance.
026         */
027        private int limit;
028
029        /**
030         * Constructor with parameters
031         * @param sourceSet Seed to the query
032         * @param limit Distance limit
033         */
034        public PathsBetweenQuery(Collection<Set<Node>> sourceSet, int limit)
035        {
036                this.sourceSet = sourceSet;
037                this.limit = limit;
038        }
039
040        public Set<GraphObject> run()
041        {
042                /**
043                 * Distance labels of graph objects. Note that each source set may have a distinct label for
044                 * the object.
045                 */
046                Map<GraphObject, Map<Set<Node>, Integer>> fwdObj = new HashMap<GraphObject, Map<Set<Node>, Integer>>();
047                Map<GraphObject, Map<Set<Node>, Integer>> revObj = new HashMap<GraphObject, Map<Set<Node>, Integer>>();
048
049                Set<GraphObject> result = new HashSet<GraphObject>();
050
051                for (Set<Node> set : sourceSet)
052                {
053                        BFS bfsFwd = new BFS(set, null, Direction.DOWNSTREAM, limit);
054                        BFS bfsRev = new BFS(set, null, Direction.UPSTREAM, limit);
055
056                        recordLabels(fwdObj, set, bfsFwd.run());
057                        recordLabels(revObj, set, bfsRev.run());
058                }
059
060
061                /**
062                 * Only the graph objects whose sum of two search labels, coming from different sets,
063                 * being smaller than or equal to the distance limit will be in the result.
064                 */
065                for (GraphObject go : fwdObj.keySet())
066                {
067                        if (!revObj.containsKey(go)) continue;
068
069                        if (onTheResultPath(fwdObj.get(go), revObj.get(go)))
070                        {
071                                result.add(go);
072                        }
073                }
074
075                Set<Node> sources = new HashSet<Node>();
076                for (Set<Node> set : sourceSet)
077                {
078                        sources.addAll(set);
079                }
080
081                CycleBreaker breaker = new CycleBreaker(result, sources, limit);
082                breaker.breakCycles();
083
084                Prune prune = new Prune(result, sources);
085                prune.run();
086
087                return result;
088        }
089
090        private void recordLabels(Map<GraphObject, Map<Set<Node>, Integer>> labels, Set<Node> set,
091                Map<GraphObject, Integer> bfsResult)
092        {
093                for (GraphObject go : bfsResult.keySet())
094                {
095                        if (!labels.containsKey(go)) labels.put(go, new HashMap<Set<Node>, Integer>());
096
097                        labels.get(go).put(set, bfsResult.get(go));
098                }
099        }
100
101        private boolean onTheResultPath(Map<Set<Node>, Integer> fwdMap, Map<Set<Node>, Integer> revMap)
102        {
103                for (Set<Node> set1 : fwdMap.keySet())
104                {
105                        for (Set<Node> set2 : revMap.keySet())
106                        {
107                                if (set1 == set2) continue;
108
109                                int dist = fwdMap.get(set1) + revMap.get(set2);
110
111                                if (dist <= limit) return true;
112                        }
113                }
114                return false;
115        }
116}