Простые запросы на большие диаграммы

Question

У меня вопрос о больших данных графа. Предположим, что у нас есть большой граф с почти 100 миллионами ребер и около 5 миллионов узлов, в этом случае лучшая платформа для построения графов, о которой вы знаете, может дать все простые пути длины < = k (для k = 3,4 , 5) между любыми двумя заданными узлами. Главная проблема заключается в скорости получения этих путей. Другое дело, что график направлен, но мы хотели бы, чтобы программа игнорировала направления при вычислении путей, но все же возвращала фактически направленные ребра, когда она видит эти пути.

Например:

а -> с < - д -> Ь правильный путь между узлами 'а' и 'B' длины 3.

Заранее спасибо.

Answer 1

Так что это способ сделать это в сетиx. Это примерно на основе решения, которое я дал here. Я предполагаю, что a->b и a<-b - это два разных пути, которые вы хотите. Я собираюсь вернуть это как список списков. Каждый подсписщик является (упорядоченным) ребрами пути.

import networkx as nx 
import itertools 

def getPaths(G,source,target, maxLength, excludeSet=None): 
    #print source, target, maxLength, excludeSet 
    if excludeSet== None: 
     excludeSet = set([source]) 
    else: 
     excludeSet.add(source)# won't allow a path starting at source to go through source again. 
    if maxLength == 0: 
     excludeSet.remove(source) 
     return [] 
    else: 
     if G.has_edge(source,target): 
      paths=[[(source,target)]] 
     else: 
      paths = [] 
     if G.has_edge(target,source): 
      paths.append([(target,source)]) 
     #neighbors_iter is a big iterator that will give (neighbor,edge) for each successor of source and then for each predecessor of source. 

     neighbors_iter = itertools.chain(((neighbor,(source,neighbor)) for neighbor in G.successors_iter(source) if neighbor != target),((neighbor,(neighbor,source)) for neighbor in G.predecessors_iter(source) if neighbor != target)) 

     #note that if a neighbor is both a predecessor and a successor, it shows up twice in this iteration. 

     paths.extend([[edge] + path for (neighbor,edge) in neighbors_iter if neighbor not in excludeSet for path in getPaths(G,neighbor,target,maxLength-1,excludeSet)]) 

     excludeSet.remove(source) #when we move back up the recursion, don't want to exclude this source any more 

     return paths 

G=nx.DiGraph() 
G.add_edges_from([(1,2),(2,3),(1,3),(1,4),(3,4),(4,3)]) 

print getPaths(G,1,3,2) 

>[[(1, 3)], [(1, 2), (2, 3)], [(1, 4), (4, 3)], [(1, 4), (3, 4)]] 

Я бы ожидать, что путем изменения алгоритма Дейкстра в NetworkX вы прибудете на более эффективный алгоритм (обратите внимание, что Дейкстры алгоритм имеет отсечку, но по умолчанию он только собирается вернуть кратчайший путь, и он будет следовать краевому направлению).

Это альтернативная версия всего файла paths.extend: paths.extend ([[edge] + путь для (соседний, ребро) в соседнем_истреле, если сосед не в excludeSet для пути в getPaths (G, соседний, целевой , maxLength-1, excludeSet), если len (path)> 0])

Answer 2

Я бы рекомендовал использовать Gephi для удобства и учебы.

Если вы нашли его, то Neo4j выполнит ваше требование с немного кодирования.