标签: adjacency-matrix

有人知道如何在python中处理巨大矩阵吗？我必须处理形状为（10 ^ 6,10 ^ 6）的邻接矩阵，并执行包括加法，缩放和点积的操作。使用numpy数组，我在ram上遇到了问题。

我对图表和邻接矩阵感到困惑.我正在为一个类做一个任务,我有一个节点的文本文件和一个边缘的文本文件,我必须阅读它们中的每个并使它们成为一个图形,然后我可以在其上执行操作,例如确定图形是否为连接,找到最小的生成树,遍历和查找路径.我之前从未使用过图表,而且我对整个事情感到困惑,我想知道是否有人可以帮我解释一下这些.

首先,我自己构建一个图形(可能是节点和边类？)然后从中构造一个邻接矩阵？或者邻接矩阵本身是图形？

然后我对如何将相邻矩阵实现到程序中感到困惑.节点的名称是"ND5"和"NR7",所以我必须设置和读取[ND5] [NR7]的边缘,但我不知道如何设置像这样的2d数组的字符串外面和里面的数字.

我一直在网上搜索并阅读我教科书中关于图表的整章,我真的不明白设置这个图的第一步基本步骤.我非常感谢你的帮助.谢谢.

在bfs中我们必须查找每个节点,并且对于每个节点,我们必须查看row的所有元素.这不需要O(V ^ 2)(邻接矩阵中的元素数)时间,因此对于邻接矩阵不应该总时间为O(V ^ 2 + E).

是否可以在"get.adjacency()"之后将邻接矩阵保存为R中的邻接矩阵？我试过了

test <- get.adjacency(network)

但是我收到了错误

Error in View : cannot coerce class "structure("dgCMatrix", package = "Matrix")" to a data.frame. 

我正在使用RStudio和iGraph包.

假设我有两个选项来生成网络的邻接矩阵:nx.adjacency_matrix()以及我自己的代码.我想测试我的代码的正确性,并提出了一些奇怪的不等式.

示例:3x3网格网络.

import networkx as nx
N=3
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
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.sort()
vals.sort()
pos2=dict(zip(vals,inds))
plt.figure()
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200)

这是可视化:

邻接矩阵nx.adjacency_matrix():

B=nx.adjacency_matrix(G)
B1=B.todense()

[[0 0 0 0 0 1 0 0 1]
 [0 0 0 1 0 1 0 0 0]
 [0 0 0 …

假设我有一个如下所示的向量:

x <- sample(5, 500, replace = TRUE)

这样每个元素对应于从1到5的某个索引.

从这个向量创建二元邻接矩阵的有效方法是什么？详细说明,矩阵A应该是A[i,j] = 1if x[i] = x[j]和0否则.

给定图,我怎么能用adj矩阵表示它？我已经阅读了很多教程,帖子,幻灯片等,但我无法理解它,我只需要一点点推动.

替代文字http://i39.tinypic.com/10xu4hv.png

我想知道igraph中是否有函数来计算加权图中顶点之间的连接概率,其中边的权重是相邻顶点连接的概率.

我已经基于这样的邻接矩阵构建了一个图形,其中相邻连接概率形成权重(这适用于河流网络,因此图的每个节点仅连接到单个下游节点).

我本来希望使用shortest.pathsigraph中的功能,但总和权重而不是计算它们的产品,我无法找到改变它的方法.

下面的示例显示了我如何根据我拥有的数据构建邻接矩阵,即顶点连接到其下游顶点(ProbConn)的概率,然后是下游顶点(下游)的标识.最下游的顶点是河口,因此它与其他顶点无关(因此称为下游的向量以NA开头).

library(igraph)

# vector of probability of connectivity to downstream vertex
ProbConn <- c(0, 1, 0.945881098491627, 0.997349787519144, 0.891475447373691,
0.993221681072185, 0.48071450525165, 0.0292543433507856, 0.0248645581575872,
1, 0.00540807765075205, 0.661465657844344, 0.108524549747512,
0.383311676351655, 0.708853495942148, 0.00150109592270933, 0.463859846404347,
0.0011491165581467, 2.87879700370202e-09, 0.536140153595653,
0.00831752330277812, 0.00185182893416988, 0.0186237313262708,
0.398961560996748, 0.582414707676981, 0.338534342155656, 1, 0.00137024127706289,
0.291146504057852, 1, 0.0743301054564134, 0.0514743607033332,
1, 1)

# the downstream vertex of each node
downstream <- c(NA, 1, 2, 3, 4, 5, 6, 2, 2, 7, 5, 8, 4, 6, 10, 3, 11, 3, 4, …

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

假设我有以下图表：

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的加权邻接矩阵？

我想知道将邻接矩阵转换为表示一个节点与另一个节点之间的连接的字典的有效方法是什么？

矩阵示例：

matrix = [
[0,1,0,0,0,0],
[0,0,0,0,0,0],
[0,1,0,1,0,0],
[0,0,0,0,0,0],
[0,0,0,1,0,1],
[1,0,0,0,0,0]
]

输出示例：

{0: [1], 1: [], 2: [1, 3], 3: [], 4: [3, 5], 5: [0]}

我下面的代码实际上生成了正确的输出；但是，我认为这是非常低效的，因为我使用了两个 for 循环。有什么方法可以在不使用任何库的情况下优化我的代码吗？请告诉我，谢谢！

def convertAdjMatrixtoDict(m):

    graph = {}
    for idx, row in enumerate(m):
        res = []
        for r in range(len(row)):
            if row[r] != 0:
                res.append(r)
            graph[idx] = res
    return graph