Получить отключенные пары узлов в сетевом графе? - PullRequest
Новая
       36

Получить отключенные пары узлов в сетевом графе?

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

Это мой набор данных: 

4095    546
3213    2059 
4897    2661 
...
3586    2583
3437    3317
3364    1216

Каждая строка - это пара узлов, между которыми есть ребро. Весь набор данных построить график. Но я хочу получить много пар узлов, которые не связаны друг с другом. Как я могу получить 1000 (или более) таких пар узлов из набора данных? Такие как: 

2761    2788
4777    3365
3631    3553
...
3717    4074
3013    2225

Каждая строка представляет собой пару узлов без ребра.

Ответы [ 2 ]

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

Пожалуйста, смотрите часть под РЕДАКТИРОВАТЬ!

Я думаю, что другие варианты более общие и, вероятно, более приятные с программной точки зрения. Я только что быстро понял, как вы можете получить список очень простым способом, используя numpy.

Сначала создайте матрицу смежности, и ваш список узлов будет массивом: 

    import numpy as np
    node_list= np.random.randint(10 , size=(10, 2))
    A = np.zeros((np.max(node_list) + 1, np.max(node_list) + 1)) # + 1 to account for zero indexing
    A[node_list[:, 0],  node_list[:, 1]] = 1 # set connected nodes to 1
    x, y = np.where(A == 0) # Find disconnected nodes
    disconnected_list = np.vstack([x, y]).T # The final list of disconnected nodes

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

РЕДАКТИРОВАТЬ: Приведенное выше решение заставило меня задуматься слишком быстро. На данный момент решение выше обеспечивает пропущенные ребра между узлами, а не разъединенные узлы (в случае ориентированного графа). Кроме того, disconnected_list включает каждый узел дважды. Вот еще одна хакерская идея решения: 

    import numpy as np
    node_list= np.random.randint(10 , size=(10, 2))
    A = np.zeros((np.max(node_list) + 1, np.max(node_list) + 1)) # + 1 to account for zero indexing
    A[node_list[:, 0], node_list[:, 1]] = 1 # set connected nodes to 1 
    A[node_list[:, 1], node_list[:, 0]] = 1 # Make the graph symmetric
    A = A + np.triu(np.ones(A.shape)) # Add ones to the upper triangular
    # matrix, so they are not considered in np.where (set k if you want to consider the diagonal)
    x, y = np.where(A == 0) # Find disconnected nodes
    disconnected_list = np.vstack([x, y]).T # The final list of disconnected nodes
0 голосов
/ 08 ноября 2018

Просто сделайте BFS или DFS, чтобы получить размер каждого подключенного компонента за O(|E|) время. Затем, получив размеры компонентов, вы можете легко получить количество отключенных узлов: это сумма произведений каждой пары размеров.

* * 1003 Eg. Если ваш график имеет 3 связанных компонента с размерами: 50, 20, 100. Тогда количество пар отключенных узлов: 50*20 + 50*100 + 20*100 = 8000.

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

...