Okay, finally some good news. I have changed the Graph._nodes map to be a
LinkedHashMap. This change seems to have the least amount of ripple effects
to the code. With a minor a change to the testcase to insert the 2 node
first, both the Sun and the IBM JDK environments now work consistently.
I'll open a JIRA Issue and integrate these changes shortly.
Kevin
On 7/31/07, Kevin Sutter <[EMAIL PROTECTED]> wrote:
>
> 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));
> > }
> >
> > /**
> >
> >
>
