эффективный параллельный алгоритм для обновления стоимости прохождения для всех простых путей во взвешенном ориентированном графе

Я работаю с относительно небольшими ориентированными графами (~ 10 узлов), каждый из которых имеет ~ 10 000 простых путей и циклов. Я хотел бы вести отсортированный список совокупных затрат для прохождения всех этих простых путей и циклов. Мои ребра имеют несколько разных весов, но функции агрегирования являются коммутативными/ассоциативными (например, суммы и произведения) для всех из них.

Сейчас я использую rethinkdb (база данных nosql) и python. Я предварительно вычисляю все возможные простые пути, сохраняю их в хеш-карте, и просто пересчитывая обход обходным путем, каждый раз, когда обновляется вес ребра, они обходятся им. Моя хэш-карта указывает данное ребро (вес которого только что был обновлен) на все простые пути и циклы, частью которых оно является. Затем я иду и пересчитываю затраты на обход для каждого из них.

Ну, я обнаружил, что это очень медленно и не масштабируется! Я знаю, что это сложная задача, но надеялся, что это выполнимо для моих относительно небольших графиков.

Одна неэффективность моего первоначального подхода заключалась в расточительном избыточном вычислении каждого отдельного пути, даже если некоторые из них являются совокупностями друг друга. Например, стоимость A→B→C→D→E представляет собой композицию A→B→C и C→D→E. Так почему бы не вычислить их с умом? Я придумал способ сделать это, и он, похоже, ни на йоту не помог, что заставило меня подумать, что мне действительно нужно сделать шаг назад.

Итак, я зашел в Интернет, поискал и наткнулся на очень полезную статью: https://blog.blazegraph.com/?p=628 . В нем говорится:

Антипаттерн большого графа: «Поместите все в большой граф, а затем используйте те же инструменты, которые дали нам горизонтальное масштабирование для других задач: map/reduce и хранилища ключ-значение».

Мне кажется, что это именно то, что я делал (неправильно).

И кажется, что GPU является правильным решением проблемы пропускной способности памяти, упомянутой в статье... за исключением того, что я не уверен, как решить эту проблему параллельно.

Вопросы:

1. как подойти к этой проблеме параллельно? Является ли сбор-приложение-рассеивание правильным направлением? Где это было сделано раньше?

2. как я могу эффективно оптимизировать текущий подход, не проводя параллель?

Для справки, вот набросок моего текущего алгоритма:

1. перечислить все простые пути и циклы в моем графе

2. вести словарь ребер и их весов. например, если ('A','B') является ребром от узла A до узла B,

   edges_weights[('A','B')] # -> {'x': 1.3, 'y': 32, 'z': 0.231232}
   

3. сохраните словарь всех простых путей и циклов, в которых участвует каждое ребро, например:

   paths_containing_edges[('A','B')] 
   # ->
   # [
   #      (('A','B'), ('B','C')), 
   #      (('A','B'), ('B','C'), ('C','D')), 
   #      (('A','B'), ('B','C'), ('C','A')), 
   #      ... 
   #      (('A','B'), ('B','C'), ('C','D'), ('D','A'))
   # ] 
   

4. Также инициализируйте словарь путей и их стоимости:

   paths_costs = {
           (('A','B'), ('B','C')): {'x': ..., 'y': ..., 'z': ...}
   }
   

5. При обновлении ребра:

   я. обновить его веса в edges_weights

   II. найдите все простые пути, содержащие это ребро, и обновите их:

   fn = lambda p,q: p+q # the cost aggregation function        
   weight_keys = ['x','y','z']
   for path in paths_containing_edges[updated_edge]:
     # path is a tuple of edge tuples, i.e. (('A','B'),('B','C'),('C','D'))
     for w in weight_keys:
       paths_costs[path][w] = reduce(fn,[edges_weights[e][w] for e in path])
   

Ясно, что происходит много вложенных циклов и поисковых запросов... Но я изо всех сил пытаюсь понять, как я мог бы сделать что-то по-другому.