标签: graph-theory

抱歉问这个简单的问题，但是有什么方法可以确定完全连通的图吗？我读过一些论文，指出图的总连通性是图分析的前提。我在Matlab的一些图形分析工具箱中搜索了确定连通性的函数，但似乎这些工具箱中至少没有提供任何函数。您能给我一些建议吗？非常感谢！

令 G=(E,V) 为具有非负边成本的有向图。让 s 成为一个顶点。我需要找到一种算法，为每个顶点 v 找到包含 s 和 v 的最短循环。该循环可能多次包含相同的边。

显而易见的解决方案是从 s 运行 Dijkstra，以找到从 s 到每个 v 的最短路径。然后，从每个 v 再次运行 Dijkstra，以找到从 v 到 s 的最短路径。最短周期是两者的结合。

这可行，但需要 O(|V||E| + |V|^2*log|V|)。有更好的解决方案吗？

我尝试使用boost的transitive_reduction，但我不知道如何使用它。

我有一个定义为的图表：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, IQsNode*> Graph;
typedef Graph::vertex_descriptor Vertex;

我想调用该方法：

Graph TC;
boost::transitive_reduction(_fullGraph, TC,g_to_tr_map_stor,g_to_tc_map_stor);

我不知道“g_to_tr_map_stor”和“g_to_tc_map_stor”必须使用的类型。

根据我读到的信息，它一定是从顶点
到整数的映射。我尝试了很多种地图但没有成功。

一些想法？

谢谢

我使用无向图，G我的目标是找到比N 一对一关系中的节点最长的所有可能的链。

例如：

在下一张图中，一对一关系中长度超过 2 个节点的“链”是：

- d -> e -> f -> g
- c -> k -> l -> m

那么解决这个问题的最佳方法或算法是什么？

首先，我想澄清一下，我对图论和解析有向图的正确算法的经验很少，并且我在这里进行了搜索，但没有找到我想要的东西。希望你们能帮助我:)

我有一个大型有向图（大约 3000 个节点），其中有几个由连接节点组成的子图，并且子图彼此不连接。这是我这里拥有的数据的一个具有代表性的小图表：

我正在编写一个 Perl 脚本来查找从每个源节点到接收器节点的所有可能路径，并将它们存储在数组的数组中。因此，对于该图，可能的路径是：

1,2,3,4,5,6
1,2,3,4,5,7
1,8,9,10
11,12,13
11,14
15,16,17

我在脚本中完成此搜索的方法是在以下步骤中使用Graph模块：

1. 查找图中所有源节点并将它们存储在数组中
2. 找到图中所有的sink节点并将它们存储在一个数组中
3. 使用 Floyd-Warshall 算法查找所有对的短路径
4. 如果源节点和汇节点之间存在路径，则搜索 APSP Floyd-Warshall 图对象。如果存在路径，则将其存储在数组的数组中。如果没有路径，则什么也不做。

这是我的脚本中执行此操作的部分：

#Getting all source nodes in the graph:
my @source_nodes = $dot_graph->source_vertices();
my @sink_nodes = $dot_graph->sink_vertices();

# Getting all possible paths between from source to sink nodes in the graph:
print "Calculating all possible overlaps in graph\n";
my $all_possible_paths = $dot_graph->APSP_Floyd_Warshall();
print "Done\n"; 

