Index: trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6800)
+++ trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6801)
@@ -237,8 +237,8 @@
 
         LinkedList<OsmPrimitive> newToDelete = new LinkedList<OsmPrimitive>();
-        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
-        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
         graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
         newToDelete.addAll(graph.computeUploadOrder());
+        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
+        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
         toDelete = newToDelete;
     }