graph_algo.h File Reference

#include "../containers/graph.h"
#include "../containers/vertex.h"
#include "../containers/edge.h"
#include <unordered_map>
#include <iostream>
#include <vector>
#include <iterator>
#include <queue>
#include <stack>

Go to the source code of this file.

Functions
template<typename OutputIter >
OutputIter	topological_sort (UndirectedGraph &G, OutputIter dest)
template<typename OutputIter >
OutputIter	connected_components (UndirectedGraph &G, OutputIter dest)

Function Documentation

template<typename OutputIter >

OutputIter connected_components	(	UndirectedGraph &	G,
		OutputIter	dest
	)

                                                                     {
    // dest must be an iterator to an associative container.
    // The output will be a mapping of a vertex to its componenet id (an int)
    
    
    std::unordered_map<Vertex*, bool, UndirectedGraph::Hasher> visited;
    std::vector<Vertex*> pvertex_list(G.no_of_vertices());
    G.get_vertices(pvertex_list.begin());

    for(auto& pvertex : pvertex_list)
        visited[pvertex] = false;   // Initially set all the vertices to unvisited


    std::vector<Vertex*> dfs_list(G.no_of_vertices());  
    
    std::vector<Vertex*>::iterator dfs_it = dfs_list.begin();
    int component_id = 0;
    
    for(auto& pvertex : pvertex_list) {
        auto prev_it = dfs_it;
        if(!visited[pvertex])
            dfs(G, pvertex, visited, dfs_it);
        for(auto it = prev_it; it != dfs_it; it++) {
            // somehow insert at the place where dest points
        }
        
    }
    return dest;
}

template<typename OutputIter >

OutputIter topological_sort	(	UndirectedGraph &	G,
		OutputIter	dest
	)

Fills the input container with the topological order.

                                                                 {
    typedef typename std::iterator_traits<OutputIter>::value_type val_type;

    std::vector<val_type> postorder(G.no_of_vertices());
    
    dfs_order(G, postorder.begin());
    
    return copy(postorder.rbegin(), postorder.rend(), dest);
    
}