opendaylight/md-sal/samples/l2switch/implementation/src/main/java/org/opendaylight/controller/sample/l2switch/md/topology/NetworkGraphDijkstra.java

   1 /*
   2  * Copyright (c) 2014 Cisco Systems, Inc. and others.  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.controller.sample.l2switch.md.topology;
   9
  10 import com.google.common.base.Preconditions;
  11 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
  12 import edu.uci.ics.jung.graph.DirectedSparseGraph;
  13 import edu.uci.ics.jung.graph.Graph;
  14 import org.opendaylight.yang.gen.v1.urn.tbd.params.xml.ns.yang.network.topology.rev131021.NodeId;
  15 import org.opendaylight.yang.gen.v1.urn.tbd.params.xml.ns.yang.network.topology.rev131021.network.topology.topology.Link;
  16 import org.slf4j.Logger;
  17 import org.slf4j.LoggerFactory;
  18
  19 import java.util.List;
  20
  21 /**
  22  * Implementation of NetworkGraphService{@link org.opendaylight.controller.sample.l2switch.md.topology.NetworkGraphService}.
  23  * It uses Jung graph library internally to maintain a graph and optimum way to return shortest path using
  24  * Dijkstra algorithm.
  25  */
  26 public class NetworkGraphDijkstra implements NetworkGraphService {
  27
  28   private static final Logger _logger = LoggerFactory.getLogger(NetworkGraphDijkstra.class);
  29
  30   DijkstraShortestPath<NodeId, Link> shortestPath = null;
  31   Graph<NodeId, Link> networkGraph = null;
  32
  33   /**
  34    * Adds links to existing graph or creates new directed graph with given links if graph was not initialized.
  35    * @param links
  36    */
  37   @Override
  38   public synchronized void addLinks(List<Link> links) {
  39     if(links == null || links.isEmpty()) {
  40       _logger.info("In addLinks: No link added as links is null or empty.");
  41       return;
  42     }
  43
  44     if(networkGraph == null) {
  45       networkGraph = new DirectedSparseGraph<>();
  46     }
  47
  48     for(Link link : links) {
  49       NodeId sourceNodeId = link.getSource().getSourceNode();
  50       NodeId destinationNodeId = link.getDestination().getDestNode();
  51       networkGraph.addVertex(sourceNodeId);
  52       networkGraph.addVertex(destinationNodeId);
  53       networkGraph.addEdge(link, sourceNodeId, destinationNodeId);
  54     }
  55     if(shortestPath == null) {
  56       shortestPath = new DijkstraShortestPath<>(networkGraph);
  57     } else {
  58       shortestPath.reset();
  59     }
  60   }
  61
  62   /**
  63    * removes links from existing graph.
  64    * @param links
  65    */
  66   @Override
  67   public synchronized void removeLinks(List<Link> links) {
  68     Preconditions.checkNotNull(networkGraph, "Graph is not initialized, add links first.");
  69
  70     if(links == null || links.isEmpty()) {
  71       _logger.info("In removeLinks: No link removed as links is null or empty.");
  72       return;
  73     }
  74
  75     for(Link link : links) {
  76       networkGraph.removeEdge(link);
  77     }
  78
  79     if(shortestPath == null) {
  80       shortestPath = new DijkstraShortestPath<>(networkGraph);
  81     } else {
  82       shortestPath.reset();
  83     }
  84   }
  85
  86   /**
  87    * returns a path between 2 nodes. Uses Dijkstra's algorithm to return shortest path.
  88    * @param sourceNodeId
  89    * @param destinationNodeId
  90    * @return
  91    */
  92   @Override
  93   public synchronized List<Link> getPath(NodeId sourceNodeId, NodeId destinationNodeId) {
  94     Preconditions.checkNotNull(shortestPath, "Graph is not initialized, add links first.");
  95
  96     if(sourceNodeId == null || destinationNodeId == null) {
  97       _logger.info("In getPath: returning null, as sourceNodeId or destinationNodeId is null.");
  98       return null;
  99     }
 100
 101     return shortestPath.getPath(sourceNodeId, destinationNodeId);
 102   }
 103
 104   /**
 105    * Clears the prebuilt graph, in case same service instance is required to process a new graph.
 106    */
 107   @Override
 108   public synchronized void clear() {
 109     networkGraph = null;
 110     shortestPath = null;
 111   }
 112 }