标签: weighted-graph

如果我有一个矢量(例如v<-runif(1000)),我可以绘制它的直方图(它或多或少看起来像水平线,因为v它是来自均匀分布的样本).

但是,假设我有一个向量及其相关权重(例如,w<-seq(1,1000)除此之外v<-sort(runif(1000))).例如,这是table()一个更大的数据集的结果.

如何绘制新的直方图？(它应该看起来更像是y=x这个例子中的线).

我想我可以table通过使用rep(hist(rep(v,w)))反转效果但是这个"解决方案"看起来很丑陋且资源丰富(创建一个大小的中间向量sum(w)),它只支持整数权重.

我正在使用igraph for R.我的图表基于一个包含平行边缘的边缘列表(多个边缘具有相同的源和目标).我想将这些平行边缘转换为边缘属性权重.有没有一种方法可以做到这一点？

如果没有简单的方法.如何识别这些平行边缘？

    duplicated(E(net))

不会返回单个副本.我想它正在寻找重复的边缘ID.

spark的graphFrames包很棒。我可以使用命令找到从“a”到“d”的最短路径

val results = g.shortestPaths.landmarks(Seq("a", "d")).run()

但是如何定义加权图并计算两个节点之间的最短路径？

谢谢。

我正在 python 3 中构建 networkx 图。我正在使用 Pandas 数据框为图提供边和节点。这是我所做的：

test = pd.read_csv("/home/Desktop/test_call1", delimiter = ';')

g_test = nx.from_pandas_edgelist(test, 'number', 'contactNumber', edge_attr='callDuration')

我想要的是 Pandas 数据框的“callDuration”列作为 networkx 图的边的权重，边的厚度也相应地改变。

我还想获得“n”个最大加权边。

我正在与 networkx 一起计算k- shortest simple paths。nx.shortest_simple_paths(G, source, target, weight=weight)以成本递增的顺序返回路径列表（考虑权重的累积路径长度）。

我有兴趣获得这些路径的成本。networkX 中是否有任何简单的函数来获得它？

这个问题类似于这个问题：Networkx 中是否已经实现了算法来返回路径长度和路径？.

我相信该帖子中发布的答案是错误的。从如何添加用于计算图中边权重的自定义函数？我做了以下解决方案（见下文）。

这是正确的方法吗？

networkx 库中有什么简单可用的东西吗？

我的目标是找到k-shortest path的成本。

G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.size()

def path_length(G, nodes, weight):
    w = 0
    for ind,nd in enumerate(nodes[1:]):
        prev = nodes[ind]
        w += G[prev][nd][weight]
    return w

for path in nx.shortest_simple_paths(G, 'a', 'd', weight='weight'):
    print(path, len(path)) # …

虽然存在一些涉及从邻接矩阵创建图的问题，但我还没有找到太多关于从加权图中提取加权邻接矩阵的信息。

假设我有以下图表：

library(igraph)
nodes <- data.frame(name=c("a","b", "c", "d", "f", "g"))

col1 <- c("a", "g", "f","f", "d","c")
col2 <- c("b", "f","c","d","a","a")
weight <- c(1,4,2,6,2,3)
edges <- cbind.data.frame(col1,col2,weight)

g <- graph.data.frame(edges, directed=F, vertices=nodes)
E(g)$weight <- weight

如何得到图g的加权邻接矩阵？

我有一个边缘列表，我想将其转换为加权图。我用下面的代码：

edgelist <- read.table(text = "
V1 v2 weights
A B 1
B C 8
C D 6
D E 9
C F 12
F G 15",header=T)


g<-graph_from_data_frame(edgelist)
g

它将权重作为边缘的属性。但是，当我想检查它是否加权时：

is_weighted(g)

它返回了我FALSE。如何将其更改为TRUE？

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

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

给定一个像这样的简单无向网格网络：

import networkx as nx
from pylab import *
import matplotlib.pyplot as plt
%pylab inline

ncols=3
N=3 
G=nx.grid_2d_graph(N,N)
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds=[(N-j-1,N-i-1) for i,j in inds]
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10)
plt.axis('off')
plt.title('grid')
plt.show()

考虑到每条边都有与其长度相对应的权重：

#Weights
from math import sqrt

weights = dict()
for source, target in G.edges():
    x1, y1 = pos2[source]
    x2, y2 = pos2[target]
    weights[(source, target)] = round((math.sqrt((x2-x1)**2 + …

以下是我正在研究的问题：

考虑一个有向加权图 G ，其中所有边的权重都是正的。这个问题的目标是找到G 中 两个预先指定的顶点s 和 t之间 的最短路径 ，但有一个额外的扭曲：您可以将（您选择的）恰好一条边的权重更改为零。

换句话说，您必须在G 中选择一条边 以设置为零，以最小化s 和 t之间的最短路径 。给出一个有效的算法来在O ( E lg V )时间内实现这个目标， 并分析你的算法的运行时间。次优解决方案将获得较少的信用。

提示：您可能需要反转边缘，多次运行熟悉的算法，并做一些额外的工作

所以我尝试将 Dijkstra 从s运行到所有其他节点，然后我尝试反转边缘并再次从s运行它到所有其他节点。但是，我发现我们必须从s到所有其他节点运行 Dijskstra ，然后反转边，然后从所有其他节点运行 Dijkstra到t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们只需将最大权重边缘设置为零。反转边缘有什么意义？

我已经设法创建了一个随机的无向加权图，用于使用 Dijkstra 算法进行测试，但是我怎样才能做到让每个节点至少有一条边将它们连接到图？

我正在使用 Networkx，我的图形生成器如下：

import networkx as nx
import random

random.seed()
nodes = random.randint(5,10)
seed = random.randint(1,10)
probability = random.random()
G = nx.gnp_random_graph(nodes,probability,seed, False)
for (u, v) in G.edges():
    G.edges[u,v]['weight'] = random.randint(0,10)

这很好地创建了图形，我设法绘制了它，所以我实际上可以看到它，我的问题是边缘创建的概率。我不希望它太高以至于所有节点都具有最大边数，但是设置一个低值可能会导致节点具有 0 个边。有没有办法确保每个节点至少有一条边？

我已经编写了一个用于无向图的类和一个符号表来将字符串转换为数字,反之亦然但是这两个字符串方法不起作用,因为我得到了堆栈溢出错误.我实现了一个LinkedStack,它与java库中的堆栈相同.我没有收到编译错误,如果能查看toString方法,我将不胜感激.其他方法工作正常.这是下面的代码.我认为问题是当我调用迭代器时

public class EdgeWeightedGraph {
private final int V;
private int E;
private LinkedStack<Edge>[] adj;

public EdgeWeightedGraph(int V){
    this.V = V;
    this.E = 0;
    adj = new LinkedStack[V];
    for (int v = 0; v < V; v++)
    {
        adj[v] = new LinkedStack<Edge>();
    }
}

public int V(){
    return V(); // This was the error. thank you for spotting it :)
}

public int E(){
    return E;
}

public int degree(int v){
    return adj[v].size();
}

public void addEdge(Edge e){
    int v …