标签: adjacency-matrix

对于C++中的图形问题,什么是更好的,邻接列表或邻接矩阵？各有哪些优缺点？

我有以下 numpy 数组：

import numpy as np

pair_array = np.array([(205, 254), (205, 382), (254, 382), (18, 69), (205, 382), 
                       (31, 183), (31, 267), (31, 382), (183, 267), (183, 382)])

print(pair_array)

#[[205 254]
# [205 382]
# [254 382]
# [ 18  69]
# [205 382]
# [ 31 183]
# [ 31 267]
# [ 31 382]
# [183 267]
# [183 382]]

有没有办法将此数组转换为包含所有可能组合的出现次数的对称熊猫数据框？我期待这样的事情：

#     18  31  69 183 205 254 267 382 
#  18  0   0   1   0   0 …

我试图在numpy中生成对称矩阵.具体地说,这些矩阵具有随机位置条目,并且在每个条目中内容可以是随机的.沿着主对角线,我们并不关心那里的内容,所以我也将它们随机化了.

我采用的方法是首先生成一个nxn全零矩阵,然后简单地循环遍历矩阵的索引.但是,考虑到在python中考虑循环是相对昂贵的,我想知道我是否可以在不使用python的for循环的情况下实现相同的功能.

是否有一些内置于numpy中的东西可以让我更有效地实现我的目标？

这是我目前的代码:

import numpy as np
import random

def empty(x, y):
    return x*0

b = np.fromfunction(empty, (n, n), dtype = int)

for i in range(0, n):
    for j in range(0, n):
        if i == j:
            b[i][j] = random.randrange(-2000, 2000)
        else:
            switch = random.random()
            random.seed()
            if switch > random.random():
                a = random.randrange(-2000, 2000)
                b[i][j] = a
                b[j][i] = a
            else:
                b[i][j] = 0
                b[j][i] = 0

你好,我理解邻接列表和矩阵的概念,但我很困惑如何在Python中实现它们:

实现以下两个示例的算法实现但不知道从一开始的输入,因为他们在他们的示例中对其进行硬编码:

对于邻接列表:

    a, b, c, d, e, f, g, h = range(8) 
    N = [ 
     {b:2, c:1, d:3, e:9, f:4},    # a 
     {c:4, e:3},                   # b 
     {d:8},                        # c 
     {e:7},                        # d 
     {f:5},                        # e 
     {c:2, g:2, h:2},              # f 
     {f:1, h:6},                   # g 
     {f:9, g:8}                    # h 
   ] 

对于邻接矩阵:

    a, b, c, d, e, f, g, h = range(8) 
    _ = float('inf') 
    #     a b c d e f g h
    W = [[0,2,1,3,9,4,_,_], # a 
        [_,0,4,_,3,_,_,_], # …

我使用邻接矩阵来表示可以在视觉上解释为的朋友网络

Mary     0        1      1      1

Joe      1        0      1      1

Bob      1        1      0      1

Susan    1        1      1      0 

         Mary     Joe    Bob    Susan

使用这个矩阵,我想编译所有可能的友谊三角形的列表,条件是用户1是用户2的朋友,用户2是用户3的朋友.对于我的列表,不要求用户1是朋友用户3.

(joe, mary, bob)
(joe, mary, susan)
(bob, mary, susan)
(bob, joe, susan)

我有一些适用于小三角形的代码,但我需要它来扩展非常大的稀疏矩阵.

from numpy import *
from scipy import *

def buildTriangles(G):
    # G is a sparse adjacency matrix
    start = time.time()
    ctr = 0
    G = G + G.T          # I do this to make sure it is symmetric
    triples = [] …

我的问题很简单:我需要从边列表中创建一个邻接列表/矩阵.

我有一个边缘列表存储在csv文档中,其中column1 = node1和column2 = node2,我想将其转换为加权邻接列表或加权邻接矩阵.

更确切地说,这是数据的样子 - 数字只是节点ID:

node1,node2
551,548
510,512
548,553
505,504
510,512
552,543
512,510
512,510
551,548
548,543
543,547
543,548
548,543
548,542

有关如何实现从此转换为加权邻接列表/矩阵的任何提示？这就是我以前决定这样做的方法,但没有成功(由Dai Shizuka提供):

dat=read.csv(file.choose(),header=TRUE) # choose an edgelist in .csv file format
el=as.matrix(dat) # coerces the data into a two-column matrix format that igraph likes
el[,1]=as.character(el[,1])
el[,2]=as.character(el[,2])
g=graph.edgelist(el,directed=FALSE) # turns the edgelist into a 'graph object'

谢谢!

我正在尝试实现Floyd-Warshall算法.要做到这一点,它需要我设置adjacency matrix 一个加权图.我该怎么做呢？我知道这些值,并附上了加权图的图片.我试图寻找一些在线的例子,但我似乎找不到任何东西.我理解Floyd-Warshall算法我只是需要帮助才能设置它,所以我能够实现它.这是我之前构建的一个,但我不必使用特定的值.

码:

public static void buildAdjMatrix()
{

    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            if (directionAllowed(i, j) == true)
            {
                adjMatrix[i, j] = 1;
            }
            else
            {
                adjMatrix[i, j] = 50;
            }
        }
    }

}

