class DeadlockDetector {

    public Set<Transaction> victims()
    {
        int detectionId = detectionCounter++;
        LOG.log(Level.INFO, "Starting deadlock detection {0}", detectionId);
        Set<Transaction> victims = new HashSet<Transaction>();
        // WaitsFor.waiter -> WaitsFor
        Map<Transaction, WaitsFor> dependencies = lockManager.dependencies();
        List<Path> paths = new ArrayList<Path>();
        for (WaitsFor waitsFor : dependencies.values()) {
            paths.add(new Path(waitsFor));
        }
        int extensions = 0;
        List<Path> cycles = new ArrayList<Path>();
        logPaths(detectionId, 0, paths, cycles);
        do {
            for (Iterator<Path> pathIterator = paths.iterator(); pathIterator.hasNext();) {
                Path path = pathIterator.next();
                Transaction pathLast = path.last();
                WaitsFor extension = dependencies.get(pathLast);
                if (extension == null) {
                    pathIterator.remove();
                } else if (!path.extend(extension.copy())) {
                    // path contains cycle
                    cycles.add(path);
                    pathIterator.remove();
                }
            }
            logPaths(detectionId, ++extensions, paths, cycles);
        } while (!paths.isEmpty());
        for (Path path : cycles) {
            victims.add(path.victim());
        }
        return victims;
    }

    public  DeadlockDetector(LockManager lockManager);

}