001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one
003: * or more contributor license agreements. See the NOTICE file
004: * distributed with this work for additional information
005: * regarding copyright ownership. The ASF licenses this file
006: * to you under the Apache License, Version 2.0 (the
007: * "License"); you may not use this file except in compliance
008: * with the License. You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing,
013: * software distributed under the License is distributed on an
014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015: * KIND, either express or implied. See the License for the
016: * specific language governing permissions and limitations
017: * under the License.
018: */
019: package org.apache.openjpa.lib.graph;
020:
021: import org.apache.openjpa.lib.util.Localizer;
022:
023: import java.util.AbstractList;
024: import java.util.ArrayList;
025: import java.util.Arrays;
026: import java.util.Collection;
027: import java.util.Collections;
028: import java.util.Comparator;
029: import java.util.HashMap;
030: import java.util.Iterator;
031: import java.util.LinkedList;
032: import java.util.List;
033: import java.util.Map;
034:
035: /**
036: * <p>Performs a depth-first analysis of a given {@link Graph}, caching
037: * information about the graph's nodes and edges. See the DFS algorithm
038: * in the book 'Introduction to Algorithms' by Cormen, Leiserson, and
039: * Rivest. The algorithm has been modified to group sibling nodes without
040: * connections together during the topological sort.</p>
041: *
042: * @author Abe White
043: * @since 1.0.0
044: * @nojavadoc
045: */
046: public class DepthFirstAnalysis {
047:
048: private static final Localizer _loc = Localizer
049: .forPackage(DepthFirstAnalysis.class);
050:
051: private final Graph _graph;
052: private final Map _nodeInfo = new HashMap();
053: private Comparator _comp;
054:
055: /**
056: * Constructor. Performs the analysis on the given graph and caches
057: * the resulting information.
058: */
059: public DepthFirstAnalysis(Graph graph) {
060: _graph = graph;
061:
062: // initialize node infos
063: Collection nodes = graph.getNodes();
064: for (Iterator itr = nodes.iterator(); itr.hasNext();)
065: _nodeInfo.put(itr.next(), new NodeInfo());
066:
067: // visit all nodes -- see intro to algo's book
068: NodeInfo info;
069: Object node;
070: for (Iterator itr = nodes.iterator(); itr.hasNext();) {
071: node = itr.next();
072: info = (NodeInfo) _nodeInfo.get(node);
073: if (info.color == NodeInfo.COLOR_WHITE)
074: visit(graph, node, info, 0, new LinkedList());
075: }
076: }
077:
078: /**
079: * Visit a node. See Introduction to Algorithms book for details.
080: */
081: private int visit(Graph graph, Object node, NodeInfo info,
082: int time, List path) {
083: // discover node
084: info.color = NodeInfo.COLOR_GRAY;
085:
086: // explore all vertices from that node depth first
087: Collection edges = graph.getEdgesFrom(node);
088: Edge edge;
089: Object other;
090: NodeInfo otherInfo;
091: int maxChildTime = time - 1;
092: int childTime;
093: for (Iterator itr = edges.iterator(); itr.hasNext();) {
094: edge = (Edge) itr.next();
095: other = edge.getOther(node);
096: otherInfo = (NodeInfo) _nodeInfo.get(other);
097: if (otherInfo.color == NodeInfo.COLOR_WHITE) {
098: // undiscovered node; recurse into it
099: path.add(edge);
100: childTime = visit(graph, other, otherInfo, time, path);
101: path.remove(edge);
102: edge.setType(Edge.TYPE_TREE);
103: } else if (otherInfo.color == NodeInfo.COLOR_GRAY) {
104: childTime = -1;
105: edge.setType(Edge.TYPE_BACK);
106: // calculate the cycle including this edge
107: edge.setCycle(cycleForBackEdge(edge, path));
108: } else {
109: childTime = otherInfo.finished;
110: edge.setType(Edge.TYPE_FORWARD);
111: // find the cycle including this edge
112: List cycle = new LinkedList();
113: cycle.add(edge);
114: if (cycleForForwardEdge(graph, other, node, cycle)) {
115: edge.setCycle(cycle);
116: }
117: }
118: maxChildTime = Math.max(maxChildTime, childTime);
119: }
120:
121: // finished with node
122: info.color = NodeInfo.COLOR_BLACK;
123: info.finished = maxChildTime + 1;
124: return info.finished;
125: }
126:
127: /**
128: * Set the comparator that should be used for ordering groups of nodes
129: * with the same dependencies.
130: */
131: public void setNodeComparator(Comparator comp) {
132: _comp = comp;
133: }
134:
135: /**
136: * Return the nodes in topologically-sorted order. This is often used
137: * to order dependencies. If each graph edge (u, v) represents a
138: * dependency of v on u, then this method will return the nodes in the
139: * order that they should be evaluated to satisfy all dependencies. Of
140: * course, if the graph is cyclic (has back edges), then no such ordering
141: * is possible, though this method will still return the correct order
142: * as if edges creating the cycles did not exist.
143: */
144: public List getSortedNodes() {
145: Map.Entry[] entries = (Map.Entry[]) _nodeInfo.entrySet()
146: .toArray(new Map.Entry[_nodeInfo.size()]);
147: Arrays.sort(entries, new NodeInfoComparator(_comp));
148: return new NodeList(entries);
149: }
150:
151: /**
152: * Return all edges of the given type. This method can be used to
153: * discover all edges that cause cycles in the graph by passing it
154: * the {@link Edge#TYPE_BACK} or {@link Edge#TYPE_FORWARD} edge type.
155: */
156: public Collection getEdges(int type) {
157: Collection typed = null;
158: Edge edge;
159: Object node;
160: for (Iterator nodes = _graph.getNodes().iterator(); nodes
161: .hasNext();) {
162: node = nodes.next();
163: for (Iterator itr = _graph.getEdgesFrom(node).iterator(); itr
164: .hasNext();) {
165: edge = (Edge) itr.next();
166: if (edge.getType() == type) {
167: if (typed == null)
168: typed = new ArrayList();
169: typed.add(edge);
170: }
171: }
172: }
173: return (typed == null) ? Collections.EMPTY_LIST : typed;
174: }
175:
176: /**
177: * Return the logical time that the given node was finished in
178: * the graph walk, or -1 if the node is not part of the graph.
179: */
180: public int getFinishedTime(Object node) {
181: NodeInfo info = (NodeInfo) _nodeInfo.get(node);
182: if (info == null)
183: return -1;
184: return info.finished;
185: }
186:
187: /**
188: * Returns a list of graph edges forming a cycle. The cycle begins
189: * with a type {@link Edge#TYPE_BACK} edge.
190: * @param backEdge "Starting" edge of the cycle
191: * @param path Continuous list of graph edges, may be null
192: * @param pos Index of the first edge in path continuing the cycle
193: * @return Cycle starting with a type {@link Edge#TYPE_BACK} edge
194: */
195: private List buildCycle(Edge backEdge, List path, int pos) {
196: int length = path != null ? path.size() - pos : 0;
197: List cycle = new ArrayList(length + 1);
198: cycle.add(0, backEdge);
199: for (int i = 0; i < length; i++) {
200: cycle.add(i + 1, path.get(pos + i));
201: }
202: return cycle;
203: }
204:
205: /**
206: * Computes the list of edges forming a cycle. The cycle always exists for
207: * a type {@link Edge#TYPE_BACK} edge. This method should only be called
208: * for type {@link Edge#TYPE_BACK} edges.
209: * @param edge Edge where the cycle was detected
210: * @param path Path consisting of edges to the edge's starting node
211: * @return Cycle starting with a type {@link Edge#TYPE_BACK} edge
212: */
213: private List cycleForBackEdge(Edge edge, List path) {
214: if (edge.getType() != Edge.TYPE_BACK) {
215: return null;
216: }
217:
218: List cycle;
219: int pos = 0;
220: if (path != null && !edge.getFrom().equals(edge.getTo())) {
221: // Not a single edge loop
222: pos = findNodeInPath(edge.getTo(), path);
223: assert (pos >= 0) : _loc.get("node-not-on-path", edge, edge
224: .getTo());
225: } else {
226: assert (edge.getFrom().equals(edge.getTo())) : _loc.get(
227: "edge-no-loop", edge).getMessage();
228: path = null;
229: }
230: cycle = buildCycle(edge, path, pos);
231: assert (cycle != null) : _loc.get("cycle-null", edge)
232: .getMessage();
233: return cycle;
234: }
235:
236: /**
237: * Computes the cycle of edges including node cycleTo. The cycle must not
238: * necessarily exist. This method should only be called for type
239: * {@link Edge#TYPE_FORWARD} edges.
240: * @param graph Graph
241: * @param node Current node
242: * @param cycleTo End node for loop
243: * @param path Path from loop end node to current node
244: * @return True if a cycle has been found. The cycle will be contained in
245: * the <code>path</code> parameter.
246: */
247: private boolean cycleForForwardEdge(Graph graph, Object node,
248: Object cycleTo, List path) {
249: boolean found = false;
250: Collection edges = graph.getEdgesFrom(node);
251: for (Iterator itr = edges.iterator(); !found && itr.hasNext();) {
252: Edge edge = (Edge) itr.next();
253: Object other = edge.getOther(node);
254: // Single edge loops are ignored
255: if (!node.equals(other)) {
256: if (other.equals(cycleTo)) {
257: // Cycle complete
258: path.add(edge);
259: found = true;
260: } else if (!path.contains(edge)) {
261: // Walk this edge
262: path.add(edge);
263: found = cycleForForwardEdge(graph, other, cycleTo,
264: path);
265: if (!found) {
266: // Remove edge again
267: path.remove(edge);
268: }
269: }
270: }
271: }
272: return found;
273: }
274:
275: /**
276: * Finds the position of the edge starting from a particular node in the
277: * continuous list of edges.
278: * @param node Node on the cycle.
279: * @param path Continuous list of graph edges.
280: * @return Edge index if found, -1 otherwise.
281: */
282: private int findNodeInPath(Object node, List path) {
283: int pos = -1;
284: if (path != null) {
285: for (int i = 0; i < path.size(); i++) {
286: if (((Edge) path.get(i)).getFrom().equals(node)) {
287: pos = i;
288: }
289: }
290: }
291: return pos;
292: }
293:
294: /**
295: * Test, if the analysis didn't find cycles.
296: */
297: public boolean hasNoCycles() {
298: // a) there must not be any back edges
299: if (!getEdges(Edge.TYPE_BACK).isEmpty()) {
300: return false;
301: }
302: // b) there might be forward edges
303: // make sure these don't indicate cycles
304: Collection edges = getEdges(Edge.TYPE_FORWARD);
305: if (!edges.isEmpty()) {
306: for (Iterator itr = edges.iterator(); itr.hasNext();) {
307: Edge edge = (Edge) itr.next();
308: if (edge.getCycle() != null) {
309: return false;
310: }
311: }
312: }
313: return true;
314: }
315:
316: /**
317: * Comparator for toplogically sorting entries in the node info map.
318: */
319: private static class NodeInfoComparator implements Comparator {
320:
321: private final Comparator _subComp;
322:
323: public NodeInfoComparator(Comparator subComp) {
324: _subComp = subComp;
325: }
326:
327: public int compare(Object o1, Object o2) {
328: Map.Entry e1 = (Map.Entry) o1;
329: Map.Entry e2 = (Map.Entry) o2;
330: NodeInfo n1 = (NodeInfo) e1.getValue();
331: NodeInfo n2 = (NodeInfo) e2.getValue();
332:
333: // sort by finished order
334: int ret = n1.finished - n2.finished;
335: if (ret == 0 && _subComp != null)
336: ret = _subComp.compare(e1.getKey(), e2.getKey());
337: return ret;
338: }
339: }
340:
341: /**
342: * List of node-to-nodeinfo entries that exposes just the nodes.
343: */
344: private static class NodeList extends AbstractList {
345:
346: private final Map.Entry[] _entries;
347:
348: public NodeList(Map.Entry[] entries) {
349: _entries = entries;
350: }
351:
352: public Object get(int idx) {
353: return _entries[idx].getKey();
354: }
355:
356: public int size() {
357: return _entries.length;
358: }
359: }
360: }
|