Implementing Graph Algorithms

[theconqueror_sof]

Hi, please suggest me some easy problems where I can start solving Graph problems!
I'm at a bottleneck here, i.e. I've observed some problems where I need to apply BFS (like SPOJ - BITMAP) but I'm unable to implement that as per the problem specifications. I've recently solved "Is it a Tree" on SPOJ.
Below is my code for standard BFS and DFS. I know this needs to be modelled and modified depending on problems, but I've no idea how to do that! Let's take for example the problem BITMAP! Now the way they are giving input is in the form of an adjacency matrix and that too in a string where each char needs to be separated and then added into a adjacency matrix, but I've implemented a BFS using adjacency list, do I need to write a BFS for a adjacency matrix now!? (I guess yes obviously!) But then, the one implementation I know is Gray-Black-White BFS. Its like I know what needs to be done but I' don't know how to do it. Also how to approach them? Another problem: "The Great Escape" - opc.iarcs.org.in/index.php/problems/GREATESC and on SPOJ there's another problem called "Philosopher's Stone"
It's like I have a rough idea on what needs to be done, but I'm unable to implement that.

 #include <iostream>
    #include <stack>
    #include <list>
    #include <algorithm>
    #include <stdio.h>
    #include <vector>
    #include <queue>
    #include <cstdlib>
    using namespace std;
    int N, M;
    vector<std::list<int> > adj ;
    vector<bool> visited ;
    long long int visitor=0;
        void bfs( int start);
