标签: graph-theory

因此,我理解在图中找到最长的简单路径的问题是NP难的,因为您可以通过将边权重设置为1并查看最长简单路径的长度是否等于数量来轻松解决哈密顿电路问题.边缘.

我的问题是:如果你采用图表,找到最大边缘权重m,用每个边缘权重w替换m - w,并运行标准的最短路径算法,你会得到什么样的路径？它显然不是最长的简单路径,因为如果是,那么NP = P,我认为类似的东西的证明会更复杂= P.

我使用pydot python库生成了带点语言的Graphviz图像. 生成的Graphviz图

但边缘正在绘制曲线.

我需要这种:预期的Graphviz输出.

我打开使用任何其他开源库作为我的web项目.

请提供graphviz或任何图书馆链接的任何解决方案,这将有很大帮助.

这是一个理论/迂腐的问题:想象一下属性,其中每个属性可以由多个其他人拥有.此外,从所有权的一次迭代到下一次,两个邻近的所有者可以决定部分地结合所有权.例如:

territory 1, t=0: a,b,c,d
territory 2, t=0: e,f,g,h

territory 1, t=1: a,b,g,h
territory 2, t=1: g,h

也就是说,c并d不再拥有自己的财产; 可以这么说g,h成了肥猫.

我目前将这个数据结构表示为一个树,每个孩子可以有多个父母.我的目标是将其融入复合设计模式中; 但我遇到的问题是如何在客户可能会回过头来更新以前的所有权而不会破坏整个结构.

我的问题是双重的.

1. 简单:这个数据结构有什么方便的名称,这样我可以自己谷歌吗？

2. 辛苦:我做错了什么？当我编码时,我试着保持口头禅,"保持简单,愚蠢",在我脑海里,我觉得我打破了这个信条.

我知道最长的路径问题对于一般图表来说是NP难的.但是,我正在考虑一种特殊的图形,包括一个周期,加上周期的每个顶点上的一个附加边缘事件.例如,对于长度为7的循环,我们有图表:

所有边都是加权的(权重是实数,可以是正数或负数).我想在此图上找到最大的简单路径,其中路径的大小是路径上边缘权重的总和.

该算法应该是循环大小的线性.但任何想法都值得赞赏.

假设我有7个小垃圾箱,每个垃圾箱里面都有以下数量的弹珠:

var smallBins = [1, 5, 10, 20, 30, 4, 10];

我将这些小容器分配给2个大容器,每个容器具有以下最大容量:

var largeBins = [40, 50];

