Merge branch 'master' of ssh://gerrit.onlab.us:29418/onos-next
diff --git a/core/api/src/main/java/org/onlab/onos/event/AbstractEvent.java b/core/api/src/main/java/org/onlab/onos/event/AbstractEvent.java
index 93dca8e..f5c9691 100644
--- a/core/api/src/main/java/org/onlab/onos/event/AbstractEvent.java
+++ b/core/api/src/main/java/org/onlab/onos/event/AbstractEvent.java
@@ -1,5 +1,7 @@
package org.onlab.onos.event;
+import static com.google.common.base.MoreObjects.toStringHelper;
+
/**
* Base event implementation.
*/
@@ -48,4 +50,10 @@
return subject;
}
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("time", time).add("type", type())
+ .add("subject", subject()).toString();
+ }
+
}
diff --git a/core/api/src/main/java/org/onlab/onos/event/AbstractEventAccumulator.java b/core/api/src/main/java/org/onlab/onos/event/AbstractEventAccumulator.java
new file mode 100644
index 0000000..c5bfa23
--- /dev/null
+++ b/core/api/src/main/java/org/onlab/onos/event/AbstractEventAccumulator.java
@@ -0,0 +1,143 @@
+package org.onlab.onos.event;
+
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Timer;
+import java.util.TimerTask;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Base implementation of an event accumulator. It allows triggering based on
+ * event inter-arrival time threshold, maximum batch life threshold and maximum
+ * batch size.
+ */
+public abstract class AbstractEventAccumulator implements EventAccumulator {
+
+ private final Timer timer;
+ private final int maxEvents;
+ private final int maxBatchMillis;
+ private final int maxIdleMillis;
+
+ private TimerTask idleTask = new ProcessorTask();
+ private TimerTask maxTask = new ProcessorTask();
+
+ private List<Event> events = Lists.newArrayList();
+
+ /**
+ * Creates an event accumulator capable of triggering on the specified
+ * thresholds.
+ *
+ * @param timer timer to use for scheduling check-points
+ * @param maxEvents maximum number of events to accumulate before
+ * processing is triggered
+ * @param maxBatchMillis maximum number of millis allowed since the first
+ * event before processing is triggered
+ * @param maxIdleMillis maximum number millis between events before
+ * processing is triggered
+ */
+ protected AbstractEventAccumulator(Timer timer, int maxEvents,
+ int maxBatchMillis, int maxIdleMillis) {
+ this.timer = checkNotNull(timer, "Timer cannot be null");
+
+ checkArgument(maxEvents > 1, "Maximum number of events must be > 1");
+ checkArgument(maxBatchMillis > 0, "Maximum millis must be positive");
+ checkArgument(maxIdleMillis > 0, "Maximum idle millis must be positive");
+
+ this.maxEvents = maxEvents;
+ this.maxBatchMillis = maxBatchMillis;
+ this.maxIdleMillis = maxIdleMillis;
+ }
+
+ @Override
+ public void add(Event event) {
+ idleTask = cancelIfActive(idleTask);
+ events.add(event);
+
+ // Did we hit the max event threshold?
+ if (events.size() == maxEvents) {
+ maxTask = cancelIfActive(maxTask);
+ schedule(1);
+ } else {
+ // Otherwise, schedule idle task and if this is a first event
+ // also schedule the max batch age task.
+ idleTask = schedule(maxIdleMillis);
+ if (events.size() == 1) {
+ maxTask = schedule(maxBatchMillis);
+ }
+ }
+ }
+
+ // Schedules a new processor task given number of millis in the future.
+ private TimerTask schedule(int millis) {
+ TimerTask task = new ProcessorTask();
+ timer.schedule(task, millis);
+ return task;
+ }
+
+ // Cancels the specified task if it is active.
+ private TimerTask cancelIfActive(TimerTask task) {
+ if (task != null) {
+ task.cancel();
+ }
+ return task;
+ }
+
+ // Task for triggering processing of accumulated events
+ private class ProcessorTask extends TimerTask {
+ @Override
+ public void run() {
+ idleTask = cancelIfActive(idleTask);
+ maxTask = cancelIfActive(maxTask);
+ processEvents(finalizeCurrentBatch());
+ }
+ }
+
+ // Demotes and returns the current batch of events and promotes a new one.
+ private synchronized List<Event> finalizeCurrentBatch() {
+ List<Event> toBeProcessed = events;
+ events = Lists.newArrayList();
+ return toBeProcessed;
+ }
+
+ /**
+ * Returns the backing timer.
+ *
+ * @return backing timer
+ */
+ public Timer timer() {
+ return timer;
+ }
+
+ /**
+ * Returns the maximum number of events allowed to accumulate before
+ * processing is triggered.
+ *
+ * @return max number of events
+ */
+ public int maxEvents() {
+ return maxEvents;
+ }
+
+ /**
+ * Returns the maximum number of millis allowed to expire since the first
+ * event before processing is triggered.
+ *
+ * @return max number of millis a batch is allowed to last
+ */
+ public int maxBatchMillis() {
+ return maxBatchMillis;
+ }
+
+ /**
+ * Returns the maximum number of millis allowed to expire since the last
+ * event arrival before processing is triggered.
+ *
+ * @return max number of millis since the last event
+ */
+ public int maxIdleMillis() {
+ return maxIdleMillis;
+ }
+}
diff --git a/core/api/src/main/java/org/onlab/onos/event/EventAccumulator.java b/core/api/src/main/java/org/onlab/onos/event/EventAccumulator.java
new file mode 100644
index 0000000..e556afb
--- /dev/null
+++ b/core/api/src/main/java/org/onlab/onos/event/EventAccumulator.java
@@ -0,0 +1,26 @@
+package org.onlab.onos.event;
+
+import java.util.List;
+
+/**
+ * Abstraction of an accumulator capable of collecting events and at some
+ * point in time triggers processing of all previously accumulated events.
+ */
+public interface EventAccumulator {
+
+ /**
+ * Adds an event to the current batch. This operation may, or may not
+ * trigger processing of the current batch of events.
+ *
+ * @param event event to be added to the current batch
+ */
+ void add(Event event);
+
+ /**
+ * Processes the specified list of accumulated events.
+ *
+ * @param events list of accumulated events
+ */
+ void processEvents(List<Event> events);
+
+}
diff --git a/core/api/src/main/java/org/onlab/onos/net/topology/TopologyService.java b/core/api/src/main/java/org/onlab/onos/net/topology/TopologyService.java
index 36ee666..7c6be33 100644
--- a/core/api/src/main/java/org/onlab/onos/net/topology/TopologyService.java
+++ b/core/api/src/main/java/org/onlab/onos/net/topology/TopologyService.java
@@ -20,6 +20,13 @@
Topology currentTopology();
/**
+ * Indicates whether the specified topology is the latest or not.
+ * @param topology topology descriptor
+ * @return true if the topology is the most recent; false otherwise
+ */
+ boolean isLatest(Topology topology);
+
+ /**
* Returns the set of clusters in the specified topology.
*
* @param topology topology descriptor
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/impl/DefaultTopology.java
new file mode 100644
index 0000000..cb55819
--- /dev/null
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/DefaultTopology.java
@@ -0,0 +1,64 @@
+package org.onlab.onos.net.trivial.impl;
+
+import org.onlab.onos.net.AbstractModel;
+import org.onlab.onos.net.provider.ProviderId;
+import org.onlab.onos.net.topology.Topology;
+
+/**
+ * Default implementation of the topology descriptor. This carries the
+ * backing topology data.
+ */
+public class DefaultTopology extends AbstractModel implements Topology {
+
+ private final long time;
+ private final int clusterCount;
+ private final int deviceCount;
+ private final int linkCount;
+ private final int pathCount;
+
+ /**
+ * Creates a topology descriptor attributed to the specified provider.
+ *
+ * @param providerId identity of the provider
+ * @param time creation time in system nanos
+ * @param clusterCount number of clusters
+ * @param deviceCount number of devices
+ * @param linkCount number of links
+ * @param pathCount number of pre-computed paths
+ */
+ DefaultTopology(ProviderId providerId, long time, int clusterCount,
+ int deviceCount, int linkCount, int pathCount) {
+ super(providerId);
+ this.time = time;
+ this.clusterCount = clusterCount;
+ this.deviceCount = deviceCount;
+ this.linkCount = linkCount;
+ this.pathCount = pathCount;
+ }
+
+ @Override
+ public long time() {
+ return time;
+ }
+
+ @Override
+ public int clusterCount() {
+ return clusterCount;
+ }
+
+ @Override
+ public int deviceCount() {
+ return deviceCount;
+ }
+
+ @Override
+ public int linkCount() {
+ return linkCount;
+ }
+
+ @Override
+ public int pathCount() {
+ return pathCount;
+ }
+
+}
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/impl/DefaultTopologyDescription.java
index 773762a..c438146 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/impl/DefaultTopologyDescription.java
@@ -1,46 +1,117 @@
package org.onlab.onos.net.trivial.impl;
import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
+import com.google.common.collect.Maps;
+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.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.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.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.onos.net.Link.Type.INDIRECT;
+
/**
* Default implementation of an immutable topology data carrier.
*/
-public class DefaultTopologyDescription implements TopologyDescription {
+class DefaultTopologyDescription implements TopologyDescription {
+
+ private static final GraphPathSearch<TopoVertex, TopoEdge> DIJKSTRA =
+ new DijkstraGraphSearch<>();
private final long nanos;
+ private final Map<DeviceId, TopoVertex> vertexesById = Maps.newHashMap();
private final Graph<TopoVertex, TopoEdge> graph;
- private final Map<DeviceId, GraphPathSearch.Result<TopoVertex, TopoEdge>> results;
+ 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;
+// private final Multimap<ClusterId, DeviceId> clusterDevices;
+// private final Multimap<ClusterId, Link> clusterLinks;
+// private final Map<DeviceId, TopologyCluster> deviceClusters;
- public DefaultTopologyDescription(long nanos, Graph<TopoVertex, TopoEdge> graph,
- Map<DeviceId, GraphPathSearch.Result<TopoVertex, TopoEdge>> results,
- Map<ClusterId, TopologyCluster> clusters,
- Multimap<ClusterId, DeviceId> clusterDevices,
- Multimap<ClusterId, Link> clusterLinks,
- Map<DeviceId, TopologyCluster> deviceClusters) {
+
+ DefaultTopologyDescription(long nanos, Iterable<Device> devices, Iterable<Link> links) {
this.nanos = nanos;
- this.graph = graph;
- this.results = results;
- this.clusters = clusters;
- this.clusterDevices = clusterDevices;
- this.clusterLinks = clusterLinks;
- this.deviceClusters = deviceClusters;
+ 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.
+ 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();
+ return clusters;
+ }
+
+ // 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
@@ -54,7 +125,7 @@
}
@Override
- public GraphPathSearch.Result<TopoVertex, TopoEdge> pathResults(DeviceId srcDeviceId) {
+ public Result<TopoVertex, TopoEdge> pathResults(DeviceId srcDeviceId) {
return results.get(srcDeviceId);
}
@@ -75,6 +146,105 @@
@Override
public TopologyCluster clusterFor(DeviceId deviceId) {
- return deviceClusters.get(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 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;
+ }
+ }
+
}
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/impl/SimpleDeviceManager.java
index c322b70..135edd9 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/impl/SimpleDeviceManager.java
@@ -150,7 +150,8 @@
}
// Personalized device provider service issued to the supplied provider.
- private class InternalDeviceProviderService extends AbstractProviderService<DeviceProvider>
+ private class InternalDeviceProviderService
+ extends AbstractProviderService<DeviceProvider>
implements DeviceProviderService {
InternalDeviceProviderService(DeviceProvider provider) {
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/impl/SimpleDeviceStore.java
index 6d16a61..1c1502e 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/impl/SimpleDeviceStore.java
@@ -28,7 +28,8 @@
import static org.onlab.onos.net.device.DeviceEvent.Type.*;
/**
-
+ * Manages inventory of infrastructure DEVICES using trivial in-memory
+ * structures implementation.
*/
class SimpleDeviceStore {
diff --git a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleHostManager.java b/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleHostManager.java
index 05557c5..3152209 100644
--- a/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleHostManager.java
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleHostManager.java
@@ -158,7 +158,7 @@
// Posts the specified event to the local event dispatcher.
private void post(HostEvent event) {
- if (event != null && eventDispatcher != null) {
+ if (event != null) {
eventDispatcher.post(event);
}
}
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/impl/SimpleLinkManager.java
index d900c5b..1930ea1 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/impl/SimpleLinkManager.java
@@ -36,8 +36,8 @@
@Component(immediate = true)
@Service
public class SimpleLinkManager
-extends AbstractProviderRegistry<LinkProvider, LinkProviderService>
-implements LinkService, LinkAdminService, LinkProviderRegistry {
+ extends AbstractProviderRegistry<LinkProvider, LinkProviderService>
+ implements LinkService, LinkAdminService, LinkProviderRegistry {
private static final String DEVICE_ID_NULL = "Device ID cannot be null";
private static final String LINK_DESC_NULL = "Link description cannot be null";
@@ -46,7 +46,7 @@
private final Logger log = getLogger(getClass());
private final AbstractListenerRegistry<LinkEvent, LinkListener>
- listenerRegistry = new AbstractListenerRegistry<>();
+ listenerRegistry = new AbstractListenerRegistry<>();
private final SimpleLinkStore store = new SimpleLinkStore();
@@ -79,7 +79,7 @@
public Set<Link> getDeviceLinks(DeviceId deviceId) {
checkNotNull(deviceId, DEVICE_ID_NULL);
return Sets.union(store.getDeviceEgressLinks(deviceId),
- store.getDeviceIngressLinks(deviceId));
+ store.getDeviceIngressLinks(deviceId));
}
@Override
@@ -98,7 +98,7 @@
public Set<Link> getLinks(ConnectPoint connectPoint) {
checkNotNull(connectPoint, CONNECT_POINT_NULL);
return Sets.union(store.getEgressLinks(connectPoint),
- store.getIngressLinks(connectPoint));
+ store.getIngressLinks(connectPoint));
}
@Override
@@ -146,8 +146,9 @@
}
// Personalized link provider service issued to the supplied provider.
- private class InternalLinkProviderService extends AbstractProviderService<LinkProvider>
- implements LinkProviderService {
+ private class InternalLinkProviderService
+ extends AbstractProviderService<LinkProvider>
+ implements LinkProviderService {
InternalLinkProviderService(LinkProvider provider) {
super(provider);
@@ -157,27 +158,31 @@
public void linkDetected(LinkDescription linkDescription) {
checkNotNull(linkDescription, LINK_DESC_NULL);
checkValidity();
- log.debug("Link {} detected", linkDescription);
LinkEvent event = store.createOrUpdateLink(provider().id(),
- linkDescription);
- post(event);
+ linkDescription);
+ if (event != null) {
+ log.debug("Link {} detected", linkDescription);
+ post(event);
+ }
}
@Override
public void linkVanished(LinkDescription linkDescription) {
checkNotNull(linkDescription, LINK_DESC_NULL);
checkValidity();
- log.info("Link {} vanished", linkDescription);
LinkEvent event = store.removeLink(linkDescription.src(),
- linkDescription.dst());
- post(event);
+ linkDescription.dst());
+ if (event != null) {
+ log.info("Link {} vanished", linkDescription);
+ post(event);
+ }
}
@Override
public void linksVanished(ConnectPoint connectPoint) {
checkNotNull(connectPoint, "Connect point cannot be null");
checkValidity();
- log.info("Link for connection point {} vanished", connectPoint);
+ log.info("Links for connection point {} vanished", connectPoint);
removeLinks(getLinks(connectPoint));
}
@@ -185,7 +190,7 @@
public void linksVanished(DeviceId deviceId) {
checkNotNull(deviceId, DEVICE_ID_NULL);
checkValidity();
- log.info("Link for device {} vanished", deviceId);
+ log.info("Links for device {} vanished", deviceId);
removeLinks(getDeviceLinks(deviceId));
}
}
@@ -200,7 +205,7 @@
// Posts the specified event to the local event dispatcher.
private void post(LinkEvent event) {
- if (event != null && eventDispatcher != null) {
+ if (event != null) {
eventDispatcher.post(event);
}
}
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/impl/SimpleLinkStore.java
index d10c3a4..9de3d5b 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/impl/SimpleLinkStore.java
@@ -25,7 +25,7 @@
import static org.onlab.onos.net.link.LinkEvent.Type.LINK_UPDATED;
/**
- * Manages inventory of infrastructure links using trivial in-memory link
+ * Manages inventory of infrastructure links using trivial in-memory structures
* implementation.
*/
class SimpleLinkStore {
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/impl/SimpleTopologyManager.java
index 1e95598..33b2a18 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/impl/SimpleTopologyManager.java
@@ -72,25 +72,26 @@
}
@Override
- protected TopologyProviderService createProviderService(TopologyProvider provider) {
- return new InternalTopologyProviderService(provider);
+ public Topology currentTopology() {
+ return store.currentTopology();
}
@Override
- public Topology currentTopology() {
- return null;
+ public boolean isLatest(Topology topology) {
+ checkNotNull(topology, TOPOLOGY_NULL);
+ return store.isLatest(topology);
}
@Override
public Set<TopologyCluster> getClusters(Topology topology) {
checkNotNull(topology, TOPOLOGY_NULL);
- return null;
+ return store.getClusters(topology);
}
@Override
public Graph<TopoVertex, TopoEdge> getGraph(Topology topology) {
checkNotNull(topology, TOPOLOGY_NULL);
- return null;
+ return store.getGraph(topology);
}
@Override
@@ -98,7 +99,7 @@
checkNotNull(topology, TOPOLOGY_NULL);
checkNotNull(src, DEVICE_ID_NULL);
checkNotNull(dst, DEVICE_ID_NULL);
- return null;
+ return store.getPaths(topology, src, dst);
}
@Override
@@ -107,21 +108,21 @@
checkNotNull(src, DEVICE_ID_NULL);
checkNotNull(dst, DEVICE_ID_NULL);
checkNotNull(weight, "Link weight cannot be null");
- return null;
+ return store.getPaths(topology, src, dst, weight);
}
@Override
public boolean isInfrastructure(Topology topology, ConnectPoint connectPoint) {
checkNotNull(topology, TOPOLOGY_NULL);
checkNotNull(connectPoint, CONNECTION_POINT_NULL);
- return false;
+ return store.isInfrastructure(topology, connectPoint);
}
@Override
public boolean isInBroadcastTree(Topology topology, ConnectPoint connectPoint) {
checkNotNull(topology, TOPOLOGY_NULL);
checkNotNull(connectPoint, CONNECTION_POINT_NULL);
- return false;
+ return store.isInBroadcastTree(topology, connectPoint);
}
@Override
@@ -135,6 +136,11 @@
}
// Personalized host provider service issued to the supplied provider.
+ @Override
+ protected TopologyProviderService createProviderService(TopologyProvider provider) {
+ return new InternalTopologyProviderService(provider);
+ }
+
private class InternalTopologyProviderService
extends AbstractProviderService<TopologyProvider>
implements TopologyProviderService {
@@ -147,8 +153,15 @@
public void topologyChanged(TopologyDescription topoDescription,
List<Event> reasons) {
checkNotNull(topoDescription, "Topology description cannot be null");
- log.info("Topology changed due to: {}",
+
+ log.info("Topology changed due to: {}", // to be removed soon
reasons == null ? "initial compute" : reasons);
+ TopologyEvent event = store.updateTopology(topoDescription, reasons);
+ if (event != null) {
+ log.info("Topology changed due to: {}",
+ reasons == null ? "initial compute" : reasons);
+ eventDispatcher.post(event);
+ }
}
}
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/impl/SimpleTopologyProvider.java
new file mode 100644
index 0000000..0e9ea3d
--- /dev/null
+++ b/core/trivial/src/main/java/org/onlab/onos/net/trivial/impl/SimpleTopologyProvider.java
@@ -0,0 +1,177 @@
+package org.onlab.onos.net.trivial.impl;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Reference;
+import org.apache.felix.scr.annotations.ReferenceCardinality;
+import org.onlab.onos.event.AbstractEventAccumulator;
+import org.onlab.onos.event.Event;
+import org.onlab.onos.event.EventAccumulator;
+import org.onlab.onos.net.device.DeviceEvent;
+import org.onlab.onos.net.device.DeviceListener;
+import org.onlab.onos.net.device.DeviceService;
+import org.onlab.onos.net.link.LinkEvent;
+import org.onlab.onos.net.link.LinkListener;
+import org.onlab.onos.net.link.LinkService;
+import org.onlab.onos.net.provider.AbstractProvider;
+import org.onlab.onos.net.provider.ProviderId;
+import org.onlab.onos.net.topology.TopologyDescription;
+import org.onlab.onos.net.topology.TopologyProvider;
+import org.onlab.onos.net.topology.TopologyProviderRegistry;
+import org.onlab.onos.net.topology.TopologyProviderService;
+import org.slf4j.Logger;
+
+import java.util.List;
+import java.util.Timer;
+import java.util.concurrent.ExecutorService;
+
+import static java.util.concurrent.Executors.newFixedThreadPool;
+import static org.onlab.onos.net.device.DeviceEvent.Type.*;
+import static org.onlab.util.Tools.namedThreads;
+import static org.slf4j.LoggerFactory.getLogger;
+
+/**
+ * Simple implementation of a network topology provider/computor.
+ */
+@Component(immediate = true)
+public class SimpleTopologyProvider extends AbstractProvider
+ implements TopologyProvider {
+
+ // TODO: make these configurable
+ private static final int MAX_EVENTS = 100;
+ private static final int MAX_IDLE_MS = 50;
+ private static final int MAX_BATCH_MS = 200;
+ private static final int MAX_THREADS = 8;
+
+ // FIXME: Replace with a system-wide timer instance
+ private static final Timer TIMER = new Timer();
+
+ private final Logger log = getLogger(getClass());
+
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected TopologyProviderRegistry providerRegistry;
+
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected DeviceService deviceService;
+
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected LinkService linkService;
+
+ private volatile boolean isStarted = false;
+
+ private TopologyProviderService providerService;
+ private DeviceListener deviceListener = new InnerDeviceListener();
+ private LinkListener linkListener = new InnerLinkListener();
+
+ private EventAccumulator accumulator;
+ private ExecutorService executor;
+
+ /**
+ * Creates a provider with the supplier identifier.
+ */
+ public SimpleTopologyProvider() {
+ super(new ProviderId("org.onlab.onos.provider.topology"));
+ }
+
+ @Activate
+ public synchronized void activate() {
+ executor = newFixedThreadPool(MAX_THREADS, namedThreads("topo-compute-%d"));
+ accumulator = new TopologyChangeAccumulator();
+
+ providerService = providerRegistry.register(this);
+ deviceService.addListener(deviceListener);
+ linkService.addListener(linkListener);
+
+ isStarted = true;
+ triggerTopologyBuild(null);
+ log.info("Started");
+ }
+
+ @Deactivate
+ public synchronized void deactivate() {
+ deviceService.removeListener(deviceListener);
+ linkService.removeListener(linkListener);
+ providerRegistry.unregister(this);
+ providerService = null;
+
+ executor.shutdownNow();
+ executor = null;
+
+ isStarted = false;
+ log.info("Stopped");
+ }
+
+ /**
+ * Triggers assembly of topology data citing the specified events as the
+ * reason.
+ *
+ * @param reasons events which triggered the topology change
+ */
+ private void triggerTopologyBuild(List<Event> reasons) {
+ executor.execute(new TopologyBuilderTask(reasons));
+ }
+
+ // Builds the topology using the latest device and link information
+ // and citing the specified events as reasons for the change.
+ private void buildTopology(List<Event> reasons) {
+ log.info("YO! Computing topology");
+ if (isStarted) {
+ TopologyDescription desc =
+ new DefaultTopologyDescription(System.nanoTime(),
+ deviceService.getDevices(),
+ linkService.getLinks());
+ providerService.topologyChanged(desc, reasons);
+ }
+ }
+
+ // Callback for device events
+ private class InnerDeviceListener implements DeviceListener {
+ @Override
+ public void event(DeviceEvent event) {
+ DeviceEvent.Type type = event.type();
+ if (type == DEVICE_ADDED || type == DEVICE_REMOVED ||
+ type == DEVICE_AVAILABILITY_CHANGED) {
+ accumulator.add(event);
+ }
+ }
+ }
+
+ // Callback for link events
+ private class InnerLinkListener implements LinkListener {
+ @Override
+ public void event(LinkEvent event) {
+ accumulator.add(event);
+ }
+ }
+
+ // Event accumulator for paced triggering of topology assembly.
+ private class TopologyChangeAccumulator
+ extends AbstractEventAccumulator implements EventAccumulator {
+
+ TopologyChangeAccumulator() {
+ super(TIMER, MAX_EVENTS, MAX_BATCH_MS, MAX_IDLE_MS);
+ }
+
+ @Override
+ public void processEvents(List<Event> events) {
+ triggerTopologyBuild(events);
+ }
+
+ }
+
+ // Task for building topology data in a separate thread.
+ private class TopologyBuilderTask implements Runnable {
+ private final List<Event> reasons;
+
+ public TopologyBuilderTask(List<Event> reasons) {
+ this.reasons = reasons;
+ }
+
+ @Override
+ public void run() {
+ buildTopology(reasons);
+ }
+ }
+
+}
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/impl/SimpleTopologyStore.java
index 1a54cad..7944a53 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/impl/SimpleTopologyStore.java
@@ -1,8 +1,127 @@
package org.onlab.onos.net.trivial.impl;
+import org.onlab.graph.Graph;
+import org.onlab.onos.event.Event;
+import org.onlab.onos.net.ConnectPoint;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.net.Path;
+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.Topology;
+import org.onlab.onos.net.topology.TopologyCluster;
+import org.onlab.onos.net.topology.TopologyDescription;
+import org.onlab.onos.net.topology.TopologyEvent;
+
+import java.util.List;
+import java.util.Set;
+
/**
* Manages inventory of topology snapshots using trivial in-memory
- * implementation.
+ * structures implementation.
*/
-public class SimpleTopologyStore {
+class SimpleTopologyStore {
+
+ private volatile DefaultTopology current;
+
+ /**
+ * Returns the current topology snapshot.
+ *
+ * @return current topology descriptor
+ */
+ Topology currentTopology() {
+ return current;
+ }
+
+ /**
+ * Indicates whether the topology is the latest.
+ *
+ * @param topology topology descriptor
+ * @return true if topology is the most recent one
+ */
+ boolean isLatest(Topology topology) {
+ // Topology is current only if it is the same as our current topology
+ return topology == current;
+ }
+
+ /**
+ * Returns the set of topology SCC clusters.
+ *
+ * @param topology topology descriptor
+ * @return set of clusters
+ */
+ Set<TopologyCluster> getClusters(Topology topology) {
+ return null;
+ }
+
+ /**
+ * Returns the immutable graph view of the current topology.
+ *
+ * @param topology topology descriptor
+ * @return graph view
+ */
+ Graph<TopoVertex, TopoEdge> getGraph(Topology topology) {
+ return null;
+ }
+
+ /**
+ * Returns the set of pre-computed shortest paths between src and dest.
+ *
+ * @param topology topology descriptor
+ * @param src source device
+ * @param dst destination device
+ * @return set of shortest paths
+ */
+ Set<Path> getPaths(Topology topology, DeviceId src, DeviceId dst) {
+ return null;
+ }
+
+ /**
+ * Computes and returns the set of shortest paths between src and dest.
+ *
+ * @param topology topology descriptor
+ * @param src source device
+ * @param dst destination device
+ * @param weight link weight function
+ * @return set of shortest paths
+ */
+ Set<Path> getPaths(Topology topology, DeviceId src, DeviceId dst,
+ LinkWeight weight) {
+ return null;
+ }
+
+ /**
+ * Indicates whether the given connect point is part of the network fabric.
+ *
+ * @param topology topology descriptor
+ * @param connectPoint connection point
+ * @return true if infrastructure; false otherwise
+ */
+ boolean isInfrastructure(Topology topology, ConnectPoint connectPoint) {
+ return false;
+ }
+
+ /**
+ * Indicates whether the given connect point is part of the broadcast tree.
+ *
+ * @param topology topology descriptor
+ * @param connectPoint connection point
+ * @return true if in broadcast tree; false otherwise
+ */
+ boolean isInBroadcastTree(Topology topology, ConnectPoint connectPoint) {
+ return false;
+ }
+
+ /**
+ * Generates a new topology snapshot from the specified description.
+ *
+ * @param topoDescription topology description
+ * @param reasons list of events that triggered the update
+ * @return topology update event or null if the description is old
+ */
+ TopologyEvent updateTopology(TopologyDescription topoDescription,
+ List<Event> reasons) {
+ return null;
+ }
+
}
diff --git a/core/trivial/src/test/java/org/onlab/onos/event/impl/SimpleEventDispatcherTest.java b/core/trivial/src/test/java/org/onlab/onos/event/impl/SimpleEventDispatcherTest.java
new file mode 100644
index 0000000..88ba165
--- /dev/null
+++ b/core/trivial/src/test/java/org/onlab/onos/event/impl/SimpleEventDispatcherTest.java
@@ -0,0 +1,117 @@
+package org.onlab.onos.event.impl;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.onlab.onos.event.AbstractEvent;
+import org.onlab.onos.event.EventSink;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.TimeUnit;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the even dispatcher mechanism.
+ */
+public class SimpleEventDispatcherTest {
+
+ private final SimpleEventDispatcher dispatcher = new SimpleEventDispatcher();
+ private final PrickleSink prickleSink = new PrickleSink();
+ private final GooSink gooSink = new GooSink();
+
+ @Before
+ public void setUp() {
+ dispatcher.activate();
+ dispatcher.addSink(Prickle.class, prickleSink);
+ dispatcher.addSink(Goo.class, gooSink);
+ }
+
+ @After
+ public void tearDown() {
+ dispatcher.removeSink(Goo.class);
+ dispatcher.removeSink(Prickle.class);
+ dispatcher.deactivate();
+ }
+
+ @Test
+ public void post() throws Exception {
+ prickleSink.latch = new CountDownLatch(1);
+ dispatcher.post(new Prickle("yo"));
+ prickleSink.latch.await(100, TimeUnit.MILLISECONDS);
+ validate(prickleSink, "yo");
+ validate(gooSink);
+ }
+
+ @Test
+ public void postEventWithBadSink() throws Exception {
+ gooSink.latch = new CountDownLatch(1);
+ dispatcher.post(new Goo("boom"));
+ gooSink.latch.await(100, TimeUnit.MILLISECONDS);
+ validate(gooSink, "boom");
+ validate(prickleSink);
+ }
+
+ @Test
+ public void postEventWithNoSink() throws Exception {
+ dispatcher.post(new Thing("boom"));
+ validate(gooSink);
+ validate(prickleSink);
+ }
+
+ private void validate(Sink sink, String... strings) {
+ int i = 0;
+ assertEquals("incorrect event count", strings.length, sink.subjects.size());
+ for (String string : strings) {
+ assertEquals("incorrect event", string, sink.subjects.get(i++));
+ }
+ }
+
+ private enum Type { FOO };
+
+ private static class Thing extends AbstractEvent<Type, String> {
+ protected Thing(String subject) {
+ super(Type.FOO, subject);
+ }
+ }
+
+ private static class Prickle extends Thing {
+ protected Prickle(String subject) {
+ super(subject);
+ }
+ }
+
+ private static class Goo extends Thing {
+ protected Goo(String subject) {
+ super(subject);
+ }
+ }
+
+ private static class Sink {
+ final List<String> subjects = new ArrayList<>();
+ CountDownLatch latch;
+
+ protected void process(String subject) {
+ subjects.add(subject);
+ latch.countDown();
+ }
+ }
+
+ private static class PrickleSink extends Sink implements EventSink<Prickle> {
+ @Override
+ public void process(Prickle event) {
+ process(event.subject());
+ }
+ }
+
+ private static class GooSink extends Sink implements EventSink<Goo> {
+ @Override
+ public void process(Goo event) {
+ process(event.subject());
+ throw new IllegalStateException("BOOM!");
+ }
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java b/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java
index 07dc70b..a0d569b 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java
@@ -15,7 +15,8 @@
* @param <V> vertex type
* @param <E> edge type
*/
-public class AdjacencyListsGraph<V extends Vertex, E extends Edge<V>> implements Graph<V, E> {
+public class AdjacencyListsGraph<V extends Vertex, E extends Edge<V>>
+ implements Graph<V, E> {
private final Set<V> vertexes;
private final Set<E> edges;
diff --git a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
new file mode 100644
index 0000000..ebd451f
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
@@ -0,0 +1,195 @@
+package org.onlab.graph;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Tarjan algorithm for searching a graph and producing results describing
+ * the graph SCC (strongly-connected components).
+ */
+public class TarjanGraphSearch<V extends Vertex, E extends Edge<V>>
+ implements GraphSearch<V, E> {
+
+ /**
+ * {@inheritDoc}
+ * <p/>
+ * This implementation produces results augmented with information on
+ * SCCs within the graph.
+ * <p/>
+ * To prevent traversal of an edge, the {@link EdgeWeight#weight} should
+ * return a negative value as an edge weight.
+ */
+ @Override
+ public SCCResult<V, E> search(Graph<V, E> graph, EdgeWeight<V, E> weight) {
+ SCCResult<V, E> result = new SCCResult<>(graph);
+ for (V vertex : graph.getVertexes()) {
+ VertexData data = result.data(vertex);
+ if (data == null) {
+ connect(graph, vertex, weight, result);
+ }
+ }
+ return result.build();
+ }
+
+ /**
+ * Scans the specified graph, using recursion, and produces SCC results.
+ *
+ * @param graph graph to search
+ * @param vertex current vertex to scan and connect
+ * @param weight optional edge weight
+ * @param result graph search result
+ * @return augmentation vertexData for the current vertex
+ */
+ private VertexData<V> connect(Graph<V, E> graph, V vertex,
+ EdgeWeight<V, E> weight,
+ SCCResult<V, E> result) {
+ VertexData<V> data = result.addData(vertex);
+
+ // Scan through all egress edges of the current vertex.
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ V nextVertex = edge.dst();
+
+ // If edge weight is negative, skip it.
+ if (weight != null && weight.weight(edge) < 0) {
+ continue;
+ }
+
+ // Attempt to get the augmentation vertexData for the next vertex.
+ VertexData<V> nextData = result.data(nextVertex);
+ if (nextData == null) {
+ // Next vertex has not been visited yet, so do this now.
+ nextData = connect(graph, nextVertex, weight, result);
+ data.lowLink = Math.min(data.lowLink, nextData.lowLink);
+
+ } else if (result.visited(nextData)) {
+ // Next vertex has been visited, which means it is in the
+ // same cluster as the current vertex.
+ data.lowLink = Math.min(data.lowLink, nextData.index);
+ }
+ }
+
+ if (data.lowLink == data.index) {
+ result.addCluster(data);
+ }
+ return data;
+ }
+
+ /**
+ * Graph search result augmented with SCC vertexData.
+ */
+ public static final class SCCResult<V extends Vertex, E extends Edge<V>>
+ implements Result {
+
+ private final Graph<V, E> graph;
+ private List<Set<V>> clusterVertexes = new ArrayList<>();
+ private List<Set<E>> clusterEdges = new ArrayList<>();
+
+ private int index = 0;
+ private final Map<V, VertexData<V>> vertexData = new HashMap<>();
+ private final List<VertexData<V>> visited = new ArrayList<>();
+
+ private SCCResult(Graph<V, E> graph) {
+ this.graph = graph;
+ }
+
+ /**
+ * Returns the number of SCC clusters in the graph.
+ *
+ * @return number of clusters
+ */
+ public int clusterCount() {
+ return clusterEdges.size();
+ }
+
+ /**
+ * Returns the list of strongly connected vertex clusters.
+ *
+ * @return list of strongly connected vertex sets
+ */
+ public List<Set<V>> clusterVertexes() {
+ return clusterVertexes;
+ }
+
+ /**
+ * Returns the list of edges linking strongly connected vertex clusters.
+ *
+ * @return list of strongly connected edge sets
+ */
+ public List<Set<E>> clusterEdges() {
+ return clusterEdges;
+ }
+
+ // Gets the augmentation vertexData for the specified vertex
+ private VertexData<V> data(V vertex) {
+ return vertexData.get(vertex);
+ }
+
+ // Adds augmentation vertexData for the specified vertex
+ private VertexData<V> addData(V vertex) {
+ VertexData<V> d = new VertexData<>(vertex, index);
+ vertexData.put(vertex, d);
+ visited.add(0, d);
+ index++;
+ return d;
+ }
+
+ // Indicates whether the given vertex has been visited
+ private boolean visited(VertexData data) {
+ return visited.contains(data);
+ }
+
+ // Adds a new cluster for the specified vertex
+ private void addCluster(VertexData data) {
+ Set<V> vertexes = findClusterVertices(data);
+ clusterVertexes.add(vertexes);
+ clusterEdges.add(findClusterEdges(vertexes));
+ }
+
+ private Set<V> findClusterVertices(VertexData data) {
+ VertexData<V> nextVertexData;
+ Set<V> vertexes = new HashSet<>();
+ do {
+ nextVertexData = visited.remove(0);
+ vertexes.add(nextVertexData.vertex);
+ } while (data != nextVertexData);
+ return Collections.unmodifiableSet(vertexes);
+ }
+
+ private Set<E> findClusterEdges(Set<V> vertexes) {
+ Set<E> edges = new HashSet<>();
+ for (V vertex : vertexes) {
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ if (vertexes.contains((edge.dst()))) {
+ edges.add(edge);
+ }
+ }
+ }
+ return Collections.unmodifiableSet(edges);
+ }
+
+ public SCCResult<V, E> build() {
+ clusterVertexes = Collections.unmodifiableList(clusterVertexes);
+ clusterEdges = Collections.unmodifiableList(clusterEdges);
+ return this;
+ }
+ }
+
+ // Augments the vertex to assist in determining SCC clusters.
+ private static final class VertexData<V extends Vertex> {
+ final V vertex;
+ int index;
+ int lowLink;
+
+ private VertexData(V vertex, int index) {
+ this.vertex = vertex;
+ this.index = index;
+ this.lowLink = index;
+ }
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
index 4ee9006..96985b5 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -31,17 +31,17 @@
@Test
public void searchGraphWithNegativeCycles() {
- Set<TestVertex> vertexes = new HashSet<>(vertices());
+ Set<TestVertex> vertexes = new HashSet<>(vertexes());
vertexes.add(Z);
Set<TestEdge> edges = new HashSet<>(edges());
edges.add(new TestEdge(G, Z, 1.0));
edges.add(new TestEdge(Z, G, -2.0));
- g = new AdjacencyListsGraph<>(vertexes, edges);
+ graph = new AdjacencyListsGraph<>(vertexes, edges);
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -50,10 +50,10 @@
assertEquals("incorrect path length", 5, p.edges().size());
assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
- paths = search.search(g, A, G, weight).paths();
+ paths = search.search(graph, A, G, weight).paths();
assertEquals("incorrect paths count", 0, paths.size());
- paths = search.search(g, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 6, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
index f9c752d..d99e485 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -29,10 +29,10 @@
// Executes the default test
protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -41,7 +41,7 @@
assertEquals("incorrect path length", pathLength, p.edges().size());
assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
- paths = search.search(g, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
index 8881e84..944919b 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -33,11 +33,11 @@
protected void executeDefaultTest(int minLength, int maxLength,
double minCost, double maxCost) {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(g, A, H, weight);
+ search.search(graph, A, H, weight);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect path count", 1, paths.size());
@@ -57,12 +57,12 @@
}
public void executeBroadSearch() {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
// Perform narrow path search to a specific destination.
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(g, A, null, weight);
+ search.search(graph, A, null, weight);
assertEquals("incorrect paths count", 7, result.paths().size());
int[] types = new int[]{0, 0, 0, 0};
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index 1731440..840eddd 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -32,22 +32,22 @@
@Test
public void noPath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, A, 1),
- new TestEdge(C, D, 1),
- new TestEdge(D, C, 1)));
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, A, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, C, 1)));
GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, B, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
- paths = gs.search(g, A, D, weight).paths();
+ paths = gs.search(graph, A, D, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 0, paths.size());
- paths = gs.search(g, A, null, weight).paths();
+ paths = gs.search(graph, A, null, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
@@ -55,40 +55,40 @@
@Test
public void simpleMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(A, C, 1),
- new TestEdge(B, D, 1),
- new TestEdge(C, D, 1)));
- executeSearch(graphSearch(), g, A, D, weight, 2, 2.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(B, D, 1),
+ new TestEdge(C, D, 1)));
+ executeSearch(graphSearch(), graph, A, D, weight, 2, 2.0);
}
@Test
public void denseMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
- of(new TestEdge(A, B, 1),
- new TestEdge(A, C, 1),
- new TestEdge(B, D, 1),
- new TestEdge(C, D, 1),
- new TestEdge(D, E, 1),
- new TestEdge(D, F, 1),
- new TestEdge(E, G, 1),
- new TestEdge(F, G, 1),
- new TestEdge(A, G, 4)));
- executeSearch(graphSearch(), g, A, G, weight, 5, 4.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(B, D, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(D, F, 1),
+ new TestEdge(E, G, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(A, G, 4)));
+ executeSearch(graphSearch(), graph, A, G, weight, 5, 4.0);
}
@Test
public void dualEdgeMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
- of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
- new TestEdge(B, D, 2), new TestEdge(B, C, 1),
- new TestEdge(B, E, 4), new TestEdge(C, E, 1),
- new TestEdge(D, H, 5), new TestEdge(D, E, 1),
- new TestEdge(E, F, 1), new TestEdge(F, D, 1),
- new TestEdge(F, G, 1), new TestEdge(F, H, 1),
- new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
- executeSearch(graphSearch(), g, A, E, weight, 3, 3.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
+ of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
+ new TestEdge(B, D, 2), new TestEdge(B, C, 1),
+ new TestEdge(B, E, 4), new TestEdge(C, E, 1),
+ new TestEdge(D, H, 5), new TestEdge(D, E, 1),
+ new TestEdge(E, F, 1), new TestEdge(F, D, 1),
+ new TestEdge(F, G, 1), new TestEdge(F, H, 1),
+ new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
+ executeSearch(graphSearch(), graph, A, E, weight, 3, 3.0);
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
index 44b1137..5c930c4 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -19,7 +19,7 @@
static final TestVertex H = new TestVertex("H");
static final TestVertex Z = new TestVertex("Z");
- protected Graph<TestVertex, TestEdge> g;
+ protected Graph<TestVertex, TestEdge> graph;
protected EdgeWeight<TestVertex, TestEdge> weight =
new EdgeWeight<TestVertex, TestEdge>() {
@@ -35,7 +35,7 @@
}
}
- protected Set<TestVertex> vertices() {
+ protected Set<TestVertex> vertexes() {
return of(A, B, C, D, E, F, G, H);
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
new file mode 100644
index 0000000..9bf3acf
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
@@ -0,0 +1,110 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.TarjanGraphSearch.SCCResult;
+
+/**
+ * Tarjan graph search tests.
+ */
+public class TarjanGraphSearchTest extends GraphTest {
+
+ private void validate(SCCResult<TestVertex, TestEdge> result, int cc) {
+ System.out.println("Cluster count: " + result.clusterVertexes().size());
+ System.out.println("Clusters: " + result.clusterVertexes());
+ assertEquals("incorrect cluster count", cc, result.clusterCount());
+ }
+
+ private void validate(SCCResult<TestVertex, TestEdge> result,
+ int i, int vc, int ec) {
+ assertEquals("incorrect cluster count", vc, result.clusterVertexes().get(i).size());
+ assertEquals("incorrect edge count", ec, result.clusterEdges().get(i).size());
+ }
+
+ @Test
+ public void basic() {
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 6);
+ }
+
+ @Test
+ public void singleCluster() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, A, 1)));
+
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 1);
+ validate(result, 0, 8, 8);
+ }
+
+ @Test
+ public void twoUnconnectedCluster() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1)));
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+ @Test
+ public void twoWeaklyConnectedClusters() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1),
+ new TestEdge(B, E, 1)));
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+ @Test
+ public void twoClustersConnectedWithIgnoredEdges() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1),
+ new TestEdge(B, E, -1),
+ new TestEdge(E, B, -1)));
+
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, weight);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+}