void dfs( int start);
int main()
{

    cin>>N>>M;
    adj.resize(N);
    visited.resize(N);
    for(int i=0; i < visited.size(); i++)
        visited[i]=false;
    for(int i = 0; i < M; i++ )
        {
            int u,v;
            cin>>u;
            cin>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
cout<<"BFS Traversal"<<endl;
bfs(0);
cout<<"DFS Traversal"<<endl;
dfs(0);
           /* if(M==N-1)
                dfs(0);
            else { cout<<"NO"<<endl; exit(0);}
        if(M==N-1 && visitor==N)
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
*/
        return 0;

}
void condition()
{
    cout<<"NO"<<endl;
    exit(0);
}
void dfs( int start)
{
    stack<int> s;

    s.push(start);
    while(!s.empty())
        {
            int top=s.top();
            s.pop();

            if(visited[top]==false)
            {
                cout<<" "<<top;
                visited[top]=true; visitor++;
                std::list<int> li=adj[top];
                int a=0;
                for(std::list<int>::iterator iter= li.begin(); iter!=li.end(); iter++)
                    {
                       // a++;
                        //if(a>2) condition();
                        int temp=*iter;

                        s.push(temp);
                    }
                 //   a=0;
            }


        }
}

    void bfs( int start)
{
    queue<int> s;

    s.push(start);
    while(!s.empty())
        {
            int top=s.front();
            s.pop();

            if(visited[top]==false)
            {
                cout<<" "<<top;
                visited[top]=true; visitor++;
                std::list<int> li=adj[top];
                int a=0;
                for(std::list<int>::iterator iter= li.begin(); iter!=li.end(); iter++)
                    {
                       // a++;
                        //if(a>2) condition();
                        int temp=*iter;

                        s.push(temp);
                    }
                 //   a=0;
            }


        }
}

[leppyr64]

Let's focus on one problem at a time.

For BITMAP the input is a grid, not an adjacency matrix. If you are to model the input as a graph you must determine what constitutes a node and what constitutes an edge. Each node is a cell on the grid and is defined by a row and column coordinate. Each node is adjacent to up to 4 other nodes. Your edges are the transitions to those four nodes.

[theconqueror_sof]

Alright, so do I need something like this:

bool grid[200][200]

I can move up/down/left/right by using something like:
(x, y+1) (x, y-1), (x+1, y), (x-1, y). If x or y is greater than or less than the given dimensions then we will be out of bounds so return false in that case. So do I need a struct to represent x and y co-ordinates of the grid? Additionally, a boolean visited[][] array could be used to ensure everything is visited only once. But where to apply the distance formula given for two adjacent points in the grid? While visiting neighbours!?

[leppyr64]

I assume that you meant int grid. You will use that to store the distances from a 1. This can also do double duty as your visited array as long as you initialize it properly.

People commonly use pair to represent this. You could just as easily declare a struct.

[theconqueror_sof]

Okay, so I need to perform a BFS on all '1' pixels. Below, I've made a rough implementation of a BFS traversal on a grid. Currently I'm not moving diagonally (I believe that can be done by simply adding two more lines).
Now the problem I have is in calculating distance from ith row and jth column. How do I keep track of which row and column I am on currently?
distance = abs(x - xprev) + abs(y-yprev) ! Please check my code
I made a

bool fills[200][200]

for tracking whether a pixel is visited before. But you said that

int grid[200][200]

can be used to achieve both the objectives. But how?

class node
    {
    public:
    int x;
    int y;
    node() : x( 0 ), y( 0 ) {}
    node( int pX, int pY ) : x( pX ), y( pY ) { }
int TraverseGrid(int x, int y)
    {
        int result=0;
        queue<node> s;
        node a;
        a.x=x;
        a.y=y;
        s.push(a);
        while(s.empty()==false)
    {
        node top=s.front();
        s.pop();
        if(top.x < 0 || top.x>=n) continue;
        if (top.y < 0 || top.y >=m) continue;
        if(fills[top.x][top.y]) continue;
        fills[top.x][top.y]=true;
       //formula for calculating distance here.
        s.push(node(top.x+1, top.y));
        s.push(node(top.x, top. y+1));
        s.push(node(top.x, top.y-1));
        s.push(node(top.x-1, top.y));
    }
}

[leppyr64]

You should push all of the start nodes into the queue at once. The distance to the next point from a 1 is the distance from the 1 to the current cell plus one.

[theconqueror_sof]

But how do I keep track of the previous node? For example, lets say the BITMAP is something like this:

0001
0011
0110

Now, if I need to push the "1" points (0, 3),(1, 2), (1,3), (2,1), (2,2) in the queue and apply BFS to each of the "1"s. Distance to the neighbouring pixels is 1+previous pixel. But my question is how do I keep track of previous visited gridpoint?
nodes

top.x and top.y

would correspond to x and y co-ordinates of the pixel, right?

        distance=distance+1;
    if(distance < distance[x][y])
        distance[x][y]=distance;
    s.push(node(top.x+1, top.y));
    s.push(node(top.x, top. y+1));
    s.push(node(top.x, top.y-1));
    s.push(node(top.x-1, top.y));

[leppyr64]

You can't just blindly push nodes into the queue. You only push a node into the queue if it's the first time that you're able to reach it.

When (0,3) is popped off the front of the queue you will not be pushing the adjacent (1,3) onto the queue because it already has a calculated distance of 0. You will push (0,2) though and update its distance to 1. Later, when you pop (1,2) off the queue you will not be pushing the adjacent (0,2) onto the queue because it already has a calculated distance of 1.

[theconqueror_sof]

So an "if" condition of checking whether that pixel is visited is enough for that? The problem is how do I refer to visited[200][200] now, i.e. visited[top.x][top.y] doesn't work.
[code] int TraverseGrid(int x, int y)
{
int result=0;
queue s;
node a;
a.x=x;
a.y=y;
s.push(a);
while(s.empty()==false)
{
node top=s.front();
s.pop();
if(top.x < 0 || top.x>=n) continue;
if (top.y < 0 || top.y >=m) continue;
if(visited[top.x][top.y]) continue;
visited[top.x][top.y]=true;
distance[top.x][top.y]=distance+1;
if(!visited[top.x+1][top.y])
s.push(node(top.x+1, top.y));
if(!visited[top.x][top.y +1]) //repeat same condition below/?
s.push(node(top.x, top. y+1));
s.push(node(top.x, top.y-1));
s.push(node(top.x-1, top.y));

}[/code]

[leppyr64]

All of the pixels that have a 1 need to be pushed in at the same time with a distance of 0. You need to run one BFS, not one for every 1.

[theconqueror_sof]

Thanks leppy, but I'm still confused. Here is what I have done so far:

1. By default initialized distance to some random number, and initialized the "visited[i][j]" to false.

2. Accepted input for grid from the user (well, the problem clearly does not have a whitespace between pixels, so string parsing will be required, but lets worry about that later).
   3.Whichever grid pixels were "1", I pushed them into queue s.

3. Now how can I modify my BFS for distance?
   [code]
   int main()
   {
   int t;
   cin>>t;
   while(t--)
   {
   int n, m;

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
       {
           distance[i][j]=99999; visited[i][j]=false; 
       }

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
        {
            int temp;
            cin>>temp;
            grid[i][j]=temp;
            if(temp==1)
                s.push(node(i, j));
            dist[i][j]=0;
        }
        TraverseGrid(1,1);



}[/code]

BFS
[code]
int TraverseGrid(int x, int y)
{

    while(s.empty()==false)
{
    node top=s.front();
    s.pop();
  if(grid[x][y]==1)
        continue;
    if(top.x < 0 || top.x>=n) continue;
    if (top.y < 0 || top.y >=m) continue;[/code]

[leppyr64]

You know the distance at (x,y). So the distance at (x+1,y), if it hasn't already been reached, will be the distance at (x,y)+1.

[theconqueror_sof]

I could get only this far:

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    using namespace std;
        int result=0;
bool visited[600][400];
int grid[200][200];
int dist[200][200];
int n, m;
class node
{
public:
int x;
int y;
node() : x( 0 ), y( 0 ) {}
node( int pX, int pY ) : x( pX ), y( pY ) {}

/*node(int pX, int pY)
    {
        x=pX;
        y=pY;
    }*/
};


    queue<node> s;
void TraverseGrid(int x, int y)
{

    while(s.empty()==false)
{
    node top=s.front();
    s.pop();
    if(grid[x][y]==1)
        continue;
    if(top.x < 0 || top.x>=n) continue;
    if (top.y < 0 || top.y >=m) continue;
    if(visited[top.x][top.y]) continue;
    visited[top.x][top.y]=true;


    if(!visited[top.x+1][top.y])
    {


        dist[top.x+1][top.y]=1+dist[top.x][top.y];

            s.push(node(top.x+1, top.y));
    }

    if(!visited[top.x][top.y+1])
    {dist[top.x][top.y+1]=1+dist[top.x][top.y];
    s.push(node(top.x, top.y+1)); }

    if(!visited[top.x][top.y-1])
    {dist[top.x][top.y-1]=1+dist[top.x][top.y];s.push(node(top.x, top.y-1)); }

    if(!visited[top.x-1][top.y])
    { dist[top.x-1][top.y]=1+dist[top.x][top.y];s.push(node(top.x-1, top.y));}

}

}
int main()
{
    int t;
    cin>>t;
    while(t--)
{
    int n, m;
    cin>>n>>m;

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
        {dist[i][j]=9999; visited[i][j]=false;}

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
        {
            int temp;
            cin>>temp;
            grid[i][j]=temp;
            if(temp==1)
                s.push(node(i, j));
            dist[i][j]=0;
        }
        TraverseGrid(1,1);


for(int i=1; i <= n; i++){
    for(int j=1; j <= m; j++)
       cout<<dist[i][j];
       cout<<endl;
}

}



}

[leppyr64]

Is there something wrong with that? It looks fine to me.

[theconqueror_sof]

This is the output I get:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

[leppyr64]

Why? Put some debugging print statements in there. See what your code is doing. This is how you fix things in the real world and is a valuable lesson to learn.

[theconqueror_sof]

Yeah it is not performing the BFS, i.e. while debugging I figured out that it just pops the elements which I had pushed, and even though

!visited[][]

evaluates correctly, it does not go inside the "if" blocks!

[leppyr64]

It doesn't even get to those if blocks.

[theconqueror_sof]

Yes, how can I fix that?

[leppyr64]

You fix that by removing the statement that's preventing it from getting there.

I'm really trying to help you, but I really don't want to just write your code for you. You need to think and learn. The reason that your code is failing right now is painfully obvious if you were to take the time to walk through it with the test case and see what it is doing.