| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| package org.apache.openjpa.lib.graph; |
| |
| import java.util.Collection; |
| import java.util.Iterator; |
| import java.util.List; |
| |
| import org.apache.openjpa.lib.test.AbstractTestCase; |
| import org.junit.Before; |
| import org.junit.Test; |
| |
| import static org.junit.Assert.*; |
| |
| |
| /** |
| * <p>Tests the {@link DepthFirstAnalysis} type.</p> |
| * |
| * @author Abe White |
| */ |
| public class TestDepthFirstAnalysis |
| extends AbstractTestCase { |
| |
| private DepthFirstAnalysis _dfa = null; |
| |
| @Before |
| public void setUp() { |
| setUpGraph1(); |
| } |
| |
| public void setUpGraph1() { |
| Graph graph = new Graph(); |
| Object node1 = new Object(); |
| Object node2 = new Object(); |
| Object node3 = new Object(); |
| Object node4 = new Object(); |
| graph.addNode(node1); |
| graph.addNode(node2); |
| graph.addNode(node3); |
| graph.addNode(node4); |
| graph.addEdge(new Edge(node1, node2, true)); |
| graph.addEdge(new Edge(node2, node3, true)); |
| graph.addEdge(new Edge(node3, node1, true)); |
| graph.addEdge(new Edge(node3, node4, true)); |
| graph.addEdge(new Edge(node2, node2, true)); |
| _dfa = new DepthFirstAnalysis(graph); |
| } |
| |
| public void setUpGraph2() { |
| Graph graph = new Graph(); |
| Integer node1 = 1; |
| Integer node2 = 2; |
| Integer node3 = 3; |
| Integer node4 = 4; |
| Integer node5 = 5; |
| graph.addNode(node2); // has to be first node for testcase |
| graph.addNode(node5); |
| graph.addNode(node4); |
| graph.addNode(node3); |
| graph.addNode(node1); |
| graph.addEdge(new Edge(node5, node4, true)); |
| graph.addEdge(new Edge(node4, node3, true)); |
| graph.addEdge(new Edge(node3, node3, true)); |
| graph.addEdge(new Edge(node3, node2, true)); |
| graph.addEdge(new Edge(node2, node5, true)); |
| graph.addEdge(new Edge(node2, node4, true)); |
| graph.addEdge(new Edge(node1, node4, true)); |
| _dfa = new DepthFirstAnalysis(graph); |
| } |
| |
| @Test |
| public void testNodeSorting() { |
| Collection nodes = _dfa.getSortedNodes(); |
| assertEquals(4, nodes.size()); |
| |
| int time = 0; |
| Object node; |
| for (Object o : nodes) { |
| node = o; |
| assertTrue(time <= _dfa.getFinishedTime(node)); |
| time = _dfa.getFinishedTime(node); |
| } |
| } |
| |
| @Test |
| public void testEdgeTyping() { |
| Collection edges = _dfa.getEdges(Edge.TYPE_BACK); |
| assertEquals(2, edges.size()); |
| Iterator itr = edges.iterator(); |
| Edge edge0 = (Edge) itr.next(); |
| Edge edge1 = (Edge) itr.next(); |
| assertTrue((edge0.getTo().equals(edge0.getFrom())) |
| || edge1.getTo().equals(edge1.getFrom())); |
| } |
| |
| @Test |
| public void testBackEdges() { |
| setUpGraph2(); |
| Collection edges = _dfa.getEdges(Edge.TYPE_BACK); |
| assertEquals(2, edges.size()); |
| Iterator itr = edges.iterator(); |
| Edge edge0 = (Edge) itr.next(); |
| Edge edge1 = (Edge) itr.next(); |
| if (edge0.getTo().equals(edge0.getFrom())) { |
| assertTrue(edge0.getCycle() != null && |
| edge0.getCycle().size() == 1); |
| List cycle = edge1.getCycle(); |
| assertTrue(cycle != null && cycle.size() == 4); |
| assertTrue(((Edge)cycle.get(0)).getFrom().equals( |
| ((Edge)cycle.get(3)).getTo())); |
| } else if (edge1.getTo().equals(edge1.getFrom())) { |
| assertTrue(edge1.getCycle() != null && |
| edge1.getCycle().size() == 1); |
| assertTrue(edge1 == edge1.getCycle()); |
| List cycle = edge0.getCycle(); |
| assertTrue(cycle != null && cycle.size() == 4); |
| assertTrue(((Edge)cycle.get(0)).getFrom().equals( |
| ((Edge)cycle.get(3)).getTo())); |
| } else { |
| // should not happen |
| assertFalse(true); |
| } |
| } |
| |
| @Test |
| public void testForwardEdges() { |
| setUpGraph2(); |
| Collection edges = _dfa.getEdges(Edge.TYPE_FORWARD); |
| assertEquals(2, edges.size()); |
| Iterator itr = edges.iterator(); |
| Edge edge0 = (Edge) itr.next(); |
| Edge edge1 = (Edge) itr.next(); |
| if (edge0.getCycle() == null) { |
| List cycle = edge1.getCycle(); |
| assertTrue(cycle != null && cycle.size() == 3); |
| assertTrue(((Edge)cycle.get(0)).getFrom().equals( |
| ((Edge)cycle.get(2)).getTo())); |
| } else if (edge1.getCycle() == null) { |
| List cycle = edge0.getCycle(); |
| assertTrue(cycle != null && cycle.size() == 3); |
| assertTrue(((Edge)cycle.get(0)).getFrom().equals( |
| ((Edge)cycle.get(2)).getTo())); |
| } else { |
| // should not happen |
| assertFalse(true); |
| } |
| } |
| |
| } |