标签: adjacency-matrix

目前我正在开发一个程序,解决(如果可能的话)任何给定的尺寸从3X4到26x30的迷宫.我使用adj矩阵(稀疏)和adj列表来表示图形.我想知道如何输出DFS使用一个然后另一个方法找到解决方案所花费的总时间.以编程方式,我怎么能产生这样的基准？

我想知道是否有一种比我在下面所做的更快的方法来从分水岭图像计算区域邻接矩阵.

输入:分水岭图像,N个区域标记为1到N.

输出:这N个区域的邻接矩阵.

1.对于每个区域,计算相应的掩码并将所有掩码放入向量中:

vector<Mat> masks;    
for(int i = 0; i < N; i++ )
{    
// Create the corresponding mask
Mat mask;    
compare(wshed, i+1, mask, CMP_EQ);

// Dilate to overlap the watershed line (border)
dilate(mask, mask, Mat());

// Add to the list of masks
masks.push_back(mask);    
}

2.定义一个函数来检查两个区域是否相邻:

bool areAdjacent(const Mat& mask1, const Mat& mask2)
{
    // Get the overlapping area of the two masks
    Mat m;
    bitwise_and(mask1, mask2, m);

    // Compute the size of the overlapping area
    int size …

我正在寻找一种重新排序技术来将邻接矩阵的连通分量组合在一起.

例如,我用蓝色和绿色两组进行了说明.最初,'1的条目分布在矩阵的行和列中.通过重新排序行和列,所有'1'可以位于矩阵的两个连续部分中,更清楚地显示蓝色和绿色分量.

我不记得这种重新排序技术是什么.我搜索了邻接矩阵,集团,排序和重新排序的许多组合.

我发现的最接近的点击是

1. symrcm 将元素移近对角线,但不制作组.

2. 有没有办法重新排序矩阵的行和列,以创建一个密集的角,在R？重点是删除完全空的行和列

请提供此技术的通用名称,以便我可以更有效地谷歌,或指向我的Matlab功能的方向.

我有兴趣测试一些网络可视化技术,但在尝试这些功能之前,我想使用数据帧构建一个邻接矩阵(from,to),如下所示.

 Id   Gender   Col_Cold_1  Col_Cold_2  Col_Cold_3  Col_Hot_1  Col_Hot_2   Col_Hot_3  
 10   F         pain       sleep        NA         infection  medication  walking
 14   F         Bump       NA           muscle     NA         twitching   flutter
 17   M                    pain         hemoloma   Callus     infection   
 18   F         muscle                  pain                  twitching   medication

我的目标是创建一个邻接矩阵,如下所示

1) All values in columns with keyword Cold will contribute to the rows  
2) All values in columns with keyword Hot will contribute to the columns

例如,pain, sleep, Bump, muscle, hemaloma具有关键字Cold的列下的单元格值是,它们将形成行和单元格值,例如infection, medication, Callus, walking, twitching, flutter在具有关键字 …

我正在尝试计算邻接矩阵的加权拓扑重叠，但无法弄清楚如何使用正确地做到这一点numpy。的R，做正确执行功能是WGCNA（https://www.rdocumentation.org/packages/WGCNA/versions/1.67/topics/TOMsimilarity）。等式4中详细说明了计算此公式的公式（我认为），我相信下面可以正确地重现该公式。

有谁知道如何正确实现它，以反映WGCNA版本？

是的，我知道，rpy2但是如果可能的话，我正在尝试对此进行轻量化。

对于初学者，我的对角线不是1，并且值与原始值没有一致的错误（例如，不是全部由表示x）。

在中计算时R，我使用了以下内容：

> library(WGCNA, quiet=TRUE)
> df_adj = read.csv("https://pastebin.com/raw/sbAZQsE6", row.names=1, header=TRUE, check.names=FALSE, sep="\t")
> df_tom = TOMsimilarity(as.matrix(df_adj), TOMType="unsigned", TOMDenom="min")
# ..connectivity..
# ..matrix multiplication (system BLAS)..
# ..normalization..
# ..done.
# I've uploaded it to this url: https://pastebin.com/raw/HT2gBaZC

我不确定我的代码在哪里不正确。该R版本的源代码在这里，但是它使用的是C后端脚本？这对我来说很难解释。

这是我的实现Python：

import pandas as pd
import numpy as …

是否有可能转换的邻接矩阵所定义的一和零的 这里为距离矩阵所定义的在这里 ，其中每个链路将是单位长度1的？

我正在寻找用于表示图形的不同数据结构，我遇到了 Nvidia CUDA Toolkit，并在 source_indices、destination_offsets 的帮助下找到了表示图形的新方法。

被这种创新的图形表示所吸引，我寻找了其他表示图形的方法。但没有发现任何新东西。

我想知道除了邻接矩阵或列表之外，是否还有其他方式来表示图...

背景

我正在尝试建模一个可以在每个时间步更改其配置的系统。各种配置是预先知道的，不依赖于时间步长。在某些配置之间允许转换，而在其他配置之间禁止转换。目标是构建一个跨越多个时间步长的允许转换的邻接矩阵。

环境

让A成为s*s*k表示允许转换的逻辑矩阵，并A1...Ak表示 的页面/切片A：

A1 = A(:,:,1); A2 = A(:,:,2); ... Ak = A(:,:,k);

第三维的含义是转换需要多少时间步，例如：如果A(1,3,2)非零，则表示状态#1可以转换为状态#3，这将需要2时间步。

让B成为我们想要构建的邻接矩阵，它表示nt时间步长。的形状B应该是示意性的（以块矩阵表示法）：

A1 = A(:,:,1); A2 = A(:,:,2); ... Ak = A(:,:,k);

其中主块对角线由nt0 个块组成，并且 的切片A逐渐“向右推”直到“时间用完”， 的切片A最终“超出”了B? 表明不可能有更多的转换。由于B由nt*nt s*s块组成，因此其大小为(nt*s)×(nt*s)。

问题：给定Aand nt，我们如何B以最节省 CPU 和内存的方式构造？

笔记 …

我的数据对象有data.adj_t参数，给我稀疏邻接矩阵。我怎样才能从中得到edge_index尺寸张量？[2, num_edges]

我在处理图形数据时面临以下子任务：

我需要为具有来自“边界”索引数组的多个完全连接组件的图构造 COO 格式的图连接矩阵。

举个例子，给定数组

borders = [0, 2, 5]

由此产生的 COO 矩阵应该是

coo_matrix = [[0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4],
              [0, 1, 0, 1, 2, 3, 4, 2, 3, 4, 2, 3, 4]].

也就是说，borders数组包含应形成完全连接的子图的节点范围（包括起始索引，排除结束索引）。

我想出了以下算法，但我怀疑性能可以提高：

import numpy as np

def get_coo(borders):

    edge_list = []
    for s, e in zip(borders, borders[1:]):
        
        # create fully-connected subgraph
        arr = np.arange(s, e)
        t = np.array(np.meshgrid(arr, arr)).T.reshape(-1, 2)
        t = t.T

        edge_list.append(t) …