Added javadocs and separated trivial implementations into distinct packages.
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceManager.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceManager.java
similarity index 99%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceManager.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceManager.java
index 135edd9..221a249 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceManager.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceManager.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.device.impl;
import org.apache.felix.scr.annotations.Activate;
import org.apache.felix.scr.annotations.Component;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceStore.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceStore.java
similarity index 99%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceStore.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceStore.java
index 1c1502e..6317b14 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleDeviceStore.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/device/impl/SimpleDeviceStore.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.device.impl;
import com.google.common.collect.ImmutableList;
import org.onlab.onos.net.DefaultDevice;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkManager.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkManager.java
similarity index 99%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkManager.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkManager.java
index 1930ea1..a817bb6 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkManager.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkManager.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.link.impl;
import static com.google.common.base.Preconditions.checkNotNull;
import static org.slf4j.LoggerFactory.getLogger;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkStore.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkStore.java
similarity index 99%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkStore.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkStore.java
index 9de3d5b..2ba7a30 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleLinkStore.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/link/impl/SimpleLinkStore.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.link.impl;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableSet;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopology.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/DefaultTopology.java
similarity index 96%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopology.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/DefaultTopology.java
index cb55819..c20acd8 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopology.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/DefaultTopology.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.topology.impl;
import org.onlab.onos.net.AbstractModel;
import org.onlab.onos.net.provider.ProviderId;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyManager.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyManager.java
similarity index 98%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyManager.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyManager.java
index 33b2a18..70f001c 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyManager.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyManager.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.topology.impl;
import org.apache.felix.scr.annotations.Activate;
import org.apache.felix.scr.annotations.Component;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyStore.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyStore.java
similarity index 98%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyStore.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyStore.java
index 7944a53..1b9766d 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyStore.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/impl/SimpleTopologyStore.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.topology.impl;
import org.onlab.graph.Graph;
import org.onlab.onos.event.Event;
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopologyDescription.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java
similarity index 68%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopologyDescription.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java
index c438146..87d2c47 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopologyDescription.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java
@@ -1,29 +1,35 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.topology.provider.impl;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
+import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;
import org.onlab.graph.AdjacencyListsGraph;
import org.onlab.graph.DijkstraGraphSearch;
import org.onlab.graph.Graph;
import org.onlab.graph.GraphPathSearch;
+import org.onlab.graph.TarjanGraphSearch;
import org.onlab.onos.net.ConnectPoint;
import org.onlab.onos.net.Device;
import org.onlab.onos.net.DeviceId;
import org.onlab.onos.net.Link;
import org.onlab.onos.net.topology.ClusterId;
+import org.onlab.onos.net.topology.DefaultTopologyCluster;
import org.onlab.onos.net.topology.LinkWeight;
import org.onlab.onos.net.topology.TopoEdge;
import org.onlab.onos.net.topology.TopoVertex;
import org.onlab.onos.net.topology.TopologyCluster;
import org.onlab.onos.net.topology.TopologyDescription;
+import java.util.HashSet;
+import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import static com.google.common.base.MoreObjects.toStringHelper;
import static org.onlab.graph.GraphPathSearch.Result;
+import static org.onlab.graph.TarjanGraphSearch.SCCResult;
import static org.onlab.onos.net.Link.Type.INDIRECT;
/**
@@ -33,25 +39,32 @@
private static final GraphPathSearch<TopoVertex, TopoEdge> DIJKSTRA =
new DijkstraGraphSearch<>();
+ private static final TarjanGraphSearch<TopoVertex, TopoEdge> TARJAN =
+ new TarjanGraphSearch<>();
private final long nanos;
private final Map<DeviceId, TopoVertex> vertexesById = Maps.newHashMap();
private final Graph<TopoVertex, TopoEdge> graph;
private final Map<DeviceId, Result<TopoVertex, TopoEdge>> results;
private final Map<ClusterId, TopologyCluster> clusters;
-// private final Multimap<ClusterId, DeviceId> clusterDevices;
-// private final Multimap<ClusterId, Link> clusterLinks;
-// private final Map<DeviceId, TopologyCluster> deviceClusters;
+ // Secondary look-up indexes
+ private Multimap<ClusterId, DeviceId> devicesByCluster;
+ private Multimap<ClusterId, Link> linksByCluster;
+ private Map<DeviceId, TopologyCluster> clustersByDevice;
+ /**
+ * Creates a topology description to carry topology vitals to the core.
+ *
+ * @param nanos time in nanos of when the topology description was created
+ * @param devices collection of devices
+ * @param links
+ */
DefaultTopologyDescription(long nanos, Iterable<Device> devices, Iterable<Link> links) {
this.nanos = nanos;
this.graph = buildGraph(devices, links);
this.results = computeDefaultPaths();
this.clusters = computeClusters();
-// this.clusterDevices = clusterDevices;
-// this.clusterLinks = clusterLinks;
-// this.deviceClusters = deviceClusters;
}
// Constructs the topology graph using the supplied devices and links.
@@ -99,9 +112,62 @@
// Computes topology SCC clusters using Tarjan algorithm.
private Map<ClusterId, TopologyCluster> computeClusters() {
Map<ClusterId, TopologyCluster> clusters = Maps.newHashMap();
+ SCCResult<TopoVertex, TopoEdge> result = TARJAN.search(graph, new NoIndirectLinksWeight());
+
+ // Extract both vertexes and edges from the results; the lists form
+ // pairs along the same index.
+ List<Set<TopoVertex>> clusterVertexes = result.clusterVertexes();
+ List<Set<TopoEdge>> clusterEdges = result.clusterEdges();
+
+ // Scan over the lists and create a cluster from the results.
+ for (int i = 0, n = result.clusterCount(); i < n; i++) {
+ Set<TopoVertex> vertexSet = clusterVertexes.get(i);
+ Set<TopoEdge> edgeSet = clusterEdges.get(i);
+
+ DefaultTopologyCluster cluster =
+ new DefaultTopologyCluster(ClusterId.clusterId(i),
+ vertexSet.size(), edgeSet.size(),
+ findRoot(vertexSet).deviceId());
+
+ findClusterDevices(vertexSet, cluster);
+ findClusterLinks(edgeSet, cluster);
+ }
return clusters;
}
+ // Scan through the set of cluster vertices and convert it to a set of
+ // device ids; register the cluster by device id as well.
+ private void findClusterDevices(Set<TopoVertex> vertexSet,
+ DefaultTopologyCluster cluster) {
+ Set<DeviceId> ids = new HashSet<>(vertexSet.size());
+ for (TopoVertex v : vertexSet) {
+ DeviceId deviceId = v.deviceId();
+ devicesByCluster.put(cluster.id(), deviceId);
+ clustersByDevice.put(deviceId, cluster);
+ }
+ }
+
+ private void findClusterLinks(Set<TopoEdge> edgeSet,
+ DefaultTopologyCluster cluster) {
+ for (TopoEdge e : edgeSet) {
+ linksByCluster.put(cluster.id(), e.link());
+ }
+ }
+
+ // Finds the vertex whose device id is the lexicographical minimum in the
+ // specified set.
+ private TopoVertex findRoot(Set<TopoVertex> vertexSet) {
+ TopoVertex minVertex = null;
+ for (TopoVertex vertex : vertexSet) {
+ if (minVertex == null ||
+ minVertex.deviceId().toString()
+ .compareTo(minVertex.deviceId().toString()) < 0) {
+ minVertex = vertex;
+ }
+ }
+ return minVertex;
+ }
+
// Fetches a vertex corresponding to the given connection point device.
private TopoVertex vertexOf(ConnectPoint connectPoint) {
DeviceId id = connectPoint.deviceId();
@@ -232,7 +298,7 @@
// Link weight for measuring link cost as hop count with indirect links
// being as expensive as traversing the entire graph to assume the worst.
- private class HopCountLinkWeight implements LinkWeight {
+ private static class HopCountLinkWeight implements LinkWeight {
private final int indirectLinkCost;
public HopCountLinkWeight(int indirectLinkCost) {
@@ -247,4 +313,12 @@
}
}
+ // Link weight for preventing traversal over indirect links.
+ private static class NoIndirectLinksWeight implements LinkWeight {
+ @Override
+ public double weight(TopoEdge edge) {
+ return edge.link().type() == INDIRECT ? -1 : 1;
+ }
+ }
+
}
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyProvider.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/SimpleTopologyProvider.java
similarity index 98%
rename from core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyProvider.java
rename to core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/SimpleTopologyProvider.java
index 0e9ea3d..7594c93 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyProvider.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/SimpleTopologyProvider.java
@@ -1,4 +1,4 @@
-package org.onlab.onos.net.trivial.impl;
+package org.onlab.onos.net.trivial.topology.provider.impl;
import org.apache.felix.scr.annotations.Activate;
import org.apache.felix.scr.annotations.Component;