标签: directed-graph

我正在尝试找出一种算法,用于在有向图上找到路径.这不是一个传统的路径,我找不到任何像这样的东西的引用.

我想找到具有最大最小重量的路径.

即如果有两条路径的权重为10-> 1-> 10且2-> 2-> 2则第二路径被认为优于第一路径,因为最小权重(2)大于第一路径的最小权重( 1).

如果有人可以找到一种方法来做到这一点,或者只是指向一些参考资料的方向,那将是非常有用的:)

编辑::我似乎忘了提到我正试图从一个特定的顶点到另一个特定的顶点.非常重要的一点:/

EDIT2 ::如下所述,我应该强调边缘权重是非负的.

我目前正在开发一个项目,该项目使用有向超图框架枚举动态程序的k-best解决方案.我当前的实现(在Python中)运行良好,但速度相当慢.该算法执行许多紧密循环和相当多的递归.我真的认为我可以使用C++实现实现显着的速度提升.然而,经过一段时间的搜索,我无法找到任何在C++中提供超图实现的库(特别是有向超图 - 但我甚至无法找到无向超图的库).有谁知道这样的图书馆？几年前似乎有一个GSoC提议将超图支持提升,但它看起来并没有真正成功.

问题:循环问题允许您在通过特定弧的流动中具有下限和上限.我理解的上界(就像管道一样,只有很多东西可以通过).但是,我很难理解下限的想法.这是什么意思？将解决问题的算法...

• 尝试确保每个具有下限的弧将至少获得那么多的流量,如果找不到方法则完全失败？
• 如果不能满足下限,只需忽略弧线？这对我来说更有意义,但是意味着在结果图中可能存在流量为0的弧,即

上下文:我正在尝试找到一种方法来快速安排一组事件,每个事件都有一个长度和一组可能的时间来安排它们.我正在尝试将此问题简化为循环问题,因为存在有效的算法.

我将每个事件都放在有向图中作为一个节点,并为它提供应该填充的时隙量.然后我将所有可能的时间添加为节点,最后添加所有时间段,如下所示(所有弧点指向右侧):

前两个事件具有单个可能的时间和长度1,并且最后一个事件具有4的长度和两个可能的时间.

这个图表有意义吗？更具体地说,"填充"的时隙数量是2(只有'简单')还是6,如图所示？

(如果有任何不同,我正在使用LEMON库中的push-relabel算法.)

首先,我得到了一个N​​*N距离矩阵,对于每个点,我计算了它的最近邻居,所以我们有一个N*2矩阵,看起来像这样:

0 -> 1  
1 -> 2  
2 -> 3  
3 -> 2  
4 -> 2  
5 -> 6  
6 -> 7  
7 -> 6  
8 -> 6  
9 -> 8

Run Code Online (Sandbox Code Playgroud)

第二列是最近邻居的索引.所以这是一种特殊的有向图,每个顶点都有,只有一个外度.

当然,我们可以先将N*2矩阵转换为标准图形表示,然后执行BFS/DFS以获取连接的组件.

但是,鉴于这个特殊图表的特点,还有其他快速的方法来完成这项工作吗？

我将非常感激.

更新:

我在这里为这种情况 实现了一个简单的算法.

看,我没有使用union-find算法,因为数据结构可能会让事情变得那么容易,我怀疑它是否是我案例中最快的方法(我的意思是实际上).

您可能会认为_merge过程可能很耗时,但如果我们在分配新标签时将边缘交换到连续位置,则合并可能成本很低,但需要另外N个空格来跟踪原始索引.

我需要找到一种算法,用于在有向图中找到所有根,在O(n + m)中.

我有一个查找单个根的算法:

1. 在V中的某些v上运行DFS(v).如果结果是单个生成树,则v是根.否则,结果就是一片树林.然后:
2. 在最后一棵树的根目录上运行DFS(u).如果结果是单个生成树,则u是根.否则,图中没有根.

现在,如果我想找到所有的根,那么每次在最后一棵树的不同顶点上运行上述算法O(n)次的最佳方法是什么？假设我找到了一个根,如果存在另一个根,那么它必须在最后一棵树上,那么如果我继续运行上述算法直到收到"没有根存在"或者直到遍历所有顶点,那么它是O(n + m)吗？

提前致谢 !

考虑有向图,如下所示:

其中,(A)最初,实体黑边被断言:

• 0→{1,3}
• 1→{2}
• 3→{4}
• 4→{2}

然后(B)计算传递闭包以添加以下(虚线)边:

• 0→{2,4}
• 3→{2}

对于最终图形中的任何顶点,如何有效地计算某些边缘可访问的"直接"邻居,这些邻居无法通过不同的更长路径访问？我想要的输出显示在(A)中.我没有区分断言(粗体)或推断(虚线)的边缘.

这个问题是否有一个众所周知的名称,有没有一种直接的方法来实现这个JGraphT？

思考:

也许这可以通过使用拓扑排序的顶点来实现,例如TS = [0,1,3,4,2].

