标签: graph-theory

我试图在一个可能有循环但没有自循环的有向加权图中找到权重小于N 的两个顶点之间的所有路径。到目前为止，我只能通过使用AllDirectedPaths然后过滤掉权重大于 N 的路径来做到这一点：

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> g = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
AllDirectedPaths<String, DefaultWeightedEdge> allPaths = new AllDirectedPaths<>(g);
int maxWeight = 30;
List<GraphPath<String, DefaultWeightedEdge>> pathsLimitedByWeight = allPaths.getAllPaths(startVertex, endVertex, false, maxWeight / minGraphLatency)
    .filter(graphPath -> graphPath.getWeight() < maxWeight)
    .collect(Collectors.toList());

这种方法显然是次优的，因为对于较大的图形它很慢。为了限制输出并使其更快，我提供maxPathLength了AllDirectedPaths#getAllPaths，我将其设置为路径可以除以图中边的最小权重的最大权重，因为在我的情况下，边权重是一个整数并且总是大于1.

我考虑过使用KShortestSimplePathscustom PathValidator，但它只支持简单的路径，即不允许循环。

如果有的话，我在 jgrapht 中还有什么其他选项可以用来解决查找所有路径而不必自己遍历图形。

关系parent-child数据框如下：

  parent_id child_id
1         1        2
2         2        3
3         3        4

目标是实现以下目标，即先前数据框的扩展版本，其中所有后代（子代、孙子等）都分配给每个父代（包括父代/子代本身）：

   parent_id child_id
1          1        1
2          1        2
3          1        3
4          1        4
5          2        2
6          2        3
7          2        4
8          3        3
9          3        4
10         4        4

我的问题是：在 R 中实现这一目标的最快方法（或其中之一）是什么？

我已经尝试过各种方法 - 从 for 循环、SQL 递归到使用igraph（如此处所述）。它们都相当慢，并且其中一些在处理大量组合时还容易崩溃。

sqldf下面是和 的示例igraph，在比上面稍大的数据帧上进行基准测试。

library(sqldf)
library(purrr)
library(dplyr)
library(igraph)

df <- data.frame(parent_id = 1:1000L)
df$child_id <- df$parent_id + 1L …

我非常喜欢Yahoo Pipes的界面(http://pipes.yahoo.com/pipes/),并希望为不同的问题创建类似的界面.是否有任何库可以让我创建一个具有相同基本外观的界面？

我特别喜欢管道的行为以及它们不仅仅是直线.

编辑:该应用程序将基于Web.我愿意使用Flash或Javascript.

我有一大堆加权节点,边缘将节点簇连接在一起.该图遵循典型的小世界布局.

我希望找到一种路径寻找算法,它在处理器功率上并不昂贵,找到沿着最佳路径的路径,其中节点是最有利的加权,最快路径不是最重要的因素.该算法还考虑了承载和流量重新路由.

(旁注:可以在这里使用神经网络吗？)

谢谢

我在看ACO.对于这类问题,还有比ACO更好的东西吗？

正确的A*算法找到成本最低或最快的路由,没有负载平衡.

假设最快或最短的路线不是最重要的路线,更重要的是遵循加权节点具有特定值的路径.NO1.

NO2.如果使用A*,该路由上的流量会过载,那么突然该路径是多余的.因此,与A*一样酷,它没有ACO的某些特性,即固有的负载平衡.

- 除非我误解和误解A*

然后是什么击败了ACO？

它真的看起来像ACO和A*之间的展示,有很多关于A*的积极谈论,我一定会更深入地了解它.

首先回应大卫; 我可以在后台运行ACO模拟并提出最佳路径,所以是的,有一个初始启动成本,但幸运的是,启动并不重要.所以我可以多次运行模拟.一个真正的麻烦是找到连接的源节点和目标节点.而A*似乎很容易就能做到这一点.现在当这个网络像数百万个节点一样变得非常大时会发生什么.A*能够轻松扩展吗？

我将进一步研究A*.但是我给你留下了最后一个问题!

A*能够和Antnet(ACO)一样扩展吗？

设G是包含周期的未加权有向图.我正在寻找一种算法,它可以找到/创建所有非循环图G',它由G中的所有顶点和G的边缘子集组成,只要小到足以使G'非循环.

更正式:所需算法使用G并创建一组非循环图S,其中S中的每个图G'满足以下属性:

1. G'包含G的所有顶点.
2. G'包含G的边缘子集,使得G'是非循环的.
3. G'的边缘数量最大化.这意味着:没有G''令人满意的属性1和2,这样G''包含更多的边,然后G'和G''是非循环的.

背景:原始图G模拟元素之间的成对排序.由于图中的循环,这不能被用作对所有元素的排序.因此,最大非循环图G'应该模拟这种排序的最佳可能近似,试图尽可能多地考虑成对排序关系.

在一种天真的方法中,人们可以去除所有可能的边缘组合,并在每次移除后检查是否有空隙.在这种情况下,存在强烈分支的变化树,意味着时间和空间复杂性差.

注意:问题可能与生成树有关,您可以将G'图定义为一种有向生成树.但请记住,在我的场景中,G'中的一对边可能具有相同的起始或相同的结束顶点.这与文献中使用的定向生成树的某些定义相冲突.

编辑:添加了与生成树相关的直观描述,背景信息和注释.

我正在阅读用于查找最小生成树的算法(在加权图的情况下)以及查找图是否具有哈密顿路径(这取决于哈密顿循环的存在).我把一切搞砸了.那哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点.虽然我们可以使用有效的算法来查找生成树(可能是最小的生成树),但为什么我们不能找到哈密顿电路的算法？我们可以继续一次添加和删除一个边缘,直到我们达到一个周期,也许,我们可以找到一个哈密顿周期？

这是我的问题:我有一个序列S(非空但可能不是不同)设置s_i,并且对于每个s_i需要知道S(i≠j)中有多少个集合s_j是s_i的子集.

我还需要增量性能:一旦我完成所有计数,我可以用s_i的某个子集替换一组s_i并逐步更新计数.

使用纯功能代码执行所有这些将是一个巨大的优势(我在Scala中的代码).

由于set包含是一个部分排序,我认为解决我的问题的最好方法是构建一个DAG,它表示集合的Hasse图,边表示包含,并将一个整数值连接到表示大小的每个节点节点下方的子d加1.但是,我已经被困了好几天试图开发从部分排序构建Hasse图的算法(让我们不谈增量!),即使我认为它会是一些标准本科教材.

这是我的数据结构:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

我的DAG由根列表和一些部分排序定义:

class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
  def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))

  private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (roots == Nil) collected
    else {
      val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
      collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
    }
}

