CODEWITHSUNDEEP
c++algorithmgraphadjacency-list
adam
adam

Reputation: 37

How to reverse an Adjacency list?

Let's say my adjacency list is as follows:

0 : 1
1 : 0

it's reverse should be empty because there is two arcs in the initial list:

0:
1:

or

0 : 1
1 :

becomes

0 : 
1 : 0

another example:

0 : 
1 :

becomes

0 : 1
1 : 0

last example

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

becomes

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

is there an algorithm to do this ?

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++ )
            if ( (*_adjacences[i])[j] == 1 ) // or 0 or 2 or 3 or 4 or ... like last example
                //r->addArcs( i, (*_adjacences[i])[j] ); //adds an arc from A to B
            
    return r;
}

Upvotes: 0

Views: 539

Answers (1)

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

Just invert the adjacency matrix.

Wherever you have a 0, replace it with a 1, and vice versa. Only exclude the diagonal, always put a 0 there.

Upvotes: 1

Related Questions