逆向图 [英] 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;
  }

其中_adjacences是: vector<向量<整数>*>_adjacences;

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

和 addArcs 是:

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

示例:

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

我的完整代码如下:

Graphe.hpp

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

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

我的主要人

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

这给了我

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

推荐答案

制作反向列表时，您不想将原始列表中的索引用作源顶点，因此需要取消引用列表.所以您要使用

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

有更好的方法来编写该函数(如基于范围的for循环).

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

这篇关于逆向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！