algo/algo-impl/src/main/java/org/opendaylight/algo/impl/ShortestPathFirst.java

   1 /*
   2  * Copyright (c) 2016 Orange. All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.algo.impl;
   9
  10 import java.util.HashMap;
  11 import java.util.List;
  12 import org.opendaylight.graph.ConnectedEdge;
  13 import org.opendaylight.graph.ConnectedGraph;
  14 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
  15 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
  16 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
  17 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
  18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
  19 import org.opendaylight.yangtools.yang.common.Uint32;
  20 import org.slf4j.Logger;
  21 import org.slf4j.LoggerFactory;
  22
  23 /**
  24  * This Class implements a simple Shortest Path First path computation algorithm based on standard IGP Metric.
  25  *
  26  * @author Olivier Dugeon
  27  * @author Philippe Niger
  28  * @author Philippe Cadro
  29  */
  30 public class ShortestPathFirst extends AbstractPathComputation {
  31
  32     private static final Logger LOG = LoggerFactory.getLogger(ShortestPathFirst.class);
  33
  34     private HashMap<Long, CspfPath> visitedVertices;
  35
  36     public ShortestPathFirst(ConnectedGraph graph) {
  37         super(graph);
  38         visitedVertices = new HashMap<Long, CspfPath>();
  39     }
  40
  41     public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
  42         ConstrainedPathBuilder cpathBuilder;
  43         List<ConnectedEdge> edges;
  44         CspfPath currentPath;
  45         int currentCost = Integer.MAX_VALUE;
  46
  47         LOG.info("Start SPF Path Computation from {} to {} with constraints {}", src, dst, cts);
  48
  49         /* Initialize algorithm */
  50         this.constraints = cts;
  51         cpathBuilder = initializePathComputation(src, dst);
  52         if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
  53             LOG.warn("Initial configurations are not met. Abort!");
  54             return cpathBuilder.build();
  55         }
  56
  57         visitedVertices.clear();
  58
  59         while (priorityQueue.size() != 0) {
  60             currentPath = priorityQueue.poll();
  61             visitedVertices.put(currentPath.getVertexKey(), currentPath);
  62             LOG.debug("Process path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
  63             edges = currentPath.getVertex().getOutputConnectedEdges();
  64
  65             for (ConnectedEdge edge : edges) {
  66                 /* Check that Edge point to a valid Vertex and is suitable for the Constraint Address Family */
  67                 if (pruneEdge(edge, currentPath)) {
  68                     LOG.trace("  Prune Edge {}", edge.toString());
  69                     continue;
  70                 }
  71                 if ((relax(edge, currentPath)) && (pathDestination.getCost() < currentCost)) {
  72                     currentCost = pathDestination.getCost();
  73                     cpathBuilder.setPathDescription(getPathDescription(pathDestination.getPath()))
  74                             .setMetric(Uint32.valueOf(pathDestination.getCost()))
  75                             .setStatus(ComputationStatus.Active);
  76                     LOG.debug("  Found a valid path up to destination {}", cpathBuilder.getPathDescription());
  77                 }
  78             }
  79         }
  80         /* The priority queue is empty => all the possible (vertex, path) elements have been explored
  81          * The "ConstrainedPathBuilder" object contains the optimal path if it exists
  82          * Otherwise an empty path with status failed is returned
  83          */
  84         if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
  85                 || (cpathBuilder.getPathDescription().size() == 0)) {
  86             cpathBuilder.setStatus(ComputationStatus.Failed);
  87         } else {
  88             cpathBuilder.setStatus(ComputationStatus.Completed);
  89         }
  90         return cpathBuilder.build();
  91     }
  92
  93     private boolean relax(ConnectedEdge edge, CspfPath currentPath) {
  94         LOG.debug("    Start relaxing Edge {} to Vertex {}", edge.toString(), edge.getDestination().toString());
  95         final Long nextVertexKey = edge.getDestination().getKey();
  96
  97         /* Verify if we have not visited this Vertex to avoid loop */
  98         if (visitedVertices.containsKey(nextVertexKey)) {
  99             return false;
 100         }
 101
 102         /* Get Next Vertex from processedPath or create a new one if it has not yet processed */
 103         CspfPath nextPath = processedPath.get(nextVertexKey);
 104         if (nextPath == null) {
 105             nextPath = new CspfPath(edge.getDestination());
 106             processedPath.put(nextPath.getVertexKey(), nextPath);
 107         }
 108
 109         /* Compute Cost from source to this next Vertex and add or update it in the Priority Queue
 110          * if total path Cost is lower than cost associated to this next Vertex.
 111          * This could occurs if we process a Vertex that as not yet been visited in the Graph
 112          * or if we found a shortest path up to this Vertex. */
 113         int totalCost = edge.getEdge().getEdgeAttributes().getMetric().intValue() + currentPath.getCost();
 114         if (nextPath.getCost() > totalCost) {
 115             nextPath.setCost(totalCost)
 116                     .replacePath(currentPath.getPath())
 117                     .addConnectedEdge(edge);
 118             /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we modify the path
 119              * weight, the Priority Queue must be re-ordered. So, we need fist to remove the CspfPath if it is present
 120              * in the Priority Queue, then, update the Path Weight, and finally (re-)insert it in the Priority Queue.
 121              */
 122             priorityQueue.removeIf((path) -> path.getVertexKey().equals(nextVertexKey));
 123             nextPath.setKey(totalCost);
 124             priorityQueue.add(nextPath);
 125             LOG.debug("    Added path to Vertex {} in the Priority Queue with weight {}",
 126                     nextPath.getVertex().toString(), nextPath.getKey());
 127         }
 128         /* Return True if we reach the destination, false otherwise */
 129         return pathDestination.equals(nextPath);
 130     }
 131 }