graph-theory相关内容

最小添加到强连通图

我有一组节点和它们之间的有向边.边缘没有重量. 如何找到必须添加的最小数量的边以使图牢固连接(即，应该有从每个节点到所有其他节点的路径)?这个问题有名字吗? 解决方案 这是一个非常经典的图形问题. 运行类似Tarjan-SCC算法的算法以查找所有SCC.考虑 每个SCC作为新顶点，在这些 顶点，根据原始图，我们可以得到一个新图. 显然，新图是有向无环图(DAG). 在DAG中 ..
发布时间：2020-08-22 19:59:56 其他开发

确定给定的加权图是否具有唯一的MST

我正在寻找一种算法(或其他方法)来确定给定的加权图在O(ElogV)中是否具有唯一的MST(最小生成树)? 我对权重一无所知(例如weight(e1)！= weight(e2))，如果该图仅具有一个唯一的MST，则算法仅返回True；否则，则返回False. 我首先使用Kruskal的算法，然后检查find-set(u)== find-set(v)，以便在MST中有一个圆圈，但是这种方 ..
发布时间：2020-08-22 19:26:42 其他开发

可视化对GraphViz太大的无向图?

我需要一些建议，以绘制具有178,000个节点和500,000条边的无向图.我已经尝试过Neato，Tulip和Cytoscape. Neato甚至都不遥不可及，Tulip和Cytoscape声称他们可以应付，但似乎不行. (郁金香什么也不做，Cytoscape声称正在工作，然后停下来.) 我只喜欢矢量格式的文件(ps或pdf)，其节点的布局合理. 解决方案 Graphviz本身提供 ..
发布时间：2020-07-23 04:00:29 其他开发

根据家谱数据计算家庭关系

考虑到以下数据模式(从我的实际数据模式简化，仅显示直接应用于此问题的列)，我希望能够计算家族树中两个人之间的家族关系: individual ---------- id gender child ---------- child_id father_id mother_id 通过这种结构，如何计算两个个体ID(例如堂兄，曾祖父等)之间的关系. 此外，由于实际上存在两种关系(即A- ..
发布时间：2020-07-23 01:43:29 其他开发

图论的C ++库列表

我将开始一个有关自动机和图论的科学项目，我正在寻找一个支持以下功能的图库: 有向图/无向图 图同构测试(即图g1是同构w.r.t. g2吗?) 子图同构测试(即，图g1与g2的子图同构吗?) 图搜索，访问等 可能是非常快的，因为我需要进行一些认真的计算 我了解 Boost图形库，但是到目前为止，它缺乏子图测试我从它的文档中了解了. 所以，我的问题是:请问哪个是最好的c + ..
发布时间：2020-07-10 02:58:42 C/C++开发

普里姆的算法时间复杂度

我正在查看 Wikipedia条目中的Prim算法，我注意到它的时间了邻接矩阵的复杂度为O(V ^ 2)，堆和邻接列表的时间复杂度为O(E lg(V))，其中E是边的数量，V是图中顶点的数量./p> 由于Primer算法用于较密集的图中，因此E可以逼近V ^ 2，但是当这样做时，堆的时间复杂度变为O(V ^ 2 lg(V))，大于O(V ^ 2) ).显然，堆将仅通过搜索数组来提高性能，但是时间 ..
发布时间：2020-07-03 22:54:54 其他开发

用不相交的元素将嵌套列表分成几组

我有一个看起来像这样的列表 my_list = [[1, 2, 3, 4], [4, 5, 6, 7], [9, 10, 11, 12]] ，我想找到最好的方法将列表分为两组，以使每组中的各个元素不重叠.例如，在上面的示例中，两个组将是 group1 = [[1, 2, 3, 4], [4, 5, 6, 7]] group2 = [[9, 10, 11, 12]] 这是因为9， ..
发布时间：2020-06-26 13:38:23 Python

xslt的优雅示例?

