CODEWITHSUNDEEP
c++graphimplementation
V0ldek
V0ldek

Reputation: 10583

Deleting edges from an undirected graph

I have an undirected graph implemented as

vector<int> G[V];

or

list<int> G[V];

, makes me no difference, and I need to delete edges from it in O(1). A matrix of connections is out of the question, ammount of vertecies is 10^5. The problem is as follows:

for(int i = 0; i < G[w].size(); i++)
{
    int u = G[w][i];
    // erase G[w][i];
    // erase the edge (u, w) in G[u] in constant time
}

How do I implement it.

Upvotes: 0

Views: 3999

Answers (2)

V0ldek
V0ldek

Reputation: 10583

Sooo, it's been a long time since I asked this question, but seeing it still unanswered I came to supplement a solution I used back then.

So, presuming the edges are stored in an array of adjacency lists

std::list<Edge> G[V];

we can have the Edges defined as follows:

struct Edge {
    int vertex;
    std::list<Edge>::iterator siblingIterator;
}

And the remove routine is straightforward then

for(auto &edge : G[w]) {
    G[edge.vertex].erase(edge.siblingIterator);
}

G[w].clear();

Since remove with a list iterator takes constant time, then erasing one undirected edge (so the directed edge and its sibling with inverted direction) takes O(1).

I'm not going to dwelve into the past and fix all the bad practice things in my limited C++ skills from back then, but the gist of the solution is simple: just keep a reference to the sibling. Case closed.

Upvotes: 1

nils
nils

Reputation: 2524

Mixing C-style arrays and containers of the STL like this

vector<int> G[V];

isn't considered good style. Why not use vector< vector< int > >?

Regarding your request to have an erase()-function which is O(1), I think that you are faced with a trade-off: either you have very fast access but frequent modifications of the container are rather expensive (std::vector), or the other way around (std::map, std::list, ...).

The following example offers the requested constant erase()-functionality, but finding the element that is going to be removed is logarithmic. But maybe it helps you finding what you want:

#include <vector>
#include <set>

typedef int Vertex;
typedef std::vector< Vertex > Vertices;

struct Edge
{
    int a;
    int b;

    Edge( int a, int b ) : a( a ), b( b ) {}

    // Needed for std::set.
    bool operator< ( const Edge & other ) const
    {
        if ( a < other.a ) return true;
        if ( a > other.a ) return false;

        return b < other.b;
    }
};

 typedef std::set< Edge > Edges;

struct Graph
{
    Vertices vertices;
    Edges edges;
};

int main( int argc, char ** argv )
{
    Graph graph;

    // Add vertices.
    graph.vertices.push_back( Vertex( 0 ) ); // Vertex 0
    graph.vertices.push_back( Vertex( 1 ) ); // Vertex 1
    graph.vertices.push_back( Vertex( 2 ) ); // Vertex 2
    graph.vertices.push_back( Vertex( 3 ) ); // Vertex 3

    // Connect vertices.
    graph.edges.insert( Edge( 0, 1 ) ); // Connect vertex 0 and vertex 1.
    graph.edges.insert( Edge( 0, 1 ) ); // Connect vertex 1 and vertex 2.
    graph.edges.insert( Edge( 1, 2 ) ); // Connect vertex 2 and vertex 3.
    graph.edges.insert( Edge( 2, 0 ) ); // Connect vertex 3 and vertex 0.

    // Remove the edge between vertices 1 and 2 again.
    Edges::iterator it = graph.edges.find( Edge( 1, 2 ) );

    if ( it != graph.edges.end() )
        graph.edges.erase( it ); // The complexity of erase() is constant, but find() logarithmic.
}

Upvotes: 0

Related Questions