How can I convert adjacency list to incidence matrix and vice-versa?

Here is my Graph class which contains adjacency list:

typedef std::vector<std::list<unsigned int>> AdjacencyList;
class Graph
{
public:
    Graph(size_t vertices);
    // to test
    // Constructs a 'Graph' object, 
    // expecting a pointer to the 'AdjacencyList'
    // and the number of vertices
    Graph(std::shared_ptr<AdjacencyList> adjListPtr, int vertices);
    // to test
    // Constructs a 'Graph' object from 'AdjacencyMatrix' object
    Graph(AdjacencyMatrix matrix);
    void addEdge(int src, int dest);
    // prints the vector of lists(Adjacancy list) in the 
    // Graph object to Standart Output(stdout)
    //
    // How to use example:
    // std::cout << Graph object;
    friend std::ostream& operator<<(std::ostream &os, const Graph &rhs);
    // transforms Graph object to the Matrix of Incidence object
    // Graph object isn't deleted
    MatrixOfIncidence toMatrixOfIncidence();
    // transforms Graph object to the Adjacency Matrix object
    // Graph object isn't deleted
    AdjacencyMatrix toAdjacencyMatrix();
    void edit();
private:
    size_t numVertices;
    std::shared_ptr<AdjacencyList> adjList;
};

Here is my derived MatrixOfIncidence class:

class MatrixOfIncidence : public Matrix
{
public:
    MatrixOfIncidence(int numOfPeaks, int numOfEdges);
    MatrixOfIncidence(std::vector<std::vector<short int>> mx);
    // transforms 'AdjacencyMatrix' object
    // to the 'Graph' object
    Graph toAdjacencyList() override;
    // transforms 'MatrixOfIncidence' object
    // to the 'AdjacencyMatrix'
    // it is used in toAdjacencyList() method
    AdjacencyMatrix toAdjacencyMatrix();
private:
    // row and columns
    size_t peaks, edges;
};

Here is my base matrix class:

// base abstract class
// provides some common functionality for derived classes
class Matrix
{
public:
    virtual ~Matrix() {};
    // edits a matrix
    virtual void edit();
    // transforms 'Matrix' object
    // to the 'Graph' object
    virtual Graph toAdjacencyList() = 0;
    // prints the 'Matrix' object to Standart Output(stdout)
    //
    // How to use example:
    // std::cout << Matrix object;
    friend std::ostream& operator<<(std::ostream &os, const Matrix &rhs);
protected:
    std::vector<std::vector<short int>> matrix;
};

I have tried to implement the transformation methods via AdjacencyMatrix, but it didn’t work, it made a mess and it resulted in spaghetti code.
For example, here’s the code in main():

MatrixOfIncidence mx(3, 3);
Graph gr = mx.toAdjacencyList();
std::cout << gr;

And here is the output of this code:

         V0    V1    V2   
  E/V0    1    1    1     
  E/V1    0    1   -1     
  E/V2    0    1   -1     
Do you want to edit(Y/n): n
0: 1-end
1: 0-2-end
2: 1-end

I can’t come up with the implementations of methods:

  • Graph::toMatrixOfIncidence()
  • MatrixOfIncidence::toAdjacencyList()

Source: Windows Questions C++

LEAVE A COMMENT