- Main Page
- Namespaces
- Classes
- Files

# 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().