标签: directed-graph

我需要在Clojure中表示有向图.我想将图中的每个节点表示为一个对象(可能是一个记录),其中包含一个名为" :edges可以从当前节点直接访问的节点集合"的字段.希望不言而喻,但我希望这些图表是不可改变的.

只要我进行拓扑排序并"从叶子上"构建每个图形,我就可以用这种方法构造有向无环图.

但是,这种方法不适用于循环图.我能想到的一个解决方法是为整个图形设置一个单独的集合(可能是地图或矢量).然后:edges,每个节点中的字段将具有键(或索引)到图的边集合中.添加这种额外的间接级别是有效的,因为我可以在他们(将)引用的东西之前创建密钥(或索引),但它感觉就像一个kludge.每当我想要访问一个相邻节点时,我不仅需要进行额外的查找,而且还必须传递全局边缘集合,这感觉非常笨拙.

我听说有些Lisps有办法创建循环列表而不需要使用变异函数.有没有办法在Clojure中创建不可变的循环数据结构？

(有向)图表代表有限自动机.到目前为止,我的测试程序已经写出了用于测试的点文件.这对于回归测试(将验证的输出文件保存在subversion中,询问是否存在更改)和可视化都非常好.但是,有一些问题......

基本上,我想要一些可以从C++中调用的东西,它可以为我的状态和过渡计划一个布局,但是将绘图留给我 - 这将允许我绘制我想要的东西并在GUI(wxWidgets)窗口上绘制.

我还想要一个允许商业用途的许可证 - 我目前不需要它,我可能很好地作为开源发布,但我不想限制我的选择ATM.

GraphViz的问题是(1)关于在Windows上从源构建的警告,(2)用于呈现和解析的所有不必要的依赖性,以及(3)(假定的)缺少具体且纯粹用于布局的文档API.

基本上,我希望能够指定我的状态(具有边界矩形大小)和过渡,并读出每个过渡的状态和航点的位置,然后基于这些坐标自己绘制.我还没有弄清楚应该如何处理转换上的注释,但应该有一些规定来为那些指定边界框大小,将它们与转换相关联,以及读出位置.

有谁知道可以处理这些要求的库？

我不一定反对为自己实施某些东西,但在这种情况下,如果可能的话,我宁愿避免它.

我有一个循环有向图.从叶子开始,我希望将附加到每个节点下游的数据传播到可从该节点到达的所有节点.特别是,我需要在周期稳定的任何周期内继续推送数据.

我完全相信这是一个股票图遍历问题.但是,我在寻找合适的算法时遇到了一些困难 - 我想我缺少一些关键的搜索关键字.

在我尝试编写自己的半O(n ^ 3)算法之前,有人能指出我一个合适的解决方案吗？什么是叫这个特殊的问题？

我读过Tree是Graphs的特例.图可以是定向的或不定向的.但是如果我们认为树作为数据结构是指向还是无向图？

我需要检查有向图是否强连接,或者换句话说,是否所有节点都可以到达任何其他节点(不一定是通过直接边缘).

一种方法是在每个节点上运行DFS和BFS,并查看所有其他节点仍然可访问.

有没有更好的方法来做到这一点？

我想在我的程序中嵌入一个绘制画布的流程图.用户可以:

• 绘制"节点"(矩形节点就足够了)和"边缘"(最好是正交)来连接"节点";
• 使用鼠标拖动节点进行布局并调整矩形大小;
• 用鼠标选择一个或多个节点进行删除,复制,粘贴等;
• 通过鼠标选择一个或多个节点来编辑它们的预定义属性(体积,温度,压力等).
• 改变颜色(可选)
• 向/从文件保存/读取数据.

绘图后,程序只需要获取连接逻辑(在数据结构中像Directed图)和属性进行进一步计算.

是否有任何免费或开源的C++库来执行此操作？(不需要跨平台,在Windows中可用就足够了.)

设G是包含周期的未加权有向图.我正在寻找一种算法,它可以找到/创建所有非循环图G',它由G中的所有顶点和G的边缘子集组成,只要小到足以使G'非循环.

更正式:所需算法使用G并创建一组非循环图S,其中S中的每个图G'满足以下属性:

1. G'包含G的所有顶点.
2. G'包含G的边缘子集,使得G'是非循环的.
3. G'的边缘数量最大化.这意味着:没有G''令人满意的属性1和2,这样G''包含更多的边,然后G'和G''是非循环的.

背景:原始图G模拟元素之间的成对排序.由于图中的循环,这不能被用作对所有元素的排序.因此,最大非循环图G'应该模拟这种排序的最佳可能近似,试图尽可能多地考虑成对排序关系.

在一种天真的方法中,人们可以去除所有可能的边缘组合,并在每次移除后检查是否有空隙.在这种情况下,存在强烈分支的变化树,意味着时间和空间复杂性差.

注意:问题可能与生成树有关,您可以将G'图定义为一种有向生成树.但请记住,在我的场景中,G'中的一对边可能具有相同的起始或相同的结束顶点.这与文献中使用的定向生成树的某些定义相冲突.

编辑:添加了与生成树相关的直观描述,背景信息和注释.

根据维基百科的说法,我在Python中实现了Tarjan的强连接组件算法,但它无法正常工作.算法很短,我找不到任何区别,所以我不知道它为什么不起作用.我试图检查原始文件,但找不到它.

这是代码.

def strongConnect(v):
  global E, idx, CCs, c, S
  idx[v] = (c, c) #idx[v][0] for v.index # idx[v][1] for v.lowlink
  c += 1
  S.append(v)  
  for w in [u for (v2, u) in E if v == v2]:
    if idx[w][0] < 0:
      strongConnect(w)
      # idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) #fixed, thx
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))
    elif w in S:
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][0]))
  if (idx[v][0] == idx[v][1]):
    i = S.index(v)
    CCs.append(S[i:])
    S = S[:i]

E = …

我正在寻找一种方法来对给定的定向未加权图执行拓扑排序,其中包含循环.结果不仅应包含顶点的排序,还应包含给定排序违反的边集.这组边缘应该是最小的.

由于我的输入图可能很大,我不能使用指数时间算法.如果在多项式时间内无法计算最优解,那么对于给定的问题,什么启发式算法是合理的？

我很难找到一种方法来正确地对边缘进行分类,同时在有向图上进行广度优先搜索.

在广度优先或深度优先搜索期间,您可以对满足4个类的边进行分类:

• 树
• 背部
• 交叉
• 向前

Skiena [1]给出了一个实现.如果沿着从v1到v2的边缘移动,这里有一种在Java中的DFS期间返回类的方法,以供参考.父映射返回当前搜索的父顶点,以及timeOf()方法,即发现顶点的时间.

if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
    if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
    if ( processed.contains( v2 ) )
    {
        if ( timeOf( v1 ) < timeOf( v2 ) )
        {
            return EdgeClass.FORWARD;
        }
        else
        {
            return EdgeClass.CROSS;
        }
    }
    return EdgeClass.UNCLASSIFIED;

我的问题是我无法在有向图上进行宽度优先搜索.例如:

下图 - 这是一个循环 - 是可以的:

A -> B
A -> C
B …