mmn: Manchester Markov Network library

Classes to represent markov networks (nodes with connections to neighbours). Includes algorithms to find the minimum of assignment problems of the form E = sum f(x(i)) + sum g(x(i),x(j)) where f(x) is a cost for assignment to a particular node, and g(x1,x2) is a pair-wise cost for neighbouring nodes.

Where the graph defined by nodes and arcs is a tree structure, (ie acyclic) a variant of dynamic programming can efficiently find the minima.

Where the graph has a limited number of closed loops, other fairly efficient algorithms can be used.

The mmn_dp_solver computes minima for graphs which can be reduced to empty sets by repeatedly removing any node with one or two neighbours. If there are na arcs, and n options per node, it has a complexity of about na*n^3 in the worst case (every node depending on two others).

The mmn_graph_rep1 stores a representation of the graph optimised for computing the dependancies of the nodes suitable for solving in a sequential manner.


Generated on Sun Nov 22 06:26:09 2009 for contrib/mul/mmn by  doxygen 1.5.5