CODEWITHSUNDEEP
c++algorithmmatrix
user2489034
user2489034

Reputation: 239

Count degree in an undirected graph - logic issue

I have the incidence matrix, and based on it I'm counting a degree of each vertex in a graph.

Let's assume that this is the current incidence matrix:

-1 -1  1  0  1  0
 1  0 -1 -1  0  1
 0  1  0  1 -1 -1

Rows are vertices, columns are the edges. -1 means the edge comes out of the vertex, +1 that it comes in.

If this is the undirected graph, the matrix contain some certain pattern, like here:

-1  0  1  0  0  0
 1  0 -1  0  0  0
 0  0  0  0  0  0

Two rows - same vertices. Two edges, directed differently. This is the representation of:

But made this way:

In directed graph to count the degree of a vertex (any edges connected with it) I was just counting -1 and +1 in every row. That worked.

The problem is - the degree is multiplied by 2 everywhere in the undirected graph, because the matrix is naturally "converting" line edges into two arrow edges, like on the picture.

The question is - How can I reduce the degree so that it counts one line edge instead of two arrow edges using incidence matrix, if the edges are placed randomly?

To clear thing up, this is the algorithm that doesn't work properly for what I want:

for(int i = 0; i < cols; i++)
{
   int deg = 0;
   for(int j = 0; j < rows; j++)
   {
      if(matrix[i][j] != 0) deg++;
   }
   std::cout << "Degree of " << i + 1 << " vertex is " << deg;
}

How can I change the if instruction to reduce the repeated, inversed columns?

Upvotes: 1

Views: 2554

Answers (1)

Gene
Gene

Reputation: 46990

What you call an incidence matrix really isn't. It's an edge list. Edge lists have the problems you're seeing: duplicates, dual representation for each undirected edge, etc. They are almost never the best choice of data structure for a graph.

In an incidence matrix, the rows and columns are both vertices. A 1 (or label value if the edges are labeled) in row i, column i means there is an edge from i to j. A zero (or other value meaning "none") means no edge.

If the graph is undirected, then the matrix is symmetric: an edge from i to j always has a match from j to i. Therefore you can erase either the upper or lower triangle of the matrix without losing information.

Once the vertices are numbered, the incidence matrix is unique. Duplicates can't happen. If edges are unlabeled, then it can be stored in a bitmap.

Computing directed graph in-degree just means counting the 1's in the column for the vertex. Out-degree is counting 1's in the row. If the graph is undirected, represented by a triangular array, the same procedure works just fine. No division by 2 is needed.

The primary disadvantage of an incidence matrix is that it needs O(n^2) space to store every graph of n vertices no matter how many edges it has. This might be a problem if the graph is "sparse," i.e. it has only O(n) edges. In this case, the preferred data structure is the adjacency list, which I'll let you read about for yourself.

Upvotes: 1

Related Questions