Package gavo :: Package utils :: Module algotricks :: Class IndexedGraph

Class IndexedGraph

object --+
         |
        IndexedGraph

is a graph that is indexed by both incoming and outgoing edges.

The constructor argument edges is an iterable of (from, to)-tuples, where both from and to must be hashable.

The class keeps a set rootNodes of "root nodes" (i.e. those with no incoming edges).

To find leaf nodes, you'd have to compute allNodes-set(outgoingIndex).

You may access allNodes, rootNodes, incomingIndex, and outgoingIndex reading, but any external change to them will wreak havoc.

Instance Methods

__init__(self, edges)
x.__init__(...) initializes x; see help(type(x)) for signature

source code

__nonzero__(self)

source code

addEdge(self, comeFrom, goTo)

source code

removeEdge(self, comeFrom, goTo)

source code

getEdge(self)
returns a random edge.

source code

getSomeRootNode(self)
returns an arbitrary element of rootNodes.

source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Properties
Inherited from `object`: `__class__`

Method Details

init(self, edges)
(Constructor)

source code

x.__init__(...) initializes x; see help(type(x)) for signature

Overrides: object.__init__: (inherited documentation)

getEdge(self)

source code

returns a random edge.

It raises an IndexError if the graph is empty.

getSomeRootNode(self)

source code

returns an arbitrary element of rootNodes.

This will raise a KeyError if no root nodes are left.

Class IndexedGraph

__init__(self, edges) (Constructor)

getEdge(self)

getSomeRootNode(self)

init(self, edges)
(Constructor)