loopremover/implementation/src/main/java/org/opendaylight/l2switch/loopremover/topology/NetworkGraphImpl.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.l2switch.loopremover.topology;
   9
  10 import com.google.common.base.Preconditions;
  11 import edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree;
  12 import edu.uci.ics.jung.graph.DelegateTree;
  13 import edu.uci.ics.jung.graph.Graph;
  14 import edu.uci.ics.jung.graph.SparseMultigraph;
  15 import edu.uci.ics.jung.graph.util.EdgeType;
  16 import java.util.ArrayList;
  17 import java.util.Collection;
  18 import java.util.HashSet;
  19 import java.util.List;
  20 import java.util.Set;
  21 import javax.annotation.concurrent.GuardedBy;
  22 import org.opendaylight.yang.gen.v1.urn.tbd.params.xml.ns.yang.network.topology.rev131021.NodeId;
  23 import org.opendaylight.yang.gen.v1.urn.tbd.params.xml.ns.yang.network.topology.rev131021.network.topology.topology.Link;
  24 import org.slf4j.Logger;
  25 import org.slf4j.LoggerFactory;
  26
  27 /**
  28  * Implementation of NetworkGraphService
  29  * {@link org.opendaylight.l2switch.loopremover.topology.NetworkGraphService}. It
  30  * uses Jung graph library internally to maintain a graph and optimum way to
  31  * return shortest path using Dijkstra algorithm.
  32  */
  33 public class NetworkGraphImpl implements NetworkGraphService {
  34
  35     private static final Logger LOG = LoggerFactory.getLogger(NetworkGraphImpl.class);
  36
  37     @GuardedBy("this")
  38     private Graph<NodeId, Link> networkGraph;
  39     private final Set<String> linkAdded = new HashSet<>();
  40
  41     // Enable following lines when shortest path functionality is required.
  42     // DijkstraShortestPath<NodeId, Link> shortestPath = null;
  43
  44     /**
  45      * Adds links to existing graph or creates new directed graph with given
  46      * links if graph was not initialized.
  47      *
  48      * @param links
  49      *            The links to add.
  50      */
  51     @Override
  52     public synchronized void addLinks(List<Link> links) {
  53         if (links == null || links.isEmpty()) {
  54             LOG.info("In addLinks: No link added as links is null or empty.");
  55             return;
  56         }
  57
  58         if (networkGraph == null) {
  59             networkGraph = SparseMultigraph.<NodeId, Link>getFactory().get();
  60         }
  61
  62         for (Link link : links) {
  63             if (linkAlreadyAdded(link)) {
  64                 continue;
  65             }
  66             NodeId sourceNodeId = link.getSource().getSourceNode();
  67             NodeId destinationNodeId = link.getDestination().getDestNode();
  68             networkGraph.addVertex(sourceNodeId);
  69             networkGraph.addVertex(destinationNodeId);
  70             networkGraph.addEdge(link, sourceNodeId, destinationNodeId, EdgeType.UNDIRECTED);
  71         }
  72
  73         /*
  74          * if(shortestPath == null) { shortestPath = new
  75          * DijkstraShortestPath<>(networkGraph); } else { shortestPath.reset();
  76          * }
  77          */
  78     }
  79
  80     @GuardedBy("this")
  81     private boolean linkAlreadyAdded(Link link) {
  82         String linkAddedKey = null;
  83         if (link.getDestination().getDestTp().hashCode() > link.getSource().getSourceTp().hashCode()) {
  84             linkAddedKey = link.getSource().getSourceTp().getValue() + link.getDestination().getDestTp().getValue();
  85         } else {
  86             linkAddedKey = link.getDestination().getDestTp().getValue() + link.getSource().getSourceTp().getValue();
  87         }
  88         if (linkAdded.contains(linkAddedKey)) {
  89             return true;
  90         } else {
  91             linkAdded.add(linkAddedKey);
  92             return false;
  93         }
  94     }
  95
  96     /**
  97      * Removes links from existing graph.
  98      *
  99      * @param links
 100      *            The links to remove.
 101      */
 102     @Override
 103     public synchronized void removeLinks(List<Link> links) {
 104         Preconditions.checkNotNull(networkGraph, "Graph is not initialized, add links first.");
 105
 106         if (links == null || links.isEmpty()) {
 107             LOG.info("In removeLinks: No link removed as links is null or empty.");
 108             return;
 109         }
 110
 111         for (Link link : links) {
 112             networkGraph.removeEdge(link);
 113         }
 114         /*
 115          * if(shortestPath == null) { shortestPath = new
 116          * DijkstraShortestPath<>(networkGraph); } else { shortestPath.reset();
 117          * }
 118          */
 119
 120     }
 121
 122     /**
 123      * returns a path between 2 nodes. Uses Dijkstra's algorithm to return
 124      * shortest path.
 125      *
 126      * @param sourceNodeId the source node Id
 127      * @param destinationNodeId the destination node Id
 128      */
 129     // @Override
 130     /*
 131      * public synchronized List<Link> getPath(NodeId sourceNodeId, NodeId
 132      * destinationNodeId) { Preconditions.checkNotNull(shortestPath,
 133      * "Graph is not initialized, add links first.");
 134      *
 135      * if(sourceNodeId == null || destinationNodeId == null) { _logger.info(
 136      * "In getPath: returning null, as sourceNodeId or destinationNodeId is null."
 137      * ); return null; }
 138      *
 139      * return shortestPath.getPath(sourceNodeId, destinationNodeId); }
 140      */
 141
 142     /**
 143      * Clears the prebuilt graph, in case same service instance is required to
 144      * process a new graph.
 145      */
 146     @Override
 147     public synchronized void clear() {
 148         networkGraph = null;
 149         linkAdded.clear();
 150         // shortestPath = null;
 151     }
 152
 153     /**
 154      * Forms MST(minimum spanning tree) from network graph and returns links
 155      * that are not in MST.
 156      *
 157      * @return The links in the MST (minimum spanning tree)
 158      */
 159     @Override
 160     public synchronized List<Link> getLinksInMst() {
 161         List<Link> linksInMst = new ArrayList<>();
 162         if (networkGraph != null) {
 163             PrimMinimumSpanningTree<NodeId, Link> networkMst = new PrimMinimumSpanningTree<>(
 164                     DelegateTree.<NodeId, Link>getFactory());
 165             Graph<NodeId, Link> mstGraph = networkMst.apply(networkGraph);
 166             Collection<Link> mstLinks = mstGraph.getEdges();
 167             linksInMst.addAll(mstLinks);
 168         }
 169         return linksInMst;
 170     }
 171
 172     /**
 173      * Get all the links in the network.
 174      *
 175      * @return The links in the network.
 176      */
 177     @Override
 178     public synchronized List<Link> getAllLinks() {
 179         List<Link> allLinks = new ArrayList<>();
 180         if (networkGraph != null) {
 181             allLinks.addAll(networkGraph.getEdges());
 182         }
 183         return allLinks;
 184     }
 185 }