问题标签 [graph-traversal]

我在遍历以下类型的图表时遇到问题。

• 在每个节点上可能有多个输入和输出。
• 每个输出可以指向多个输入（例如 A 的第三个输出到 C 和 D）
• 在每个节点上，根据输入中提供的值进行一些计算。输出的结果提供给其他节点的输入。
• 要从一个节点遍历到下一个节点，我必须知道所有输入的值。

想到这个遍历：

• 在 A 处，使用唯一的输入来计算所有的输出
• 使用 A 的第一个输出从 A 移动到 C。
• 在 C，我们不知道另一个输入，所以回溯到 A。
• 在 A 处，使用第二个输出到达 B。
• 在 B，我们没有所有的输入，所以回溯到 A。
• 在 A 处，取第三个输出并到达 B。
• 在 B，现在我们有所有的输入来计算输出。
• 在 B，通过第一个输出到达 C。
• 在 C 处，我们拥有所有输入，因此进行计算并到达 E。
• 等等

那么您认为哪种遍历算法在这种情况下效果最好。BFS 可能不起作用，因为在我的情况下，当我到达一个节点时我不知道所有输入，并且不可能回溯。

我必须在 C# 中实现它。

编辑：好的，这是一个更简单的例子来说明我的问题。为什么只有第一个任务被放入队列？

原来的：

我需要遍历这个 DAG。当我访问一个节点时，我会清理它。在所有父节点都干净之前，我无法清理节点。

我正在尝试的方法是让工作线程的当前节点检查其所有子节点以查看哪些子节点可以处理。任何可以处理的都添加到任务池中。

我的问题是我不知道如何将新任务添加到 TaskPool 并处理它们。这只是清理 DAG 中的第一个节点，然后退出，让其他一切都变脏。

完整代码在这里： http: //pastebin.com/LLfMyKVp

我有一个由节点 a、b、c、d、e、fg 组成的有向循环图，其中任何一个节点都连接到每个其他节点。边缘可以是单向的或双向的。我需要打印出这样的有效订单，例如。f->a->c->b->e->d->g 这样我就可以从开始节点到达结束节点。请注意，所有节点都必须出现在输出列表中。另请注意，图中可能存在循环。

我想出什么：基本上首先我们可以尝试找到一个起始节点。如果存在一个没有传入边的节点（最多可能有一个这样的节点）。我可能会找到一个起始节点，也可能不会。另外我会做一些预处理来找到节点的总数（我们称之为n）。现在我将从开始节点开始一个 DFS，当我到达它们时将节点标记为已访问并计算我访问了多少个节点。如果我可以通过这种方法到达 n 个节点。我做完。如果我点击一个节点，从该节点到任何未访问的节点都没有出边，我已经走到了死胡同，我将再次将该节点标记为未访问，减少指针并转到其前一个节点以尝试不同的路线.

当我找到一个起始节点时就是这种情况。如果我没有找到起始节点，我将不得不尝试使用各种节点。

我不知道我是否接近解决方案。任何人都可以在这方面帮助我吗？

我正在编写一个名为 的模板类RootedBinaryTree，它具有类似链表的结构，其元素的类型为Node，这是我在下面的头文件中定义的结构。二叉树中的每个节点都有 aparent Node *并且可以有 aleftChild Node *和 arightChild Node *或者没有子节点。（例如：如果你要画一个有根的二叉树，它应该看起来像这样http://mathworld.wolfram.com/images/eps-gif/CompleteBinaryTree_1000.gif）。

一个有根的二叉树有两个成员：root一个currentPosition是节点类型。当我超载时，operator=()我必须做类似的事情currentPosition = RHS.currentPosition;（这是我目前在那里写的）。我知道这是不正确的，我需要做的是在树中找到与*this树中的节点相对应currentPosition Node *的RHS节点。

我的问题是：什么是遍历 RHS 树找到它并在调用树中currentPosition Node *找到对应的好算法？Node

