Entfernen von Elementen aus LinkedHashMap und ListBuffer von ListBuffer, die als Vertex-Attribute in einer Graphenstruktur verwendet werden

Question

Ich habe in Scala ein Diagramm mit der GraphX-API erstellt. In meinem Graph, hat jeder Knoten eine LinkedHashMap[Int, ListBuffer[ListBuffer[Int]]] als Attribut: jedes Paar (Schlüssel, Wert) des LinkedHashMap darstellt:

• Schlüssel: id eines Knotens - als Int
• Wert: alle möglichen Wege zu erreichen der Knoten - jeder Weg ist ein ListBuffer[Int], so habe ich eine ListBuffer von ListBuffer[Int]

(I Pregel verwendet habe, die LinkedHashMap s zu erstellen). Also, ich möchte den Fall eines Entfernens eines Knotens aus dem Graph implementieren. Was ich zu tun ist:

1. Entfernen in jedem LinkedHashMap, das Element mit dem Schlüssel == id_of_the_node
2. Entfernen in jedem ListBuffer[ListBuffer[Int]], die Listen (Pfade), die die gelöschten Knoten (der Pfad enthält nicht mehr vorhanden).

Angenommen, ich habe die folgenden Knoten (Ich werde die anderen weglassen):

Knoten 1: (1,Map(5 -> ListBuffer(ListBuffer(1, 3, 5), ListBuffer(1, 4, 5)), 6 -> ListBuffer(ListBuffer(1, 3, 6)), 3 -> ListBuffer(ListBuffer(1, 3)), 4 -> ListBuffer(ListBuffer(1, 4)), 1 -> ListBuffer(ListBuffer(1))))

Knoten 2: (2,Map(5 -> ListBuffer(ListBuffer(2, 1, 3, 5), ListBuffer(2, 1, 4, 5)), 6 -> ListBuffer(ListBuffer(2, 1, 3, 6)), 3 -> ListBuffer(ListBuffer(2, 1, 3)), 4 -> ListBuffer(ListBuffer(2, 1, 4)), 1 -> ListBuffer(ListBuffer(2, 1)), 2 -> ListBuffer(ListBuffer(2))))

Knoten 3: (3,Map(5 -> ListBuffer(ListBuffer(3, 5)), 6 -> ListBuffer(ListBuffer(3, 6)), 3 -> ListBuffer(ListBuffer(3))))

Und angenommen, Ich möchte den Knoten 3 von myGraph löschen. Dann sollte die Knoten Attribute werden:

Knoten 1: (1, Map(5 -> ListBuffer(ListBuffer(1, 4, 5)), 4 -> ListBuffer(ListBuffer(1, 4)), 1 -> ListBuffer(ListBuffer(1))))

Knoten 2: (2, Map(5 -> ListBuffer(ListBuffer(2, 1, 4, 5)), 4 -> ListBuffer(ListBuffer(2, 1, 4)), 1 -> ListBuffer(ListBuffer(2, 1)), 2 -> ListBuffer(ListBuffer(2))))

Knoten 3: (-1, LinkedHashMap[ListBuffer[ListBuffer[]]]()) - ich weiß nicht, wie ein leeres LinkedHashMap[ListBuffer[ListBuffer[Int]]] zuweisen.

Ich habe die folgende Methode definiert:

def del(nodeToDelete: Int, vertexMap: collection.mutable.LinkedHashMap[Int,ListBuffer[ListBuffer[Int]]]): collection.mutable.LinkedHashMap[Int,ListBuffer[ListBuffer[Int]]] = { 
     vertexMap.keySet.foreach{ k => 
     if(k == nodeToDelete) vertexMap.remove(k) 
     } 
     vertexMap 
    } 

Aber es ist nur für den Punkt 1 oben erwähnt (das Entfernen des Elements mit der Taste == id_of_the_node). Plus, wenn ich es an den Scheitelpunkten von myGraph wie folgt anrufe, gibt es mir das gewünschte Ergebnis nicht.

myGraph.vertices.map(vertex => vertex._2).map(myMap => del(3,myMap)) 

Wie die Methode richtig schreiben (Umsetzung sowohl Punkt 1 und 2)? Und wie man es auf verwendet? In Pseudo-Code:

foreach key k of vertexMap 
if(k == nodeToDelete) vertexMap.remove(k) 
foreach ListBuffer l1 
    foreach ListBuffer l2 
    if (l2.contains(nodeTodelete)) remove the list 
