which datastructure to use here?

[sc7]

I recently met with a graph theory question which asks us to some operations on a graph, I can't seem to put my finger on the right datastructure to use there for these ops.

- We can have as large as 2*10^5 nodes.
ops:
- We can add new nodes.
- We can delete nodes from inbetween.

the problem is in adding and removing nodes.
I don't know what to use there.
I tried with using simple vector<pair<int,int> >[MAX] but that doesn't seem to work as it's giving segmentation fault in some TCs. Then I tried with adjancy list but the problem there is I don't know what to do when I add new node? Should I resize() , but that doesn't work,it doesn't even run sample TC.

Can anyone help me with this?

[JLBorges]

An adjacency-list can be implemented using a std:map or std::unordered_map, where each key is a vertex, and the mapped value is a std:vector containing a sequence of edges.

For example, where the vertices are int as in your example above:

#include <map>
#include <vector>
#include <iostream>

template< typename VERTEX_TYPE > using adjacency_list_type = std::map< VERTEX_TYPE, std::vector<VERTEX_TYPE> > ;

using adjacency_list = adjacency_list_type<int> ;

// input of pairs of adjacent vertices of a directed graph
// 1 7 => edge from 1 -------> 7
// 2 7 => edge from 2 -------> 7
// 1 5 => edge from 1 -------> 5
// etc.
adjacency_list create( std::istream& stm )
{
    adjacency_list graph ;
    int a, b ;
    while( stm >> a >> b ) { graph[a].push_back(b) ; graph[b] ; }
    return graph ;
}

[sc7]

@JLBorges I have pm'ed you the full problem , can you suggest how can I imlement this there ?

[JLBorges]

I'll have a look at at when I can spare some time. (Don't expect a reply within hours.)

[sc7]

ok cool, thanks :)

[JLBorges]

Something along these lines, perhaps:

#include <map>
#include <vector>

// each vertex (node) is identified by an integer

// an edge going away from a particular vertex is identified by a pair:
// destination vertex, weight
using edge_type = std::pair<int,int> ;

// as in the earlier case, the adjacency list is represented as a map
// the key is the verex (int) and the mapped value is a sequence of edges going away from this vertex
using adjacency_list = std::map< int, std::vector<edge_type> > ;

// add an edge from vertex from to vertex to with weight w
adjacency_list& add_edge( adjacency_list& graph, int from, int to, int weight )
{
    // add the edge { to, weight } to the sequence of outgoing edges of from
    graph[from].emplace_back( to, weight ) ;
    graph[to] ; // create the edge to if it does not already exist
    return graph ;
}

// remove the vertex v from the graph
adjacency_list& remove_vertex( adjacency_list& graph, int v )
{
    graph.erase(v) ; // remove the key

    // remove all the edges which were leading to this removed vertex
    for( auto& pair : graph ) // for each of the entries in the graph
    {
        auto& edges = pair.second ; // outgoing edges from this vertex
        for( auto iter = edges.begin() ; iter != edges.end() ; ) // for each outgoing edge
        {
            if( iter->first == v ) iter = edges.erase(iter) ; // remove it if the destination is v
            else ++iter ;
        }
    }

    return graph ;
}