Transpose an oriented graph

[azaiiez]

I want to reverse an oriented graph.

I'm able to create the oriented Graph but I have to reverse it.

an oriented graph 𝐺〈𝑆, 𝐴〉 and its inverse 𝐺 ′〈𝑆 ′ , 𝐴 ′ 〉 are this way:

a) 𝑆 = 𝑆 ′ (Have same heads.)

b) 𝑎 ∈ 𝐴 → 𝑎 ∉ 𝐴 ′ (Arcs of 𝐺 are not in 𝐺 ′ .)

c) 𝑎 ∉ 𝐴 → 𝑎 ∈ 𝐴 ′ (Arcs not in 𝐺 are in 𝐺 ′ .)

This is my Graphe.hpp

#include "Graphe.hpp"

#include <iostream>
#include <vector>

using namespace std;

class Graphe
{
private:
    vector< vector< int > * > _adjacences;
public:
    Graphe() = default;
    Graphe( int a_nbHeads );
    ~Graphe() = default;

    int nbHeads( void ) const;
    vector< int > * adjacences( int a_head );
    void addArc( int a_head1, int a_head2 );

    Graphe * grapheInverse( void );

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

and this is my Graphe.cpp

#include "Graphe.hpp"

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

using namespace std;

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

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

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

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

Graphe *Graphe::grapheInverse( void ){
  // THIS IS WHERE I NEED HELP
return nullptr;
}

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

int main( int argn, char * argv[] ){
    Graphe g( 5 );
    g.addArc( 0, 1 );
    g.addArc( 0, 4 );
    g.addArc( 1, 0 );
    g.addArc( 1, 4 );
    g.addArc( 2, 0 );
    g.addArc( 2, 1 );
    g.addArc( 2, 3 );
    g.addArc( 2, 4 );
    g.addArc( 4, 3 );
    g.addArc( 4, 1 );

    // inverting the Graph
    Graphe *r = g.grapheInverse();
}

[azaiiez]

no one ?

[MikeyBoy]

This isn't some professional answering service, where people are sitting around waiting to answer your questions in a few minutes. We're just ordinary people who come into these forums when we feel like it, read the threads we feel like when we feel like it, and answer the threads we can when we feel like it.

It may take hours, or days, for someone to read your question, know the answer, and have the time and enthusiasm to answer it.

Expecting an answer within 40 minutes is silly, especially when it's in some specialised mathematical area that many readers will know nothing about.

[jlb]

Also you would probably get help faster if you actually attempted to invert the graph.

What does your un-inverted look like?

What do you want your inverted graph to look like.

It would probably also help if your code actually compiled.

||=== Build: Debug in c++homework (compiler: gcc9-2) ===|
main.cpp||In member function ‘void Graphe::addArc(int, int)’:|
main.cpp|42|error: ‘a_sommet1’ was not declared in this scope|
main.cpp||In member function ‘std::vector<int>* Graphe::adjacences(int)’:|
main.cpp|52|warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int>*>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]|
main.cpp||In function ‘std::ostream& operator<<(std::ostream&, const Graphe&)’:|
main.cpp|65|warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int>*>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]|
main.cpp|67|warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]|
main.cpp||In function ‘int main(int, char**)’:|
main.cpp|94|warning: unused variable ‘r’ [-Wunused-variable]|
main.cpp|80|warning: unused parameter ‘argn’ [-Wunused-parameter]|
main.cpp|80|warning: unused parameter ‘argv’ [-Wunused-parameter]|
||=== Build failed: 1 error(s), 6 warning(s) (0 minute(s), 0 second(s)) ===|

[lastchance]

#include <iostream>
#include <vector>
#include <initializer_list>
#include <utility>
using namespace std;

class Graph
{
   int numNodes;
   vector< vector<bool> > adj;
public:
   Graph( int N )
   {
      numNodes = N;
      adj = vector<vector<bool>>( N, vector<bool>( N, false ) );
   }

   int size(){ return numNodes; }

   void insert( int a, int b ){ adj[a][b] = true; }

   void insert( const initializer_list<pair<int,int>> &L )
   {
      for ( auto pr : L ) insert( pr.first, pr.second );
   }

   void flip( int a, int b ){ adj[a][b] = !adj[a][b]; }

   void print()
   {
      cout << "Number of nodes: " << numNodes << '\n';
      cout << "Arcs:\n";
      for ( int i = 0; i < numNodes; i++ )
      {
         for ( int j = 0; j < numNodes; j++ ) if ( adj[i][j] ) cout << i << '\t' << j << '\n';
      }
   }
};


Graph invert( const Graph &G )
{
   Graph H = G;
   for ( int i = 0; i < H.size(); i++ )
   {
      for ( int j = 0; j < H.size(); j++ ) if ( i != j ) H.flip( i, j );
   }
   return H;
}


int main()
{
   Graph G( 5 );
   G.insert( { {0,1},{0,4},{1,0},{1,4},{2,0},{2,1},{2,3},{2,4},{4,3},{4,1} } );

   cout << "Original graph:\n";
   G.print();
   cout << "\nInverted graph:\n";
   invert(G).print();
}