utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java

/*
 * Copyright 2014 Open Networking Laboratory
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.onlab.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

/**
 * Basis for various graph path search algorithm implementations.
 *
 * @param <V> vertex type
 * @param <E> edge type
 */
public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
        implements GraphPathSearch<V, E> {

    private double samenessThreshold = Double.MIN_VALUE;

    /**
     * Sets a new sameness threshold for comparing cost values; default is
     * is {@code 0.000000001}.
     *
     * @param threshold fractional double value
     */
    public void setSamenessThreshold(double threshold) {
        samenessThreshold = threshold;
    }

    /**
     * Returns the current sameness threshold for comparing cost values.
     *
     * @return current threshold
     */
    public double samenessThreshold() {
        return samenessThreshold;
    }

    /**
     * Default path search result that uses the DefaultPath to convey paths
     * in a graph.
     */
    protected class DefaultResult implements Result<V, E> {

        private final V src;
        private final V dst;
        protected final Set<Path<V, E>> paths = new HashSet<>();
        protected final Map<V, Double> costs = new HashMap<>();
        protected final Map<V, Set<E>> parents = new HashMap<>();

        /**
         * Creates the result of path search.
         *
         * @param src path source
         * @param dst optional path destination
         */
        public DefaultResult(V src, V dst) {
            checkNotNull(src, "Source cannot be null");
            this.src = src;
            this.dst = dst;
        }

        @Override
        public V src() {
            return src;
        }

        @Override
        public V dst() {
            return dst;
        }

        @Override
        public Set<Path<V, E>> paths() {
            return paths;
        }

        @Override
        public Map<V, Double> costs() {
            return costs;
        }

        @Override
        public Map<V, Set<E>> parents() {
            return parents;
        }

        /**
         * Indicates whether or not the given vertex has a cost yet.
         *
         * @param v vertex to test
         * @return true if the vertex has cost already
         */
        boolean hasCost(V v) {
            return costs.get(v) != null;
        }

        /**
         * Returns the current cost to reach the specified vertex.
         *
         * @param v vertex to reach
         * @return cost to reach the vertex
         */
        double cost(V v) {
            Double c = costs.get(v);
            return c == null ? Double.MAX_VALUE : c;
        }

        /**
         * Updates the cost of the vertex using its existing cost plus the
         * cost to traverse the specified edge.
         *
         * @param vertex  vertex to update
         * @param edge    edge through which vertex is reached
         * @param cost    current cost to reach the vertex from the source
         * @param replace true to indicate that any accrued edges are to be
         *                cleared; false to indicate that the edge should be
         *                added to the previously accrued edges as they yield
         *                the same cost
         */
        void updateVertex(V vertex, E edge, double cost, boolean replace) {
            costs.put(vertex, cost);
            if (edge != null) {
                Set<E> edges = parents.get(vertex);
                if (edges == null) {
                    edges = new HashSet<>();
                    parents.put(vertex, edges);
                }
                if (replace) {
                    edges.clear();
                }
                edges.add(edge);
            }
        }

        /**
         * Removes the set of parent edges for the specified vertex.
         *
         * @param v vertex
         */
        void removeVertex(V v) {
            parents.remove(v);
        }

        /**
         * If possible, relax the specified edge using the supplied base cost
         * and edge-weight function.
         *
         * @param edge            edge to be relaxed
         * @param cost            base cost to reach the edge destination vertex
         * @param ew              optional edge weight function
         * @param forbidNegatives if true negative values will forbid the link
         * @return true if the edge was relaxed; false otherwise
         */
        boolean relaxEdge(E edge, double cost, EdgeWeight<V, E> ew,
                          boolean... forbidNegatives) {
            V v = edge.dst();
            double oldCost = cost(v);
            double hopCost = ew == null ? 1.0 : ew.weight(edge);
            if (hopCost < 0 && forbidNegatives.length == 1 && forbidNegatives[0]) {
                return false;
            }

            double newCost = cost + hopCost;
            boolean relaxed = newCost < oldCost;
            boolean same = Math.abs(newCost - oldCost) <= samenessThreshold;
            if (same || relaxed) {
                updateVertex(v, edge, newCost, !same);
            }
            return relaxed;
        }

        /**
         * Builds a set of paths for the specified src/dst vertex pair.
         */
        protected void buildPaths() {
            Set<V> destinations = new HashSet<>();
            if (dst == null) {
                destinations.addAll(costs.keySet());
            } else {
                destinations.add(dst);
            }

            // Build all paths between the source and all requested destinations.
            for (V v : destinations) {
                // Ignore the source, if it is among the destinations.
                if (!v.equals(src)) {
                    buildAllPaths(this, src, v);
                }
            }
        }

    }

    /**
     * Builds a set of all paths between the source and destination using the
     * graph search result by applying breadth-first search through the parent
     * edges and vertex costs.
     *
     * @param result graph search result
     * @param src    source vertex
     * @param dst    destination vertex
     */
    private void buildAllPaths(DefaultResult result, V src, V dst) {
        DefaultMutablePath<V, E> basePath = new DefaultMutablePath<>();
        basePath.setCost(result.cost(dst));

        Set<DefaultMutablePath<V, E>> pendingPaths = new HashSet<>();
        pendingPaths.add(basePath);

        while (!pendingPaths.isEmpty()) {
            Set<DefaultMutablePath<V, E>> frontier = new HashSet<>();

            for (DefaultMutablePath<V, E> path : pendingPaths) {
                // For each pending path, locate its first vertex since we
                // will be moving backwards from it.
                V firstVertex = firstVertex(path, dst);

                // If the first vertex is our expected source, we have reached
                // the beginning, so add the this path to the result paths.
                if (firstVertex.equals(src)) {
                    path.setCost(result.cost(dst));
                    result.paths.add(new DefaultPath<>(path.edges(), path.cost()));

                } else {
                    // If we have not reached the beginning, i.e. the source,
                    // fetch the set of edges leading to the first vertex of
                    // this pending path; if there are none, abandon processing
                    // this path for good.
                    Set<E> firstVertexParents = result.parents.get(firstVertex);
                    if (firstVertexParents == null || firstVertexParents.isEmpty()) {
                        break;
                    }

                    // Now iterate over all the edges and for each of them
                    // cloning the current path and then insert that edge to
                    // the path and then add that path to the pending ones.
                    // When processing the last edge, modify the current
                    // pending path rather than cloning a new one.
                    Iterator<E> edges = firstVertexParents.iterator();
                    while (edges.hasNext()) {
                        E edge = edges.next();
                        boolean isLast = !edges.hasNext();
                        DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path);
                        pendingPath.insertEdge(edge);
                        frontier.add(pendingPath);
                    }
                }
            }

            // All pending paths have been scanned so promote the next frontier
            pendingPaths = frontier;
        }
    }

    // Returns the first vertex of the specified path. This is either the source
    // of the first edge or, if there are no edges yet, the given destination.
    private V firstVertex(Path<V, E> path, V dst) {
        return path.edges().isEmpty() ? dst : path.edges().get(0).src();
    }

    /**
     * Checks the specified path search arguments for validity.
     *
     * @param graph graph; must not be null
     * @param src   source vertex; must not be null and belong to graph
     * @param dst   optional target vertex; must belong to graph
     */
    protected void checkArguments(Graph<V, E> graph, V src, V dst) {
        checkNotNull(graph, "Graph cannot be null");
        checkNotNull(src, "Source cannot be null");
        Set<V> vertices = graph.getVertexes();
        checkArgument(vertices.contains(src), "Source not in the graph");
        checkArgument(dst == null || vertices.contains(dst),
                      "Destination not in graph");
    }

}