在通过XAML进行了漫长的学习循环之后，我回到了HTML和javascript，并意识到声明性代码的概念(就转换规则而言)是一个非常强大的概念. 尽管XSLT语法过多，但XML的处理却是声明式转换编程的基石.但是，我总是很难理解如何将XSLT用于日常任务(使用XML). 除了生成HTML之外，XSLT还可以通过哪些优雅的示例很好地解决编程问题? 我猜它擅长于图形转换和数据重新处理 ..
发布时间：2020-06-22 18:53:24 其他开发

寄存器分配和溢出，简单的方法?

我正在寻找一种将局部变量分配给寄存器的方法.我知道有几种严肃的方法可以做到这一点(即在Wikipedia上提到的 ) ，但我对如何完成“起毛"感到困惑.而且，相关文献令人生畏.我希望有一些更简单的方法可以满足我的要求: 正确性-一种算法，无论有多少局部变量，该算法都会生成正确的代码. 简单性-无需阅读过多文献就可以理解的东西. 效率-它需要比当前方法更好，即: 将操作x = y # ..
发布时间：2020-06-18 19:35:31 其他开发

深度优先搜索的完整性

我引用了人工智能:一种现代方法: 深度优先搜索的属性在很大程度上取决于是否使用图搜索版本或树搜索版本.避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它将最终扩展每个节点.另一方面，树搜索版本不是完整的[...].深度优先树搜索可以在不增加内存开销的情况下进行修改，因此它会根据从根到当前节点的路径上的状态来检查新状态.这避免了有限状态空间中的无限循环，但并没有避免冗余路径的泛 ..
发布时间：2020-06-17 19:06:06 AI人工智能

图形工具中有关嵌套块模型的基本问题

关于 graph-tool library 中的minimize_nested_blockmodel_dl 函数.有没有办法找出哪个顶点落在哪个块上?换句话说，要从每个块中提取一个列表，其中包含其顶点的标签. 对于网络理论的业余爱好者(例如绘制有向边的正方形是为了暗示所考虑的两个块之间的基础边的主方向?可以使用不同的颜色很好地显示块，但是在非常概念上，顶点的块分类背后是哪些类型的图案或边线/ ..
发布时间：2020-06-17 19:05:25 Python

使用Cytoscape.js在所有节点上执行集中功能

我需要计算图上每个节点的程度，紧密度和中间度。我目前正在 cy.ready（）事件之后的每个节点上使用Cytoscape.js内置的函数。但是，由于图形非常大（250个以上的节点，650个以上的连接），因此计算时间太长。有人可以建议一种更有效的方法吗？ var computeSNA = function（）{ //如果不运行已设置... if（data.sna）返回false c ..
发布时间：2020-06-11 01:50:10 前端开发

Gremlin-如何找到仅通过G的从A到Z的路径

在Gremlin方面需要一些帮助：如果我知道起始顶点和终止顶点，并且起始和终止BUT之间有多个路径，则在此过程中会有几个顶点。如何根据已有的数据找到正确的路径？ 例如，在这里我必须找到从“学院”到“雀科”的路径 gV（）。has（'station'，'college'）。 repeat（out（）。simplePath（）） .until（has（'station'，'finc ..
发布时间：2020-06-05 18:33:14 其他开发

使用列表列表保存图形中的每个路径

我必须实现dfs算法以保存来自起始节点的所有路径。因此，例如，我有以下图形： 我有一个列表 path = [] 来保存从节点1开始的所有路径。因此，我的列表将只有起始节点1： 1 ，然后我将检查1的邻居（即节点2），列表将为： [1,2] 。 现在，我检查2的邻居，分别是3和4。现在，我认为列表类似于 [[1,2,3]，[1,2,4]] ，最后的最终列表将是 [[1,2,3]，[1,2,4 ..
发布时间：2020-06-03 21:57:50 Python

图中所有可能的路径

给定一个图 G（V，E），一个源顶点 s 和目标顶点 d ，问题是要找到所有可能的从 s 到 d 的路径，其中 G 可能包含循环和循环。我想获得所有简单的路径，不允许循环。 这个问题的复杂性是什么？ 解决方案 此问题是NP难题，因为其输出的输入可能成指数大小。 找到之间的最长路径两点已经是NP难点了（减少了哈密顿路径问题），所以找到所有这些点也是一样。 通过查看图中两个顶 ..
发布时间：2020-06-03 21:47:07 其他开发