Наименьшая длина пути между соседями соединенных вершин (не любые две случайные вершины!) - PullRequest
Новая
       33

Наименьшая длина пути между соседями соединенных вершин (не любые две случайные вершины!)

3 голосов
/ 15 апреля 2019

Ранее я задавал похожий вопрос, но, как мне кажется, он был неясен.У меня есть неориентированный и невзвешенный граф из 10000 вершин и около 5000000 ребер, которые я зачитываю их в python как список ребер.

В своей работе я пытаюсь построить функцию из каждого ребра, котораязависит от расстояния между соседями вершин на каждом ребре.Предположим, у нас есть две соединенные вершины v1, v2 представляют ребро, для v1 существует n1 связанных соседей, а также есть n2 соседей, связанных с v2.Чтобы построить мою функцию, мне нужно получить расстояния между соседями n1 и n2.Для всех ребер графа функция выглядит следующим образом: 

e_1*d_1 +e_1*d_2 +...+e_1*d_n+...e_m*d_1+...e_m*d_n

где n - количество соседей для обеих вершин на каждом ребре, d_n - расстояние между этими вершинами, m - количество ребер вграф и e_m - это последнее ребро в этом графе.

Обычно, если мы хотим получить кратчайшую длину пути, мы думаем о обходе графа, как алгоритм Дейкстры или Bfs, особенно о том, что мой граф невзвешенный.Я использовал много функций, уже написанных в таких пакетах, как networkx и igraph, но эти функции неэффективны и отнимают много времени для моего графика.Например, функция shortest_paths_dijkstra() занимает около 6,9 часов, чтобы определить расстояние, потому что мне нужно вызывать ее много раз.Также функция all_pairs_shortest_path _length занимает около 13 минут (фиксируя длину пути, известную как обрезание, равной 3) и еще 16 минут для вызова расстояния для каждой пары соседей в графе!

Как написано в вопросенам нужно получить расстояние между соседями v1, v2, чтобы максимальное расстояние равнялось 3, поскольку v1, v2 соединены.Я чувствую, что есть более умное решение, чтобы уменьшить сложность времени, используя тот факт, что возможные расстояния для пути (в моем случае) 0, 1, 2, 3, так что мне не нужно проходить весь график для каждого пути междуисточник и цель!просто я ищу умный способ получить расстояние между соседями (а не двумя произвольно выбранными вершинами)!

Я написал этот код, но он занимает много времени, около 54 минут, поэтому он неэффективен.! 

neighbor1 = {}
neighbor2 = {}
distance = {}
for i in list(edges.values()):
  list_of_distances = []
  neighbor1 = tuple(graph.vs[graph.neighbors(i[0], mode="all")]["name"])
  neighbor2 = tuple(graph.vs[graph.neighbors(i[1], mode="all")]["name"])
  for n2 in neighbor2:
    for n1 in neighbor1:
       if n1 == n2:
            list_of_distances.append(0)
       elif (n1 != n2) and not graph.are_connected(n1,n2):
            if ( graph.are_connected(i[0],n2) ) or ( graph.are_connected(n1,i[1])  ): 
               list_of_distances.append(2)
            elif ( not graph.are_connected(i[0],n2)  ) or ( not graph.are_connected(n1,i[1]) ):
               list_of_distances.append(3)
       else:
            list_of_distances.append(1)
  distance[tuple(i)] = list_of_distances

Я хотел бы знать, есть ли другой способ, которому не нужно много памяти и времени, чтобы получить эти расстояния, или есть ли возможность изменить один метод обхода графа, такой как Bfs илиDijkstra, так что нет необходимости искать весь граф каждую итерацию и просто делать что-то локальное (если это можно сказать).Спасибо за любую помощь

1 Ответ

0 голосов
/ 18 апреля 2019

У вас чрезвычайно сложная вычислительная задача, поэтому ваш скрипт работает часами.Вы можете попытаться распараллелить его с CUDA или с чем-то похожим, или вы можете попытаться создать большой кеш (ГБ).Но если вы не можете или не хотите, я советую вам не использовать функции networkx / igraph, потому что они очень медленные для вас.Вы можете решить свою проблему без 1000000 запусков DFS.Вот одно из возможных решений с использованием наборов Python (думаю, это будет быстрее, чем у вас, может быть, не очень).

import networkx as nx

# Create a graph like yours
G = nx.fast_gnp_random_graph(1000, 0.05)

# Create neighbours dict
G_adj = dict(G.adjacency())
nbrs_dict = {node: {n for n in G_adj[node]} for node in G_adj}

# Result dict
distances = {}

# For every edge:
for e in G.edges:

    # Start value
    dist_value = 0

    # Get N1 and N2 neighbours
    n1_nbrs = nbrs_dict[e[0]]
    n2_nbrs = nbrs_dict[e[1]]

    # Triangles - nodes that connected to both N1 and N2
    # Every triangle value = 0
    tri = n1_nbrs & n2_nbrs
    for t in tri:

        # Get neighbours to find nodes with distance length = 2
        t_nbrs = nbrs_dict[t]

        t_in_n1 = n1_nbrs & t_nbrs
        t_in_n2 = n2_nbrs & t_nbrs

        t_not_in_n1 = n1_nbrs - t_nbrs
        t_not_in_n2 = n2_nbrs - t_nbrs

        dist_value += len(t_in_n1) + len(t_in_n2)
        dist_value += (2 * len(t_not_in_n1)) + (2 * len(t_not_in_n2))

    # Exclude all triangle nodes because we processed them all
    n1nt_nbrs = n1_nbrs - tri
    n2nt_nbrs = n2_nbrs - tri

    # Select squares - nodes with length = 1
    direct = set([])
    for n1 in n1nt_nbrs:
        nbrs = nbrs_dict[n1]
        d = nbrs & n2nt_nbrs
        for node in d:
            direct.add((n1, node))
    dist_value += len(direct)

    # Exclude squares so we have only nodes with length = 3
    n1final = n1nt_nbrs - set(e[0] for e in direct)
    n2final = n2nt_nbrs - set(e[1] for e in direct)
    dist_value += 3 * len(n1final) * len(n2final)

    # Distance for an edge
    distances[e] = dist_value

В любом случае, ваша проблема имеет сложность O(n^3), поэтому я настоятельно рекомендую вам попробовать разбить ваш график.Возможно, у вас мостов или просто несколько подключенных компонентов.Если вы будете обрабатывать их отдельно, вы невероятно увеличите свою скорость.

...