问题标签 [graph]

考虑以下简单的 DAG：

还有一个表，#bar，描述了这个（我使用的是 SQL Server 2005）：

现在想象一下，我有一些其他任意标准来选择第一个和最后一个边，即 1->2 和 3->4。我想用这些来找到我的图表的其余部分。

我可以按如下方式编写递归 CTE（我使用的是MSDN中的术语）：

但是，这会导致边 3->4 被选择两次：

如何防止查询递归到已经描述的子图中？如果在查询的“递归成员”部分中，我可以引用到目前为止由递归 CTE 检索到的所有数据（并在递归成员中提供一个谓词指示，不包括已访问的节点），我就可以实现这一点。但是，我认为我只能访问递归成员的最后一次迭代返回的数据。

当有很多这样的重复时，这将无法很好地扩展。有没有办法防止这种不必要的额外递归？

请注意，我可以在语句的最后一行使用“select distinct”来获得所需的结果，但这似乎是在完成所有（重复）递归之后应用的，所以我认为这不是一个理想的解决方案。

编辑- hainstech 建议通过添加一个谓词来排除在起始集中显式递归的向下路径来停止递归，即仅递归where foo.child_id not in (1,3)。这仅适用于上述情况，因为它很简单——所有重复的部分都从锚节点集中开始。它不能解决它们可能不是的一般情况。例如，考虑将边 1->4 和 4->5 添加到上述集合中。边缘 4->5 将被捕获两次，即使使用建议的谓词。:(

我想知道其他人发现什么是 Rails 应用程序的最佳图形库/插件/宝石等。

当我说最好的时候，我想我的意思是易于实施和自定义图表的能力。

我以前使用过 openflashchart2 并且喜欢它的整体外观/效果，尽管根据需要自定义所有内容有时会很痛苦。您有经验或建议可以为我指明更好的方向吗？非常感谢。

我正在寻找一个库来用 Python 绘制 ASCII 图形（用于控制台）。该图非常简单：它只是管道的流程图。

我看到了 NetworkX 和 igraph，但没有看到输出到 ascii 的方法。

你有这方面的经验吗？

非常感谢！

帕特里克

编辑 1：我实际上找到了一个库做我需要的，但它在 perl Graph::Easy中。我可以从 python 调用代码，但我不太喜欢这个想法......仍在寻找 python 解决方案:)

我正在用 Python 重写一个数据驱动的遗留应用程序。其中一个主表被称为“图形表”，并且看起来确实是有向图，所以我正在探索 NetworkX 包，看看将它用于图形表操作是否有意义，并真正实现它是一个图形，而不是一组复杂的数组。

但是，我开始怀疑我们使用此表的方式是否不适合实际的图形操作库。NetworkX 的大部分功能似乎都倾向于以某种方式表征图本身，确定两个节点之间的最短距离，诸如此类。这些都与我的申请无关。

我希望如果我可以在这里描述实际用法，有人可以告诉我我是否只是遗漏了一些东西——我以前从未真正使用过图表，所以这是很有可能的——或者我是否应该探索其他一些东西数据结构。（如果是这样，你有什么建议？）

我们主要使用该表将用户提供的关键字字符串转换为组件的有序列表。这构成了 95% 的用例；其他 5% 是“给定部分关键字字符串，提供所有可能的补全”和“生成所有可能的合法关键字字符串”。哦，并验证图表是否存在畸形。

这是该表的编辑摘录。列是：

关键字 innode outnode 组件

给定关键字字符串“acs,wfc1,f555w”和这个表，遍历逻辑是：

• 从节点 1 开始；“acs”在字符串中，所以转到节点 20。

• 节点 20 的所有关键字都不在字符串中，因此选择默认值，选择 hst_ota，然后转到节点 30。

• “acs”在字符串中，所以转到节点 10000。

• “wfc1”在字符串中，所以转到节点 10100。

• 只有一种选择；转到节点 10101。

• 只有一个选择，所以拿起 acs_wfc_im123 并转到节点 10130。

• “f555w”在字符串中，所以选择 acs_f555w 并转到节点 10140。

• 只有一个选择，所以转到节点 10300。

• “wfc1”在字符串中，所以选择 acs_wfc_ebe_win12f 并转到节点 10310。

• 只有一个选择，所以拿起 acs_wfc_ccd1 并转到节点 10320——它不存在，所以我们完成了。

因此最终的组件列表是

我可以仅从该表的 innodes 和 outnodes 制作一个图表，但我一生都无法弄清楚如何构建关键字信息，以确定在面对多种可能性时做出哪个选择。

