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