# print "Extending overlapping contigs\n"; 
my @all_paths;
foreach my $source (@source_nodes) {
    foreach …

有人可以帮助我理解 LFR 基准和随机块模型之间的区别吗？我正在尝试比较人工数据集和真实数据集上的社区检测算法，在人工部分我不知道哪个基准生成器更合理？

所以我目前正在研究一个单词梯子问题的项目，我已经构建了用于存储所有字典单词的图表并在其中添加了边，我使用 boost 图库完成了此操作。

但令我困惑的是该breadth_first_search()函数，似乎参数只采用起始顶点，但没有结束顶点。

我检查了文档并注意到我可以为该搜索功能定义 BFS 访问者，但由于我是 boost 库的新手，我无法弄清楚它是如何工作的。

谁能解释如何实现寻找两个顶点之间的最短路径？我正在使用无向且未加权的图。

#include <iostream> // std::cout
#include <fstream>
#include <string>
#include <stdlib.h>
#include <utility> // std::pair
#include "headers.h"
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace std;

//Define a class that has the data you want to associate to every vertex and 
edge
//struct Vertex{ int foo;}
//  struct Edge{std::string blah;}

struct VertexProperties {
  string name;
  VertexProperties(string name) : name(name) {}
};

//typedef property<edge_weight_t, int> EdgeWeightProperty;
//typedef property<vertex_name_t, string> VertexNameProperty; …

def calculateShortestPath(self,vertexList,edgeList,startVertex):
    startVertex.minDistance=0

    for i in range(0,len(vertexList)-1):#N-1 ITERATION
        for edge in edgeList:
            #RELAXATION PROCESS
            u=edge.startVertex
            v=edge.targetVertex
            newDistance=u.minDistance+edge.weight
            if newDistance<v.minDistance:
                v.minDistance=newDistance
                v.predecessor=u
    for edge in edgeList:# FINAL ITERATION TO DETECT NEGATIVE CYCLES
        if self.hasCycle(edge):
            print("NEGATIVE CYCLE DETECTED")
            self.HAS_CYCLE=True
            return

上述函数是贝尔曼-福特算法实现的一部分。我的问题是，如何确定经过 N-1 次迭代后，已经计算出最小距离？在 Dijkstra 的情况下，据了解，一旦优先级队列变空，所有最短路径都已创建，但我无法理解此处 N-1 背后的推理。

N-Length of the Vertex List.
Vertex List-contains the different vertex.
EdgeList-List of the different Edges.

由于我是从教程视频中阅读的，因此实施可能是错误的。感谢您的帮助

抽象问题

我想在完整的加权二分图中找到最佳的最大匹配，其中两组顶点的大小差异很大，即一组顶点非常大，另一组非常小。

匈牙利算法不是解决此问题的好方法，因为它将虚拟顶点添加到较小的集合中，使得两个集合具有相同的大小，因此我失去了其中一个顶点集合非常小的所有潜在效率增益。

更具体地说

我已将对象（边界框）分为两组，并且有一个相似性度量（杰卡德重叠）来衡量任意两个对象的相似程度。我想产生两个集合之间的匹配，使得所有单独匹配的相似度之和最大。

问题在于，其中一组仅包含很少的对象，例如 10 个，而第二组非常大，例如 10,000 个对象。第一组中的 10 个对象中的每一个都需要与第二组中的 10,000 个对象中的一个进行匹配。

两组大小的不对称让我想知道如何有效地做到这一点。我无法使用匈牙利算法生成 10,000 x 10,000 矩阵。

在 C# 项目中，我需要执行一组测试。每个测试都有自己所依赖的测试集合。需要测试网络来形成有向无环图（DAG）。

使用符号 A -> B -> C，其中 A、B、C 代表测试，然后

C 依赖于 B，\nB 依赖于 A。

我已经有了一个对测试进行排序的算法，以便我可以按顺序处理它们，从而尊重所有依赖项。也就是说，顺序意味着每个 test\xe2\x80\x99s 依赖项在整个图的测试本身被评估之前被评估。

我想要的是一种算法，它首先进行一组测试，然后可以将它们划分为单独的 DAG 图（如果存在）。每个 DAG don\xe2\x80\x99t 中的测试需要排序，因为可以单独完成。这样做的原因是我可以将每个独立的 DAG 作为单独的任务运行，并通过这种方式获得一些效率。

因此，考虑一组测试 A、B、C、D、E、F，其依赖关系为：

A -> B -> C\n\nD -> C\n\nE -> F\n

根据算法，我想要 2 组测试，

Set 1) A,B,C,D\n\nSet 2) E,F\n

更新：C# 代码帮助向 Eric 提出请求。

    public class Graph\n{\n    private List<Node> _nodes = new List<Node>();\n\n    public IReadOnlyList<Node> Nodes => _nodes;\n\n    public void AddNode(Node node)\n    {\n        _nodes.Add(node);\n …