标签: directed-graph

检测有向图中所有周期的最有效算法是什么？

我有一个有向图表示需要执行的作业计划,作业是节点,依赖是边缘.我需要检测此图中循环的错误情况,从而导致循环依赖.

在DOT语言中GraphViz,我试图表示一个依赖关系图.我需要能够在容器内部拥有节点,并且能够使节点和/或容器依赖于其他节点和/或容器.

我subgraph用来代表我的容器.节点链接工作正常,但我无法弄清楚如何连接子图.

鉴于下面的程序,我需要能够连接cluster_1并cluster_2使用箭头,但我尝试过的任何东西都会创建新节点而不是连接集群:

digraph G {

    graph [fontsize=10 fontname="Verdana"];
    node [shape=record fontsize=10 fontname="Verdana"];

    subgraph cluster_0 {
        node [style=filled];
        "Item 1" "Item 2";
        label = "Container A";
        color=blue;
    }

    subgraph cluster_1 {
        node [style=filled];
        "Item 3" "Item 4";
        label = "Container B";
        color=blue;
    }

    subgraph cluster_2 {
        node [style=filled];
        "Item 5" "Item 6";
        label = "Container C";
        color=blue;
    }

    // Renders fine
    "Item 1" -> "Item 2";
    "Item 2" -> "Item …

如何检查有向图是否是非循环的？算法如何调用？我很感激参考.

我正在寻找一种简单的算法来"序列化"有向图.特别是我有一组在执行顺序上具有相互依赖性的文件,我想在编译时找到正确的顺序.我知道它必须是一件相当普遍的事情 - 编译器会一直这样做 - 但我的google-fu今天一直很弱.什么是'go-to'算法？

我想到等待图表,我想知道,是否有任何有效的算法来检测是否向有向图添加边缘会导致循环？

有问题的图是可变的(它们可以添加或删除节点和边).而且我们对实际知道一个有问题的周期并不感兴趣,只知道有一个是足够的(以防止添加一个有问题的边缘).

当然,可以使用算法来计算强连接组件(例如Tarjan)以检查新图是否是非循环的,但每次添加边时再次运行它似乎效率很低.

通过这里的图表我的意思是类似这些图像的东西:

理想的解决方案是:

• 仅使用托管代码
• 允许输出到位图图像
• 允许输出到WPF元素
• 包括某种交互式表面,用于显示支持节点缩放,平移和重组的图形

我也有兴趣了解可能被用作此类工作起点的项目.如果需要一些开发来实现我想要的东西,那么我已经准备好解决它了.这个目标中最复杂的部分似乎是在合理的时间范围内获得图形布局.

这是tarjan循环检测的一个有效的C#实现.

该算法可在此处找到:http: //en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

public class TarjanCycleDetect
    {
        private static List<List<Vertex>> StronglyConnectedComponents;
        private static Stack<Vertex> S;
        private static int index;
        private static DepGraph dg;
        public static List<List<Vertex>> DetectCycle(DepGraph g)
        {
            StronglyConnectedComponents = new List<List<Vertex>>();
            index = 0;
            S = new Stack<Vertex>();
            dg = g;
            foreach (Vertex v in g.vertices)
            {
                if (v.index < 0)
                {
                    strongconnect(v);
                }
            }
            return StronglyConnectedComponents;
        }

        private static void strongconnect(Vertex v)
        {
            v.index = index;
            v.lowlink = index;
            index++;
            S.Push(v);

            foreach (Vertex w in …

我试图networkx在项目中使用一些图形表示,我不知道如何做一些应该简单的事情.我创建了一个带有一堆节点和边的有向图,这样在这个图中只有一个根元素.现在,我想做的是从根开始,然后遍历每个元素的子元素并从中提取一些信息.我如何获得这个DiGraph的根元素？

所以它会是这样的:

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do

    root = myDiGraph.root()
    for child in root.children():
        iterateThroughChildren(child)

def iterateThroughChildren(parent):
    if parent.hasNoChildren(): return
    for child in parent.children():
        //do something
        //
        iterateThroughChildren(child)

我没有在文档中看到任何提示检索DiGraph根的简单方法 - 我应该手动推断这个吗？:O我试着iter(myDiGraph)希望它会从根开始迭代,但顺序似乎是随机的......:\

将不胜感激,谢谢!

我想实现一个节点接口,基本上是一个DAG,每个节点在它的输入连接上执行操作,并输出一些东西(你可以连接到另一个节点)

一些示例应用:

• Apples"Shake" - 截图
• The Foundrys"Nuke" - 截图
• MindNode - 截图
• vvvv - 截图
• Quartz Composer - 截图

作为第一个目标,我想拥有一个只有2个节点的图形应用程序.一个简单输出一个固定数字的"数字"和一个"加"节点,它取两个输入并输出两者之和.

正如人们已经回答的那样,我对如何在代码中表示数据有一个粗略的想法,例如在Python中寻找伪代码:

class Number:
    def __init__(self, value):
        self.value = value

    def eval(self):
        return self.value

class Add:
    def __init__(self, input1, input2):
        self.input1 = input1
        self.input2 = input2

    def eval(self):
        return self.input1.eval() + self.input2.eval()


a = Number(20)
b = Number(72)

adder = Add(a, b)
print adder.eval()

我如何围绕此包装自定义GUI？像下面的东西,但略少手绘!

我从哪里开始？我目前打算用Objective-C/Cocoa编写它,尽管我对其他语言的建议不仅仅是开放的.

有关Graphviz Library中dot的算法是否有任何文档(完整的伪代码？)？

我只找到了一些部分伪代码文档.