算法顶点连接，从向边一览 [英] Algorithm for Vertex connections From List of Directed Edges

问题描述

有向图G =（V，E）的平方图G2 =（V，E2）这样，美→w是在E2，当且仅如果u≠W和有一个顶点v，使得两个ü→V和v→w分别在E2。输入文件简单地列出了以任意顺序边缘为有序顶点对，与在单独的行每​​边。顶点从1开始编号，以顶点的总数。

The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that u→w is in E2 if and only if u ≠ w and there is a vertex v such that both u→v and v→w are in E2. The input file simply lists the edges in arbitrary order as ordered pairs of vertices, with each edge on a separate line. The vertices are numbered in order from 1 to the total number of vertices.

*自我循环和重复/平行边不允许

*self-loops and duplicate/parallel edges are not allowed

如果我们看一下输入数据的一个例子：

If we look at the an example of input data:

1 6
1 4
1 3
2 4
2 8
2 6
2 5
3 5
3 2
3 6
4 7
4 5
4 6
4 8
5 1
5 8
5 7
6 3
6 4
7 5
7 4
7 6
8 1

那么输出将是：

Then the output would be:

1: 3 4 7 8 5 2 6
2: 5 6 3 4 1 8 7
3: 1 7 8 6 5 4
4: 5 6 8 7 3 1
5: 3 1 4 6
6: 2 7 5 8
7: 1 5 6 8 3 4
8: 6 4 3

我写在C code。

I'm writing the code in C.

我的想法是通过文件来运行，看看他们有多少顶点，然后分配一个指针数组。继续通过列表中再次搜索流向何方行有一个1，然后看看那里的对应号领先。如果它不是一个重复的或相同的数字（1），那么我将把它添加到一个链表，从指针数组。我会做到这一点的文件中的每个数字顶点号。

My thoughts are to run through the file, see how many vertices they are and then allocate an array of pointers. Proceed to go through the list again searching for just where the line has a 1 in it, then look at where those corresponding numbers lead. If its not a duplicate or the same number(1) then I'll add it to a linked list, from the array of pointers. I will do this for every number vertex number in the file.

不过，我觉得这是非常低效的，而不是去这样做的最佳方式。如果任何人有任何其他建议，我将非常感谢。

However, I feel this is terribly inefficient, and not the best way to go about doing this. If anyone has any other suggestions I would be extremely grateful.

推荐答案

如果我得到它的权利，你想建立一个结果，其中有一个和两个为每个节点的距离的所有节点都表示每个节点设置。

if I get it right, you want to build a result set for each node where all nodes with a distance of one and two for each node are stated.

因此​​，可以保持在比特列的邻接矩阵，其中一个位是1时存在边缘和零，如果没有边缘。

therefore, one can hold the edges in an adjacency matrix of bit arrays, where a bit is one when an edge exists and zero if not.

现在我们可以用自己乘这个矩阵。在这种情况下，乘法意味着你可以在行和列做出和。

now one can multiply this matrix with itself. in this case multiply means you can make an AND on row and column.

一个小例子（对不起，不知道如何正确地插入矩阵）：

A small example (sorry, don't know how to insert a matrix properly):

0 1 0   0 1 0   0 0 1
0 0 1 x 0 0 1 = 1 1 0
1 1 0   1 1 0   0 1 1

该矩阵包含了一个用于访问分两步所有节点。只是它的邻接矩阵两个而不是一个步骤。如果你现在还是这个矩阵与您最初的矩阵，你有一个矩阵，持有长一和二的所有路径。

This matrix contains a one for all nodes reachable in two steps. simply it's the adjacency matrix for two instead of one steps. If you now OR this matrix with your initial matrix you have a matrix which holds all paths of length one and two.

该方法具有多重优势。在第一位的操作都非常快。在CPU parallyzes你的计算，你可以停下来，结果基质细胞，如果一对被发现的地方，结果给人一种。

this approach has multiple advantages. at first bit operations are very fast. the cpu parallyzes your calculations and you can stop for the result matrix cell if one pair is found where the results gives one.

此外它是有据可查的如何计算并行矩阵乘法

furthermore it is well documented how to calculate matrix multiplication in parallel.

您可以轻松地计算出pathes的所有其他长度。对于长度K一个人来计算：

you can easily calculate all other length of pathes. for a length k one has to calculate:

A^k = A^(k-1) * A

希望帮助

这篇关于算法顶点连接，从向边一览的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！