2
\$\begingroup\$

I implemented a strongly connected graph code in C++.

matrix_graph.h

#pragma once
#include "stdafx.h"

class matrix_graph
{
private:
    int** v;
    int vertexes;
public:
    matrix_graph(int**, int);
    ~matrix_graph(void);
    void reverse();
    int get_max_vertexes();
    bool is_connected(int i,int j);
};

matrix_graph.cpp

#include "stdafx.h"
#include <iostream>
#include "matrix_graph.h"

using namespace std;

matrix_graph::matrix_graph(int** g, int N)
{
    v = g;
    vertexes = N;
}

matrix_graph::~matrix_graph(void)
{}

void matrix_graph::reverse()
{
    for(int i=0;i<vertexes;i++)
        for(int j=0;j<vertexes;j++) 
        {
            if(v[i][j] == 1 && v[j][i]==0){
                v[j][i] = -1;
                v[i][j] = 0;        
            }
        }

    for(int i=0;i<vertexes;i++)
        for(int j=0;j<vertexes;j++) 
        {
            if(v[i][j] == -1 )
                v[i][j] = 1;
        }
}

int matrix_graph::get_max_vertexes()
{
    return vertexes;
}

bool matrix_graph::is_connected(int i,int j)
{
        return (v[i][j]==1);
}

Main code:

enum Color {WHITE,GREY,BLACK};

void matrix_dfs_visit(matrix_graph m , int i , std::list<int>& q , Color* c)
{
    int N = m.get_max_vertexes();
    c[i] = GREY;
    for(int j=0;j<N;j++){
        if(i!=j){
            if( m.is_connected(i,j))
                if(c[j] == WHITE)
                  matrix_dfs_visit(m,j,q,c);
        }
    }
    c[i] = BLACK;
    q.push_front(i);
}

void dfs(matrix_graph m, std::list<int>& visited_vertexes_in_order )
{
    int N = m.get_max_vertexes();
    Color* c = new Color[N];
    for(int i=0;i<N;i++)
        c[i] = WHITE;
    for(int i=0;i<N;i++)    
        if(c[i] == WHITE)
            matrix_dfs_visit(m,i,visited_vertexes_in_order ,c);
}

void dfs_transpose(matrix_graph &m , std::list<int> &visited_vertexes_in_order)
{
    int N = m.get_max_vertexes();

    Color* c = new Color[N];
    for(int i=0;i<N;i++)
        c[i] = WHITE;

    for(list<int>::iterator iter = visited_vertexes_in_order.begin();iter != visited_vertexes_in_order.end();iter++){
        int scc_head = *iter;
        if(c[scc_head] == WHITE){
            list<int> scc;
            matrix_dfs_visit(m,scc_head ,scc,c);
            print_scc(scc);
        }
    }
}

void print_scc(list<int> & l){
    cout << "Strongly Connected Component:";
    for(list<int>::iterator iter=l.begin(); iter !=l.end();iter++)
        cout<< " "<<*iter;
    cout<<"\n";
}

void get_strongly_connected_component(matrix_graph &m)
{
    list<int> visited_vertexes_in_order;    
    dfs(m,visited_vertexes_in_order);
    m.reverse();
    dfs_transpose(m,visited_vertexes_in_order);
}

void process()
{

    int v[7][7] = {
        {0,1,0,0,0,0,0},
        {0,0,1,1,0,0,0},
        {1,0,0,0,0,0,0},
        {0,0,0,0,1,0,0},
        {0,0,0,0,0,1,0},
        {0,0,0,1,0,0,1},
        {0,0,0,0,0,0,0}
    };

    int* v_ptr[7] = {v[0],v[1],v[2],v[3],v[4],v[5],v[6]};
    matrix_graph m(&v_ptr[0],7);
    get_strongly_connected_component(m);
}

Please give any reviews, especially on the reverse function and the whole design. Naming convention here is also pretty weak I think.

\$\endgroup\$
1
\$\begingroup\$

Firstly, I think you class name can be improved somewhat. Sure, it tells you the underlying data structure that the graph will use (sort of, anyway), but it doesn't tell you anything about what kind of graph it is. Unless you read the source, you won't know that this is supposed to represent a directed graph - so why not put that in the name: directed_matrix_graph.

Speaking of underlying data structure, simply taking an int** that you don't copy, but simply use as-is, is generally not good practice. Most users of a class like this will assume that it manages its own memory. This puts the onus on the user to make sure everything used in your class remains within scope. I'd recommend replacing this with a std::vector<std::vector<int>> which manages its own memory. This should probably have a constructor which it initializes from a template; something like:

class matrix_graph
{
private:
    std::vector<std::vector<int>> vertexes;

public:
    template <typename Iterator>
    matrix_graph(Iterator begin, Iterator end)
    {
        std::vector<int> v(begin, end);
        for(std::size_t i = 0; i < v.size(); ++i) {
            vertexes.push_back(v);
        }
    }

...
};

Destructors shouldn't take parameters (even void), and you shouldn't declare one if it isn't going to do anything: the compiler generated one will suffice in this case.

Both int get_max_vertexes() and bool is_connected(int i,int j) should be const methods, as these don't change the underlying matrix_graph:

int get-max_vertexes() const;
bool is_connected(int i, int j) const;

On to the main code: your dfs has a memory leak: you declare new Color[N] but never delete[] it. Again, using a std::vector will make these sorts of problems go away. It will also simplify the code:

void dfs(matrix_graph m, std::list<int>& visited_vertexes_in_order )
{
    std::vector<Color> c(m.get_max_vertexes(), WHITE);
    for(int i = 0;i < N; i++)    
        if(c[i] == WHITE)
            matrix_dfs_visit(m, i, visited_vertexes_in_order, c);
}

In matrix_dfs_visit and dfs, you pass your matrix_graph by value and call it recursively. If you were actually storing graph vertexes in your class, this would get very slow very quickly. You aren't modifying the underlying matrix_graph here, so you should pass it by const-reference instead: const matrix_graph& m.

You have another memory leak in dfs_transpose, same solution applies as above. You pass your matrix_graph here by reference, but it is never changed. Since bool is_connected(int i, int j) should be const (if you change it per the advice given above), you can now pass by const matrix_graph&.

Similar complaint for void print_scc(list<int> & l), should be const list<int>& l. Anything that doesn't change should always be passed by const, this will make sure that the underlying object isn't changed (well, as long as people don't start const_casting things, but you have bigger problems in that case).

The algorithms themselves look like they come straight from CLRS so I won't bother going over them.

Some other general comments:

  • Use whitespace in loops: for(int i=0;i<vertexes;i++) is so much harder to read than for(int i = 0; i < vertexes; i++).
  • Avoid using namespace std as much as possible, even in .cpp files. In fact, you don't even use any standard library components in your matrix_graph.cpp file, so it doesn't even need to be there in the first place. Even if you did, the absolutely tiny time savings you get by not having to type out std:: in a few places is not worth the potential name clashes.
  • Put your code in a namespace, it's generally good practice.
  • In general, be careful of memory leaks. Use new as little as possible. Prefer std::vector to manually dealing with arrays: they stop memory leaks and offer much better exception safety.
\$\endgroup\$
  • \$\begingroup\$ Thanks..I take all your points...basically avoid arrays..use const references and avoid std namespace... is making a typedef of std containers a good idea? \$\endgroup\$ – sethi Jun 23 '13 at 14:44
  • \$\begingroup\$ @sethi Sure, if it makes things easier and/or clearer. \$\endgroup\$ – Yuushi Jun 23 '13 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.