Java 类org.apache.commons.collections15.ListUtils 实例源码

项目：alevin-svn2 文件：Yen.java

@Override
protected List<List<E>> getShortestPathsIntern(final V source,
        final V target, int k) {
    LinkedList<List<E>> found_paths = new LinkedList<List<E>>();
    PriorityQueue<WeightedPath> prioQ = new PriorityQueue<WeightedPath>();
    DijkstraShortestPath<V, E> blockedDijkstra;

    // Check if target is reachable from source.
    if (dijkstra.getDistance(source, target) == null)
        return found_paths;

    // Add Dijkstra solution, the first shortest path.
    found_paths.add(dijkstra.getPath(source, target));

    while (found_paths.size() < k) {
        List<E> curShortestPath = found_paths.getLast();

        int maxIndex = curShortestPath.size();

        // Split path into Head and NextEdge
        for (int i = 0; i < maxIndex; i++) {
            List<E> head = curShortestPath.subList(0, i /* excluded */);
            V deviation = head.isEmpty() ? source : graph.getDest(head
                    .get(i - 1));

            // 1. Block edges.
            Graph<V, E> blocked = blockFilter(head, deviation, found_paths);

            // 2. Get shortest path in graph with blocked edges.
            blockedDijkstra = new DijkstraShortestPath<V, E>(blocked, nev);

            Number dist = blockedDijkstra.getDistance(deviation, target);
            if (dist == null)
                continue;

            List<E> tail = blockedDijkstra.getPath(deviation, target);

            // 3. Combine head and tail into new path.
            List<E> candidate = new ArrayList<E>(i + tail.size());
            candidate.addAll(head);
            candidate.addAll(tail);

            // Check if we already found this solution
            boolean duplicate = false;
            for (WeightedPath path : prioQ)
                if (ListUtils.isEqualList(path.getPath(), candidate)) {
                    duplicate = true;
                    break;
                }

            if (!duplicate)
                prioQ.add(new WeightedPath(candidate));
        }

        if (prioQ.isEmpty())
            break; // We have not found any new candidate!
        else
            found_paths.add(prioQ.poll().getPath());
    }

    return found_paths;
}

项目：org.datagr4m 文件：HierarchicalEdgeModel.java

@Override
public List<IBoundedItem> findItemsBetween(IBoundedItem in, IBoundedItem out){
    // these list will contain the item referenced by edges also containing IN or OUT item
    List<IBoundedItem> ins = new ArrayList<IBoundedItem>();
    List<IBoundedItem> outs = new ArrayList<IBoundedItem>();

    for(Tube tube: rootTubes){
        retrieveInOutItems(tube, in, out, ins, outs);
    }
    for(IEdge edge: internalEdges){
        retrieveInOutItems(edge, in, out, ins, outs);
    }

    return ListUtils.intersection(ins, outs);
}

项目：alevin-svn2 文件：SuurballeTarjan.java

/**
 * Combines two disjoint paths from two SuurballeTarjan input paths.
 * 
 * @param path1
 *            Dijkstra shortest path
 * @param path2
 *            Dijkstra shortest path in partly reverted graph
 * @return the two disjoint paths
 */
private List<List<E>> findTwoWays(List<E> path1, List<E> path2) {
    final V source = graph.getSource(path1.get(0));
    final V target = graph.getDest(path1.get(path1.size() - 1));

    // Remove common links.
    Iterator<E> it1 = path1.iterator();
    while (it1.hasNext()) {
        E e1 = it1.next();

        Iterator<E> it2 = path2.iterator();
        while (it2.hasNext()) {
            E e2 = it2.next();

            // ensure disjointness
            if (comparator.compare(e1, e2) == 0) { // for multigraph
                if (graph.isSource(source, e1)
                        || graph.isSource(source, e2)
                        || graph.isDest(target, e1)
                        || graph.isDest(target, e2))
                    return null; // Removing required edge

                it1.remove();
                it2.remove();
                break; // inner loop
            }
        }
    }

    if (path1.isEmpty() || path2.isEmpty())
        return null; // no disjoint solution found

    // Now recombine the two paths.
    List<E> union = ListUtils.union(path1, path2); // concatenate

    List<E> p1 = recombinePaths(path1, target, union);
    if (p1 == null)
        return null;

    List<E> p2 = recombinePaths(path2, target, union);
    if (p2 == null)
        return null;

    if (!union.isEmpty())
        throw new AssertionError("BUG");

    List<List<E>> solution = new LinkedList<List<E>>();
    solution.add(p1);
    solution.add(p2);
    return solution;
}

