Added javadocs and separated trivial implementations into distinct packages.
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java
new file mode 100644
index 0000000..87d2c47
--- /dev/null
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/topology/provider/impl/DefaultTopologyDescription.java
@@ -0,0 +1,324 @@
+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;
+
+/**
+ * Default implementation of an immutable topology data carrier.
+ */
+class DefaultTopologyDescription implements TopologyDescription {
+
+ 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;
+
+ // 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();
+ }
+
+ // Constructs the topology graph using the supplied devices and links.
+ private Graph<TopoVertex, TopoEdge> buildGraph(Iterable<Device> devices,
+ Iterable<Link> links) {
+ Graph<TopoVertex, TopoEdge> graph =
+ new AdjacencyListsGraph<>(buildVertexes(devices),
+ buildEdges(links));
+ return graph;
+ }
+
+ // Builds a set of topology vertexes from the specified list of devices
+ private Set<TopoVertex> buildVertexes(Iterable<Device> devices) {
+ Set<TopoVertex> vertexes = Sets.newHashSet();
+ for (Device device : devices) {
+ TopoVertex vertex = new TVertex(device.id());
+ vertexesById.put(vertex.deviceId(), vertex);
+ vertexes.add(vertex);
+ }
+ return vertexes;
+ }
+
+ // Builds a set of topology vertexes from the specified list of links
+ private Set<TopoEdge> buildEdges(Iterable<Link> links) {
+ Set<TopoEdge> edges = Sets.newHashSet();
+ for (Link link : links) {
+ edges.add(new TEdge(vertexOf(link.src()), vertexOf(link.dst()), link));
+ }
+ return edges;
+ }
+
+ // Computes the default shortest paths for all source/dest pairs using
+ // the multi-path Dijkstra and hop-count as path cost.
+ private Map<DeviceId, Result<TopoVertex, TopoEdge>> computeDefaultPaths() {
+ LinkWeight weight = new HopCountLinkWeight(graph.getVertexes().size());
+ Map<DeviceId, Result<TopoVertex, TopoEdge>> results = Maps.newHashMap();
+
+ // Search graph paths for each source to all destinations.
+ for (TopoVertex src : vertexesById.values()) {
+ results.put(src.deviceId(), DIJKSTRA.search(graph, src, null, weight));
+ }
+ return results;
+ }
+
+ // 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();
+ TopoVertex vertex = vertexesById.get(id);
+ if (vertex == null) {
+ // If vertex does not exist, create one and register it.
+ vertex = new TVertex(id);
+ vertexesById.put(id, vertex);
+ }
+ return vertex;
+ }
+
+ @Override
+ public long timestamp() {
+ return nanos;
+ }
+
+ @Override
+ public Graph<TopoVertex, TopoEdge> graph() {
+ return graph;
+ }
+
+ @Override
+ public Result<TopoVertex, TopoEdge> pathResults(DeviceId srcDeviceId) {
+ return results.get(srcDeviceId);
+ }
+
+ @Override
+ public Set<TopologyCluster> clusters() {
+ return ImmutableSet.copyOf(clusters.values());
+ }
+
+ @Override
+ public Set<DeviceId> clusterDevices(TopologyCluster cluster) {
+ return null; // clusterDevices.get(cluster.id());
+ }
+
+ @Override
+ public Set<Link> clusterLinks(TopologyCluster cluster) {
+ return null; // clusterLinks.get(cluster.id());
+ }
+
+ @Override
+ public TopologyCluster clusterFor(DeviceId deviceId) {
+ return null; // deviceClusters.get(deviceId);
+ }
+
+ // Implementation of the topology vertex backed by a device id
+ private static class TVertex implements TopoVertex {
+
+ private final DeviceId deviceId;
+
+ public TVertex(DeviceId deviceId) {
+ this.deviceId = deviceId;
+ }
+
+ @Override
+ public DeviceId deviceId() {
+ return deviceId;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(deviceId);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof TVertex) {
+ final TVertex other = (TVertex) obj;
+ return Objects.equals(this.deviceId, other.deviceId);
+ }
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return deviceId.toString();
+ }
+ }
+
+ // Implementation of the topology edge backed by a link
+ private class TEdge implements TopoEdge {
+ private final Link link;
+ private final TopoVertex src;
+ private final TopoVertex dst;
+
+ public TEdge(TopoVertex src, TopoVertex dst, Link link) {
+ this.src = src;
+ this.dst = dst;
+ this.link = link;
+ }
+
+ @Override
+ public Link link() {
+ return link;
+ }
+
+ @Override
+ public TopoVertex src() {
+ return src;
+ }
+
+ @Override
+ public TopoVertex dst() {
+ return dst;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(link);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof TEdge) {
+ final TEdge other = (TEdge) obj;
+ return Objects.equals(this.link, other.link);
+ }
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("src", src).add("dst", dst).toString();
+ }
+ }
+
+ // 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 static class HopCountLinkWeight implements LinkWeight {
+ private final int indirectLinkCost;
+
+ public HopCountLinkWeight(int indirectLinkCost) {
+ this.indirectLinkCost = indirectLinkCost;
+ }
+
+ @Override
+ public double weight(TopoEdge edge) {
+ // To force preference to use direct paths first, make indirect
+ // links as expensive as the linear vertex traversal.
+ return edge.link().type() == INDIRECT ? indirectLinkCost : 1;
+ }
+ }
+
+ // 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;
+ }
+ }
+
+}