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

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

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

我有大约3500个防洪设施,我想将其表示为确定流路径的网络(基本上是有向图).我目前正在使用SqlServer和CTE递归检查所有节点及其上游组件,只要上游路径不分叉,这就可以工作.然而,由于增加了上游复杂性,一些查询比其他查询指数长得多,即使它们在物理上不太远(即两个或三个"下游"段).在某些情况下,我会在杀死查询之前让它超过十分钟.我正在使用一个简单的双列表,一列是设施本身,另一列是第一列中列出的设施的上游设施.

我尝试使用当前工具添加索引以帮助加快速度,但这没有任何区别.并且,对于图中可能的连接,任何节点可以具有多个上游连接,并且可以从多个"下游"节点连接.

当然有可能在数据中有循环,但我还没有找到一种好的方法来验证这一点(除了CTE查询报告最大递归计数命中时;这些很容易修复).

所以,我的问题是,我存储这些信息是错误的吗？有没有比CTE更好的方法来查询上游点？

我有一个项目列表(下面的蓝色节点),由我的应用程序的用户分类.类别本身可以自行分组和分类.

得到的结构可以表示为有向无环图(DAG),其中项目是图表拓扑底部的汇点,顶部类别是源.请注意,虽然某些类别可能已经定义得很好,但很多都是用户定义的,并且可能非常混乱.

例:

_{(来源:theuprightape.net)}

在该结构上,我想执行以下操作:

• 查找特定节点下方的所有项目(接收器)(欧洲所有项目)
• 查找通过所有n个节点集的所有路径(如果有)(通过SMTP从example.com发送的所有项目)
• 找到位于所有节点下方的所有节点(交叉点:goyish brown foods)

第一个似乎很简单:从节点开始,按照所有可能的路径到底部并收集那里的项目.但是,有更快的方法吗？记住我已经通过的节点可能有助于避免不必要的重复,但还有更多的优化吗？

我怎么去第二个呢？似乎第一步是确定集合中每个节点的高度,以确定在哪个(s)开始,然后找到包括集合其余部分的所有路径.但这是最好的(甚至是好的)方法吗？

维基百科上列出的图遍历算法似乎都关注于找到特定节点或两个节点之间最短或最有效的路由.我认为两者都不是我想要的,或者我只是没有看到这对我的问题有何影响？我还应该在哪里阅读？

一些编程语言(如haskell)允许模块之间的循环依赖.由于编译器需要知道在编译一个模块时导入的所有模块的所有定义,如果某些模块相互导入或发生任何其他类型的循环,它通常必须做一些额外的工作.在这种情况下,编译器可能无法像没有导入周期的模块那样优化代码,因为可能尚未分析导入的函数.通常只有一个循环的一个模块必须以这种方式编译,因为二进制对象没有依赖性.我们称之为模块环路断路器

特别是如果导入周期是交错的,那么在编译由数百个模块组成的大项目时,如何最大限度地减少环路断路器的数量是很有趣的.

是否有一个算法给出一组依赖性输出最少数量的模块需要编译为循环断路器才能成功编译程序？

例

我试着澄清我在这个例子中的含义.

考虑与四个模块项目A,B,C和D.这是这些模块之间的依赖关系列表,输入X y方式y取决于x:

A C
A D
B A
C B
D B

可视化为ASCII图的相同关系:

D ---> B
^    / ^
|   /  |
|  /   |
| L    |
A ---> C

此依赖关系图中有两个循环:ADB和ACB.要打破这些循环,可以编译模块C和D循环断路器.显然,这不是最好的方法.编译A为一个环路断路器完全足以打破两个环路,你需要编译一个较少的模块作为一个环路断路器.

我有一个经典的依赖解决问题.我以为我朝着正确的方向前进,但现在我遇到了障碍,我不知道该怎么办.

背景

在已知的Universe(所有工件的缓存及其依赖关系)中,每个工件和版本之间都存在1-> n关系,并且每个版本可能包含一组不同的依赖关系.例如:

A
  1.0.0
    B (>= 0.0.0)
  1.0.1
    B (~> 0.1)
B
  0.1.0
  1.0.0

给定一组"需求约束",我想找到最好的解决方案("最佳"是仍然满足所有约束的最高版本).以下是解决方案的"需求约束"示例:

solve!('A' => '~> 1.0') #=> {"A" => "1.0.1", "B" => "0.1.0"}

实际上,有更多的要求:

solve!('A' => '~> 1.0', 'B' => '>= 0.0.0', 'C' => '...', 'D' => '...')

(版本遵循语义版本标准)

我试过了

当前的解决方案使用回溯并且性能不高.我做了一些挖掘,发现性能问题是由于宇宙的大小造成的.我决定尝试另一种方法,构建了"可能性" DAG图的只是一组要求:

class Graph
  def initialize
    @nodes = {}
    @edges = {}
  end

  def node(object)
    @nodes[object] ||= Set.new
    self
  end

  def edge(a, b)
    node(a)
    node(b)

    @nodes[a].add(b)

    self
  end

  def nodes
    @nodes.keys …

使用点有向图语言,是否可以创建具有不同rankdir的子图？

我尝试了以下,但没有奏效.尽管子图中存在rankdir ="TB",但两个图都是从左到右.

digraph g {
    rankdir="LR";
    LEFT->RIGHT;
    clusterrank="local";

    subgraph cluster1 { 
        rankdir="TB";    
        node[style=filled];         
        color=black;
        TOP->BOTTOM;                
    }   
}

