1

我使用 GraphX API 在 Scala 中构建了一个图形。在我的图中，每个顶点都有一个LinkedHashMap[Int, ListBuffer[ListBuffer[Int]]]as 属性：每对 (key, value) 的LinkedHashMap代表：

  • 键：节点的 id - asInt
  • 值：到达节点的所有可能路径 - 每条路径都是 a ListBuffer[Int]，所以我有 a ListBufferofListBuffer[Int]

（我曾经Pregel创建过LinkedHashMaps）。所以，我想实现从图中删除节点的情况。我要做的是：

  1. 在 eachLinkedHashMap中删除带有键 == id_of_the_node 的元素
  2. 在 eachListBuffer[ListBuffer[Int]]中删除包含已删除节点的列表（路径）（路径将不再存在）。

假设我有以下节点（我将省略其他节点）：

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

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

节点 3：(3,Map(5 -> ListBuffer(ListBuffer(3, 5)), 6 -> ListBuffer(ListBuffer(3, 6)), 3 -> ListBuffer(ListBuffer(3))))

假设我想从中删除3节点myGraph。那么，节点的属性应该变成：

节点 1：(1, Map(5 -> ListBuffer(ListBuffer(1, 4, 5)), 4 -> ListBuffer(ListBuffer(1, 4)), 1 -> ListBuffer(ListBuffer(1))))

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

节点 3：(-1, LinkedHashMap[ListBuffer[ListBuffer[]]]())- 我不知道如何分配一个空的LinkedHashMap[ListBuffer[ListBuffer[Int]]].

我定义了以下方法：

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
    }

但这只是为了1上面提到的一点（使用键 == id_of_the_node 删除元素）。另外，如果我在myGraph如下的顶点上调用它，它不会给我想要的结果。

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

如何正确编写方法（同时实现点1和2）？以及如何使用它myGraph.vertices？在伪代码中：

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)

此外，LinkedHashMap该方法是否具有最佳时间复杂度的数据结构remove？

4

1 回答 1

0

因为我没有 GraphX Api，所以我使用了一些你的代码，我希望紧密相关，定义，像这样：

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

对于 node2 和 3，依此类推，只需导入 ListBuffer 即可在 REPL 中工作。然后我可以通过过滤删除：

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 代表内部和外部 ListBuffers。

更新：具有删除功能的可执行示例：

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

对于多个节点，映射它们并删除空结果：

    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))))
于 2017-12-31T04:29:35.483 回答