Index: trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6775)
+++ trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6776)
@@ -232,7 +232,14 @@
         relationsToAdd.removeAll(noProblemRelations);
 
-        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
+        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
         newToAdd.addAll(graph.computeUploadOrder());
         toAdd = newToAdd;
+
+        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());
+        toDelete = newToDelete;
     }
 
@@ -268,16 +275,12 @@
      */
     private static class RelationUploadDependencyGraph {
-        private Map<Relation, Set<Relation>> children;
+        private Map<Relation, Set<Relation>> children = new HashMap<Relation, Set<Relation>>();
         private Collection<Relation> relations;
-        private Set<Relation> visited;
+        private Set<Relation> visited = new HashSet<Relation>();
         private List<Relation> uploadOrder;
-
-        public RelationUploadDependencyGraph() {
-            this.children = new HashMap<Relation, Set<Relation>>();
-            this.visited = new HashSet<Relation>();
-        }
-
-        public RelationUploadDependencyGraph(Collection<Relation> relations) {
-            this();
+        private final boolean newOrUndeleted;
+
+        public RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
+            this.newOrUndeleted = newOrUndeleted;
             build(relations);
         }
@@ -286,10 +289,10 @@
             this.relations = new HashSet<Relation>();
             for(Relation relation: relations) {
-                if (!relation.isNewOrUndeleted() ) {
+                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
                     continue;
                 }
                 this.relations.add(relation);
                 for (RelationMember m: relation.getMembers()) {
-                    if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
+                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
                         addDependency(relation, (Relation)m.getMember());
                     }