问题标签 [digraphs]

我们处理一个有向图，它可能包含或不包含循环，并且可能连接或不连接。我们希望找到最小的顶点集，以便图中的每个其他顶点都可以从它们访问。

例如，给定：http: //i.stack.imgur.com/wtRYB.png（所以不会让我发布图片：/）

解决方案可以是 (A, E) 或 (A, F)。

我的第一种方法是寻找没有父节点（indegree = 0）的节点，但这没有考虑到上述循环。

经过快速搜索，我发现关于 SO 中的非循环有向图的内容相对较少。那么，您可以建议我的最低复杂度算法是什么？

代码：

上面的程序，当使用 GCC 4.8.1 编译时-Wall，-std=c11会给出以下警告：

但是当我将身体更改main为：

没有警告被抛出。

那么，为什么编译器在使用三合字母时会警告我，而在使用二合字母时却没有？

我知道Girvan - Newman算法 - 这是算法：

1. 首先计算网络中所有现有边的介数。
2. 具有最高介数的边被移除。
3. 重新计算受移除影响的所有边缘的介数。
4. 重复步骤 2 和 3，直到没有边缘。

但我想用这个算法在有向图中找到 k 个分量，其中 k 是给定的整数。
我怎样才能做到这一点？可能吗？
谢谢。

我只是拿起 NetworkX 并尝试学习如何将它与 Shapefile 一起使用。

现在我有一个带有道路网络的 .shp，我想用 NetworkX 在图中表示它，这样我就可以找到 2 个 GPS 点之间的最短路径。我尝试使用它，但问题是当我运行 write_shp() 函数时，我会丢失边，因为有向图不允许在相同的两个节点之间存在多个边。下图中的箭头显示了我使用有向图丢失的边的示例。

所以我想知道是否有任何方法可以创建 MultiDiGraph，这样我就不会丢失任何边缘，或者是否有任何我可以使用的方法。我在想也许我可以编写一些代码来从 Shapefile 中提取属性并在不使用 NetworkX 的 read_shp() 的情况下创建 MultiDiGraph，但是我根本没有任何使用图表的经验，所以我不确定它是否有可能。

我非常感谢您能给我的任何帮助或指导，或者如果我错过了任何文档，请告诉我。提前致谢。

我有一个表示网格的矩阵，由 0s、1s 和 2s 组成。网格上没有任何元素时为 0，有可移动元素时为 1，不可移动元素时为 2。

例如：

我想把它变成一个有向图，每个 1 是一个顶点，边是两个顶点之间的链接。为此，我想使用 jgrapht 库，并尝试使用他们的演示代码：

但是，此代码根据用 声明的顶点数创建一个随机有向图size，而我需要将矩阵的元素 (1s) 添加为顶点，然后使用程序生成有向图并返回循环数（在上面的矩阵将有 3 个周期）。

我不知道如何替换该行：

将矩阵元素作为输入。有谁知道如何做到这一点 ？（我使用基于java的处理）

我正在尝试修改 Jgrapht 的函数以将一个点的几个坐标（int，int）作为参数。我创建了一个由 (x,y) 定义的类和一个 Point 对象，并将其作为directedGraph 的参数

我想要做的是能够使用：

当我运行代码时，我得到错误“方法 addVertex 不适用于参数 (int,int)”，即使参数是Point(int,int) 定义的。我应该如何着手进行这项工作？

我使用基于 Java 的处理

我使用填充算法来查看矩阵的 1 和 2 是否正在循环。

例如：

会变成：

我在 (2,7) 的给定点初始化算法，并且算法每 1 个链接到起始点就会变成 3s。我还想实现一个有向图（使用 jgrapht），每个 1 都是一个顶点，并且在两个相邻的 1 之间创建一个边。因此，每次算法将 1 变为 3 时，它都会使 3 成为顶点并创建一条边，最后一个点被填充。

注意：我使用reactivision，所以检测到的每个标记都作为1添加到矩阵中。由于我现在无法使用10个标记进行测试，所以我在程序中添加了一个矩阵。

这是我的代码的一部分：[编辑]：我现在粘贴了我的整个代码，因为我找不到错误

但是，当我运行它时，我得到一个错误“illegalArgumentException：图中没有这样的顶点[x = 2 y = 7]”，这是起点。因此，我尝试通过以下方式将此点定义为顶点：

接着：

但它仍然不起作用我总是在这一行得到同样的错误： directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));但在 Flood Fill 算法中的不同位置取决于 Reactivision 检测到标记的位置（所以它在 UP、DOWN、LEFT 或 RIGHT 部分算法）。

我完全被困住了。我添加了一个打印语句，因此每次执行 draw 方法时，它都会返回图形的顶点并且 [2,7] 在那里......我想不通，有人可以帮我吗？

我正在寻找一种方法来避免在我的 digraph 中创建重复项（我使用 jgrapht 库）。

我读了一些说要使用的主题：directedGraph.setCloneable(false); 但这似乎不对，在图书馆的文档中找不到它，而且我在这一行收到一个错误，说它不存在。

我使用以下方法创建了我的图表：

然后它根据洪水填充算法向其添加顶点（在算法通过每个点时添加顶点和边，下面是它的一部分）：

但是当我打印顶点列表时，我需要删除或避免创建重复的顶点。有没有办法做到这一点？

编辑：我创建了一个 Point 类：

有没有办法“预处理”C99 风格的有向图以获得 C 文件（或.i预处理的源），使得生成的文件不包含任何有向图？

例如，给定以下源代码：

使用 GCC 的预处理器选项 ( -E, plus -dDfor good measure) 足以摆脱%:digraph （在这个例子中被评估和重新打印#define），但不是其他的。

Clang 的行为方式相同，因此没有多大帮助。

据我了解，简单的正则表达式替换不起作用，因为它们最终会替换字符串中的出现。

我有一个使用创建的有向图：

顶点和边是使用在矩阵中实现的 Flood Fill 算法创建的。在我使用的矩阵中，只有 0、1 和 2。Flood 填充算法检测是否存在由 1s 和 2s 形成的循环，并且当它通过 1s 时，它将它们变成 3s。例子：

会变成：

当算法通过矩阵时，它会创建顶点（遇到的每个 1）和边（在两个连续点之间）。这是算法，它从矩阵中的点 (2,7) 开始：

因此，每个 Point 对象/顶点都没有我可以使用的标识符，例如：

我想打印每个顶点的向外边缘的数量。我在 jgrapht 库中找到了这个函数：

因此，我尝试像遍历列表一样遍历顶点集（在我的 Draw 方法中，它一直在 Processing 中循环，这意味着在程序运行时，Draw 方法会继续执行）。这是我的 draw 方法和启动 Flood Fill 的 circuitState() 方法（我通常使用 Reactivision 向矩阵添加元素：检测到的每个标记在矩阵中显示为 1，但为了测试它，我创建了一个矩阵）：

但它找不到我用这个类创建的 Point 对象：

有没有更简单的方法来做到这一点？如果没有，我缺少什么来允许其他方法使用 Point 对象？（奇怪的是我使用 Point 对象是其他方法，它工作正常，为什么 Draw 方法无法访问它？）我使用基于 Java 的处理