-
1 votesanswersviews
Apache Airflow调度程序不会在计划时触发DAG
当我计划每天在特定时间运行DAG时，DAG执行根本不会发生 . 但是，当我重新启动Airflow网络服务器和调度程序时，DAG在该特定日期的预定时间执行一次，并且从第二天开始不执行 . 我使用的是带有python 2.7.6的Airflow版本v1.7.1.3 . 这里是DAG代码： from airflow import DAG from airflow.operators.bash_opera... -
4 votesanswersviews
如何调用DAG拓扑重组？
我很长时间对直接无环图（DAG）感兴趣，在阅读维基百科的拓扑排序之后，我没有发现任何涉及 layers numbering 的方法的特别提及（尽管图中广泛提到了绘图） . 使用这种方法，图形在技术上不是拓扑排序的，但是知道每个节点包含层（级别）的正确数字，我们总是可以判断特定节点"bigger"是否在拓扑上 . 另一方面，只要我们没有有序列表，我们就无法在拓扑上枚举节点（尽管这... -
0 votesanswersviews
计算有向非循环图中的传入边
给定有向非循环图（DAG），是否存在一个在 linear time 中运行的算法，该算法计算每个顶点（以及该边缘的源）的入度，假定我们知道一个根节点（从中可以得到一个节点）到达每个其他顶点）？ -
26 votesanswersviews
在有向无环图中找到最低共同祖先的算法？
想象一下有向无环图如下，其中： "A"是根（总是只有一个根） 每个节点都知道其父节点 节点名称是任意的 - 没有什么可以从它们推断出来 我们从另一个来源得知节点是按照A到G的顺序添加到树中的（例如它们是版本控制系统中的提交） 我可以使用什么算法来确定两个任意节点的最低共同祖先（LCA），例如，共同的祖先： B和E是B. D和F是B. 注意： ... -
0 votesanswersviews
在N步骤内的DIrected非循环图最短路径
我有一个问题，即在正加权有向无环图中找到最短路径，但是限制了最大N步数（路径中的边） . 假设路径存在 . 该图的附加属性是如果边（i，j）在图中，那么任何边（i，k）也在i <k <j的图中 . 我只对图的开始和结束之间的最短路径感兴趣（在拓扑排序之后） . 我知道有一种有效的算法用于O（V E）中有向无环图中的最短路径，但它没有考虑步长限制 . 我想不出任何方法可以使它成为O（（V... -
9 votesanswersviews
DAG中最长的路径
为了找到DAG中最长的路径，我知道2种算法：算法1：做拓扑排序使用动态编程对sort〜或〜算法2的结果：使用DFS枚举DAG中的所有路径，并且记录时间最长 . 似乎列举所有DFS路径比算法更复杂1.这是真的吗？ -
2 votesanswersviews
如何从固定节点开始获取DAG中最长的路径？
我想知道如何从节点0（最小节点）开始在DAG中获取最长路径 我搜索了wiki并得到了以下算法： algorithm dag-longest-path is input: Directed acyclic graph G output: Length of the longest path length_to = array with |V(G)| elements of ... -
-1 votesanswersviews
NetworkX在开始顶点找到DAG中最长路径而没有错误的最有效方法
从某个顶点开始，如何找到相对于该顶点的最长路径？我一直在浏览，无法找到这个问题的解决方案，这个问题实际上适用于所有可能的DAG案例 . NetworkX中的源代码是首选，但常规的python也很好 . 我真的很好奇为什么我无法找到任何正确的工作示例，我确实理解这是一个NP型问题，但我想知道它最有效的方式 . -
5 votesanswersviews
DAG - 确保存在单个源和单个接收器的算法
我必须确保我们的应用程序中的图形是具有唯一源和独特接收器的DAG . 具体而言，我必须确保对于给定的起始节点和结束节点（两者都在一开始就知道），图中的每个节点都位于从起始节点到结束节点的路径上 . 我已经有一个Tarjan算法的实现，我用它来识别周期，一个拓扑排序算法，我可以运行一旦Tarjan的算法报告图是一个DAG . 确保图表符合此标准的最有效方法是什么？ -
0 votesanswersviews
从循环图中提取树/ DAG
给定有向循环图，如何获得代表输入图的各种DAG /树？实际上，我想从给定的电路（定向和循环）图中提取各种树 . 任何帮助将不胜感激 . -
2 votesanswersviews
将循环转换为非循环图
我想将循环图转换为非循环图 . 是否有伪代码可以做到这一点？我确实尝试过搜索，但大部分都是基于马尔可夫链或研究文章返回的数学 . 我想写一个程序来做它，任何方向都会有用 . 例如，请考虑下面的图表 . A->B B->C C->A 我在一个讲座中看到了一个解决方案，但是讲座中提到了一些解决方案，并参考了之前教过的内容并且无法理解 . 简而言之，它以一种方式复制层中的节点，结束图... -
2 votesanswersviews
NetworkX：在DAG中查找最长路径，返回所有关联最大值
我无法弄清楚如何更新networkx dag_find_longest_path（）算法以返回绑定“N”而不是返回找到的第一个最大边缘，或者返回所有与最大权重相关的边缘列表 . 我首先从pandas dataframe创建了一个DAG，它包含一个像下列子集一样的边缘列表： edge1 edge2 weight 115252161:T 115252162:A ... -
0 votesanswersviews
具有重复有序节点和/或边的Python Networkx或igraph DAG
问题 我正在努力构建基因组学中我们称之为“变体图”的东西，而我无法弄清楚如何使用Networkx做到这一点 . 我愿意创建自己的代码或其他图形包 . 目的 总体目的是比较下面的两个图表来计算在每个位置发现核苷酸（A，G，T，C）的次数，然后返回每个位置具有最高计数的字母以创建共有序列 . 参考图 首先，我需要构建一个图形，首先创建一个参考图形，如上面第一行所示，跟踪每个位置的字母（核苷酸） . ... -
3 votesanswersviews
针对傻瓜的迭代/动态拓扑排序
我目前正在C中实现动态DAG图 - 将通过UI向用户显示，并且节点/边的插入/移除将是常见操作 . 图表的大小可能从真正的小规模到大规模 - 我的目标是支持数百万个节点 . 因此，我正在寻找一种最佳的数据结构，它不会在内存中占用太多空间，而且还可以通过拓扑排序的节点进行快速插入/删除以及快速多线程迭代（因此需要多个节点）可以并行执行） . 我没有做过任何剖析，看看每次进行修改时重新计算完整图形的拓...