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}