问题标签 [weighted-graph]

我目前正在尝试获取来自节点 1 的唯一路径的数量 .. 加权有向无环图的最大长度 N，我已经计算出获得最大长度，但我一直坚持获取给定路径的数量最长长度...

数据输入如下：

.... 作为节点 1-> 节点 2，权重为 34，

我已经研究出如何使用这个来实现最长的路径长度：

首先我制作一个顶点列表

接下来我遍历我的字典，将每个节点设置为最大权重

完成后，最后一个节点的权重将是最大值，所以我可以调用

以获得最大重量。这似乎执行得很快，并且即使在更大的数据集上执行时也可以轻松找到最大长度路径，然后我取我的最大值并将其运行到这个函数中：

一旦我们到达结束节点，我只需检查我们当前的总和是否为最大值，如果是，则将计数加一，如果不通过。

这适用于输入，例如 8 个节点，最长路径为 20，找到 3 条路径，以及输入，例如 100 个节点，最长长度为 149，只有 1 个该长度的唯一路径，但是当我尝试做一个数据集时具有 91 个节点，例如最长路径 1338 和唯一路径数为 32，该函数需要非常长的时间，它可以工作但很慢。

有人可以给我一些提示，说明我的函数出了什么问题，导致它需要很长时间才能从 1..N 中找到路径长度 X 的#？我假设它的运行时间呈指数增长，但我不确定如何修复它

谢谢您的帮助！

编辑：好的，我想太多了，并且以错误的方式解决了这个问题，我重组了我的方法，我的代码现在如下：

我在我的 Vertice 类中添加了一个 pathsTo 变量，它将保存 MAX 长度的唯一路径的数量

我正在使用 Python 3 和 Networkx 1.11。

我制作了一个加权图，在边缘和一些节点上有权重，但是当我计算最短路径的权重时，没有考虑节点的权重（下面的代码）。

有人知道如何确保考虑节点权重吗？

谢谢！山姆

我有一个关于 PageRank 如何显示“权重”的影响的问题。我想使用贸易价值作为权重来计算贸易国家的PageRank，我的代码如下所示。但我发现结果与未加权的结果相同。我不知道为什么。

有人可以帮助我了解如何在 PageRank 计算中显示“权重”吗？

关于加权图：

如果 A->B 的权重为 3，B->A 的权重为 1，这是否意味着 A 和 B 之间有 2 条边？我有 95% 的把握答案是肯定的，但我想确定一下。我正在尝试查看具有此类权重方案的有向图是否自动成为多重图。

感谢您的宝贵意见！

马库斯

下面是我当前的代码，我在实现 addvertex 函数时遇到了麻烦，我不太确定从哪里开始，因为我对 c++ 相当陌生，任何帮助将不胜感激。有人告诉我使用地图是最简单的方法。

该图需要计算最小生成树、深度和广度优先遍历以及实现迭代器。

addvertex 函数会将传递的顶点添加到图中（没有边）。

我正在使用 OrientDB ETL 模块将数据从 CSV 文件导入图形数据库。CSV 文件的格式如下：

我希望一旦我将它导入到 orientdb 中，每个a,和都保存为类中的一个顶点b，并且从到开始创建一个边，边权重作为csv 文件中的对应项。cdurlid_1urlid_2score

谁能帮我处理 ETL 的配置（JSON）文件？

我已经尝试过这里建议的解决方案：Easest way to import a simple csv file to a graph with OrientDB ETL但没有得到预期的结果。

I have been researching Graph theory and Dijsktra's only to find myself with too many ways to go about this, and I'm not sure which to apply to this specific problem. Here are the requirements:

In centralized routing, all the routing information is generated and maintained in a centralized location. A common way of maintaining routing information centrally is via a routing matrix. A routing matrix has a row and a column for each node in the network, where a row corresponds to the source node and a column corresponds to the destination node. The entry in row i column j is a pair (x , y), where x is the first node on the shortest path from i to j, and y is the cost of the shortest path from i to j.

Write a program that reads a weighted graph representing a network, and finds and outputs the corresponding routing matrix. The routing matrix will be written both to the screen and to an output file. Use Dijkstra’s algorithm to find the shortest cost and path between nodes. The program runs from the command line with two optional command line arguments. Use the following command line options to indicate the presence of a command line argument: -i (for input file name) and –o (for output file name). If no command line arguments are present, the program uses “xy_input.txt” and “xy_output.txt” as default input and output file names respectively. See examples below:

• java xy_rmatrix
• java xy_rmatrix –i xy_rmatrixi.txt –o xy-rmatrixo.txt

Sample Input/Output: The input file contains zero or more lines representing a graph of a network. Each line represents a bi-directional edge that is made up of two vertices (routers) and the cost associated with the link (communication line) between them. One or more whitespaces (blank, tab, etc.) will separate data on each line and the node names might be a string rather than a single character. Note that the routing matrix rows and columns are listed in alphabetical order.

Input:

Output:

My main question is, for this particular problem is it necessary to store the contents of the input file in its own data structure such as a graph or adjacency list, and how would I go about implementing these in Java with vertices/nodes and edges in a way that I can perform Dijsktra's Algorithm?

Am I also correct to assume that the routing matrix specified is synonymous with an adjacency matrix?

Note: I am not fishing for code, just a step in the right direction.

我在Stata中有以下数据：

我正在尝试使用以下命令创建药物半衰期的箱线图：

当我包含权重选项时，一些生成的箱线图由多个点组成，而不是典型的四分位距和中位数：

为什么会发生这种情况，我该如何解决？

给定一个类似下面的矩阵（但要大得多），它描述了一个加权无向图，

我想计算最大权重（x），以便连接诱导子图。由于假设初始图是连接的，因此必须有一个临界阈值x-critical，对于任何x <= x- critical ，提取的子图都是连接的。

出于这个原因，我构建了下面的函数来检查每个权重（按升序排序），如果图形的邻接矩阵呈现任何rowSums等于零。

问题是这种方法真的很浪费时间，我想知道是否有更有效的方法来计算该阈值。

我一直在尝试使用igraphR 中的包来绘制一个网络，其中每对节点在 -4 和 4 之间具有加权关系（-4 表示“尽可能远”）当我最初绘制数据时，我是能够使用权重来注释链接粗细，但不影响布局。修剪“最差”的边缘会有所帮助，但会导致弱链接节点从图表中脱落，参见 #64 和 #119 这个示例，并且似乎不能很好地将“低”值节点分开。最终，我想要的是将节点绘制为接近“相似”节点，而远离不同节点。（编辑：更改数据文件中的Weighttoweight有帮助，将重新提出问题以更清楚地询问）

我的代码和我的示例日期文件在这里：https ://www.dropbox.com/s/kuqo3a8twa149gd/paris_rouen.zip?dl=0