我很困在这里.我最后向DAG添加了一个新值v:

1. 找到DAG中v的所有"根子集"rs_i,即v的子集,使得rs_i的超集不是v的子集.这可以通过在图上执行搜索(BFS或DFS)非常容易地完成( …

我是python的新手,我正在研究图形问题,我想绘制这个图表以便更好地理解它.我知道matplotlib模块应该是为此导入的,但我不知道如何将它添加到项目中.(我是一个java开发人员,它就像在你的类路径中添加jar一样)

当我尝试做的时候

import matplotlib

我收到以下错误:

File "/Library/Python/2.7/site-packages/networkx-1.7rc1-py2.7.egg/networkx/drawing/nx??_pylab.py", line 114, in draw
    raise ImportError("Matplotlib required for draw()")
ImportError: Matplotlib required for draw()
ImportError: No module named matplotlib.pyplot

任何人都可以帮助我吗？我是否需要下载任何东西才能让它在模块中运行？

我有一些看起来像这样的数据:

vertex_numbers = [1, 2, 3, 4, 5, 6]

# all order here is unimportant - this could be a set of frozensets and it would
# not affect my desired output. However, that would be horribly verbose!
edges = [
    (1, 2),
    (1, 3),
    (1, 4),
    (1, 5),

    (2, 3),
    (3, 4),
    (4, 5),
    (5, 2),

    (2, 6),
    (3, 6),
    (4, 6),
    (5, 6)
]

上面的例子描述了一个八面体 - 对顶点1到6进行编号,其中1和6彼此相对,每个条目描述每个边的末端的顶点数.

从这些数据中,我想生成一个面部列表.面部保证是三角形的.这是上面输入的一个这样的面部列表,由手工确定:

faces = [
    (1, 2, 3),
    (1, 3, …

我很难找到一种方法来正确地对边缘进行分类,同时在有向图上进行广度优先搜索.

在广度优先或深度优先搜索期间,您可以对满足4个类的边进行分类:

• 树
• 背部
• 交叉
• 向前

Skiena [1]给出了一个实现.如果沿着从v1到v2的边缘移动,这里有一种在Java中的DFS期间返回类的方法,以供参考.父映射返回当前搜索的父顶点,以及timeOf()方法,即发现顶点的时间.

if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
    if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
    if ( processed.contains( v2 ) )
    {
        if ( timeOf( v1 ) < timeOf( v2 ) )
        {
            return EdgeClass.FORWARD;
        }
        else
        {
            return EdgeClass.CROSS;
        }
    }
    return EdgeClass.UNCLASSIFIED;

我的问题是我无法在有向图上进行宽度优先搜索.例如:

下图 - 这是一个循环 - 是可以的:

A -> B
A -> C
B …