通过并行分组最小化作业调度
我遇到了一个工作安排问题，即扭曲最小化的约束.任务是-我有很多工作，每个工作对其他工作都有各种依赖性，没有周期.这些作业也具有类别，如果它们属于同一类别，则可以免费并行运行.因此，我想对作业进行排序，以使每个作业都依赖于其依赖项，但要按照它们按类别分组的方式进行排列(以并行运行许多作业)，以最大程度地减少我运行的串行作业的数量.也就是说，相同类别的相邻作业被计为单个串行作业. 我知道我可以进
..
graph-theory相关内容
Barabasi-Albert模型，错误指数
我正在尝试使用Barabasi-Albert模型生成无标度网络.该模型预测度分布遵循p(k)〜k ^ -3，但我的显示为k ^ -2. 该算法取自Barabasi的书，网址为: http://barabasi.com/networksciencebook ， 这是相关的段落: Barabasi的算法 这是我的代码，有人可以帮我找出问题所在吗? import numpy as
..
拜访最少重复访问图的图中的所有节点
我有一个基于图块的地图，其中一些图块是墙，其他图块是可步行的.步行砖构成了我想在路径规划中使用的图形.我的问题是，他们有什么好的算法可以找到可访问图形中每个节点的路径，从而最大程度地减少重复访问? 例如: 地图示例http://img220.imageshack.us/img220/3488/mapq .png 如果底部的黄色图块是起点，则访问重复次数最少的所有图块的最佳路径是:
..
我正在尝试在Python中执行有向图的可传递约简
作为警告，我对python还是没有经验 我正在尝试使用networkx库执行有向图的可传递约简.我已经找到一种算法，但是在实现它时遇到了麻烦.快速搜索之后，我在其他堆栈交换问题中发现了与我的算法相似的算法，但未演示如何实际编码该算法. 这是我的算法: For X in Nodes For Y in Nodes For z in Nodes if (
..
在其他限制条件下添加边以引导无环图
我有DAG.我有此操作可在两个节点之间添加一条边. 如果从B可以到达A，则B是A的父母.如果A可以从B到达而无需经过另一个节点，则B是A的直接父代. 此图的要求为: 没有周期. 对于任何节点，都有直接父级P [1]，P [2]，P [3] ...的列表.对于任何i和j，P [i]都不是P [j]的父级. 如果添加边，则不满足要求1，则不构造边. 如果添加边缘，则不满足条件
..
如果我对DAG进行拓扑排序，是否可以丢弃一半邻接矩阵?
我认为我已经了解了如下所述的特殊情况，但是我缺乏进行证明的理论知识，因此找不到任何提及它的资料.如果我的理解是正确的，那么我可以在邻接矩阵上节省一半的空间，如果不是的话，我可能会遇到一些非常奇怪的错误.因此，我想确定一下，如果背景更扎实的人可以复习我的推理，我将不胜感激. 假设我在n * n邻接矩阵中表示n个顶点的DAG，因此如果存在从顶点i到顶点j的边，则条目i,j为1，否则为0.由于该图
..
如何最小化最短路径树的总成本
我有一个有正的边权重的有向无环图.它具有一个源和一组目标(距源最远的顶点).我找到了从源到每个目标的最短路径.其中一些路径重叠.我想要的是最短路径树，该树将所有边缘上的权重总和最小化. 例如，考虑两个目标.在所有边缘权重相等的情况下，如果它们在大部分长度上共享一条最短路径，那么它比两条大部分不重叠的最短路径(树中更少的边缘等于更低的总体成本)更好. 另一个示例:两个路径在其长度的一小部
..
Networkx:获取节点之间的距离
我是使用NetworkX的初学者，我试图找到一种方法来检测哪些节点彼此之间的距离为x. 我首先使用此算法来获取所有对 path=nx.all_pairs_dijkstra_path(G) 但是我仍然不确定如何使用for循环来检测节点之间的距离. 我将不胜感激.谢谢 解决方案 NetworkX具有自动计算加权图和非加权图的最短路径(或仅路径长度)的方法.确保针对用例使用正确的
..
如何序列化图结构?
平面文件和关系数据库为我们提供了一种序列化结构化数据的机制. XML对序列化非结构化的树状数据非常有用. 但是许多问题最好用图形表示.例如，一个热仿真程序将使用通过电阻性边缘相互连接的温度节点. 那么序列化图结构的最佳方法是什么?我知道XML在某种程度上可以做到这一点，就像关系数据库可以序列化复杂的对象网络一样:它通常可以工作，但很容易变得难看. 我知道graphviz程序使用的
..
如何使用networkx + python枚举图中的所有*最大*集团?
如果您查看 https://en.wikipedia.org/wiki/Clique_problem ，您会注意到集团与最大集团之间有所区别.最大派别仅包含在其他派别中.所以我想要那些团体，但是networkx似乎只提供: networkx.algorithms.clique.enumerate_all_cliques(G) 所以我尝试了一种简单的for循环过滤机制(见下文).
..
识别给定边的连接图
我如何将甚至是间接相关的人归为一组?具体来说，使用如下所示的数据集的前两列，我如何在SAS中(可能使用DATA步骤或PROC SQL)以编程方式导出第三列?有非迭代算法吗? 背景:每个人都有多个地址.通过每个地址，每个人都连接到零个或多个人.如果连接了两个人，则他们将获得相同的组ID.如果人A直接连接到B，而人B连接到C，则人A，B和C共享一个组. data people; input
..
合并(加入)networkx图
说我有两个networkx图，G和H: G=nx.Graph() fromnodes=[0,1,1,1,1,1,2] tonodes=[1,2,3,4,5,6,7] for x,y in zip(fromnodes,tonodes): G.add_edge(x,y) H=nx.Graph() fromnodes=range(2,8) tonodes=range(8,14) for
..
如何防止graphviz中的边相互重叠
我有一个在graphviz中创建的图，但是问题是边彼此重叠(我每行有5-7个节点)，因此很难为每个节点分辨出它连接的节点 如何使边缘不互相重叠?让他们彼此交叉没关系. 解决方案 我假设您有一个带点布局的有向图. 我认为没有魔术开关可以防止边缘重叠. Graphviz尝试开箱即用. 一些建议可能会有所帮助，具体取决于图表: 边缘集中器(concentrate = tr
..
如何确定两个节点是否连接?
我担心这可能会解决NP-Complete问题.我希望有人可以给我一个答案，答案是否正确.我正在寻找的答案不仅仅是“是"或“不是".我想知道为什么.如果您可以说，“这基本上是这个问题'x'，它不是NP完全的.(维基百科链接)" (不，这不是家庭作业) 有没有一种方法可以确定两个点是否连接在任意无向图上.例如以下 Well | | A | +--B--+--C--
..
如何合并有交集的集合(连通分量算法)?
是否有任何有效的方法来合并具有交集的集合.例如: l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}] 预期结果是: r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}] 所有具有交集(公共分量)的集合都应合并.例如: {1, 3} & {2, 3} # {3} 因此这两个集合应该合并:
..
如何检测将边添加到有向图是否导致循环?
我遇到了等待图，我想知道是否有任何有效的算法来检测是否添加了有向图的边缘会导致一个循环? 所讨论的图形是可变的(它们可以添加或删除节点和边).而且，我们对知道一个犯罪周期并不感兴趣，只是知道一个周期就足够了(以防止增加一个犯罪边缘). 当然，可以使用一种算法来计算强连接的组件(例如Tarjan的组件)来检查新图是否非循环，但是每次添加边缘时再次运行它似乎效率很低. /p> 解决方案
..
如何使用Python检测有向图中的循环?
我有一些输入，例如:[('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')].我要查找的是此edgeList表示的有向图中是否存在循环. 我阅读了一个讨论: https://www.geeksforgeeks.org /detect-cycle-in-a-graph/，但是在以下情况下会出现一些错误: g = Graph(3) g.addEdge('A
..
从python中的元组或集合列表中找到不相交集合的集合
这是问题所在:我有一个元组列表(也可以根据需要设置).例如: a = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6)] 我要查找的是列表 r = [(1, 5, 4, 2, 3, 6, 7)] 因为一旦将所有集合放在一起，交点就不为空. 例如 a = [(1, 5), (4, 2), (4, 3), (5, 4), (
..
查找无向图的所有派系
如何列出无向图的所有派系? (并非所有最大派系都像Bron-Kerbosch算法一样) 解决方案 最优解决方案是这样的，因为在一个完整的图中有2 ^ n个团.考虑使用递归函数的所有节点子集.对于每个子集，如果子集的节点之间都存在所有边，则将1加到您的计数器中:(这几乎是C ++中的伪代码) int clique_counter = 0; int n; //number of node
..
可多次访问顶点的TSP
我正在解决一个有加权有向图，并且我必须从原点开始，至少访问所有顶点一次并以尽可能短的路径返回原点的问题.从本质上讲，这将是TSP的经典示例，除了我请勿有一个约束，即每个顶点只能被访问一次.在我的情况下，沿路径可以多次访问除原点以外的任何顶点，如果这样做会使路径更短.因此，例如在包含顶点V1, V2, V3的图形中，这样的路径将是有效的，因为它是最短的路径: ORIGIN -> V1 -> V
..