Описание тега strongly-connected-graph
1
ответ
Неправильно подключен компонент Тарьяна или мой код неверен?
Я пытаюсь реализовать алгоритм сильно связанного графа Тарьяна ( https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm), вот мой код, и я не понимаю, почему вершина 4 и вершина 5 также выводятся как сильно связанные компон…
07 янв '17 в 23:20
3
ответа
Визуализация сильно связанных компонентов в результате использования Cypher
Я использовал neo4j-mazerunner для анализа отношения strong_connected_components на моем графике. Процесс завершился, и теперь я получил свойство strong_connected_components на своих узлах. Я использовал следующий запрос, чтобы получить строки узлов…
05 дек '16 в 09:50
2
ответа
Сделайте уже существующий график полностью подключенным
У меня есть график этой структуры: G = { '1':['100', '134', '1435'], '145':['4', '2345', '253'], '3773':['12'], '773':['1211', '629']} График на самом деле очень большой, с 6378 узлами и 39932 ребрами. Моя проблема в том, что график отключен, и я хо…
15 янв '19 в 22:28
2
ответа
Как найти сильно связанные компоненты в графике?
Я пытаюсь самостоятельно изучить теорию графов, и теперь пытаюсь понять, как найти SCC в графе. Я прочитал несколько разных вопросов / ответов по SO (например, 1, 2, 3, 4, 5, 6, 7, 8), но я не могу найти один с полным пошаговым примером, которому я …
08 ноя '15 в 05:11
1
ответ
Почему я получаю StackOverFlowError при попытке DFS на этом графике найти сильно связанный компонент?
Я пытаюсь написать алгоритм, который определяет, сильно ли связан граф или нет. Я думаю, что мой код почти правильный, хотя я продолжаю получать StackOverFlowError. Я лично думаю, что из-за цикла в графе, с которым я тестирую свой алгоритм, мой код …
12 май '18 в 04:46
0
ответов
Networkx дает строго связанную проверку, не определенную
Я использую networkx(первый раз), чтобы проверить, что граф сильно связан или нет, но я понимаю, что он не определен. Как указано в документе, это должно работать. Мой пробег: import networkx as nx G = nx.DiGraph() w = [(0, 1), (0, 3), (0, 4), (2,4)…
30 ноя '15 в 07:18
1
ответ
Алгоритм, чтобы найти путь, который посещает каждую вершину в ориентированном графе, по крайней мере, один раз
У меня есть SCC ориентированного графа. Я хочу найти путь, который посещает каждую вершину в этом SCC хотя бы один раз, начиная с вершины s. Я знаю, что это может быть проблемой NP. Независимо от того, как я могу решить это?
08 ноя '17 в 06:45
2
ответа
Сильно компонент
Я пытаюсь написать алгоритм с графом G и двумя узлами "x" и "y" в качестве ввода, который возвращает информацию о том, существует ли циклический путь от "x" до "y" Является ли хорошей идеей сначала найти сильно связанные компоненты, а затем проверит…
25 окт '17 в 18:18
1
ответ
Нахождение дуг между сильно связанными компонентами
Имея график и все его сильно связанные компоненты, мне было интересно, какой самый эффективный способ найти дуги, соединяющие два SCC. Все решения, которые я нашел, включают в себя прохождение всех узлов, и мне было интересно, есть ли способ сделать…
18 мар '18 в 21:20
1
ответ
Является ли сильно связная компонента SCC в теории графов DAG?
Я пытался решить проблему, чтобы разработать алгоритм, чтобы определить, является ли прямой граф полусвязным. Кто-то говорит, что это можно сделать с помощью топологической сортировки каждого SCC в графе. И SCC гарантированно будет DAG. Тем не менее…
17 ноя '18 в 17:31
2
ответа
DFS быстрее, чем BFS при поиске определенного узла в SSC?
Я хочу найти кратчайший путь от узла к другому узлу в Сильно Связанном Компоненте, узлы могут быть выбраны произвольно. На ум приходят два метода поиска: поиск в глубину или поиск в ширину.Можно ли доказать, что для какой-то ситуации одно предпочтит…
07 ноя '18 в 16:43
1
ответ
Как извлечь матрицу смежности гигантского компонента графа, используя R?
Я хотел бы извлечь матрицу смежности гигантского компонента графа, используя R. Например, я могу создать Erdos-Renyi g(n,p) n = 100 p = 1.5/n g = erdos.renyi.game(n, p) coords = layout.fruchterman.reingold(g) plot(g, layout=coords, vertex.size = 3, …
08 июн '18 в 03:19
1
ответ
Пользовательский вывод edgelist в сети x
Я пытаюсь реализовать алгоритм Тарьян для практики. Я решил сгенерировать случайный граф, чтобы дать в качестве входных данных для алгоритма, добавляя по одному ребру за раз. Я сгенерировал случайный график и сохранил его в файле, как показано ниже …
02 май '17 в 20:03
3
ответа
Сильно связанные компоненты: алгоритм Косараю
В алгоритме Косараю я натолкнулся на две возможные реализации: 1) Поиск сильно связных компонент в обращенном графе в топологическом порядке вершин исходного графа. 2) Поиск сильно связных компонент в исходном графе в топологическом порядке вершин в…
02 ноя '18 в 05:16
0
ответов
Перестал работать pythonw.exe
Я реализую двухпроходный алгоритм Косараю, который может вычислять сильно связанные компоненты в ориентированном графе. Я могу получить правильный результат с небольшими входными данными, но когда входные данные больше ( 70M TXT, предупреждение! Это…
19 янв '17 в 00:25
1
ответ
Нахождение максимального количества узлов сильно связаны, учитывая количество узлов и ребер
"Учитывая количество узлов и количество ребер, соединяющих эти узлы, расположите эти ребра так, чтобы максимальное количество узлов было сильно связано. Верните количество узлов, которые могут быть сильно связаны". Мне интересно, есть ли формула для…
17 дек '17 в 07:38
1
ответ
Как получить сильно связанные компоненты с сетью из графа?
У меня есть график, случайно сгенерированный с networkx, Я хочу извлечь из этого графика сильно связанные компоненты. Почему у меня только один большой scc, использующий встроенный networkx функционировать? n = random.randint(10, 500) p = random.ran…
09 июл '18 в 22:07
2
ответа
Как построить массив, чтобы представить отношения узлов в сильно связанном компоненте?
Для ориентированного графа G(V, E) с n узлами я хочу создать целочисленный массив a, а его длина равна n. Если есть путь от узла 1 до 2, то a[1] <= a[2], если они находятся в одном и том же сильно связанном компоненте a[1] = a[2], если нет пути о…
02 фев '18 в 17:49
3
ответа
Как узнать, существует ли путь от одного SCC к другому?
Для графа, после нахождения сильно связанных компонентов, как найти количество SCC, которые имеют путь друг к другу? Я хочу найти, если есть путь к SCC2 от SCC1.
04 ноя '17 в 21:17
2
ответа
Можно ли сгенерировать время окончания алгоритма Косараджу из исходного графика, а не из обратного графика?
В алгоритме Косараджу время окончания генерируется из обращенного графика. Затем сильно связанные компоненты обнаруживаются из исходного графа, выполняя DFS, начиная с самого большого до самого низкого времени окончания, созданного ранее. Можно ли с…
03 авг '16 в 00:36