Solved

# How to represent adjacency list using vector in c++

Posted on 2008-11-07
1,416 Views
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.
0
Question by:Beebutter

Author Comment

Is anybody looking in to this problem?
0

LVL 39

Accepted Solution

>>>> 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:

{ 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)
{
...
}
}

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

{
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);
}
{
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

{ 0, 1, 1, 0, },
{ 1, 0, 0, 0, },
{ 1, 3, 1, 1, },
{ 1, 0, 0, 1, },
};

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

0

Author Comment

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

LVL 39

Expert Comment

If you would define the ADM

{
...

};

you exactly meet the requirements (though it is not much won by that ...).
0

Author Comment

Ok I will try doing that way
0

Author Comment

I tried doing like this

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";
}
}

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

Author Comment

sorry i missed two lines over there

I tried doing like this

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);
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
cout << adjacencyList[i][j] << " "; // not working
cout << "\n";
}
}

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

LVL 39

Expert Comment

First, I strongly would suggest to make a proper indent.

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";
}
}

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);

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 (itl= itr->begin(); itl != itr->end(); ++itl)
cout << *itl << " "; //  working

0

## Featured Post

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.