nemo-impl/src/main/java/org/opendaylight/nemo/intent/algorithm/RoutingAlgorithm.java

   1 /*\r
   2  * Copyright (c) 2015 Huawei, Inc. and others. All rights reserved.\r
   3  *\r
   4  * This program and the accompanying materials are made available under the\r
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,\r
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html\r
   7  */\r
   8 \r
   9 package org.opendaylight.nemo.intent.algorithm;\r
  10 \r
  11 import edu.uci.ics.jung.algorithms.filters.EdgePredicateFilter;\r
  12 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;\r
  13 import edu.uci.ics.jung.graph.DirectedSparseGraph;\r
  14 import edu.uci.ics.jung.graph.Graph;\r
  15 import edu.uci.ics.jung.graph.util.EdgeType;\r
  16 import org.apache.commons.collections15.Predicate;\r
  17 import org.apache.commons.collections15.Transformer;\r
  18 \r
  19 import java.util.Collection;\r
  20 import java.util.List;\r
  21 \r
  22 /**\r
  23  * Implement the SPF and CSPF algorithms based on the Dijkstra's algorithm.\r
  24  *\r
  25  * @author Zhigang Ji\r
  26  */\r
  27 public class RoutingAlgorithm {\r
  28     /**\r
  29      * The current network topology graph.\r
  30      */\r
  31     private Graph<Vertex, Edge> graph;\r
  32 \r
  33     /**\r
  34      * The Dijkstra shortest path algorithm instance.\r
  35      */\r
  36     private DijkstraShortestPath<Vertex, Edge> dijkstraShortestPath;\r
  37 \r
  38     public RoutingAlgorithm() {\r
  39         super();\r
  40 \r
  41         graph = new DirectedSparseGraph<Vertex, Edge>();\r
  42         dijkstraShortestPath = new DijkstraShortestPath<Vertex, Edge>(graph, new Transformer<Edge, Number>() {\r
  43             @Override\r
  44             public Number transform(Edge edge) {\r
  45                 return edge.getMetric();\r
  46             }\r
  47         }, false);\r
  48 \r
  49         return;\r
  50     }\r
  51 \r
  52     /**\r
  53      * Get the vertex with the given id from the network topology graph.\r
  54      *\r
  55      * @param vertexId The given vertex id.\r
  56      * @return The vertex with the given id.\r
  57      */\r
  58     public Vertex getVertex(String vertexId) {\r
  59         for ( Vertex vertex : graph.getVertices() ) {\r
  60             if ( vertex.getId().equals(vertexId) ) {\r
  61                 return vertex;\r
  62             }\r
  63         }\r
  64 \r
  65         return null;\r
  66     }\r
  67 \r
  68     /**\r
  69      * Get the edge with the given id from the network topology graph.\r
  70      *\r
  71      * @param edgeId The given edge id.\r
  72      * @return The edge with the given id.\r
  73      */\r
  74     public Edge getEdge(String edgeId) {\r
  75         for ( Edge edge : graph.getEdges() ) {\r
  76             if ( edge.getId().equals(edgeId) ) {\r
  77                 return edge;\r
  78             }\r
  79         }\r
  80 \r
  81         return null;\r
  82     }\r
  83 \r
  84     /**\r
  85      * Get all vertices from the network topology graph.\r
  86      *\r
  87      * @return The collection of all vertices.\r
  88      */\r
  89     public Collection<Vertex> getVertices() {\r
  90         return graph.getVertices();\r
  91     }\r
  92 \r
  93     /**\r
  94      * Add a vertex into the network topology graph.\r
  95      *\r
  96      * @param vertex The vertex to be added.\r
  97      */\r
  98     public void addVertex(Vertex vertex) {\r
  99         graph.addVertex(vertex);\r
 100 \r
 101         return;\r
 102     }\r
 103 \r
 104     /**\r
 105      * Add an edge into the network topology graph.\r
 106      *\r
 107      * @param edge The edge to be added.\r
 108      */\r
 109     public void addEdge(Edge edge) {\r
 110         graph.addEdge(edge, getVertex(edge.getSrc()), getVertex(edge.getDest()), EdgeType.DIRECTED);\r
 111 \r
 112         return;\r
 113     }\r
 114 \r
 115     /**\r
 116      * Update an edge in the network topology graph with the new one.\r
 117      *\r
 118      * @param newEdge The given new edge.\r
 119      */\r
 120     public void updateEdge(Edge newEdge) {\r
 121         Edge edge = getEdge(newEdge.getId());\r
 122 \r
 123         edge.setMetric(newEdge.getMetric());\r
 124         edge.setBandwidth(newEdge.getBandwidth());\r
 125 \r
 126         return;\r
 127     }\r
 128 \r
 129     /**\r
 130      * Remove the vertex with the given id from the network topology graph.\r
 131      *\r
 132      * @param vertexId The given vertex id.\r
 133      */\r
 134     public void removeVertex(String vertexId) {\r
 135         Vertex vertex = getVertex(vertexId);\r
 136 \r
 137         if ( null != vertex ) {\r
 138             graph.removeVertex(vertex);\r
 139         }\r
 140 \r
 141         return;\r
 142     }\r
 143 \r
 144     /**\r
 145      * Remove the edge with the given id from the network topology graph.\r
 146      *\r
 147      * @param edgeId The given edge id.\r
 148      */\r
 149     public void removeEdge(String edgeId) {\r
 150         Edge edge = getEdge(edgeId);\r
 151 \r
 152         if ( null != edge ) {\r
 153             graph.removeEdge(edge);\r
 154         }\r
 155 \r
 156         return;\r
 157     }\r
 158 \r
 159     /**\r
 160      * Compute a shortest path from the given source vertex to target\r
 161      * one without any constraint.\r
 162      *\r
 163      * @param source The given source vertex.\r
 164      * @param target The given target vertex.\r
 165      * @return A list of the edges on the shortest path, in order of\r
 166      * their occurrence on this path.\r
 167      */\r
 168     public List<Edge> computePath(Vertex source, Vertex target) {\r
 169         return dijkstraShortestPath.getPath(source, target);\r
 170     }\r
 171 \r
 172     /**\r
 173      * Compute a shortest path with the given bandwidth from the given\r
 174      * source vertex to target one.\r
 175      *\r
 176      * @param source The given source vertex.\r
 177      * @param target The given target vertex.\r
 178      * @param bandwidth The given bandwidth for the path.\r
 179      * @return A list of the edges on the shortest path, in order of\r
 180      * their occurrence on this path.\r
 181      */\r
 182     public List<Edge> computePath(Vertex source, Vertex target, final long bandwidth) {\r
 183         EdgePredicateFilter<Vertex, Edge> edgeEdgePredicateFilter = new EdgePredicateFilter<Vertex, Edge>(new Predicate<Edge>() {\r
 184             @Override\r
 185             public boolean evaluate(Edge edge) {\r
 186                 return edge.getBandwidth() >= bandwidth;\r
 187             }\r
 188         });\r
 189 \r
 190         Graph<Vertex, Edge> filteredGraph = edgeEdgePredicateFilter.transform(graph);\r
 191         DijkstraShortestPath<Vertex, Edge> tempDijkstraShortestPath = new DijkstraShortestPath<Vertex, Edge>(filteredGraph, new Transformer<Edge, Number>() {\r
 192             @Override\r
 193             public Number transform(Edge edge) {\r
 194                 return edge.getMetric();\r
 195             }\r
 196         }, false);\r
 197 \r
 198         return tempDijkstraShortestPath.getPath(source, target);\r
 199     }\r
 200 \r
 201     @Override\r
 202     public String toString() {\r
 203         return "RoutingAlgorithm{" +\r
 204                 "vertices=" + graph.getVertices() +\r
 205                 ", edges=" + graph.getEdges() +\r
 206                 '}';\r
 207     }\r
 208 }\r