Input format of adjacency matrix
How are the graph edges counted when reading sparse graph adjacency matrix --
are the edges (i,j) and (j,i) connecting vertices i and j counted once or twice?
The manual (for rel. 2.1.1) says that the input file must contain a line for each
vertex/node listing the adjacent vertices of the given vertex. If the vertices
#i and #j are connected, does this mean that the (i+1)th line of the input file
must contain j as an adjacent vertex, and (j+1)th line must contain i as an adjacent
vertex? Also, does the total number of edges count both the edges i-j and j-i
(essentially, counts the same edge twice), or does it count i-j/j-i only once?
Another question: if there are vertices without any neighbours (disconnected),
what should the corresponding lines in the input file contain -- an empty line,
or are such disjoint vertices illegal?
Submitted by r08n on Fri, 2011-09-16 06:56
»
- Login to post comments
RE: Input format of adjacency matrix
Just after I posted this I noticed that the first question has been
already answered in the thread "Problems with reading a graph".
Still, what about unconnected vertices (i.e., those that don't have
any neighbours)? Are the corresponding lines in the input file
empty?
RE: yes, an empty line indicates
yes, an empty line indicates that a vertex has no adjacent vertices. However, you should be removing those vertices from the graph in the first place, as they do not make much sense for partitioning purposes.