Вопросы по теме 'directed-acyclic-graphs'
График DAG, сгенерированный make?
Насколько я понимаю, когда make выполняется, он внутри генерирует DAG для представления всех зависимостей в проекте. Есть ли способ добраться до этого DAG и построить его график, скажем, используя что-то вроде graphviz?
Я использую gnu make на...
3114 просмотров
schedule
15.10.2023
Выборка случайных узлов из DAG
У меня есть большой ориентированный ациклический граф (DAG), из которого я хотел бы эффективно нарисовать образец узла в соответствии со следующими критериями:
Я указываю фиксированный узел A, который никогда не должен отбираться
Узлы, которые...
302 просмотров
schedule
12.08.2023
Как работает «git log --graph» или «hg graphlog»?
Я знаю, что история в Git хранится в структуре данных, называемой DAG. Я слышал о DFS и знаю, что это несколько связано.
Мне интересно, а как программы типа git log --graph или hg graphlog рисуют историю? Я всегда думал, что очень сложно...
5088 просмотров
schedule
24.10.2023
Способы отображения ориентированного ациклического графа на сетку/матрицу
У меня есть DAG со многими тысячами вершин и ребер.
Я ищу алгоритмы, которые могут располагать вершины в точках сетки таким образом, чтобы это было наиболее удобно/эстетично для человека. Моя догадка заключается в том, что наилучший макет будет...
754 просмотров
schedule
26.10.2023
Существует ли формализм для этой структуры данных?
Я ищу математический формализм для структуры данных, с которой я работаю, чтобы я мог отслеживать соответствующие теоремы и алгоритмы.
Предположим, у вас есть следующее:
Ориентированный ациклический граф тем.
В каждой теме существует одно...
333 просмотров
schedule
28.05.2022
алгоритм - Как решить арифметическое выражение DAG?
В Руководстве по разработке алгоритмов есть два связанных акциза.
В принципе, я знаю, как решить первый акциз, но я не знаю, как решить второй, используя решение первого в качестве подсказки .
Удаление арифметического выражения дерево...
7149 просмотров
schedule
04.06.2022
Самый длинный путь для взвешенного ориентированного ациклического графа
Я пытаюсь осмыслить эту проблему, а затем написать для нее код Java. Я знаю, что здесь было какое-то обсуждение, но я не вижу много ответов, поэтому я хотел бы повторить вопрос, записав свои мысли, и я надеюсь получить от вас отзывы, ребята....
3677 просмотров
schedule
06.12.2023
DAG: минимизация расстояния между записями в сгруппированных узлах
У меня есть направленный ациклический граф с узлами, которые представляют собой списки записей, которые соединяются с записями в других узлах. Вроде этого:
entry ]
entry--| ] node 1
entry | ]
----- |
entry<-| ] node 2
entry | ]...
152 просмотров
schedule
16.03.2023
является ли ориентированный граф предпочтительного присоединения графа ацикличным?
Я генерирую графики, используя модель Барабаши-Альберта, реализованную igraph:
Graph.Barabasi(10,5,directed=True)
Как я могу быть уверен, что сгенерированные ориентированные графы ацикличны? Есть ли какое-то основное свойство, которое...
534 просмотров
schedule
12.06.2022
Построение алгоритма всех путей для DAG
Пытался создать метод, который получает все мыслимые уникальные пути через DAG. Пошел с рекурсией, потому что это казалось самым простым для понимания. Закончилось этим:
public class Brutus {
//the previous nodes visited
public...
1928 просмотров
schedule
05.11.2023
Реализация объектно-ориентированных графов в С++
Мне нужно реализовать симуляцию WWW на С++ с использованием графов, где узлы — это веб-страницы, а направленные ребра — это URL-адреса.
В школе, на нашем уровне, мы еще начинаем с объектно-ориентированного программирования, поэтому они предложили...
999 просмотров
schedule
21.12.2023
Найдите путь минимальной дисперсии в направленном ациклическом графе
Дана DAG, в которой каждый узел имеет числовое значение. Я хотел бы получить путь через граф, который имеет минимальную дисперсию значений узлов.
Напомним, какой алгоритм является лучшим для поиска пути с минимальной дисперсией в направленном...
98 просмотров
schedule
25.06.2023
Создатель Apache Spark DAG
Может ли кто-нибудь помочь мне с классом, который занимается созданием DAG в apache spark. Я пытался просмотреть документацию и основные библиотеки, но не смог найти классы, связанные с созданием DAG.
https://github.com/apache/spark
358 просмотров
schedule
11.06.2023
Алгоритм линейного времени для количества различных путей из каждой вершины в ориентированном ациклическом графе
Я работаю над следующим прошлым бумажным вопросом для модуля алгоритмов:
Пусть G = (V, E) — простой ориентированный ациклический граф (DAG). Для пары вершин v, u в V мы говорим, что v достижима из u, если существует (направленный) путь из u в v в...
1313 просмотров
schedule
22.02.2022
Кодирование ориентированного графа в виде чисел
Допустим, у меня есть ориентированный граф с одним корнем и без циклов. Я хотел бы добавить тип для каждого узла (например, как целое число с некоторым настраиваемым порядком) со следующим свойством:
if Node1.type <= Node2.type then there...
888 просмотров
schedule
29.07.2022
Обновление графика JGraphT работает неправильно
Я пытаюсь реализовать своего рода метод суммирования графа, где я проверяю, есть ли у узла какие-либо дочерние элементы или нет, если нет, то узел сворачивается в своего родителя. У меня есть 2 фрагмента кода для этого, но один из них не работает...
293 просмотров
schedule
28.06.2023
Кратчайший путь прямого ациклического графа за N шагов
У меня проблема с поиском кратчайшего пути в положительно взвешенном направленном ациклическом графе, но с ограничением максимального количества шагов N (ребер на пути). Предполагается, что путь существует. Дополнительным свойством графа является...
412 просмотров
schedule
29.10.2022
Как реализован направленный ациклический граф в Hadoop или Spark?
Я продолжаю получать термин DAG в разных контекстах в экосистеме Hadoop, например
когда какое-либо действие вызывается в RDD, Spark создает DAG и отправляет его планировщику DAG.
or
Модель DAG является строгим обобщением модели...
1023 просмотров
schedule
20.04.2023
Кратчайший путь DAG против алгоритма Дейкстры
Я реализовал алгоритм Дейкстры из псевдокода, найденного в справочнике «Введение в алгоритмы», 3-е издание Кормена, для задачи поиска кратчайшего пути с одним источником.
Моя реализация была сделана на python с использованием связанных списков для...
2050 просмотров
schedule
02.07.2022
очистить восходящую задачу в воздушном потоке внутри dag
у меня задача в даге воздушного потока. у него есть три дочерних задачи. К сожалению, бывают случаи, когда эта родительская задача завершается успешно, но два из трех дочерних элементов завершаются неудачно (и повторная попытка для дочерних...
3042 просмотров
schedule
13.09.2022