Etage-Graph-0.1.7: Data-flow based graph algorithms

Safe HaskellNone



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.



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))Source

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,

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 ()Source

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 Source



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


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


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


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)