class ConstraintSolver {

    public List<DetectedRelation<T>> solve(PrintCollector printCollector) {

        List<DetectedRelation<T>> detectedRelations = Lists.newArrayList();

        // prune graph
        pruneGraph(printCollector);

        ConnectivityInspector<T, Edge> connectivityInspector = new ConnectivityInspector<>(graph);

        List<Set<T>> connectedComponents = connectivityInspector.connectedSets();

/*        for (Edge edge : graph.edgeSet()) {
            T edgeSource = graph.getEdgeSource(edge);
            T edgeTarget = graph.getEdgeTarget(edge);
            System.out.println(
                    Joiner.on(" ").join(transformToString(edgeSource), ((Annotation)edgeSource).getBegin(), ((Annotation)edgeSource).getEnd(), edgeSource.hashCode()) + "   ->  " +
                            Joiner.on(" ").join(((Annotation)edgeTarget).getCoveredText(),((Annotation)edgeTarget).getBegin(), ((Annotation)edgeTarget).getEnd(), edgeTarget.hashCode()));
        } */

        // solve each connected component separately

        // save the current state of the graph to revert
        final UndirectedGraph<T, Edge> restored = new Multigraph<>(Edge.class);
        Graphs.addGraph(restored, graph);

        printCollector.print(String.format("Graph has %2d components", connectedComponents.size()));
        for (Set<T> connectedComponent : connectedComponents) {

            // remove all vertices that are not part of the connected component
            printCollector.print(String.format("Solving connected component with %d vertices", connectedComponent.size()));
            //printCollector.print(Iterables.toString(Iterables.transform(connectedComponent, vertexToString)));

            // determine which nodes need to go
            HashSet<T> difference = Sets.newHashSet(Sets.difference(graph.vertexSet(), connectedComponent));
            graph.removeAllVertices(difference);

            detectedRelations.addAll(solveConnectedComponent(printCollector, connectedComponent));

            // restore graph
            Graphs.addGraph(graph, restored);
        }

        return detectedRelations;
    }

    private  ConstraintSolver(Set<String> types, Table<String, String, String> rel, Multigraph<T, Edge> graph);

}