Вопросы по теме 'graph-traversal'
Все пары все пути на графе
Возможно, это проблема, для которой нет оптимального решения. Предположим, у меня есть ориентированный граф, и я не знаю, есть ли у него циклы или нет (обнаружение циклов будет одним из аспектов этой проблемы). Учитывая набор вершин (возможно,...
4875 просмотров
schedule
29.08.2022
Как реализовать DFS с неизменяемыми типами данных
Я пытаюсь найти аккуратный способ обхода графа в стиле Scala, желательно с vals и неизменяемыми типами данных.
Учитывая следующий график,
val graph = Map(0 -> Set(1),
1 -> Set(2),
2 -> Set(0, 3, 4),...
5200 просмотров
schedule
07.03.2023
Найти все обходы BFS/DFS
Учитывая неориентированный циклический граф, я хочу найти все возможные обходы с помощью поиска в ширину или поиска в глубину. Это дается граф в виде списка смежности:
A-BC
B-A
C-ADE
D-C
E-C
Таким образом, все пути BFS от корня A будут...
2879 просмотров
schedule
06.08.2022
Поиск (гарантированно уникального) пути между двумя узлами в дереве
У меня есть (вероятно) простой вопрос обхода графа. Я новичок в графике, используя networkx в качестве структур данных графа. Мои графики всегда выглядят так:
0
1 8
2 3 9 10
4 5 6 7 11...
3151 просмотров
schedule
12.11.2022
Нужна помощь в параллельном обходе дага в D
Изменить: хорошо, вот гораздо более простой пример, иллюстрирующий мою проблему. почему в очередь ставится только первая задача?
import std.stdio;
import std.parallelism;
void simpleWorker(uint depth, uint maxDepth, TaskPool pool){...
255 просмотров
schedule
29.10.2022
Neo4j, какой обход следует использовать?
Сейчас я пробую учебник Neo4J Koan . Я действительно запутался в Koan06, где представлены Traversal . Метод Node.traversal устарел в пользу Traversal.traverse . Когда я попробовал, я увидел, что весь класс Traversal тоже устарел. Я прочитал...
807 просмотров
schedule
19.10.2022
Назад Ребра в дереве поиска графа в глубину
У меня есть домашнее задание, которое я выполнил, и около 3 баллов из 100 я получил за следующий вопрос.
«Предположим, вы строите дерево в глубину на ориентированном графе. Впоследствии вы замечаете, что нет никаких задних ребер. Что это...
616 просмотров
schedule
07.04.2022
Случайное блуждание по двудольному графу с Гремлином
Я хотел бы ранжировать элементы в соответствии с предпочтениями пользователя (элементы, которые нравятся пользователю) на основе случайного блуждания по ориентированному двудольному графу с использованием gremlin в Groovy.
Граф имеет следующую...
672 просмотров
schedule
11.06.2022
Учитывая DAG, удалите узлы, присутствующие исключительно в путях короче длины 3.
Я работаю с ориентированными ациклическими графами в networkx. У меня есть графики, которые выглядят как на рисунке ниже.
По сути, я хочу удалить из этого графа все узлы, которые связаны исключительно с путями длиной менее 3. Например, на...
235 просмотров
schedule
12.03.2023
Увеличивает ли добавление ребер в Neo4j обработку, необходимую для всех запросов?
Я пытаюсь разработать схему базы данных для Neo4j. Есть несколько способов сделать это. Я мог бы поместить данные как 1) свойства узла или 2) как ребра, указывающие на узел . Второй вариант намного мощнее с точки зрения того, как я могу...
85 просмотров
schedule
01.12.2023
эффективный параллельный алгоритм для обновления стоимости прохождения для всех простых путей во взвешенном ориентированном графе
Я работаю с относительно небольшими ориентированными графами (~ 10 узлов), каждый из которых имеет ~ 10 000 простых путей и циклов. Я хотел бы вести отсортированный список совокупных затрат для прохождения всех этих простых путей и циклов. Мои ребра...
140 просмотров
schedule
02.05.2022
Обход DAG + стоимость в Прологе
Я пытаюсь реализовать алгоритм обхода DAG, который также получает затраты между ребрами. Я думаю, что я довольно близок, но запросы всегда возвращают недопустимые пути. Может ли кто-нибудь взглянуть и увидеть, что мне здесь не хватает?
edge(b,...
607 просмотров
schedule
15.03.2023
Как реализовать поиск в глубину на ориентированном графе, чтобы посетить все вершины
Как мы выполняем поиск в глубину на ориентированном графе, используя матрицу смежности, в которой он исследует все вершины, начиная со случайной вершины? Я попытался реализовать dfs, но он исследует только вершины, достижимые из начальной вершины....
456 просмотров
schedule
29.03.2023
Как удалить все пути, проходящие через конкретный документ или вершину во время обхода графа в ArangoDB
Я пытаюсь выполнить обход графа здесь
Я создал две коллекции в ArangoDB: коллекцию документов "Node" и коллекцию краев "Path" . Все мои узлы имеют атрибут name (метки) и соединены ребрами (линиями), как показано на рисунке выше.
Я...
61 просмотров
schedule
22.07.2023
Пользовательские посетители и пользовательские расширители в arangodb
Глядя на документацию, он говорит, что модуль обхода (@arangodb/graph/traversal) устарел с версии 3.4.0. Есть ли другой способ использовать настраиваемых посетителей и расширителей так, как это было доступно в этом модуле?
47 просмотров
schedule
25.02.2023
SQL-запрос для топологической сортировки
У меня есть ориентированный ациклический граф:
DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);
Я хочу перечислить все узлы, всегда перечисляя узел до его...
294 просмотров
schedule
24.02.2023
Как отследить путь, который посещает все узлы в bfs/dfs
Это похоже на Как проследить путь в ширине -First Search? , но метод, описанный в ответах в этом посте, похоже, не работает для моего случая.
Под путем здесь я, по сути, подразумеваю последовательность соединенных узлов, чтобы добраться от...
804 просмотров
schedule
01.07.2022
Все строки, кроме последней внутри цикла for, пропускаются
В настоящее время я пишу алгоритм рекурсии, который проходит между узлами (DFT). Но происходит что-то действительно странное, мой цикл for each пропускает пару строк внутри него, а печатает только то, что идет после оператора if внутри него.
Вот...
44 просмотров
schedule
29.04.2022
Извлеките узлы в пути графа, упорядоченном по отношению
Мне поручено найти путь и обработать узлы в нем, соблюдая их порядок на том же пути (таким образом, порядок определяется отношением).
Дан граф со следующими узлами:
CREATE (a:temporary {name: 'm2'});
CREATE (a:temporary {name: 'f1'});
CREATE...
48 просмотров
schedule
05.06.2023