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