标签: directed-graph

我需要在复杂的图形结构中找到一条或多条路径.该图使用类似于此的内容构建:

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

使这种复杂化的原因是节点可以引用回早期节点.例如,

A - > C - > E - > A.

我需要做的是获取表示通过节点的路径的堆栈列表,直到我到达具有特定值的节点.由于可能存在一些非常大的路径,我们可以尝试使用最大节点.

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

有没有人有办法建立这个(或类似的东西)？我过去做过递归,但由于某种原因,我正在考虑这个问题.我的问题指定了一个lambda表达式,但不一定需要使用lambda.我很感激任何解决方案.

旁注:我从aku的这个递归问题的优秀答案中提升了课程.虽然下面显示的优雅解决方案遍历树结构,但它似乎没有足够的灵活性来完成我需要的工作(例如,解除圆形路径和成功的轨道路径).

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

编辑:

根据以下评论和答案的输入,我在CodeProject中找到了一个很好的解决方案.它使用A*路径查找算法. 链接在这里.

我想找到符合以下规则的最长的单词序列:

• 每个单词最多可以使用一次
• 所有的单词都是字符串
• 两个字符串sa和sb级联,如果最后两个字符sa匹配的前两个字符sb.

在连接的情况下,通过重叠这些字符来执行.例如:

• sa ="torino"
• sb ="novara"
• sa concat sb ="torinovara"

例如,我有以下输入文件"input.txt":

诺瓦拉

都灵

维切利

拉文纳

那不勒斯

liverno

messania

诺维利古雷

罗马

并且,根据上述规则输出的上述文件应为:

都灵

诺瓦拉

拉文纳

那不勒斯

利沃诺

诺维利古雷

因为最长的连接是:

torinovaravennapolivornovilligure

有人可以帮我解决这个问题吗？什么是最好的数据结构？

我正在研究基于R中的跟随者关系的Twitter网络.在这个网络中,我想确定每个人中最大的团队的大小,可以在他或她的时间线中读取彼此的推文.因此我需要maximum.cliques.但是这个功能忽略了方向性.我知道它没有集成在igraph包中,但是有没有办法在有向网络中找到派系,每个节点都是主动和被动地相互连接的？

当做一个depth first search关于Directed Graph什么意思pre和post数字？

例如:

如果您从节点开始A并按字母顺序Depth First Search执行,那么如何确定前后数字？

如何复制 Erlang 有向图？文档中似乎没有复制功能。我必须手动构建副本吗？

我在 Elixir 中编码。

我有一个有向图，我想找到一条只访问每个节点一次的路径。我想以一种很好的复杂性来做到这一点。这可能吗？如果是，如何？

所以我试图用一些非常简单的json 来展示这个伟大的示例Force-Directed Graph:https://raw.githubusercontent.com/DealPete/forceDirected/master/countries.json

我的工作在这里:codepen

我从d3得到一个永无止境的错误源,一开始没有错误,表明我的代码有问题.它是这样开始的:

XHR finished loading: GET "https://raw.githubusercontent.com/DealPete/forceDirected/master/countries.json".
[...]
d3.min.js:2 Uncaught Error: missing: 0
    at ar (d3.min.js:2)
    at r (d3.min.js:5)
    at Function.e.links (d3.min.js:5)
    at pen.js:46
    at Object.<anonymous> (d3.min.js:7)
    at d.call (d3.min.js:4)
    at XMLHttpRequest.e (d3.min.js:7)
ar @ d3.min.js:2
r @ d3.min.js:5
e.links @ d3.min.js:5
(anonymous) @ pen.js:46
(anonymous) @ d3.min.js:7
call @ d3.min.js:4
e @ d3.min.js:7
d3.min.js:5 Uncaught TypeError: Cannot create property 'vx' on number '66'
    at e (d3.min.js:5)
    at d3.min.js:5
    at Fe.each …

有一个有向图(可能包含循环),每个节点都有一个值,我们怎么能得到每个节点的可达值之和.例如,在下图中:

节点1的可达和为:2 + 3 + 4 + 5 + 6 + 7 = 27

节点2的可达和为:4 + 5 + 6 + 7 = 22

.....

我的解决方案:为了获得所有节点的总和,我认为时间复杂度为O(n + m),n是节点数,m代表边数.应该使用DFS,对于每个节点,我们应该递归地使用一个方法来找到它的子节点,并在完成它的计算时保存子节点的总和,以便将来我们不需要再次计算它.需要为每个节点创建一个集合,以避免由循环引起的无限计算.

它有用吗？我认为它不够优雅,特别是必须创建许多套装.有没有更好的解决方案？谢谢.

我有一个根据数据框以from, to, cost列的形式创建的图表。我还有一条有效的路径（作为一系列顶点，格式为vpath） （我的图是有向的）。igraph

给定我的图表和路径，是否有任何函数可以给出该路径的成本？

我不是要求最短路径，因为我从 获得了路径all_shortest_paths。但是，我只获得了节点连续性，而不是我也需要的路径权重。

编辑：数据

这是我的数据框，我将其转换为图表：http://www.sharecsv.com/s/47209742f0052a37e17db37ea3af63ac/arcsWithCost.csv

而我的道路是15 4 50 212 183 112 114 37 228 119

我对图数据库非常陌生。我从阿兰戈开始。对于这个项目，我不确定将来会遇到的疑问。我不想制造瓶颈。所以我想在任何地方创建无向或双向边缘。

然而，由于仅支持有向边，我目前的理解是，如果某个顶点无法通过 a 到达，directed traversal那么我稍后会遇到瓶颈。因此，每当我创建边缘时，a -> b我也会b -> a在同一个边缘集合中创建。

我的假设正确吗？设计决策是否可以接受？