Markus,
As I thought about this a bit more, I think you nailed the basic problem --
the order of the nodes in the Graph._nodes. I just re-ran the testcase with
the Sun JDK and, sure enough, the first node visited is 2 and the testcases
passes with the expected results. But, with the IBM JDK, the first node
visited is 5 and then, of course, we get slightly different results on the
type of edges in the graph.
I will experiment a bit more with changing from HashMap to TreeMap or
something similar and see if I can get consistent graph analysis. Thanks
for your help!
Kevin
On 7/30/07, Markus Fuchs <[EMAIL PROTECTED]> wrote:
>
> Hi Kevin,
>
> The DFA result is dependent on the order of the nodes in Graph._nodes. If
> the first node visited is 2, then the result is as the Sun jdk returns it,
> if the first node visited is 5, you'll get your results. Maybe changing
> Graph._nodes from HashMap to TreeMap would give us a consistent graph
> set-ups across VMs. Then, we'd need to to re-number the nodes, so that
> current node 2 is returned first by the iterator.
>
> My intention for the graph 2 was that I liked to have a cycle detected by
> a forward edge. Edge 1->4 will be a forward edge in most configurations
> (unless the analysis starts at node 1), but doesn't indicate a cycle.
>
> Sorry that this test case costs you such a headache. If cycles are
> detected as Back- or Forward edges will always depend on the order of
> Graph._nodes.iterator(), see DepthFirstAnalysis, line 70.
>
> Thanks,
>
> -- markus.
>
> Kevin Sutter wrote:
>
> Markus,
> Thanks for the patch, but I don't need that. I already have the coding
> changes done. I'm just trying to figure out how this graphing is supposed
> to work. I figured I wanted to get the current testcase to work with the
> IBM JDK before making any other changes. If the testcase works with the Sun
> JDK, let's get the basic test working with the IBM JDK first. Then, we can
> clean up the testcase as your patch below outlines.
>
> You had another reply to this string of notes, but you had changed the
> subject line so it didn't get threaded correctly. So, I am including a
> portion of that note here to keep the string of notes together:
>
> Single node loops are considered Back edges (Back edges can't occur
> during OpenJPA dependency management). For graph 2, the DFA should find:
>
> 2 Back edges: (3,3) and (3,2)
> 2 Forward edges: (2,4) and (1,4) [the edge (1,4) doesn't indicate a cycle]
>
> This results is dependent on the first node chosen for the DFA analysis.
> This must must be node 2 for the above result. The starting point is
> determined by the order of the nodes in Graph._nodes.
>
> This is not consistent with my findings. Given the setup for graph 2 as it
> is currently coded, the analysis begins with node key of 5. From there, the
> graph is traversed and my debugging of the edges indicates the following
> (the numbers indicate the key):
>
> TREE: 5->4, 4->3, 3->2
> BACK: 3->3, 2->4, 2->5
> FWD: 1->4
>
> So, I'm confused. If the current testcase works with the Sun JDK, why am I
> getting different results just because I changed the equality checks for the
> IBM JDK? I also just tried changing the testcase per your patch for the
> node and edge definitions and I still get the same result. So, we're not on
> the same page somewhere.
>
> Any more ideas? Thanks!
>
> Kevin
>
> On 7/30/07, Markus Fuchs <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> wrote:
>
> Index:
> openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
> ===================================================================
> ---
> openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
> (revision
> 561053)
> +++
> openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
> (working
> copy)
> @@ -35,7 +35,6 @@
> private DepthFirstAnalysis _dfa = null;
>
> public void setUp() {
> - setUpGraph1();
> }
>
> public void setUpGraph1() {
> @@ -58,30 +57,30 @@
>
> public void setUpGraph2() {
> Graph graph = new Graph();
> - Integer node1 = new Integer(5);
> - Integer node2 = new Integer(4);
> + Integer node5 = new Integer(5);
> + Integer node4 = new Integer(4);
> Integer node3 = new Integer(3);
> - Integer node4 = new Integer(2);
> - Integer node5 = new Integer(1);
> + Integer node2 = new Integer(2);
> + Integer node1 = new Integer(1);
> + graph.addNode(node5);
> + graph.addNode(node4);
> + graph.addNode(node3);
> + graph.addNode(node2);
> graph.addNode(node1);
> - graph.addNode(node2);
> - graph.addNode(node3);
> - graph.addNode(node4);
> - graph.addNode(node5);
> - graph.addEdge(new Edge(node1, node2, true));
> - graph.addEdge(new Edge(node2, node3, true));
> + 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, node4, true));
> - graph.addEdge(new Edge(node4, node1, true));
> - graph.addEdge(new Edge(node4, node2, true));
> - graph.addEdge(new Edge(node5, node2, 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);
> }
>
> public void testNodeSorting() {
> + setUpGraph1();
> Collection nodes = _dfa.getSortedNodes();
> assertEquals(4, nodes.size());
> -
> int time = 0;
> Object node;
> for (Iterator itr = nodes.iterator(); itr.hasNext();) {
> @@ -92,13 +91,14 @@
> }
>
> public void testEdgeTyping() {
> + setUpGraph1();
> 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() == edge0.getFrom())
> - || edge1.getTo() == edge1.getFrom());
> + assertTrue(edge0.getTo().equals(edge0.getFrom())
> + || edge1.getTo().equals(edge1.getFrom()));
> }
>
> public void testBackEdges() {
> @@ -108,17 +108,17 @@
> Iterator itr = edges.iterator();
> Edge edge0 = (Edge) itr.next();
> Edge edge1 = (Edge) itr.next();
> - if (edge0.getTo() == edge0.getFrom()) {
> + 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() ==
> ((Edge)cycle.get(3)).getTo());
> - } else if (edge1.getTo() == edge1.getFrom()) {
>
> +
> 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() ==
> ((Edge)cycle.get(3)).getTo());
>
> +
> assertTrue(((Edge)cycle.get(0)).getFrom().equals(((Edge)cycle.get(3)).getTo()));
> } else {
> // should not happen
> assertFalse(true);
> @@ -135,11 +135,11 @@
> if (edge0.getCycle() == null) {
> List cycle = edge1.getCycle();
> assertTrue(cycle != null && cycle.size() == 3);
> - assertTrue(((Edge)cycle.get(0)).getFrom() ==
> ((Edge)cycle.get(2)).getTo());
>
> +
> 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() ==
> ((Edge)cycle.get(2)).getTo());
>
> +
> assertTrue(((Edge)cycle.get(0)).getFrom().equals(((Edge)cycle.get(2)).getTo()));
> } else {
> // should not happen
> assertFalse(true);
> Index:
> openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
> ===================================================================
> ---
> openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
> (revision
> 561053)
> +++
> openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
> (working
> copy)
> @@ -221,7 +221,7 @@
> pos = findNodeInPath(edge.getTo(), path);
> assert (pos >= 0): _loc.get("node-not-on-path", edge,
> edge.getTo());
> } else {
> - assert (edge.getFrom() == edge.getTo()):
> + assert (edge.getFrom().equals(edge.getTo())):
> _loc.get("edge-no-loop", edge).getMessage();
> path = null;
> }
> @@ -250,7 +250,7 @@
> Object other = edge.getOther(node);
> // Single edge loops are ignored
> if (node != other) {
> - if (other == cycleTo) {
> + if (other.equals(cycleTo)) {
> // Cycle complete
> path.add(edge);
> found = true;
> @@ -279,7 +279,7 @@
> int pos = -1;
> if (path != null) {
> for (int i = 0; i < path.size(); i++) {
> - if (((Edge)path.get(i)).getFrom() == node) {
> + if (((Edge)path.get(i)).getFrom().equals(node)) {
> pos = i;
> }
> }
> Index: openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
> ===================================================================
> ---
> openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java (revision
> 561053)
> +++
> openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java (working
> copy)
> @@ -106,9 +106,9 @@
> * given node is not part of this edge.
> */
> public Object getOther(Object node) {
> - if (_to == node)
> + if (_to.equals(node))
> return _from;
> - if (_from == node)
> + if (_from.equals(node))
> return _to;
> return null;
> }
> @@ -118,7 +118,7 @@
> * this method returns true if either side is equal to the given
> node.
> */
> public boolean isTo(Object node) {
> - return _to == node || (!_directed && _from == node);
> + return _to.equals(node) || (!_directed && _from.equals(node));
> }
>
> /**
> @@ -127,7 +127,7 @@
> * node.
> */
> public boolean isFrom(Object node) {
> - return _from == node || (!_directed && _to == node);
> + return _from.equals(node) || (!_directed && _to.equals(node));
> }
>
> /**
>
>