if(l1 is empty) vertexMap.remove(k) 

Auch ist LinkedHashMap die Datenstruktur mit der besten Zeit Komplexität für die remove Methode?

Answer 1

Da ich die GraphX ​​Api nicht haben, habe ich den Code für einige, ich hoffe, eng verwandt, Definition, wie folgt aus:

val node1 = (1, Map(5 -> ListBuffer(ListBuffer(1, 4, 5)), 4 -> ListBuffer(ListBuffer(1, 4)), 1 -> ListBuffer(ListBuffer(1)))) 

und so weiter für Knoten2 und 3, die in der gearbeitet REPL nur durch den Import von ListBuffer. Dann kann ich durch Filtern entfernen:

node1._2.map (_._2.filter (! _.contains (3))).filter (_.size > 0) 
/* 
res34: scala.collection.immutable.Iterable[scala.collection.mutable.ListBuffer[scala.collection.mutable.ListBuffer[Int]]] = 
List(ListBuffer(ListBuffer(1, 4, 5)), 
    ListBuffer(ListBuffer(1)), ListBuffer(ListBuffer(1, 4))) 
*/  
scala> node2._2.map (_._2.filter (! _.contains (3))).filter (_.size > 0) 
    /* 
    res35: scala.collection.immutable.Iterable[scala.collection.mutable.ListBuffer[scala.collection.mutable.ListBuffer[Int]]] = 
List(
    ListBuffer(ListBuffer(2, 1, 4, 5)), ListBuffer(ListBuffer(2, 1)), 
    ListBuffer(ListBuffer(2)), ListBuffer(ListBuffer(2, 1, 4))) 
    */ 

node3._2.map (lbouter => lbouter._2.filter (lbinner=> ! lbinner.contains (3))).filter (_.size > 0) 
res36: scala.collection.immutable.Iterable[scala.collection.mutable.ListBuffer[scala.collection.mutable.ListBuffer[Int]]] = List() 

lbouter lbinner und stehen für die inneren und äußeren ListBuffers.

Update: Ausführbare Beispiel mit Löschfunktion:

import collection.mutable._ 

def delnode (x: Int, vertexMap: Map [Int, ListBuffer [ListBuffer [Int]]]) = { 
    vertexMap.values.map (_.filter (! _.contains (x))).filter (_.size > 0) 
} 

val anode = (Map (5 -> ListBuffer (ListBuffer (1, 3, 5), ListBuffer (1, 4, 5)), 6 -> ListBuffer(ListBuffer (1, 3, 6)), 3 -> ListBuffer(ListBuffer (1, 3)), 4 -> ListBuffer(ListBuffer (1, 4)), 1 -> ListBuffer (ListBuffer(1)))) 
val bnode = (Map (5 -> ListBuffer (ListBuffer (2, 1, 3, 5), ListBuffer (2, 1, 4, 5)), 1 -> ListBuffer(ListBuffer (2, 1)), 6 -> ListBuffer(ListBuffer (2, 1, 3, 6)), 2 -> ListBuffer(ListBuffer (2)), 3 -> ListBuffer(ListBuffer (2, 1, 3)), 4 -> ListBuffer(ListBuffer (2, 1, 4)))) 
val cnode = (Map (5 -> ListBuffer (ListBuffer (3, 5)), 6 -> ListBuffer(ListBuffer (3, 6)), 3 -> ListBuffer(ListBuffer (3)))) 

delnode (3, bnode) 
/* 
res9: Iterable[scala.collection.mutable.ListBuffer[scala.collection.mutable.ListBuffer[Int]]] = 
List(
ListBuffer(ListBuffer(2)), ListBuffer(ListBuffer(2, 1, 4, 5)), 
ListBuffer(ListBuffer(2, 1, 4)), ListBuffer(ListBuffer(2, 1))) 

Für mehrere Knoten, sie Karte über und leere Ergebnisse entfernen:

List (anode, bnode, cnode).map (n => delnode (3, n)).filter (_.size > 0) 
res12: List[Iterable[scala.collection.mutable.ListBuffer[scala.collection.mutable.ListBuffer[Int]]]] = List(List(ListBuffer(ListBuffer(1, 4, 5)), ListBuffer(ListBuffer(1, 4)), ListBuffer(ListBuffer(1))), List(ListBuffer(ListBuffer(2)), ListBuffer(ListBuffer(2, 1, 4, 5)), ListBuffer(ListBuffer(2, 1, 4)), ListBuffer(ListBuffer(2, 1))))