for(i=0, i<TS.len; i++) {
  var v0 = TS[i]
  for (j=i+1; i<TS.len; j++) {
    var v1 = TS[j]
    if (edge exists v0 -> v1) {
      var otherPath = false
      for (k=i+1; k<j; k++) {
        var v2 = TS[k]
        if (path exists v0 -> v2 && path exists v2 -> v1) {
          otherPath = true 
          break
        } …

给定一个加权有向多重图，我必须找到起始顶点 u 到顶点 v 之间的最短路径。除了权重，每条边也有时间。连接 u 和 v 的路径不能超过给定的最大时间。问题是在使用 Djikstra 时，最短路径可能需要比限制更多的时间。

我的方法是找到 u 和 v 之间的所有有效路径，而不是最小化权重。但该方法由于其高复杂性而不实用。

有任何想法吗？

public int bfs(int maxDepth){
        int src = 2;
        int dest = 2;
        int i;
        int depth = 0;
        int countPaths = 0;
        int element;

        queue.add(src);

        while(!queue.isEmpty() && depth <= maxDepth)
        {   
            element = queue.remove();
            i = 0;

            while(i < 5) 
            {   
                if(arr[element][i] > 0)
                {
                    queue.add(i);

                    if(i == dest)
                        countPaths++;
                }       
                i++;
            }
        }

        queue.clear();
        return countPaths;
    }

你好!!给定源和目的地,我需要找到一条路径.就遍历图表而言,我的BFS算法工作得很好.我的问题是当我想要它时停止它.我拿出了我增加深度的地方,所以我看起来不像是一个完全白痴.我希望有人能帮帮忙.基本上我想知道如何跟踪当前的深度.谢谢!

例:

找到从C到C的路径数,最多3个停靠点.答案是两条路:

C - > D - > C(2站)

C - > E - > B - > C(3站)

示例2:找到从A到C的路径数,最多3个停靠点.答案是三条路.

A …

我正在为一位教师的家庭成员编写应用程序.她要求一个应用程序,允许她进入一群孩子,设定他们的惯用手,设置他们不能坐在旁边的人,指定每个工作台有多少个座位,然后为孩子们生成一个随机的布局,这样就没有了 - 汉德斯坐在右手边的右边,不应该坐在一起的孩子们不会坐在长凳上.

这与通用表座位算法的问题并不完全相同,因为一个工作台有2个端点,并且因为节点没有"值"来创建任何优先分组.

我决定创建一个有向图,其中边表示谁可以坐在给定孩子的右边.然后我从每个节点做一个递归DFS而不触摸节点两次,直到我得到一个触摸每个节点的路径.一个问题是,在每个工作台的"尽头",任何人都可以坐到他们的"右边".

这个算法似乎总是有效,这很好.但是,一旦我超过10个孩子在一个长凳上,假设长椅可以说20个孩子,那么运行时似乎会变得非常糟糕.我做错了什么,还是有更好的方法来解决这个问题？Java代码如下.

编辑:对不起,我没有说清楚,但我希望每次都能实现RANDOM座位安排,这样孩子们就不会被困在同一个地方或同一个长凳上或者在同一个孩子旁边.此外,我的应用程序运行此算法:

http://kcraigie.com/sittychart

目前我正在强制执行1,000,000个节点触摸的上限,这样我的服务器就不会受到冲击.您可以看到算法似乎正确缩放,直到您将每个工作台的座位设置为9左右,此时它立即变得难以处理.

private static class Person {
    private String m_name = null;
    private Handedness m_handedness = null;
    private Set<Person> m_nonadjacents = null;
}

private static class Node {
    private Person m_person = null;
    private List<Node> m_possibleRightNodes = null;
    private boolean m_isInPath = false;
}

private Stack<Node> generateSeatingArrangement() {
    // Generate randomized directed graph, start with all nodes as root nodes
    for(Person leftPerson: people.values()) {
        Node node = new Node(leftPerson);
        nodes.put(leftPerson, node);
    } …

节点是否不与边缘重叠？我将dagre d3用于该图。对于节点，我使用引导程序。如果无法自动完成，该如何手动执行？这是一个示例图。我需要一个通用解决方案，而不是专门针对Fiddle / Image中的图形。 JS小提琴

var g = new dagreD3.graphlib.Graph().setGraph({});
  for (var i = 0; i < 7; i++) {
    var html = '<div class="panel panel-primary">'
    html += '<div class="panel-heading">' + i + ' Panel</div>'
    html += '<div class="panel-body"><p style= "color: black;">Test<p></div>'
    html += '</div>'
    g.setNode(i, {
      labelType: "html",
      label: html,
      padding: 0
    })
  }
  g.setEdge(0, 1, {
    label: "",
    lineInterpolate: 'basis',
  })
  g.setEdge(1, 2, {
    label: "",
    lineInterpolate: 'basis',
  })
  g.setEdge(0, 2, {
    label: "",
    lineInterpolate: 'basis',
  })
  g.setEdge(2, …