Adjacency list using map

[hellcoder]

can we implement Adjacency list using map ?please help me out to implement that!
basic doubt is that can we map a element more than one item like adjacency list?
thanks in advance!

[JLBorges]

If it is production code, use BGL http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/index.html

If it is for learning purposes, perhaps something like this:

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

// each edge is a pair (vertex to, weight)
template < typename VERTEX_TYPE, typename WEIGHT_TYPE >
    using edge_type = std::pair< VERTEX_TYPE, WEIGHT_TYPE >  ;

// adjacency_list for a weighted directed graph:
// maps each vertex to the collection of edges radiating out of that vertex
template < typename VERTEX_TYPE, typename WEIGHT_TYPE >
using adjacency_list_type =
   std::map< VERTEX_TYPE, std::vector< edge_type<VERTEX_TYPE,WEIGHT_TYPE> > >  ;

// example: adjacency list where vertex type is int, weight type is double
using vertex_t = int ;
using weight_t = double ;
using adjacency_list_t = adjacency_list_type<vertex_t,weight_t> ;

// input is a tuple for each edge in a DAG (vertex_from, vertex_to, weight)
// 1 7 2.3 => edge from 1 -------> 7, weight 2.3
// 2 7 1.6 => edge from 2 -------> 7, weight 1.6
// 1 5 5.0 => edge from 1 -------> 5, weight 5.0
// etc.
adjacency_list_t make_adjacency_list( std::istream& stm )
{
    adjacency_list_t graph ;
    vertex_t from, to ;
    weight_t w ;
    while( stm >> from >> to >> w ) { graph[from].emplace_back(to,w) ; graph[to] ; }
    return graph ;
}

[hellcoder]

^ for unweighted graph and for learning purpose?

[MiiNiPaa]

Do you need to implement this yourself or you just need an adjancency list?
If second take a look at boost::adjacency_list : http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/adjacency_list.html

Installing boost is easy, just go to the http://www.boost.org/doc/libs/1_54_0/more/getting_started/index.html and follow instructions.

EDIT: OOPS, I was late.

[JLBorges]

> for unweighted graph and for learning purpose?

Same as above, but just knock off the weight.

For instance:
(Caveat: *** untested code ***)

#include <vector>
#include <map>
#include <iostream>
#include <string>
#include <sstream>

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

using adjacency_list = adjacency_list_type<int> ;

// input is a pair for each edge in a DAG (vertex_from, vertex_to)
// 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 ;
}

bool topological_sort( const adjacency_list& graph )
{
    std::map<int,int> num_pred_map ;
    for( auto& pair : graph )
    {
         num_pred_map[pair.first] ;
         for( auto n : pair.second ) ++num_pred_map[n] ;
    }

    while( !num_pred_map.empty() )
    {
        bool cyclic = true ;
        for( auto iter = num_pred_map.begin() ; iter != num_pred_map.end() ; )
        {
            if( iter->second == 0 )
            {
                std::cout << iter->first << ' ' ;
                for( auto& v : graph.find(iter->first)->second ) --num_pred_map[v] ;
                iter = num_pred_map.erase(iter) ;
                cyclic = false ;
            }
            else ++iter ;
        }

        if(cyclic)
        {
            std::cerr << "graph is cyclic - nodes " ;
            for( auto& pair : num_pred_map ) std::cout << pair.first << ' ' ;
            std::cout << '\n' ;
            return false ;
        }
    }
    std::cout << '\n' ;
    return true ;
}

int main()
{
    std::istringstream stm( "1 2   1 7   1 8   2 3   2 6   2 10  3 4   3 5   3 11   "
                            "6 10   6 12  8 9   8 12   9 10   9 11   11 7   12 5" ) ;
    adjacency_list graph = create(stm) ;

    std::cout << "top sort => " ; topological_sort(graph) ;
}

http://coliru.stacked-crooked.com/a/97c6e2561b5a0488