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}