Darwin
1.10(beta)

drwnMaxFlow and derived classes implement algorithms for solving the maxflow/mincut problem on directed graphs (see http://en.wikipedia.org/wiki/Maxflow_mincut_theorem). This is particularly useful for minimizing submodular quadratic pseudoBoolean functions.
The following example shows how to find the value of the minimum stcut on a simple graph.
Darwin provide a suite of routines and datastructures for learning and inference in graphical models (or energy functions). Variables in the graphical model are defined by the drwnVarUniverse object. An instance of this object should be created once and shared between all objects in the graphical model.
The most basic entity in a graphical model is the factor. The drwnFactor class defines the interface for factors. The derived drwnTableFactor class provides storage for table factors, which explicitly store the value for each variable assignment. Operations on these factors are executed by classes derived from drwnFactorOperation. The advantage of using these classes is that they can cache mappings between table entries for fast execution in interative algorithms.
The following code provides an example of multiplying two factors and then marginalizing out one of the variables. Note that the variable names are optional and only provided for convenience—most largescale applications will not make use of them and reference variables by index.
Factor operations can either be executed using temporary objects or, if executed multiple times, as named objects. For example the following two code segments have the save affect:
These operations form the basis of many of the inference routines (see Graphical Model Inference and MAP Inference (Energy Minimization)).
Graphical Model inference is conducted on factor graphs (drwnFactorGraph) and involves computing marginals (or approximate marginals) on a structured probability distribution,
The drwnInference class defines the interfaces for many of the inference algorithms implemented in Darwin. The following code snippet shows an example of loading a factor graph and running the sumproduct inference algorithm on it.
MAP Inference is conducted on factor graphs where each factor is defined in (negative) logspace, i.e., energy space,
Unlike Graphical Model Inference, the goal of MAP Inference is to find the joint assignment to the variables with highest probability (lowest energy). The interface for MAP inference is defined by the drwnMAPInference class. Currently Darwin implements the following algorithms:
The following code snippet shows an example of running the maxproduct algorithm on a factor graph.
The MAP Inference for Rosetta Protein Design demonstrates these algorithms on the Rosetta Protein Design dataset.