Data.Graph.Etage

Please read the Control.Etage framework documentation for general information how it works. Also check included test program for an example of how to work with the algorithms bellow.

Documentation

shortestPaths :: (DynGraph gr, Show a, Show b, Data a, Data b, Real b, Bounded b) => gr a b -> Incubation (Map Node (Nerve (GraphImpulse a b) AxonConductive (GraphImpulse a b) AxonConductive))

Shortest paths algorithm (from all to all nodes) using message (Impulses in the Control.Etage terminology) passing between the nodes along the edges of the graph to compute shortest paths. Loosely based on the algorithm used in the Babel routing protocol, http://www.pps.jussieu.fr/~jch/software/babel/.

It takes a Data.Graph.Inductive graph as an input and produces a map between source nodes and its corresponding Nerves, over which Impulses about shortest paths search will be send. To trigger the search sendTopologyChange should be used on returned Nerves.

One way how to collect this Impulses into an array for querying about shortest paths can be found in the test program found in this package.

While shortest paths search is lasting, information about suboptimal paths is already available. This algorithm also allows effective incremental search after graph topology changes (new nodes are added or removed, weights are changed) but this is not yet implemented.

sendTopologyChange :: Map Node (Nerve (GraphImpulse a b) AxonConductive (GraphImpulse a b) AxonConductive) -> Incubation ()

Inform nodes that topology has changed (new nodes have been added or removed, weights changed).

Currently it should only be invoked after the data-flow graph structure has been built (for example with shortestPaths). As graph topology changing interface (and thus incremental nature of algorithms) is not yet implemented.

data GraphImpulse a b

Constructors

TopologyUpdate

Informs nodes about possible improvement in the topology information, like a newly discovered shortest path.

Fields

impulseTimestamp :: ImpulseTime

originator :: LNode a

destination :: LNode a

path :: SPath b

TopologyChange

Informs nodes that topology has changed and the algorithm should be triggered (again).

Fields

impulseTimestamp :: ImpulseTime

AddOutEdges

Inform the node that new outbound edges have been attached to it, giving the node their weights.

Fields

impulseTimestamp :: ImpulseTime

newOutEdges :: Adj b

Instances

Typeable2 GraphImpulse

(Eq a, Eq b) => Eq (GraphImpulse a b)

(Data a, Data b) => Data (GraphImpulse a b)

(Ord a, Ord b) => Ord (GraphImpulse a b)

(Show a, Show b) => Show (GraphImpulse a b)

(Show a, Typeable a, Show b, Typeable b, Real b, Bounded b) => Impulse (GraphImpulse a b)