问题标签 [directed-graph]

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

只要我进行拓扑排序并“从叶子向上”构建每个图，我就可以使用这种方法构建有向无环图。

但是，这种方法不适用于循环图。我能想到的一种解决方法是对整个图形的所有边进行单独的集合（可能是地图或矢量）。然后，每个节点中的:edges字段将具有进入图形边缘集合的键（或索引）。添加这种额外的间接级别是可行的，因为我可以在它们（将）引用的东西存在之前创建键（或索引），但感觉就像是一个杂物。不仅每次要访问相邻节点时都需要进行额外的查找，而且还必须绕过全局边缘集合，感觉非常笨拙。

我听说有些 Lisps 可以创建循环列表，而无需借助变异函数。有没有办法在 Clojure 中创建不可变的循环数据结构？

我有一个有数百万个顶点和边的有向图。给出了一组顶点，假设它们被称为“START_POINTS”。还给出了另一组称为“END_POINTS”的顶点。问题是找出可以从哪个START_POINTS 到达哪个END_POINTS。

这是一个例子：

该算法应该能够说明以下内容：

某些 END_POINTS 可能无法从任何 START_POINT 到达。

现在，问题是：实现它的最有效方法是什么？

我尝试从每个 START_POINT 开始，并使用深度优先搜索（或 BFS，它确实会大大改变运行时间）找到可到达的 END_POINTS。但是，这需要很多时间，因为START_POINTS 太多（END_POINTS 也很多）。

可以优化搜索，因为 START_POINTS 的跟踪路径之间存在巨大重叠。需要记住哪些路径可以到达哪些 END_POINTS。实现这一目标的最有效方法是什么？这可能是众所周知的问题，但我还没有找到解决方案。

1月6日编辑：

我尝试实现 highBandWidth 的想法（以类似于 Keith Randall 提出的方式）：对于每个节点，如果该节点不是 START 或 END 点，则将所有输入连接到输出，然后删除该节点。

这开始非常快，很快变得非常慢，主要是因为剩余节点的输入/输出计数变得非常大并且嵌套的 for 循环会降低性能。知道如何提高效率吗？

我有一些元素数量可变的列表。每个列表都已排序，但排序算法未知。我想将列表合并成一个大列表，其中包含所有列表的顺序相同，没有重复。

示例输入：

1. XS,M,L,XL
2. S,M,XXL
3. XXS,XS,S,L

预期结果：

• XXS,XS,S,M,L,XL,XXL

预期的结果是通过匹配输入序列来获得一个合并的结果，该结果包含每个输入序列的元素以正确的顺序排列，如下所示：

如果存在位置不明确的元素，该函数应通知。在这里，它将是 XXL（它可以留在 M、L 或 XL 之后），我需要在 XL 之后手动指定它的位置（因为在这里我知道排序算法并且可以提供帮助）。我考虑过定义每两个元素的对，每对按原始列表中的顺序排列。从这个可以建立完整的列表。

这是我的问题：对于一个学校项目，我们正在尝试创建一个有向图并使其适合典型的 html 网站。我们发现它必须用 javascript 编写，因为 java 小程序不是一个选项。所以它应该是这样的：image。

图表中可视化的数据将从一些 xml 文件中收集。我们看了一下flare和其他一些包，但真正的事情是在我们的图表中的节点（箭头的粗细表示重要性）​​之间建立双向链接。还需要使整个事物可移动。有任何想法吗？谢谢你。

我只能做一个无向图。不知道如何制作一个定向的。

任何想法？

提前道歉是我误用了术语，不胜感激。我对有向图很着迷，但我从来没有数学/cs背景来了解它们的真正含义，我只是喜欢这项技术，因为它可以制作有用的图表。

我正在尝试创建一个将动态有向图呈现给浏览器的 Web 应用程序功能。我最近发现了Canviz，这是一个基于 cavas 的 xdot 渲染器，我想使用它。

Canviz 很棒，但它会渲染xdot文件，这些文件（看起来？）包含所有复杂的定位逻辑

我使用我的应用程序生成的dot文件是不包含任何定位逻辑的文件

我正在寻找可以将我dot的文件转换为xdotCanviz 可以使用的文件的 PHP 库。我意识到命令行程序dot可以做到这一点，但这是一个可再分发的 PHP Web 应用程序，我更愿意避免将任何二进制文件作为依赖项。

我的核心问题：我正在dot基于简单的定向关系生成文件，并且我想在浏览器中向最终用户显示可视化图形。我想这样做，而不必依赖服务器上特定二进制程序的存在。我认为最好的解决方案是 Canviz+PHP 来生成 xdot 文件。我正在寻找一个可以做到这一点的 PHP 库。但是，我对其他解决方案持开放态度。

正如标题所说..在java中存储连接图的最有效方法是什么？

例如，假设我有多个位置以各种方式相互连接，我必须遍历图表以查看它是否已连接..任何帮助/评论都会有所帮助，谢谢！

我需要存储一个有向图（不一定是非循环的），以便尽可能快地删除节点。我不介意存储额外的数据，以便确切知道删除节点时必须走哪些边。

如果我存储一个边列表（作为节点索引对），那么当杀死某个节点 n 时，我必须在整个列表中搜索其源或目标为 n 的边。这对我的申请来说太昂贵了。可以通过在节点中存储一些额外的数据来避免这种搜索吗？

一种想法是让每个节点将其自己的源和目标存储为两个单独的列表。当节点 n 被杀死时，它的列表也被杀死。但是，链接到节点 n 的所有目标/源如何知道更新他们自己的列表（即，从他们的列表中删除已失效的节点）？这将需要一些昂贵的搜索...

可以避免吗？

谢谢。

获取具有直接和间接外键依赖关系的表列表到 DBIx::Class 子类 foo 的最快方法是什么？我有一个基于 DBIx::Class::Schema 的 MySQL 数据库。DBIx::Class 可以直接使用，还是 SQL::Translator 可以通过生成有向图来帮助？

给定以下类：

对于输入 Foo，输出应为 [ Bar, Baz ]。

给定一个在有向图中保存边的表格，如下所示：

获取特定节点的不同无向链接数量的最佳方法是什么？没有任何重复的有向边，也没有任何节点直接链接到它们自己，我只是想避免计算重复的无向边（例如(1,2)和(2,1)）两次。

这行得通，但NOT IN对我来说味道很糟糕：

PostgreSQL 特定的解决方案对此很好。