001package org.biopax.paxtools.query.algorithm; 002 003import org.biopax.paxtools.query.model.Edge; 004import org.biopax.paxtools.query.model.GraphObject; 005import org.biopax.paxtools.query.model.Node; 006 007import java.util.HashSet; 008import java.util.Set; 009 010/** 011 * This algorithm is used internally by PathsBetween and PathsFromTo algorithms. It detects objects 012 * in the result set that are not on a path from source to target (called dangling), and removes 013 * these nodes from the result set. Dangling objects appear after breaking cycles. 014 * 015 * @author Ozgun Babur 016 */ 017public class Prune 018{ 019 private Set<GraphObject> result; 020 021 /** 022 * Source and targets merged. 023 */ 024 private Set<Node> ST; 025 026 027 /** 028 * Constructor with the input. 029 * 030 * @param result The result set 031 * @param ST Source and target nodes 032 */ 033 public Prune(Set<GraphObject> result, Set<Node> ST) 034 { 035 this.result = result; 036 this.ST = ST; 037 } 038 039 /** 040 * Executes the algorithm. 041 * @return the pruned graph 042 */ 043 public Set<GraphObject> run() 044 { 045 for (GraphObject go : new HashSet<GraphObject>(result)) 046 { 047 if (go instanceof Node) 048 { 049 checkNodeRecursive((Node) go); 050 } 051 } 052 return result; 053 } 054 055 /** 056 * Recursively checks if a node is dangling. 057 * @param node Node to check 058 */ 059 private void checkNodeRecursive(Node node) 060 { 061 if (isDangling(node)) 062 { 063 removeNode(node); 064 065 for (Edge edge : node.getUpstream()) 066 { 067 checkNodeRecursive(edge.getSourceNode()); 068 } 069 for (Edge edge : node.getDownstream()) 070 { 071 checkNodeRecursive(edge.getTargetNode()); 072 } 073 for (Node parent : node.getUpperEquivalent()) 074 { 075 checkNodeRecursive(parent); 076 } 077 for (Node child : node.getLowerEquivalent()) 078 { 079 checkNodeRecursive(child); 080 } 081 } 082 } 083 084 /** 085 * Removes the dangling node and its edges. 086 * @param node Node to remove 087 */ 088 private void removeNode(Node node) 089 { 090 result.remove(node); 091 092 for (Edge edge : node.getUpstream()) 093 { 094 result.remove(edge); 095 } 096 097 for (Edge edge : node.getDownstream()) 098 { 099 result.remove(edge); 100 } 101 } 102 103 /** 104 * Checks if the node is dangling. 105 * @param node Node to check 106 * @return true if dangling 107 */ 108 private boolean isDangling(Node node) 109 { 110 if (!result.contains(node)) return false; 111 if (ST.contains(node)) return false; 112 113 boolean hasIncoming = false; 114 115 for (Edge edge : node.getUpstream()) 116 { 117 if (result.contains(edge)) 118 { 119 hasIncoming = true; 120 break; 121 } 122 } 123 124 boolean hasOutgoing = false; 125 126 for (Edge edge : node.getDownstream()) 127 { 128 if (result.contains(edge)) 129 { 130 hasOutgoing = true; 131 break; 132 } 133 } 134 135 if (hasIncoming && hasOutgoing) return false; 136 137 boolean hasParent = false; 138 139 for (Node parent : node.getUpperEquivalent()) 140 { 141 if (result.contains(parent)) 142 { 143 hasParent = true; 144 break; 145 } 146 } 147 148 if (hasParent && (hasIncoming || hasOutgoing)) return false; 149 150 boolean hasChild = false; 151 152 for (Node child : node.getLowerEquivalent()) 153 { 154 if (result.contains(child)) 155 { 156 hasChild = true; 157 break; 158 } 159 } 160 161 return !(hasChild && (hasIncoming || hasOutgoing || hasParent)); 162 } 163}