CODEWITHSUNDEEP
c++graph
adam
adam

Reputation: 37

inverse an oriented Graph

How can I reverse not transpose an oriented graph ?

 Graphe *Graphe::grapheInverse( void ){
     Graphe *r = new Graphe (_adjacences.size() );
      for (unsigned i = 0; i < _adjacences.size(); i++){
          for (unsigned j = 0; j < _adjacences[i]->size(); j++){
              //r->addArcs(j,i); this doesn't work
          }
      }
      return r;
  }

where _adjacences is : vector< vector< int > * > _adjacences;

and addArcs is:

void Graphe::addArcs( int a_sommet1, int a_sommet2 ){
    assert( 0 <= a_sommet1 && a_sommet1 < _adjacences.size() );
    assert( nullptr != _adjacences[a_sommet1] );
    _adjacences[a_sommet1]->push_back( a_sommet2 );
}

Example:

    Graphe g( 5 );
    g.addArcs( 0, 1 );
    g.addArcs( 0, 4 );
    g.addArcs( 1, 0 );
    g.addArcs( 1, 4 );
    g.addArcs( 2, 0 );
    g.addArcs( 2, 1 );
    g.addArcs( 2, 3 );
    g.addArcs( 2, 4 );
    g.addArcs( 4, 3 );
    g.addArcs( 4, 1 );

    // inversion du graphe :
    Graphe *r = g.grapheInverse();

My full code is as follows:

Graphe.hpp

#include <iostream>
#include <vector>

using namespace std;

class Graphe
{
private:
    vector< vector< int > * > _adjacences;
public:
    Graphe( void );
    Graphe( int a_nbSommet );
    virtual ~Graphe( void );

    int nbSommet( void ) const;
    vector< int > * adjacences( int a_sommet );
    void addArcs( int a_sommet1, int a_sommet2 );

    Graphe * grapheInverse( void );

    friend ostream & operator <<( ostream &, Graphe const & );
};

Graphe.cpp

#include "Graphe.hpp"

#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

Graphe::Graphe( void )
{
}


Graphe::Graphe( int a_nbSommet ): _adjacences( a_nbSommet ){
    int i;
    for( i = 0; i < a_nbSommet; ++ i ){
        _adjacences[i] = new vector< int >();
    }
}


Graphe::~Graphe( void )
{
}


void Graphe::addArcs( int a_sommet1, int a_sommet2 ){
    assert( 0 <= a_sommet1 && a_sommet1 < _adjacences.size() );
    assert( nullptr != _adjacences[a_sommet1] );
    _adjacences[a_sommet1]->push_back( a_sommet2 );
}


int Graphe::nbSommet( void ) const{
    return _adjacences.size();
}


vector< int > *Graphe::adjacences( int a_sommet ){
    assert( 0 <= a_sommet && a_sommet < _adjacences.size() );
    return _adjacences[ a_sommet ];
}


Graphe *Graphe::grapheInverse( void ){
    Graphe *r = new Graphe (_adjacences.size() );
    for (unsigned i = 0; i < _adjacences.size(); i++)
        for ( unsigned j = 0; j < _adjacences[i]->size(); j++ )
            r->addArcs ((*_adjacences[i])[j],i); 
    return r;
}


ostream &operator <<( ostream & a_out, Graphe const & a_graphe ){
    int i = 0;
    int j = 0;

    for( i = 0; i < a_graphe._adjacences.size(); ++ i ){
        a_out << i << " : ";
        for( j = 0; j < a_graphe._adjacences[i]->size(); ++ j ){
            if( 0 != j ){
                a_out << ", ";
            }
            a_out << ( a_graphe._adjacences[i]->at(j) );
        }
        a_out << endl;
    }

    return a_out;
}

my main

#include "Graphe.hpp"


#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main( int argn, char * argv[] ){
    // construction of the graph :
    Graphe g( 5 );
    g.addArcs( 0, 1 );
    g.addArcs( 0, 4 );
    g.addArcs( 1, 0 );
    g.addArcs( 1, 4 );
    g.addArcs( 2, 0 );
    g.addArcs( 2, 1 );
    g.addArcs( 2, 3 );
    g.addArcs( 2, 4 );
    g.addArcs( 4, 3 );
    g.addArcs( 4, 1 );

    // inversion of the graph :
    Graphe *r = g.grapheInverse();

    // printing the both lists for verification
    cout << g << endl;
    cout << *r << endl;
}

this gives me:

g:
0 : 1, 4
1 : 0, 4
2 : 0, 1, 3, 4
3 : 
4 : 3, 1

r:
0 : 1, 2
1 : 0, 2, 4
2 : 
3 : 2, 4
4 : 0, 1, 2

Upvotes: 1

Views: 319

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32727

When making the reverse list, you don't want to use the index in the original list as the source vertex, you need to derefence the list. So you'll want to use

r->addArcs((*_adjacences[i])[j],i);

There are better ways to write that function (like range-based for loops).

Upvotes: 2

Related Questions