Package flumotion :: Package common :: Module dag :: Class DAG
[hide private]

Class DAG

source code

log.Loggable --+
               |
              DAG

I represent a Directed Acyclic Graph.

You can add objects to me as Nodes and then express dependency by adding edges.

Instance Methods [hide private]
 
__init__(self) source code
 
_assertExists(self, object, type=0) source code
 
addNode(self, object, type=0)
I add a node to the DAG.
source code
Boolean
hasNode(self, object, type=0)
I check if a node exists in the DAG.
source code
 
removeNode(self, object, type=0)
I remove a node that exists in the DAG.
source code
 
_getNode(self, object, type=0) source code
 
addEdge(self, parent, child, parenttype=0, childtype=0)
I add an edge between two nodes in the DAG.
source code
 
removeEdge(self, parent, child, parenttype=0, childtype=0)
I remove an edge between two nodes in the DAG.
source code
list of (object, object)
getChildrenTyped(self, object, objtype=0, types=None)
I return a list of (object, type) tuples that are direct children of this object,objtype.
source code
list of objects
getChildren(self, object, objtype=0, types=None)
I return a list of objects that are direct children of this object,objtype.
source code
list of (object, object)
getParentsTyped(self, object, objtype=0, types=None)
I return a list of (object, type) tuples that are direct parents of this object, objtype.
source code
list of (object, object)
getParents(self, object, objtype=0, types=None)
I return a list of objects that are direct parents of this object, objtype.
source code
list of (object,Integer)
getOffspringTyped(self, object, objtype=0, *types)
I return a list of (object, type) tuples that are offspring of this object,objtype.
source code
list of objects
getOffspring(self, object, objtype=0, *types)
I return a list of objects that are offspring of this object,objtype.
source code
list of (object,Integer)
getAncestorsTyped(self, object, objtype=0, *types)
I return a list of (object, type) tuples that are ancestors of this object,objtype.
source code
list of objects
getAncestors(self, object, objtype=0, *types)
I return a list of objects that are ancestors of this object,objtype.
source code
Boolean
isFloating(self, object, objtype=0)
I return whether the object is floating: no parents and no children.
source code
 
hasCycle(self)
I return whether or not the graph has a cycle.
source code
list of (object, type)
sort(self)
I return a topologically sorted list of objects.
source code
list of {Node}
_sortPreferred(self, list=None, clearState=True)
I return a topologically sorted list of nodes, using list as a preferred order for the algorithm.
source code
 
_dfs(self, node) source code
list of object
getAllNodesByType(self, type)
I return all the objects with node type specified by type
source code

Inherited from log.Loggable: __providedBy__, debug, doLog, error, info, log, logFunction, logObjectName, warning, warningFailure

Class Variables [hide private]

Inherited from log.Loggable: __implemented__, __provides__, logCategory

Method Details [hide private]

addNode(self, object, type=0)

source code 

I add a node to the DAG.

Parameters:
  • object - object to put in the DAG
  • type - optional type for the object

hasNode(self, object, type=0)

source code 

I check if a node exists in the DAG.

Parameters:
  • object - The object to check existence of.
  • type (Integer) - An optional type for the object to check.
Returns: Boolean

removeNode(self, object, type=0)

source code 

I remove a node that exists in the DAG. I also remove any edges pointing to this node.

Parameters:
  • object - The object to remove.
  • type - The type of object to remove (optional).

addEdge(self, parent, child, parenttype=0, childtype=0)

source code 

I add an edge between two nodes in the DAG.

Parameters:
  • parent - The object that is to be the parent.
  • child - The object that is to be the child.
  • parenttype - The type of the parent object (optional).
  • childtype - The type of the child object (optional).

removeEdge(self, parent, child, parenttype=0, childtype=0)

source code 

I remove an edge between two nodes in the DAG.

Parameters:
  • parent - The object that is the parent,
  • child - The object that is the child.
  • parenttype - The type of the parent object (optional).
  • childtype - The type of the child object (optional).

getChildrenTyped(self, object, objtype=0, types=None)

source code 

I return a list of (object, type) tuples that are direct children of this object,objtype.

Parameters:
  • object - object to return children of
  • objtype - type of object (optional)
  • types (list) - a list of types of children that you want. None means all.
Returns: list of (object, object)

getChildren(self, object, objtype=0, types=None)

source code 

I return a list of objects that are direct children of this object,objtype.

Parameters:
  • object - object to return children of.
  • objtype (Integer) - type of object (optional).
  • types (list of Integers) - a list of types of children that you want. None means all.
Returns: list of objects

getParentsTyped(self, object, objtype=0, types=None)

source code 

I return a list of (object, type) tuples that are direct parents of this object, objtype.

Parameters:
  • object - object to return parents of
  • objtype - type of object (optional)
  • types (list or None) - A list of types of parents that you want. None means all.
Returns: list of (object, object)

getParents(self, object, objtype=0, types=None)

source code 

I return a list of objects that are direct parents of this object, objtype.

Parameters:
  • object - object to return parents of.
  • objtype - type of object (optional)
  • types (list) - List of types of parents that you want. None means all.
Returns: list of (object, object)

getOffspringTyped(self, object, objtype=0, *types)

source code 

I return a list of (object, type) tuples that are offspring of this object,objtype.

Parameters:
  • object - object to return children of.
  • objtype (Integer) - type of object (optional).
  • types (list of Integers) - a list of types of children that you want. None means all.
Returns: list of (object,Integer)

getOffspring(self, object, objtype=0, *types)

source code 

I return a list of objects that are offspring of this object,objtype.

Parameters:
  • object - object to return children of.
  • objtype (Integer) - type of object (optional).
  • types - types of children that you want offspring returned of.
Returns: list of objects

getAncestorsTyped(self, object, objtype=0, *types)

source code 

I return a list of (object, type) tuples that are ancestors of this object,objtype.

Parameters:
  • object - object to return ancestors of.
  • objtype (Integer) - type of object (optional).
  • types - types of ancestors that you want ancestors of.
Returns: list of (object,Integer)

getAncestors(self, object, objtype=0, *types)

source code 

I return a list of objects that are ancestors of this object,objtype.

Parameters:
  • object - object to return ancestors of.
  • objtype (Integer) - type of object (optional).
  • types - types of ancestors that you want returned.
Returns: list of objects

isFloating(self, object, objtype=0)

source code 

I return whether the object is floating: no parents and no children.

Parameters:
  • object - object to check if floating.
  • objtype (Integer) - type of object (optional).
Returns: Boolean

hasCycle(self)

source code 

I return whether or not the graph has a cycle.

If it has, some operations on it will fail and raise CycleError.

_sortPreferred(self, list=None, clearState=True)

source code 

I return a topologically sorted list of nodes, using list as a preferred order for the algorithm.

Parameters:
  • list (list of (object, type)) - a list of (object, type) tuples in preference order
Returns: list of {Node}