Graphx: возможно ли выполнить программу на каждой вершине без получения сообщения? - PullRequest
Новая
       36

Graphx: возможно ли выполнить программу на каждой вершине без получения сообщения?

0 голосов
/ 29 ноября 2018

Когда я пытался реализовать алгоритм в Graphx с помощью Scala, я не находил возможным активировать все вершины в следующей итерации. Как я могу отправить сообщение всем моим вершинам графа?В моем алгоритме есть несколько супершагов, которые должны быть выполнены всеми вершинами (независимо от того, получают они сообщение или нет, потому что даже не получение сообщения - это событие, которое должно быть обработано в следующей итерации).

Я привожу здесь официальный код алгоритма SSSP, реализованного в логике Прегеля. Вы можете видеть, что только вершины, получившие сообщение, будут выполнять свою программу на следующей итерации, но в моем случае я хочу, чтобы функция pregel выполнялась итеративно, то есть каждый супершагвершины выполняют свои программы, и они могут голосовать, чтобы остановить, если это необходимо !!Рассуждения в этом примере не похожи на логику Прегеля.Пожалуйста, есть идеи, как реализовать настоящую логику Прегеля? 

val graph: Graph[Long, Double] =
  GraphGenerators.logNormalGraph(sc, numVertices = 100).mapEdges(e => e.attr.toDouble)
val sourceId: VertexId = 42 // The ultimate source
// Initialize the graph such that all vertices except the root have distance infinity.
val initialGraph = graph.mapVertices((id, _) =>
    if (id == sourceId) 0.0 else Double.PositiveInfinity)
val sssp = initialGraph.pregel(Double.PositiveInfinity)(
  (id, dist, newDist) => math.min(dist, newDist), // Vertex Program
  triplet => {  // Send Message
    if (triplet.srcAttr + triplet.attr < triplet.dstAttr) {
      Iterator((triplet.dstId, triplet.srcAttr + triplet.attr))
    } else {
      Iterator.empty
    }
  },
  (a, b) => math.min(a, b) // Merge Message
)
println(sssp.vertices.collect.mkString("\n"))

}

1 Ответ

0 голосов
/ 04 декабря 2018

После прочтения двух ответов @Mahmoud Hanafy и @Shaido, подтверждающих, что в GraphX ​​нет способа активировать вершины или проголосовать за остановку, я попытался реализовать эту логику в самом алгоритме.Итак, вот что я сделал:

  • API Прегеля отправляет init message во все вершины графа на первом супершаге, где они могут выполнить свои процедуры хотя бы один раз, прежде чем они станут неактивными.
  • В конце этого супершага каждая вершина v может отправлять сообщения своим соседям и ждать получения сообщений от других.
  • На втором супершаге не все вершиныбудет получать информацию от своих соседей, это означает, что не все вершины будут активированы во втором супершаге!Итак, чтобы решить это, нам нужно вернуться к супершагу и убедиться, что каждая вершина получит сообщение!Как?отправив сообщение себе!(Это единственный способ, которым я могу гарантировать активацию своей вершины на следующем супершаге, но я считаю, что это не лучший способ сделать это, потому что это увеличит количество отправляемых и получаемых сообщений).
  • На втором супершаге каждая вершина получит хотя бы одно сообщение и, следовательно, будет активна, чтобы выполнить свою программу.
  • Чтобы обеспечить активацию вершины на следующих супершагах, мы можемсделайте то же самое.

Повторяю, это единственный способ, с помощью которого я придумаю решение моей проблемы, но я не призываю вас использовать его.

...