source_removal.cpp File Reference

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cassert>

Classes
class	DynamicDirectedGraph

Functions
template<typename Iter >
Iter	source_removal (DynamicDirectedGraph &G, Iter dest)
int	main ()

Function Documentation

int main

(

)

           {
    DynamicDirectedGraph G(6);
    G.add_edge(0, 1);
    G.add_edge(0, 2);
    G.add_edge(1, 2);
    G.add_edge(3, 0);
    G.add_edge(4, 3);
    G.add_edge(4, 0);
    G.add_edge(5, 0);
    G.add_edge(5, 2);
    G.add_edge(5, 4);
    
    
    vector<int> top_order(G.no_of_vertices());
    vector<int>::iterator last = source_removal(G, top_order.begin());  
    for(auto elt : top_order)
        cout << elt << endl;
    
    return 0;
}

template<typename Iter >

Iter source_removal	(	DynamicDirectedGraph &	G,
		Iter	dest
	)

                                                        {
    queue<int> q;
    vector<int> vertices(G.no_of_vertices());
    
    auto last = G.get_vertices(vertices.begin());
    for(auto it = vertices.begin(); it != last; it++)
        if(G.in_degree(*it) == 0)
            q.push(*it);
    
    
    int processed_vertices = 0;
    
    while(!q.empty()) {
        int visit = q.front();
        q.pop();
        processed_vertices++;
        
        *dest++ = visit;    // Push the element to final list
        
        vector<int> adj(G.no_of_vertices());
        auto last = G.adjTo(visit, adj.begin());
        for(auto it = adj.begin(); it != last; it++) {
            G.delete_edge(visit, *it);
            if(G.in_degree(*it) == 0)
                q.push(*it);
        }    
    }
    
    assert(processed_vertices == G.no_of_vertices());
    
    
    return dest;
}