是否有其他语法可以在同一个图表中获得上/下和左/右图,或者这是不可能的？

简而言之,我需要一个快速算法来计算简单有向图中有多少非循环路径.

通过简单的图表我的意思是没有自循环或多个边缘.甲路径可以从任何节点开始,并且必须具有没有出边的节点上结束.如果没有边缘出现两次,则路径是非循环的.

我的图表(经验数据集)只有20-160个节点,但是,其中一些节点有很多周期,因此会有非常多的路径,我的天真方法对某些图形来说根本不够快我有.

我目前正在做的是使用递归函数沿着所有可能的边缘"下降",同时跟踪我已访问过的节点(并避免它们).到目前为止,我用的最快的解决方案是用C++编写的,并在递归函数中使用std :: bitset参数来跟踪已访问的节点(访问节点由位1标记).该程序在1-2分钟内在样本数据集上运行(取决于计算机速度).对于其他数据集,运行需要一天以上,或者显然要长得多.

样本数据集:http://pastie.org/1763781 (每行是边对)

样本数据集的解决方案(第一个数字是我开始的节点,第二个数字是从该节点开始的路径计数,最后一个数字是总路径计数):http: //pastie.org/1763790

如果您对复杂度较高的算法有所了解,请与我们联系.我也对近似解决方案感兴趣(用蒙特卡罗方法估算路径的数量).最后,我还想测量平均路径长度.

编辑:也在相同标题下的MathOverflow上发布,因为它可能更相关.希望这不违反规则.无法链接,因为网站不允许超过2个链接...

我有兴趣坚持个人有向图.这个问题不是要求一个全面的图形数据库解决方案,而是一个我可以用来保存和单个任意有向图的文档格式. 我不知道符号和文件格式是最明智的选择.

我主要担心的是:

1. 表现力/灵活性 - 我希望能够表达不同类型的图表.虽然标准用例是一个简单的有向图,但应该可以表达树,循环图,多图.作为最低限度,我希望支持边缘和节点的标记和加权.用于描述高图和边缘合成/超边缘的符号也是非常需要的,尽管我知道这些解决方案可能不存在.

2. 类型系统独立 - 我有兴趣表示图形的结构质量.一些解决方案包括用于类型化边缘和节点的可扩展类型系统(例如RDF/OWL).如果有明确定义的类型元素到基元(节点/边缘/属性)的规范分解,我只会对这种表示感兴趣.我在这里要避免的是能够进行等效图的多个表示,其中等价是不可辨别的.

3. 规范表示 - 应该有一种机制允许图形被规范地表示(以这种方式,规范表示的词汇等价可以用来确定等价).

4. 独立呈现 - 我更喜欢一种不依赖于图表表示的符号.这将包括空间方向,颜色,字体等.我只对表示数据感兴趣.我不喜欢DOT语言,DGML或SVG(至少对于这个特定目的)的一个特征是关注视觉表示.

5. 标准化/开放/兼容 - 我必须做的实施工作越少越好.如果格式是标准化的并且已经存在用于处理格式的可靠工具,则更优选.伴随这个要求是另一个,格式应该是高度兼容的.微软DGML的专有性质是我厌恶的原因,尽管Visual Studio工具和我主要使用.NET(现在)的事实.W3C发布RDF标准的事实是将RDF的有限子集视为代表性工具的动机.我也很欣赏GXL和GraphML,因为它们有很好的文档xml模式,因此有助于将数据与任何兼容xml的软件包集成.

6. 简单/可读性 - 我欣赏人类可读的语法和易于解释.我也很欣赏能够简化解析的表示.出于这个原因,我喜欢GML,但我担心它不够主流,不能成为一个现实的选择.我还会考虑JSON或YAML的可读性,如果它们各自能够代表复杂(非DAG)结构的能力不是那么有限的话.

7. 效率/简洁表示 - 值得考虑的是,我最终选择的任何格式都不可避免地必须通过某些网络进行持久化和转移.因此,文件大小是一个相关的考虑因素.

概观

我意识到我很可能无法找到满足我愿望清单上所有标准的解决方案.我只要求是最接近我想要的文件格式,并且不限制可扩展性不支持的用例.

我有一个巨大的图表数据集 - 让我们说它是这样的,但在更大的层面上:

1 -> 2
3 -> 4

1,2,3,4是节点,箭头是有向边.假设它们都在一个图形对象中:

import networkx as nx
G = nx.DiGraph()
G.add_nodes_from([1,2,3,4])
G.add_edge(1,2)
G.add_edge(3,4)

给定一个像这样的对象,它在图形中有两个迷你图形,我们如何拉出每个迷你图形？我觉得必须有这个词吗？我的最终结果如下:

for mini_graph in G:
    print mini_graph.nodes()

...
[1,2]
[3,4]

所以我一直在构建一个程序,使用蒙特卡罗模拟来找到进化图论的属性.其中一个关键功能是能够生成均匀分布的随机图,以便我们可以确定图的广义属性.对于连接无向图的情况,我已经实现了本答案中概述的解决方案.

然而,对于有向图,生成从Wilson算法得到的单向均匀生成树并不能确保图形是强连通的,并且似乎添加额外的边缘以使生成树双向会引入偏差您生成的图表.

我觉得我可能会遗漏一些明显/误解的东西,但基本上我的要求是,有人可以向我推荐一个高级方案,允许我生成强连接,均匀分布的随机图吗？