How to represent adjacency list using vector in c++

Hi
I have the following adjacenecy matrix
0 1 1 0
1 0 0 0
1 3 1 1
1 0 0 1

I need  to implement adjacenecy list for this matrix and then go ahead with Dijkstra's algorith to find the shortest path. I dont know how to create a 1D or 2D vector to reprsent the adj list structure.
Pleas help me on this regard.
BeebutterAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

BeebutterAuthor Commented:
Is anybody looking in to this problem?
0
itsmeandnobodyelseCommented:
>>>> I dont know how to create a 1D or 2D vector to reprsent the adj list structure.

For a fixed sized 4x4 matrix you would use normal C 2-D arrays:

    int adm[4][4] = {
                                  { 0, 1, 1, 0, },
                                  { 1, 0, 0, 0, },
                                  { 1, 3, 1, 1, },
                                  { 1, 0, 0, 1, },
                             };

you then may have loops like

    for (int r = 0; r < 4; ++r)
    {
          for (int c = 0; c < 4; ++c)
          {
                 int cell = adm[r][c];
                 ...
           }
     }

If the matrix may have arbitrary size or if you need to make calulations, I would suggest to define a own class

class ADM
{
      int** matrix;
      int     maxrow;
      int     maxcol;
public:
      ADM(int mr, int mc) : matrix(NULL), maxrow(mr), maxcol(mc)
      {
           if (mr <= 0 ||mc <= 0)
           {  maxrow = maxcol = 0; return; }
           matrix = new int*[maxrow];
           for (int r = 0; r < maxcol; ++r)
                matrix[r] = new int[maxcol];
           memset(matrix, 0, maxrow*maxcol*sizeof(int);
      }
      ~ADM()
     {
           for (int r = 0; r < maxcol; ++r)
                delete [] matrix[r];
           delete [] matrix;
      }
      bool init(int* m, int mr, int mc)
      {
           if (mr != maxrow || mc != maxcol) return false;
           for (int r = 0; r < mr; ++r)
          {
             for (int c = 0; c < mc; ++c)
             {
                matrix[r][c] = m[r*mc+c];
             }
           }
      }
      int& operator()(int r, int c)
      {
          static int err = -1;
          if (r >= 0 && r < maxrow && c >= 0 && c < maxcol)
             return matrix[r][c];
         return err;  // return reference to error variable
      }
      // more functions and operators for matrix manipulation and calculation
};

You could use the above like

    static int adminit[4][4] = {
                                  { 0, 1, 1, 0, },
                                  { 1, 0, 0, 0, },
                                  { 1, 3, 1, 1, },
                                  { 1, 0, 0, 1, },
                             };
      ADM adm(4, 4);
      adm.init(&adminit[0][0], 4, 4);

      int cell = adm(2, 1);  // get the 3 of above matrix



0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
BeebutterAuthor Commented:
Well, Thank you for your detailed response. But still it doesn't meet up to be a solution to my problem.
I have to get an adjacency list structure using vector or linked lists. The above said solution deals with adjacenecy matrix only. A adj list structure would like this for that above mentioned ADj matrix.

vertex 0 -> 1, 2
vertex 1 -> 0
vertex 2 -> 0, 1, 2, 3
vertex 3 -> 0, 4

Adj list would provide me details of all outgoing nodes from each vertex and the cost associated with it. Using this I have to implement Dijkstra's algorithm.

Is there any way of doing this, using a vector or linked list or anything else ?????
0
Fundamentals of JavaScript

Learn the fundamentals of the popular programming language JavaScript so that you can explore the realm of web development.

itsmeandnobodyelseCommented:
If you would define the ADM

class ADM
{
    vector<list<int> > adm;
    ...

};

you exactly meet the requirements (though it is not much won by that ...).
0
BeebutterAuthor Commented:
Ok I will try doing that way
0
BeebutterAuthor Commented:
I tried doing like this

vector<list<int> > adjacencyList;
list<int> inList;
for (int i = 0; i < 4; i++) {
inList.clear();
offset = 0;
getline(inputFile, s);
for (int j = 0; j < 4; j++) {
sscanf(s.c_str() + offset, "%d ", &cost);
offset = s.find_first_of(" ", offset + 1);
inList.push_back(cost);
}

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
cout << adjacencyList[i][j] << " "; // not working
cout << "\n";
}
adjacencyList.push_back(inList);
}


I dont know how to print the contents in the list in the vector.
Can you please tell me where i am going wrong and how to solve?
0
BeebutterAuthor Commented:
sorry i missed two lines over there

I tried doing like this

vector > adjacencyList;
list inList;
for (int i = 0; i < 4; i++) {
inList.clear();
offset = 0;
getline(inputFile, s);
for (int j = 0; j < 4; j++) {
sscanf(s.c_str() + offset, "%d ", &cost);
offset = s.find_first_of(" ", offset + 1);
inList.push_back(cost);
}
adjacencyList.push_back(inList);
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
cout << adjacencyList[i][j] << " "; // not working
cout << "\n";
}
adjacencyList.push_back(inList);
}



I dont know how to print the contents in the list in the vector.
Can you please tell me where i am going wrong and how to solve?
0
itsmeandnobodyelseCommented:
First, I strongly would suggest to make a proper indent.

vector<list<int> > adjacencyList;
list<int> inList;
for (int i = 0; i < 4; i++)
{
    inList.clear();
    offset = 0;
    getline(inputFile, s);
    for (int j = 0; j < 4; j++)
    {
        sscanf(s.c_str() + offset, "%d ", &cost);
        offset = s.find_first_of(" ", offset + 1);
        inList.push_back(cost);
    }
    adjacencyList.push_back(inList);
}
for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 4; j++)
        cout << adjacencyList[i][j] << " "; // not working
    cout << "\n";
}
adjacencyList.push_back(inList);
}

Then, you probably would have seen that there are two lines more in the post than in your source. If you were using Visual Studio simply select all source lines and press ALT+F8 to make the indentation.

Second, do not mix C and C++ if not necessary. Here it is the use of sscanf, which can be made better and safer in C++ using stringstreams.

  istringstream iss(s);
  while (iss >> cost)
      inList.push_back(cost);

>>>> cout << adjacencyList[i][j]
That doesn't compile cause std::list has no operator[] . You either need to replace the list<int> by vector<int> or - better- use std::list<int> iterator for iterating rather than expecting 4 values (what would explode for shorter lists as in your sample).

   vector<list<int> >::iterator itr;
   list<int>::iterator itl;
   for (itr=adjacencyList.begin();  itr!=adjacencyList.end(); ++itr)
       for (itl= itr->begin(); itl != itr->end(); ++itl)
             cout << *itl << " "; //  working


 


 
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.