以下是具体的图表:

这是我需要创建的矩阵的图片..抱歉可怕的质量......

我有一个相当大(但相当稀疏)的邻接矩阵(500x500),我试图在视觉上代表.在我看来,类似于力导向图的东西是我最好的选择,在尝试找出实现它的最佳方法时,我遇到了R的多个资源.最有帮助的是http:/上的网络可视化/kateto.net/network-visualization虽然我之前从未使用过R,但它似乎有很多有用的功能可用于这种可视化.

我已设法在下面生成一个图,但图像相当小,节点堆叠.

如果我打印到pdf而不是PNG,分辨率会略好一些,但我仍然存在堆叠问题.因此,我的问题是,如何在R中正确绘制一个大的邻接矩阵来解决这些问题.

到目前为止我的代码如下(最后几行我尝试绘制数据的几种不同方式).任何提示都非常感谢.先感谢您.

为方便起见,我在https://github.com/BStricklin/DataViz上传了我的GitHub引用的两个文件.

plot.new()
library('igraph')
setwd("D:/Downloads/polnet2016/Data files")

nodes2 <- read.csv("nodes.csv", header=T, as.is=T)
links2 <- read.csv("nodeAdjacency.csv", header=T, row.names=1)

links2 <- as.matrix(links2)

head(nodes2)
head(links2)

net2 <- graph_from_incidence_matrix(links2)
net2 <- graph_from_adjacency_matrix(links2, mode = "undirected", weighted = TRUE)
net2 <- simplify(net2, remove.multiple = F, remove.loops = T) 

V(net2)$label <- nodes2$id

deg <- degree(net2, mode="all")
V(net2)$size <- deg*3

#plot(net2)
#plot(net2, edge.label=round(E(net2)$weight, 3))
layout <- layout.reingold.tilford(net2)
#plot.igraph(net2,vertex.size=3,layout=layout.lgl)
plot.igraph(net2,vertex.size=3,vertex.label.cex=.5,layout=layout.fruchterman.reingold(net2, niter=10000))

编辑:对于任何想知道我最终如何做到这一点的人,我不得不使用MATLAB并利用图形和绘图功能.它看起来像R图像一样令人讨厌,但是通过一些节点的自定义和缩放功能的使用,它运行得很好.我仍然会对如何在R中这样做感兴趣.

我在R中有一个示例代码如下:

library(igraph)
rm(list=ls())
dat=read.csv(file.choose(),header=TRUE,row.names=1,check.names=T) # read .csv file
m=as.matrix(dat)
net=graph.adjacency(adjmatrix=m,mode="undirected",weighted=TRUE,diag=FALSE)

我使用csv文件作为输入,其中包含以下数据:

    23732   23778   23824   23871   58009   58098   58256
23732   0   8   0   1   0   10  0
23778   8   0   1   15  0   1   0
23824   0   1   0   0   0   0   0
23871   1   15  0   0   1   5   0
58009   0   0   0   1   0   7   0
58098   10  1   0   5   7   0   1
58256   0   0   0   0   0   1   0

在此之后,我使用以下命令检查重量值:

E(net)$weight

预期输出有点像这样:

> E(net)$weight
 [1] …

我想创建一个图表,显示来自邻接矩阵的节点之间的连接,如下所示.

gplot似乎是最好的工具.但是,为了使用它,我需要传递每个节点的坐标.问题是我不知道坐标应该在哪里,我希望这个函数能够为我找出一个好的布局.

例如,这是我的输出使用以下任意坐标:

 A = [1 1 0 0 1 0;
      1 0 1 0 1 0;
      0 1 0 1 0 0;
      0 0 1 0 1 1;
      1 1 0 1 0 0;
      0 0 0 1 0 0];

 crd = [0 1;
        1 1;
        2 1;
        0 2;
        1 2;
        2 2];

 gplot (A, crd, "o-");

这很难读,但是如果我稍微使用坐标并将它们更改为以下内容就会变得更具可读性.

   crd = [0.5 0;
         0 1;
         0 2;
         1 2;
         1 1;
         1.5 2.5];

我不希望完美优化的坐标或任何东西,但我怎么能告诉MATLAB自动为我找出一组坐标看起来没问题使用某种算法,所以我可以绘制一些看起来像顶部图片的东西.

提前致谢.