我的想法是创建一个空字符串并RHS使用某种深度优先搜索算法从根开始向下遍历，直到找到 currentPosition，并通过在字符串末尾附加 0 来跟踪我到达那里的路径 if我沿着树向左走，如果我从树向右走，则为 1，然后使用该字符串遍历*this树，这应该将我带到相应的Node. 但是，我知道必须有更好的方法来做到这一点（部分来自直觉，部分是因为我的导师告诉我有更好的方法哈哈）。

以下是相关文件：

RootedBinaryTree.h

RootedBinaryTree.cpp

提前感谢任何回答这个问题的人！非常感谢您的帮助。

在（室内）导航系统的图遍历算法中，以下哪个选项需要更少的处理时间/更便宜？

1. 要生成起点和终点之间的所有可能路径（图上的节点），然后应用过滤机制来匹配导航用户的能力和偏好（例如查找图上的所有路径，然后排除轮椅用户的楼梯），或

2. 一旦用户的配置文件可供系统使用，过滤图形并排除该用户不可遍历的路径，然后运行最短路径算法？

I am implementing an intercity map using graphs. Since it is undirected, I used an upper triangular adjacency matrix using a vector of vertices and vector of 'pointer to array of edges' in the Graph class.

I need to traverse such a graph. Vertices have information and edges are weighted.

Why would I need BFS or DFS in such a traversal when I already have all the vertex and edge information through direct access?

I am trying to understand Neo4J java traversal API but after a thorough reading I am stuck on certain points.

What I seem to know:

Difference between PathExpander and BranchOrderingPolicy. As per my understanding, the former tells what relationships are eligible to be explored from a particular position and the latter specifies the ordering in which they should be evaluated.

I would like to know the following things:

1. Whether or to what extent this understanding is correct or if it can be altered to give the correct understanding.

2. If correct, how is PathExpander different from Evaluator.

3. How does PathExpander and BranchOrderingPolicy work. What I intend to ask is, is PathExpander consulted everytime a relationship is added to the traversal and what does it do with the iterable of relationships returned. Similarly with branch ordering.

4. During traversal how and when do the components Expander, BranchOrdering, Evaluator, Uniqueness come into picture. Basically I wish to know the template algorithm where one would say like first expander is asked for a collection of relationships to expand and then ordering policy is consulted to select one of the eligibles....

5. If correct, does the ordering policy specified by BranchOrderingPolicy apply on the eligible relationships only(after expander has done). Perhaps it must be.

Please include anything else that might be helpful in understanding the API.

http://i.stack.imgur.com/sEJKz.png

该图显示了一个图表。这是正确的深度优先遍历吗？还是我的想法完全错误？我对dfs的理解给出了一个起点，你看看所有相邻的节点。然后，任意选择一个并递归地“访问”该节点。从 v 开始，我选择了节点 2 进行下一步。从 1 到 8 的数字表示路径。

编辑：我似乎把数字 2 和 3 弄混了！他们应该被交换。

图 2：http: //i.stack.imgur.com/KdWl6.png

The first one is as follows: given a sequence of properties that specify a path, I should return the the end node. i.e.

And the second one is kind of opposite: given a node's identifier (for simplicity suppose it is the node's ID), return the path (sequence of properties name) from the root to the node (it's guaranteed to be unique). As for now, I'm just using the shortestPath:

The queries are run from embedded database and aren't satisfying me with their speed, so I'd like to have them translated into TraversalDescriptions, but they should change dynamically, and I don't quite understand how to do this.

Or maybe these queries aren't optimal? The one with the shortestPath runs for <= 1ms, while the one with variable length runs for 10ms per single query (that's unacceptable). Maybe you have some performance tips for me?

我目前正在尝试Neo4J Koan Tutorial。我对介绍的 Koan06 感到非常困惑Traversal。方法Node.traversal已被弃用，取而代之的是Traversal.traverse. 当我尝试它时，我看到整个Traversal类也被弃用了。我阅读了文档以了解我应该使用什么，但找不到任何东西。文档甚至没有提到它Traversal已被弃用（当然，像traverse和一样的遍历方法也description被弃用但没有明确说明）。

简单的问题：我应该用什么来构建一个TraversalDescription？