package svm.instances.dependency;

import svm.instances.dependency.edmonds.Arborescence;
import svm.instances.dependency.edmonds.ChuLiuEdmonds;
import svm.instances.dependency.edmonds.graph.DenseWeightedGraph;
import svm.instances.dependency.edmonds.util.Weighted;

public class Edmonds
{
	public static DependencyTree edmonds(TokenSequence x, double[][] e)
	{
		Weighted<Arborescence<Integer>> tree = ChuLiuEdmonds.getMaxArborescence(DenseWeightedGraph.from(e), 0);
		// System.out.println("edmonds solution: " + tree.weight);
		Arborescence<Integer> heads = tree.val;
		// System.out.println(heads.parents);
		DependencyTree yPred = new DependencyTree();
		yPred.heads = new int[x.lemmas.length - 1];
		//double sol = 0;
		for (int i = 1; i < x.lemmas.length; i++)
		{
			yPred.heads[i - 1] = heads.parents.get(i);
			//sol += e[yPred.heads[i - 1]][i];
		}
		// System.out.println("reconstructed: " + sol);
		// System.out.println(Arrays.toString(yPred.heads));
		yPred.x = x;
		return yPred;
	}
}
