Package flumotion :: Package common :: Module dag

Module dag

directed acyclic graph implementation. Directed Acyclic Graph class and functionality

Version: $Rev: 7162 $

Classes

CycleError
A cycle was detected during execution of a function.

Node
I represent a Node in a Graph.

DAG
I represent a Directed Acyclic Graph.

Functions

topological_sort(items, partial_order)
Perform topological sort.

source code

Variables

__package__ = 'flumotion.common'

Function Details

Perform topological sort.

Parameters:

items - list of items
partial_order - list of pairs. If pair (a,b) is in it, it means that item a should appear before item b.

Returns:

list of the items in one of the possible orders. Raises DAG.CycleError if partial_order contains a loop.