topological_sort.hpp File Reference

#include <queue>
#include <stdexcept>
#include <iostream>
#include <ostream>
#include "data.hpp"

Go to the source code of this file.

Functions
template<class Graph, class Nodes>
void	topsort_clean_graph (Graph &graph, Nodes &nodes)
template<class Graph, class OutIterator>
void	topological_sort (Graph graph, OutIterator sorted)

---

Detailed Description

Definition in file topological_sort.hpp.

---

Function Documentation

template<class Graph, class OutIterator>

void topological_sort	(	Graph	graph,
		OutIterator	sorted
	)			[inline]

Topological sort of a directed acyclic graph. A graph is a map keyed by nodes, with sets of nodes as values. Edges run from values to keys. The sorted list of nodes is copied to an output iterator in reverse order.

Parameters:

	graph	The graph
	sorted	The output iterator

Exceptions:

std::runtime_error

if the graph contains a cycle

Precondition:

Graph::key_type == Graph::mapped_type::key_type

Definition at line 43 of file topological_sort.hpp.

References topsort_clean_graph().

Referenced by dependency_graph::sort().

template<class Graph, class Nodes>

void topsort_clean_graph	(	Graph &	graph,
		Nodes &	nodes
	)			[inline]

Listing 56-1. Topological Sort of a Directed Acyclic Graph Helper function for topological_sort(). Finds all the nodes in the graph with no incoming edges, that is, with empty values. Removes each one from the graph and adds it to the set nodes.

Parameters:

[in,out]	graph	A map of node/set pairs
[in,out]	nodes	A queue of nodes with no incoming edges

Definition at line 20 of file topological_sort.hpp.

Referenced by topological_sort().

---