Removing elements from LinkedHashMap and ListBuffer of ListBuffer, used as vertex attributes into a graph structure

Question

I have built a graph in Scala using the GraphX API. In my graph, each vertex has a LinkedHashMap[Int, ListBuffer[ListBuffer[Int]]] as attribute: every couple (key, value) of the LinkedHashMap represents:

• key: id of a node - as Int
• value: all the possible paths to reach the node - every path is a ListBuffer[Int], so i have a ListBuffer of ListBuffer[Int]

(I've used Pregel to create the LinkedHashMaps). So, I want to implement the case of removing a node from the graph. What I have to do is:

1. removing, in each LinkedHashMap, the element with the key == id_of_the_node
2. removing, in each ListBuffer[ListBuffer[Int]], the lists (paths) which contain the deleted node (the path will not exist anymore).

Suppose I have the following nodes (I will omit the others):

node 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))))

node 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))))

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

And suppose I want to delete node 3 from myGraph. Then, the nodes' attributes should become:

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

node 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))))

node 3: (-1, LinkedHashMap[ListBuffer[ListBuffer[]]]()) - I don't know how to assign an empty LinkedHashMap[ListBuffer[ListBuffer[Int]]].

I've defined the following method:

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
    }

But it's just for the point 1 mentioned above (removing the element with the key == id_of_the_node). Plus, if I call it on the vertices of myGraph as follows, it doesn't give me the wanted result.

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

How to write the method properly (implementing both point 1 and 2)? And how to use it on myGraph.vertices? In pseudocode:

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)

Also, is LinkedHashMap the data structure with the best time complexity for the remove method?

Answer 1

Since I don't have the GraphX Api, I used your code for some, I hope tightly related, definition, like this:

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

and so on for node2 and 3, which worked in the REPL by just importing ListBuffer. Then I can remove by filtering:

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 and lbinner stand for the inner and outer ListBuffers.

Update: Executable example with delete function:

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)))

For multiple nodes, map over them and remove empty results:

    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))))