标签: graph-theory

我使用 cuGraph 来计算图的最短路径，但它不是返回到特定顶点的最短路径，而是创建一个距离顶点前驱表：

        distance    vertex  predecessor
3935    0.000000    0       -1
3372    0.063761    1       173
3136    0.059330    2       236
395     0.096309    3       131
3780    0.078157    4       222
... ... ... ...
3886    0.157694    4886    4817
3062    0.226340    4887    4871
3895    0.171506    4888    4816
3057    0.165199    4889    4842
3898    0.213998    4890    4888

如何使用该图获取到特定顶点的路径？

我知道我可以循环遍历它直到到达顶点 0，但这听起来效率不高。有没有办法使用矢量化来保持高效？

我有一个由用户创建的有向无环图，其中图的每个节点（顶点）代表对某些数据执行的操作。节点的输出取决于其输入（显然），并且该输入由其父节点提供。然后输出将传递给其子级。保证不存在循环，因此可以忽略。

该图的工作原理与Blender 中的着色器编辑器相同。每个节点对其输入执行一些操作，并且该操作的成本可能任意高。因此，我只想在严格要求时评估这些操作。

当通过用户输入或其他方式更新节点时，我需要重新评估每个节点，这取决于更新节点的输出。但是，鉴于我无法证明多次评估同一节点的合理性，我需要一种方法来确定更新节点的正确顺序。基本的广度优先遍历并不能解决问题。要了解原因，请考虑此图：

传统的广度优先遍历将导致D在 之前进行评估B，尽管D依赖于B。

我尝试过反向进行广度优先遍历（即从O1和O2节点开始，向上遍历图形），但我似乎遇到了同样的问题。反向广度优先遍历将访问Dbefore B，因此I2before A，导致I2被排序在 after A，尽管A取决于I2。

我确信我在这里遗漏了一些相对简单的东西，而且我觉得反向遍历似乎是关键，但我似乎无法全神贯注并让所有部分都适合。我认为一个潜在的解决方案是按预期使用反向遍历，但不是避免多次访问每个节点，而是在每次出现时访问每个节点，确保它具有绝对正确的顺序。但是多次访问每个节点以及随之而来的指数扩展是一个非常没有吸引力的解决方案。

对于此类问题是否有众所周知的有效算法？

我试图找出一种最佳方法来获得从所有源节点到任何一个目标节点的最短路径，从而导致加权图中的权重最小。所有节点要么是源节点，要么是目标节点。因此，我们有一个图，其中 A、B、C 作为源节点，D、E、F 作为目标节点。A、B、C 必须找到到达任意一个恰好具有最短路径的目标节点的最短路径。

简单的解决方案是使用 Dijkstra 算法或类似的算法，首先找到从 A 到 D 的最短路径，然后从 A 到 E 等，然后比较每条最短路径的最终权重，看看哪条实际上是最短的。我想知道是否有更有效的解决方案。

这就是我要解决的问题

我们想要将一组 n 人（标记为 1 到 n）分成任意大小的两组。每个人都可能不喜欢某些人，他们不应该加入同一群体。给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi] 表示标记为 ai 的人不喜欢标记为 bi 的人，如果可以通过这种方式将每个人分成两组，则返回 true。

这可以通过 Python 中的 BFS 相当简单地解决：

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = defaultdict(set)
    for a, b in dislikes:
        graph[a-1].add(b-1)
        graph[b-1].add(a-1)

    q = deque({0})
    colors = [None]*n
    for i in range(n):
        if colors[i] is None:
            q = deque({i})
            colors[i] = 0
            while q:
                cur = q.popleft()
                for d in graph[cur]:
                    if colors[d] is None:
                        q.append(d)
                        colors[d] = 1 …

我怎样才能找出导致equals()返回false的原因？

我不是在问一个确定的方法,总是正确的方法,而是一些有助于开发过程的东西.目前我必须进入equals()调用(通常是它们的树),直到其中一个为假,然后进入它,令人作呕.

我想过使用对象图,将其输出到xml并比较两个对象.但是,XMLEncoder需要默认构造函数,jibx需要预编译,x-stream和简单的api不在我的项目中使用.我不介意将一个类,甚至一个包复制到我的测试区域并在那里使用它,但导入整个jar只是不会发生.

我还想过自己构建一个对象图遍历器,我可能仍然会这样做,但我不想开始处理特殊情况(有序集合,非有序集合,映射......)

知道如何去做吗？

编辑:我知道添加罐子是正常的做事方式.我知道罐子是可重复使用的单位.然而,(在我的项目中)所需的官僚机构并不能证明结果是合理的 - 我会继续进行调试和踩踏.

我尝试编写一个脚本来计算图表的连接组件,但我无法得到正确的解决方案.我有一个简单的图形,有6个节点(顶点),节点1和2连接,节点3和4连接(6个顶点; 1-2,3-4,5,6).因此该图包含4个连接组件.我使用以下脚本来计算连接的组件,但我得到错误的结果(2).

nodes = [[1, [2], False], [2, [1], False], [3, [4], False], [4, [3], False], [5, [], False], [6, [], False]]
# 6 nodes, every node has an id, list of connected nodes and boolean whether the node has already been visited    

componentsCount = 0

def mark_nodes( list_of_nodes):
    global componentsCount
    componentsCount = 0
    for node in list_of_nodes:
      node[2] = False
      mark_node_auxiliary( node)

def mark_node_auxiliary( node): 
    global componentsCount
    if not node[2] == True: 
      node[2] = True
      for neighbor in node[1]: …

正如标题所说..在java中存储连接图的最有效方法是什么？

例如,假设我有多个位置以各种方式相互连接,我必须遍历图表以查看它是否已连接..任何帮助/评论都会有所帮助,谢谢!

我正在努力解决这个算法问题:

我如何编写一个theta(m+n)算法来打印m边,n-顶点有向图中每个顶点的入度和出度,其中有向图用相邻列表表示.

我明显错过了穿过树林的森林......

我知道旅行商问题,但有没有其他算法/问题更符合我的需求/描述？我需要借助这样的数学描述来描述我的问题.

我知道起始点和终点点最多有5个点.所以我只需要计算访问这两者之间所有三个点的最短路径.Dijkstra和类似的算法试图找到两点之间的最短路径,所以在这里它们可能不会访问它们之间的所有点.或者是否有一种算法找到最短路并访问两点之间的所有点？

我（在其他SO用户的帮助下）“粘合”了一个小型C程序，该程序将字符串标签映射到边缘列表数据结构中的整数标签。例如，对于输入文件

Mike Andrew
Mike Jane
John Jane

程序输出

1 2
1 3
4 3

但是，我映射了巨大的边缘列表文件，不幸的是，与Python相比，该程序运行非常慢。下面，我用C和Python粘贴了这两个程序。请问如何提高C程序速度的指针。

#include <stdio.h>
#include <stdlib.h>

// Initial number of maximal lines in a file
enum { MAXL = 200};

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

typedef struct {
    unsigned int hashed;
     char **map;
} hash;


int insertInMap(hash *map, char *entry)
{
  int i =0;
  for (i=0;i<map->hashed;i++)
  {
    if (strcmp(map->map[i],entry) == 0)
    return i+1;
  }
  /* Warning no boundary check is added …