项目：crucian 文件：Yen.java

@Override
protected List<List<E>> getShortestPathsIntern(final V source,
                                               final V target, int k) {
    LinkedList<List<E>> found_paths = new LinkedList<List<E>>();
    PriorityQueue<WeightedPath> prioQ = new PriorityQueue<WeightedPath>();
    DijkstraShortestPath<V, E> blockedDijkstra;

    // Check if target is reachable from source.
    if (dijkstra.getDistance(source, target) == null)
        return found_paths;

    // Add Dijkstra solution, the first shortest path.
    found_paths.add(dijkstra.getPath(source, target));

    while (found_paths.size() < k) {
        List<E> curShortestPath = found_paths.getLast();

        int maxIndex = curShortestPath.size();

        // Split path into Head and NextEdge
        for (int i = 0; i < maxIndex; i++) {
            List<E> head = curShortestPath.subList(0, i /* excluded */);
            V deviation = head.isEmpty() ? source : graph.getDest(head
                    .get(i - 1));

            // 1. Block edges.
            Graph<V, E> blocked = blockFilter(head, deviation, found_paths);

            // 2. Get shortest path in graph with blocked edges.
            blockedDijkstra = new DijkstraShortestPath<V, E>(blocked, nev);

            Number dist = blockedDijkstra.getDistance(deviation, target);
            if (dist == null)
                continue;

            List<E> tail = blockedDijkstra.getPath(deviation, target);

            // 3. Combine head and tail into new path.
            List<E> candidate = new ArrayList<E>(i + tail.size());
            candidate.addAll(head);
            candidate.addAll(tail);

            // Check if we already found this solution
            boolean duplicate = false;
            for (WeightedPath path : prioQ)
                if (ListUtils.isEqualList(path.getPath(), candidate)) {
                    duplicate = true;
                    break;
                }

            if (!duplicate)
                prioQ.add(new WeightedPath(candidate));
        }

        if (prioQ.isEmpty())
            break; // We have not found any new candidate!
        else
            found_paths.add(prioQ.poll().getPath());
    }

    return found_paths;
}

项目：crucian 文件：SuurballeTarjan.java

/**
 * Combines two disjoint paths from two SuurballeTarjan input paths.
 *
 * @param path1 Dijkstra shortest path
 * @param path2 Dijkstra shortest path in partly reverted graph
 * @return the two disjoint paths
 */
private List<List<E>> findTwoWays(List<E> path1, List<E> path2) {
    final V source = graph.getSource(path1.get(0));
    final V target = graph.getDest(path1.get(path1.size() - 1));

    // Remove common links.
    Iterator<E> it1 = path1.iterator();
    while (it1.hasNext()) {
        E e1 = it1.next();

        Iterator<E> it2 = path2.iterator();
        while (it2.hasNext()) {
            E e2 = it2.next();

            // ensure disjointness
            if (comparator.compare(e1, e2) == 0) { // for multigraph
                if (graph.isSource(source, e1)
                        || graph.isSource(source, e2)
                        || graph.isDest(target, e1)
                        || graph.isDest(target, e2))
                    return null; // Removing required edge

                it1.remove();
                it2.remove();
                break; // inner loop
            }
        }
    }

    if (path1.isEmpty() || path2.isEmpty())
        return null; // no disjoint solution found

    // Now recombine the two paths.
    List<E> union = ListUtils.union(path1, path2); // concatenate

    List<E> p1 = recombinePaths(path1, target, union);
    if (p1 == null)
        return null;

    List<E> p2 = recombinePaths(path2, target, union);
    if (p2 == null)
        return null;

    if (!union.isEmpty())
        throw new AssertionError("BUG");

    List<List<E>> solution = new LinkedList<List<E>>();
    solution.add(p1);
    solution.add(p2);
    return solution;
}

