commit 2398d960b9328bdc69bdc50e1539f0627e11e407
author Andrey Komarov <andrey.komarov@NetCracker.com> Mon Sep 26 15:11:23 2016 +0300
committer Yuta HIGUCHI <y-higuchi@onlab.us> Mon Jan 23 17:27:20 2017 +0000
tree c12a3eb61e4d581592fae64a49c4b1fe41492096
parent 71a0fa4468d06e9902e735314981b2485373b946

Vector cost proposed to TST on 2016-07-13

First part implemented: weight interface introduced and integrated, default weight implementation added.

Change-Id: Ia46f1b44139069aa171a3c13faf168351bd7cc56

utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java

diff --git a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
index 94cb609..ad07d4b 100644
--- a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
@@ -37,17 +37,17 @@
      * SCCs within the graph.
      * </p>
      * <p>
-     * To prevent traversal of an edge, the {@link EdgeWeight#weight} should
-     * return a negative value as an edge weight.
+     * To prevent traversal of an edge, the {@link EdgeWeigher#weight} should
+     * return a negative value as an edge weigher.
      * </p>
      */
     @Override
-    public SccResult<V, E> search(Graph<V, E> graph, EdgeWeight<V, E> weight) {
+    public SccResult<V, E> search(Graph<V, E> graph, EdgeWeigher<V, E> weigher) {
         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);
+                connect(graph, vertex, weigher, result);
             }
         }
         return result.build();
@@ -56,14 +56,14 @@
     /**
      * 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
+     * @param graph   graph to search
+     * @param vertex  current vertex to scan and connect
+     * @param weigher optional edge weigher
+     * @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,
+                                  EdgeWeigher<V, E> weigher,
                                   SccResult<V, E> result) {
         VertexData<V> data = result.addData(vertex);
 
@@ -71,8 +71,8 @@
         for (E edge : graph.getEdgesFrom(vertex)) {
             V nextVertex = edge.dst();
 
-            // If edge weight is negative, skip it.
-            if (weight != null && weight.weight(edge) < 0) {
+            // If edge is not viable, skip it.
+            if (weigher != null && !weigher.weight(edge).isViable()) {
                 continue;
             }
 
@@ -80,7 +80,7 @@
             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);
+                nextData = connect(graph, nextVertex, weigher, result);
                 data.lowLink = Math.min(data.lowLink, nextData.lowLink);
 
             } else if (result.visited(nextData)) {