How to transform an adjacency matrix into an incidence Matrix-CodePudding

I'm trying to transform the adjacency matrix into an incidence matrix of an undirected graph. For edges : (1, 2), (1,5), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5), (5,6)

Adj matrix is :

0 1 0 0 1 1

1 0 1 0 1 0

0 1 0 1 1 0

0 0 1 0 1 0

1 1 1 1 0 1

1 0 0 0 1 0

and I expect the result for the incidence matrix to be

0 1 0 0 1 1 0 0 0

1 0 1 0 1 0 0 0 0

0 1 0 1 1 0 0 0 0

0 0 1 0 1 0 0 0 0

1 1 1 1 0 1 0 0 0

1 0 0 0 1 0 0 0 0

but, my program returns this :

1 0 0 0 0 0 0 0 0

0 1 1 0 0 0 0 0 0

0 1 0 1 1 0 0 0 0

0 0 0 1 0 1 0 0 0

1 0 1 0 1 1 0 0 0

0 0 0 0 0 0 0 0 0

My source code :

 graph constructor
 Graph(int vertices, int edges)
    {
        this->vertices = vertices;
        this->edges = edges;
        edge = std::vector<Graph::Edge*>(edges);
        for (int i = 0; i < edges; i  )
        {
            edge[i] = new Edge(this);
        }
    }

  Graph* g = new Graph(numberOfVertices, numberOfEdges);
 g->edge[0]->src = 1;
    g->edge[0]->dest = 2;

    g->edge[1]->src = 1;
    g->edge[1]->dest = 5;

    g->edge[2]->src = 1;
    g->edge[2]->dest = 6;

    g->edge[3]->src = 2;
    g->edge[3]->dest = 3;

    g->edge[4]->src = 2;
    g->edge[4]->dest = 5;

    g->edge[5]->src = 3;
    g->edge[5]->dest = 4;

    g->edge[6]->src = 3;
    g->edge[6]->dest = 5;

    g->edge[7]->src = 4;
    g->edge[7]->dest = 5;

    g->edge[8]->src = 5;
    g->edge[8]->dest = 6;

 for (i = 0; i < numberOfEdges; i  )
    {
            adjacency_matrix[g->edge[i]->src][g->edge[i]->dest] = 1;
            adjacency_matrix[g->edge[i]->dest][g->edge[i]->src] = 1;

    }

  std::cout << "Adjacency matrix : " << std::endl;
    for (i = 1; i <= numberOfVertices; i  )
    {
        for (j = 1; j <= numberOfVertices; j  )
        {
            std::cout<<adjacency_matrix[i][j]<<" ";
        }
        std::cout << std::endl;
    }

 // Incidence Matrix

    int counter = 0;
    for( int i = 1; i <= numberOfEdges; i  ){
        for(int j = i   1; j < numberOfVertices; j   ){
            if(adjacency_matrix[i][j] == 1){
                incidence_matrix[i][counter] = 1;
                incidence_matrix[j][counter] = 1;
                  counter;
            }

        }
    }
    for( int i = 1; i <= numberOfVertices; i  ){
        for(int j = 1; j <= numberOfEdges; j  ){
            std::cout<<incidence_matrix[i][j]<<" ";
        }
        std::cout<<std::endl;
    }

CodePudding user response：

The ideas in the code are correct. But the indexing in the array is wrong.

Indexing should start at 0. Note: this also applies when setting up the adjacency matrix.

The numbers you use to name the vertices/nodes where originally 1,2,3,4,5,6. I propose to call them 0,1,2,3,4,5. Your original edge (1,2) then becomes (0,1). But if we consistently rename all the vertices everywhere we end up with the same graph. The advantage of this new naming convention is that we can use these names directly as indices in the C data structures you are using. (Provided we use the corresponding integer value and not consider these names to be strings.)

The specification of the Graph becomes

Graph* g = new Graph(numberOfVertices, numberOfEdges);
g->edge[0]->src = 0;
g->edge[0]->dest = 1;

g->edge[1]->src = 0;
g->edge[1]->dest = 4;

g->edge[2]->src = 0;
g->edge[2]->dest = 5;

g->edge[3]->src = 1;
g->edge[3]->dest = 2;

g->edge[4]->src = 1;
g->edge[4]->dest = 4;

g->edge[5]->src = 2;
g->edge[5]->dest = 3;

g->edge[6]->src = 2;
g->edge[6]->dest = 4;

g->edge[7]->src = 3;
g->edge[7]->dest = 4;

g->edge[8]->src = 4;
g->edge[8]->dest = 5;

So printing the adjacency matrix becomes:

    std::cout << "Adjacency matrix : " << std::endl;
    for (i = 0; i < numberOfVertices; i  )
    {
        for (j = 0; j < numberOfVertices; j  )
        {
            std::cout<<adjacency_matrix[i][j]<<" ";
        }
        std::cout << std::endl;
    }

and the calculation of the incidence matrix becomes:

// Incidence Matrix

    int counter = 0;
    for( int i = 0; i < numberOfVertices; i  ){  //numberOfVertices!!
        for(int j = i   1; j < numberOfVertices; j   ){ 
            if(adjacency_matrix[i][j] == 1){
                incidence_matrix[i][counter] = 1;
                incidence_matrix[j][counter] = 1;
                  counter;
            }

        }
    }
    for( int i = 0; i < numberOfVertices; i  ){
        for(int j = 0; j < numberOfEdges; j  ){
            std::cout<<incidence_matrix[i][j]<<" ";
        }
        std::cout<<std::endl;
    }

Note that the order of the edges is determined now by the order in which you traverse the adjacency matrix.