更新以添加其他用例的示例：

• 给定一个字符串 "acs"，返回 ("hrc","wfc1") 作为可能的合法下一个选择

• 给定字符串“acs, wfc1, foo”，由于未使用的关键字引发异常

• 返回所有可能的合法字符串：

  • 因
  • acs, 人力资源委员会
  • acs, wfc1, f606w
  • acs, wfc1, f550m
  • acs, wfc1, f555w

• 验证所有节点都可以到达并且没有循环。

我可以为其中的前两个调整 Alex 的解决方案，但我不知道如何为最后两个做。

在 Windows 中，我正在研究使用任何主流编程语言（C#、VB.Net、Java、PERL 等）生成专业图形。到目前为止，我发现的最好的免费图表是Microsoft Chart Controls for .NET。您还建议使用哪些其他图形控件/模块？

注意：免费添加到要求中。

我有一个带有n节点的图作为邻接矩阵。

是否有可能在更短的O(n)时间内检测到水槽？

如果是，如何？如果不是，我们如何证明？

Sink 顶点是具有来自其他节点的入边且没有出边的顶点。

作为一名热心的风帆冲浪者，我对接下来的几周会有多风很感兴趣。为此，我一直在编写一个小应用程序来抓取一个流行的天气网站（仅供个人使用 - 不转发信息或任何东西）并将数据整理成一个图表，以便我可以轻松查看何时值得前往出去。

我有后端工作，但需要一种显示数据的方法。我的刮刀目前给了我两个系列的数据，这些数据告诉我一般风有多强，以及它可能会有多强。接下来我想做的是将这两个数据集显示为图表中的一对线，并​​在它们之间的区域设置阴影。

我正在考虑使用诸如flot 库之类的东西来显示数据。唯一的问题是我看不到在两条线之间遮蔽区域的方法？

如果有人对如何在 flot 或其他库或图形技术中执行此操作有建议（我的服务器上有 DJango，所以任何 pythonic 或 javascripty 都应该没问题），我很想听听他们的意见。理想情况下，这将是一个避免提供图像的 javascript 解决方案。

我正在使用 Qt 和 QWt3D 绘图工具，并扩展它们以提供我需要的一些 3-D 和 2-D 绘图功能，因此我在此过程中学习了一些 OpenGL。

我目前能够使用 OpenGL 绘制点，但只能作为圆形（或通过关闭抗锯齿来实现的“正方形”）。这些点以我喜欢的方式运行 - 即它们不会在我放大时改变大小，尽管它们的 x/y/z 位置在我缩放、平移等时会适当移动。

我想做的是使用无数形状（^、<、>、*、.等）绘制点。根据我对 OpenGL 的理解（不是很多），这并非易事，因为 OpenGL 将所有内容视为“真实”3-D 对象，因此放大任何 openGL 形状但“点”会改变对象的投影尺寸。

在做了一些阅读之后，我认为这个问题有（至少）两种可能的解决方案：

1. 使用 OpenGL 纹理。这似乎并不难，但我相信纹理图像会随着我的放大而变得越来越小——对吗？

2. 使用 OpenGL 多边形、线条等并绘制 *、三角形或其他任何东西。但是在这里我又遇到了同样的问题——如何防止 OpenGL 在缩放时重新调整“点”的大小？

每次用户缩放或平移以确保点保持相同大小时，是否只是硬着头皮重新绘制整个数据集？有没有办法告诉openGL不要重新计算对象的大小？

抱歉，如果这在某处的 OpenGL 文档中 - 我找不到它。

我正在尝试制定一种算法来找到穿过有向图的路径。这不是一条传统的道路，我找不到任何关于已经完成的类似事情的参考。

我想找到具有最大最小权重的路径。

即如果有两条路径的权重为 10->1->10 和 2->2->2，那么第二条路径被认为比第一条路径更好，因为最小权重 (2) 大于第一条的最小权重 ( 1）。

如果有人能想出办法做到这一点，或者只是向我指出一些参考材料的方向，那将非常有用:)

编辑:: 似乎我忘了提到我正试图从一个特定的顶点到另一个特定的顶点。那里很重要：/

EDIT2:: 正如下面有人指出的那样，我应该强调边缘权重是非负的。

是否有用于绘制/可视化图形的良好 C# 库？我说的是节点路径可视化而不是折线图等。（最好是原生的，而不是 pstricks 的包装器或类似的东西）谢谢