From 3cc46a664b5783ace237d57d9d2f0fadc71d9ca8 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 4 Apr 2011 20:43:53 +0000 Subject: [PATCH] speculative version of delaunay works single-threaded just fine --- .../SerialDelaunayRefinement.java | 8 +-- .../input/small.bad-interior.ele | 19 ++++++ .../input/small.bad-interior.node | 17 +++++ .../input/small.bad-interior.poly | 14 +++++ .../input/small.bad-on-border.ele | 19 ++++++ .../input/small.bad-on-border.node | 17 +++++ .../input/small.bad-on-border.poly | 14 +++++ .../SerialDelaunayRefinement.java | 62 ++++++++++++++++++- .../oooJava/DelaunayRefinement/Subgraph.java | 9 ++- .../input/small.bad-interior.ele | 19 ++++++ .../input/small.bad-interior.node | 17 +++++ .../input/small.bad-interior.poly | 14 +++++ .../input/small.bad-on-border.ele | 19 ++++++ .../input/small.bad-on-border.node | 17 +++++ .../input/small.bad-on-border.poly | 14 +++++ 15 files changed, 272 insertions(+), 7 deletions(-) create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.ele create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.node create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.poly create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.ele create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.node create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.poly create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.ele create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.node create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.poly create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.ele create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.node create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.poly diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/SerialDelaunayRefinement.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/SerialDelaunayRefinement.java index a88d7e37..71e32f0c 100644 --- a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/SerialDelaunayRefinement.java +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/SerialDelaunayRefinement.java @@ -110,13 +110,13 @@ public class SerialDelaunayRefinement { cavity.update(); - //boolean printChange = true; //(zzz % 10 == 0); + boolean printChange = true; //(zzz % 10 == 0); //remove old data - //if( printChange ) { - // System.out.println( "\n\n\nbad tri: "+mesh.getNodeData( bad_element ) ); + if( printChange ) { + System.out.println( "\n\n\nbad tri: "+mesh.getNodeData( bad_element ) ); // System.out.println( "\npre nodes: " ); - //} + } Node node; for (Iterator iterator = cavity.getPre().getNodes().iterator(); iterator.hasNext();) { node = (Node) iterator.next(); diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.ele b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.ele new file mode 100644 index 00000000..56f52607 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.ele @@ -0,0 +1,19 @@ +18 +0 0 1 4 +1 1 4 5 +2 1 2 6 +3 1 5 6 +4 2 3 6 +5 6 3 7 +6 4 8 9 +7 4 5 9 +8 5 6 9 // BAD! +9 6 9 10 +10 6 10 11 +11 6 7 11 +12 8 9 12 +13 9 12 13 +14 9 13 14 +15 9 14 10 +16 10 14 15 +17 10 11 15 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.node b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.node new file mode 100644 index 00000000..a3996b99 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.node @@ -0,0 +1,17 @@ +16 +0 0 0 0 +1 1 0 0 +2 2 0 0 +3 3 0 0 +4 0 1 0 +5 1.3 1.3 0 +6 2 1 0 +7 3.1 1 0 +8 0 2 0 +9 1 2 0 +10 2.1 2.1 0 +11 3.1 2 0 +12 0 3 0 +13 1 3.1 0 +14 2 3.1 0 +15 3 3 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.poly b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.poly new file mode 100644 index 00000000..f19824cd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-interior.poly @@ -0,0 +1,14 @@ +ignored line +12 +0 0 1 +1 1 2 +2 2 3 +3 3 7 +4 7 11 +5 11 15 +6 15 14 +7 14 13 +8 13 12 +9 12 8 +10 8 4 +11 4 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.ele b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.ele new file mode 100644 index 00000000..c452a03d --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.ele @@ -0,0 +1,19 @@ +18 +0 0 1 4 +1 1 4 5 +2 1 2 6 +3 1 5 6 +4 2 3 6 +5 6 3 7 +6 4 8 9 +7 4 5 9 +8 5 6 9 +9 6 9 10 +10 6 10 11 +11 6 7 11 +12 8 9 12 +13 12 13 14 // BAD! +14 9 12 14 +15 9 14 10 +16 10 14 15 +17 10 11 15 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.node b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.node new file mode 100644 index 00000000..fd7cf81b --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.node @@ -0,0 +1,17 @@ +16 +0 0 0 0 +1 1 0 0 +2 2 0 0 +3 3 0 0 +4 0 1 0 +5 1.1 1.1 0 +6 2 1 0 +7 3.1 1 0 +8 0 2 0 +9 1 2 0 +10 2.1 2.1 0 +11 3.1 2 0 +12 0 3 0 +13 1 3.1 0 +14 2 3.1 0 +15 3 3 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.poly b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.poly new file mode 100644 index 00000000..f19824cd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement-orig-algo/input/small.bad-on-border.poly @@ -0,0 +1,14 @@ +ignored line +12 +0 0 1 +1 1 2 +2 2 3 +3 3 7 +4 7 11 +5 11 15 +6 15 14 +7 14 13 +8 13 12 +9 12 8 +10 8 4 +11 4 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java index c8f8fea1..c4cb1d6a 100644 --- a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java @@ -39,6 +39,7 @@ public class SerialDelaunayRefinement { //Numbers below are Long.Max_Value long lasttime = 0x7fffffffffffffffL; long mintime = 0x7fffffffffffffffL; + for (long run = 0; ((run < 3) || Math.abs(lasttime - runtime) * 64 > Math.min(lasttime, runtime)) && run < 7; run++) { runtime = run(args); if (runtime < mintime) { @@ -146,7 +147,41 @@ public class SerialDelaunayRefinement { cavity.build(); //Takes up a whooping 50% of computation time and changes NOTHING but cavity :D - cavity.update(); + cavity.update(); + + + /* + LinkedList nodes = cavity.getPre().getNodes(); + LinkedList border = cavity.getPre().getBorder(); + LinkedList edges = cavity.getPre().getEdges(); + + String s = "nodes: \n"; + + for( Iterator iter = nodes.iterator(); iter.hasNext(); ) { + Node node = (Node) iter.next(); + Element element = (Element) mesh.getNodeData(node); + s += " "+element+"\n"; + } + + s += "\nborder: \n"; + + for( Iterator iter = border.iterator(); iter.hasNext(); ) { + Node node = (Node) iter.next(); + Element element = (Element) mesh.getNodeData(node); + s += " "+element+"\n"; + } + + s += "\nedges: \n"; + + for( Iterator iter = edges.iterator(); iter.hasNext(); ) { + Edge_d edge = (Edge_d) iter.next(); + Element element = (Element) mesh.getEdgeData(edge); + s += " "+element+"\n"; + } + + System.out.println( "Pre:\n"+s ); + */ + } sese storeCavity { @@ -174,7 +209,7 @@ public class SerialDelaunayRefinement { // go ahead with applying cavity when all of its // pre-nodes are still in if( cavity != null && - cavity.getPre().allNodesStillInCompleteGraph() ) { + cavity.getPre().allNodesAndBorderStillInCompleteGraph() ) { appliedCavity = true; lastAppliedCavity = cavity; @@ -229,6 +264,29 @@ public class SerialDelaunayRefinement { //} mesh.addEdge(edge); } + + + + for (Iterator iterator1 = cavity.getPost().getNodes().iterator(); + iterator1.hasNext();) { + node = (Node) iterator1.next(); + + Element e = (Element)mesh.getNodeData( node ); + + int cntOutNeighbors = 0; + for (Iterator iterator = mesh.getOutNeighbors(node); iterator.hasNext();) { + ++cntOutNeighbors; + Node neighbor = (Node) iterator.next(); + } + + int dim = e.getDim(); + int out = cntOutNeighbors; + + if( dim == 3 && out < 3 ) { + System.out.println( e+" has dim="+dim+" and num out-neighbors in graph="+out ); + } + } + } } diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java index 4c55e61e..375602c1 100644 --- a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java @@ -4,6 +4,7 @@ public class Subgraph { private final LinkedList border = new LinkedList(); private final LinkedList edges = new LinkedList(); + public Subgraph() { } @@ -50,13 +51,19 @@ public class Subgraph { } - public boolean allNodesStillInCompleteGraph() { + public boolean allNodesAndBorderStillInCompleteGraph() { for( Iterator i = nodes.iterator(); i.hasNext(); ) { Node node = (Node) i.next(); if( !node.inGraph ) { return false; } } + for( Iterator i = border.iterator(); i.hasNext(); ) { + Node node = (Node) i.next(); + if( !node.inGraph ) { + return false; + } + } return true; } diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.ele b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.ele new file mode 100644 index 00000000..56f52607 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.ele @@ -0,0 +1,19 @@ +18 +0 0 1 4 +1 1 4 5 +2 1 2 6 +3 1 5 6 +4 2 3 6 +5 6 3 7 +6 4 8 9 +7 4 5 9 +8 5 6 9 // BAD! +9 6 9 10 +10 6 10 11 +11 6 7 11 +12 8 9 12 +13 9 12 13 +14 9 13 14 +15 9 14 10 +16 10 14 15 +17 10 11 15 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.node b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.node new file mode 100644 index 00000000..a3996b99 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.node @@ -0,0 +1,17 @@ +16 +0 0 0 0 +1 1 0 0 +2 2 0 0 +3 3 0 0 +4 0 1 0 +5 1.3 1.3 0 +6 2 1 0 +7 3.1 1 0 +8 0 2 0 +9 1 2 0 +10 2.1 2.1 0 +11 3.1 2 0 +12 0 3 0 +13 1 3.1 0 +14 2 3.1 0 +15 3 3 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.poly b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.poly new file mode 100644 index 00000000..f19824cd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-interior.poly @@ -0,0 +1,14 @@ +ignored line +12 +0 0 1 +1 1 2 +2 2 3 +3 3 7 +4 7 11 +5 11 15 +6 15 14 +7 14 13 +8 13 12 +9 12 8 +10 8 4 +11 4 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.ele b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.ele new file mode 100644 index 00000000..c452a03d --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.ele @@ -0,0 +1,19 @@ +18 +0 0 1 4 +1 1 4 5 +2 1 2 6 +3 1 5 6 +4 2 3 6 +5 6 3 7 +6 4 8 9 +7 4 5 9 +8 5 6 9 +9 6 9 10 +10 6 10 11 +11 6 7 11 +12 8 9 12 +13 12 13 14 // BAD! +14 9 12 14 +15 9 14 10 +16 10 14 15 +17 10 11 15 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.node b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.node new file mode 100644 index 00000000..fd7cf81b --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.node @@ -0,0 +1,17 @@ +16 +0 0 0 0 +1 1 0 0 +2 2 0 0 +3 3 0 0 +4 0 1 0 +5 1.1 1.1 0 +6 2 1 0 +7 3.1 1 0 +8 0 2 0 +9 1 2 0 +10 2.1 2.1 0 +11 3.1 2 0 +12 0 3 0 +13 1 3.1 0 +14 2 3.1 0 +15 3 3 0 diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.poly b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.poly new file mode 100644 index 00000000..f19824cd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/input/small.bad-on-border.poly @@ -0,0 +1,14 @@ +ignored line +12 +0 0 1 +1 1 2 +2 2 3 +3 3 7 +4 7 11 +5 11 15 +6 15 14 +7 14 13 +8 13 12 +9 12 8 +10 8 4 +11 4 0 -- 2.34.1