我想找到各种小容器如何在不超出容量的情况下分布在大容器上的组合(例如,将小容器#4,#5放在大容器#2中,其余放在#1中).

约束:

• 必须将每个小容器分配给一个大容器.
• 一个大垃圾箱可以留空

这个问题很容易在O(n ^ m) O(2 ^ n)时间内解决(见下文):只需尝试每个组合,如果不超过容量,请保存解决方案.我想要更快的东西,可以处理可变数量的箱子.我可以用什么模糊的图论算法来减少搜索空间？

//Brute force
var smallBins = [1, 5, 10, 20, 30, 4, 10];
var largeBins = [40, 50];

function getLegitCombos(smallBins, largeBins) {
  var legitCombos = [];
  var assignmentArr = new Uint32Array(smallBins.length);
  var i = smallBins.length-1;
  while (true) {
    var isValid = validate(assignmentArr, smallBins, largeBins);
    if (isValid) legitCombos.push(new Uint32Array(assignmentArr));
    var allDone = increment(assignmentArr, largeBins.length,i); …

我需要回答这个问题:给定一个依赖图中的节点,通过它们自己的传递依赖对其依赖者进行分组,这些依赖会受特定的起始节点的影响.

换句话说,给定依赖图中的节点,找到直接依赖的集合的集合,其直接依赖于从该特定起始节点导出的公共依赖.

例如,给出伪代码:

let a = 1
let b = 2
let c = a + b
let d = a + b
let e = a
let f = a + e
let g = c + d

你可以计算这个图:

如果我们用作a起始节点,我们可以看到a两者的依赖性,c并且d具有依赖性g.并且f有依赖e和a.

请注意,a根本没有任何影响b,因此在决定如何对依赖者进行分组时不应将其考虑在内a.

使用a作为起始节点,我们想要获得这些分组的依赖集:

groups = {{c, d}, {e, f}}

c并且d具有直接或传递的下游关系,并且e也 …

给定未加权无向图的邻接矩阵,是否有一种有效的方法(多项式算法)来扩展/增加任何给定的两个节点s和t之间的最短路径的长度？

例:

在下面的例子中,从顶点s = 1到顶点t = 5有5个不同的"最短路径",每个都有3个长度.我想删除最少数量的边缘,以便最短路径长度被强制为4或更多.(断开图表是可以的.)

邻接矩阵(扩展以纠正示例):

 0 1 0 0 0 1 1 1 0 1 0 
 1 0 1 1 0 0 0 0 0 0 0  
 0 1 0 0 1 0 0 0 0 0 1 
 0 1 0 0 1 1 0 0 0 0 0  
 0 0 1 1 0 1 0 0 0 0 0 
 1 0 0 1 1 0 0 0 1 0 0 
 1 0 0 0 0 0 …

我有一个庞大的路由器网络,所有路由器都在社区网络中互连.我试图通过不同的方式分析这个网络并获得有用的见解以及通过分析图表(使用gephi)来改进它的方法.所以我遇到了这个称为"模块化"的措施,其定义为:

衡量网络划分为模块(也称为组,集群或社区)的强度.具有高模块性的网络在模块内的节点之间具有密集连接,但是在不同模块中的节点之间具有稀疏连接.

我的问题是,通过使用"模块化"度量,我可以从网络中学到什么？例如,当我在gephi中使用它时,每个网段都会对网络进行着色,但它有什么用呢？

我想创建一个图表,显示来自邻接矩阵的节点之间的连接,如下所示.

gplot似乎是最好的工具.但是,为了使用它,我需要传递每个节点的坐标.问题是我不知道坐标应该在哪里,我希望这个函数能够为我找出一个好的布局.

例如,这是我的输出使用以下任意坐标:

 A = [1 1 0 0 1 0;
      1 0 1 0 1 0;
      0 1 0 1 0 0;
      0 0 1 0 1 1;
      1 1 0 1 0 0;
      0 0 0 1 0 0];

 crd = [0 1;
        1 1;
        2 1;
        0 2;
        1 2;
        2 2];

 gplot (A, crd, "o-");

这很难读,但是如果我稍微使用坐标并将它们更改为以下内容就会变得更具可读性.

   crd = [0.5 0;
         0 1;
         0 2;
         1 2;
         1 1;
         1.5 2.5];

我不希望完美优化的坐标或任何东西,但我怎么能告诉MATLAB自动为我找出一组坐标看起来没问题使用某种算法,所以我可以绘制一些看起来像顶部图片的东西.

提前致谢.

我试图找到使用apache spark在大量数据上搜索不相交集(连接组件/ union-find)的算法.问题是数据量.甚至图顶点的Raw表示也不适合单机上的ram.边缘也不适合公羊.

源数据是hdfs上图形边缘的文本文件:"id1\t id2".

id作为字符串值存在,而不是int.

我发现天真的解决方案是:

1. 拿rdd of edges - > [id1:id2] [id3:id4] [id1:id3]
2. 按键分组边缘. - >[id1:[id2;id3]][id3:[id4]]
3. 为每个记录设置每组最小ID - > (flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. 从第3阶段逆转 [id2:id1] -> [id1:id2]
5. leftOuterJoin 第3阶段和第4阶段的rdds
6. 从第2阶段开始重复,而第3步的rdd大小不会改变

但这导致节点之间传输大量数据(改组)

有什么建议吗？