项目：Alevin 文件：Yen.java

@Override
protected List<List<E>> getShortestPathsIntern(final V source,
        final V target, int k) {
    LinkedList<List<E>> found_paths = new LinkedList<List<E>>();
    PriorityQueue<WeightedPath> prioQ = new PriorityQueue<WeightedPath>();
    DijkstraShortestPath<V, E> blockedDijkstra;

    // Check if target is reachable from source.
    if (dijkstra.getDistance(source, target) == null)
        return found_paths;

    // Add Dijkstra solution, the first shortest path.
    found_paths.add(dijkstra.getPath(source, target));

    while (found_paths.size() < k) {
        List<E> curShortestPath = found_paths.getLast();

        int maxIndex = curShortestPath.size();

        // Split path into Head and NextEdge
        for (int i = 0; i < maxIndex; i++) {
            List<E> head = curShortestPath.subList(0, i /* excluded */);
            V deviation = head.isEmpty() ? source : graph.getDest(head
                    .get(i - 1));

            // 1. Block edges.
            Graph<V, E> blocked = blockFilter(head, deviation, found_paths);

            // 2. Get shortest path in graph with blocked edges.
            blockedDijkstra = new DijkstraShortestPath<V, E>(blocked, nev);

            Number dist = blockedDijkstra.getDistance(deviation, target);
            if (dist == null)
                continue;

            List<E> tail = blockedDijkstra.getPath(deviation, target);

            // 3. Combine head and tail into new path.
            List<E> candidate = new ArrayList<E>(i + tail.size());
            candidate.addAll(head);
            candidate.addAll(tail);

            // Check if we already found this solution
            boolean duplicate = false;
            for (WeightedPath path : prioQ)
                if (ListUtils.isEqualList(path.getPath(), candidate)) {
                    duplicate = true;
                    break;
                }

            if (!duplicate)
                prioQ.add(new WeightedPath(candidate));
        }

        if (prioQ.isEmpty())
            break; // We have not found any new candidate!
        else
            found_paths.add(prioQ.poll().getPath());
    }

    return found_paths;
}

项目：Alevin 文件：SuurballeTarjan.java

/**
 * Combines two disjoint paths from two SuurballeTarjan input paths.
 * 
 * @param path1
 *            Dijkstra shortest path
 * @param path2
 *            Dijkstra shortest path in partly reverted graph
 * @return the two disjoint paths
 */
private List<List<E>> findTwoWays(List<E> path1, List<E> path2) {
    final V source = graph.getSource(path1.get(0));
    final V target = graph.getDest(path1.get(path1.size() - 1));

    // Remove common links.
    Iterator<E> it1 = path1.iterator();
    while (it1.hasNext()) {
        E e1 = it1.next();

        Iterator<E> it2 = path2.iterator();
        while (it2.hasNext()) {
            E e2 = it2.next();

            // ensure disjointness
            if (comparator.compare(e1, e2) == 0) { // for multigraph
                if (graph.isSource(source, e1)
                        || graph.isSource(source, e2)
                        || graph.isDest(target, e1)
                        || graph.isDest(target, e2))
                    return null; // Removing required edge

                it1.remove();
                it2.remove();
                break; // inner loop
            }
        }
    }

    if (path1.isEmpty() || path2.isEmpty())
        return null; // no disjoint solution found

    // Now recombine the two paths.
    List<E> union = ListUtils.union(path1, path2); // concatenate

    List<E> p1 = recombinePaths(path1, target, union);
    if (p1 == null)
        return null;

    List<E> p2 = recombinePaths(path2, target, union);
    if (p2 == null)
        return null;

    if (!union.isEmpty())
        throw new AssertionError("BUG");

    List<List<E>> solution = new LinkedList<List<E>>();
    solution.add(p1);
    solution.add(p2);
    return solution;
}