diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index 01f17efa..95f99dc 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -33,27 +33,6 @@
 public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
         implements GraphPathSearch<V, E> {
 
-    private double samenessThreshold = Double.MIN_VALUE;
-
-    /**
-     * Sets a new sameness threshold for comparing cost values; default is
-     * is {@link Double#MIN_VALUE}.
-     *
-     * @param threshold fractional double value
-     */
-    public void setSamenessThreshold(double threshold) {
-        samenessThreshold = threshold;
-    }
-
-    /**
-     * Returns the current sameness threshold for comparing cost values.
-     *
-     * @return current threshold
-     */
-    public double samenessThreshold() {
-        return samenessThreshold;
-    }
-
     /**
      * Default path search result that uses the DefaultPath to convey paths
      * in a graph.
@@ -63,7 +42,7 @@
         private final V src;
         private final V dst;
         protected final Set<Path<V, E>> paths = new HashSet<>();
-        protected final Map<V, Double> costs = new HashMap<>();
+        protected final Map<V, Weight> costs = new HashMap<>();
         protected final Map<V, Set<E>> parents = new HashMap<>();
         protected final int maxPaths;
 
@@ -108,7 +87,7 @@
         }
 
         @Override
-        public Map<V, Double> costs() {
+        public Map<V, Weight> costs() {
             return costs;
         }
 
@@ -124,18 +103,20 @@
          * @return true if the vertex has cost already
          */
         boolean hasCost(V v) {
-            return costs.get(v) != null;
+            return costs.containsKey(v);
         }
 
         /**
          * Returns the current cost to reach the specified vertex.
+         * If the vertex has not been accessed yet, it has no cost
+         * associated and null will be returned.
          *
          * @param v vertex to reach
-         * @return cost to reach the vertex
+         * @return weight cost to reach the vertex if already accessed;
+         *         null otherwise
          */
-        double cost(V v) {
-            Double c = costs.get(v);
-            return c == null ? Double.MAX_VALUE : c;
+        Weight cost(V v) {
+            return costs.get(v);
         }
 
         /**
@@ -151,7 +132,7 @@
          *                added to the previously accrued edges as they yield
          *                the same cost
          */
-        void updateVertex(V vertex, E edge, double cost, boolean replace) {
+        void updateVertex(V vertex, E edge, Weight cost, boolean replace) {
             costs.put(vertex, cost);
             if (edge != null) {
                 Set<E> edges = parents.get(vertex);
@@ -187,22 +168,27 @@
          * @param forbidNegatives if true negative values will forbid the link
          * @return true if the edge was relaxed; false otherwise
          */
-        boolean relaxEdge(E edge, double cost, EdgeWeight<V, E> ew,
+        boolean relaxEdge(E edge, Weight cost, EdgeWeigher<V, E> ew,
                           boolean... forbidNegatives) {
             V v = edge.dst();
-            double oldCost = cost(v);
-            double hopCost = ew == null ? 1.0 : ew.weight(edge);
-            if (hopCost < 0 && forbidNegatives.length == 1 && forbidNegatives[0]) {
+
+            Weight hopCost = ew.weight(edge);
+            if ((!hopCost.isViable()) ||
+                    (hopCost.isNegative() && forbidNegatives.length == 1 && forbidNegatives[0])) {
                 return false;
             }
+            Weight newCost = cost.merge(hopCost);
 
-            double newCost = cost + hopCost;
-            boolean relaxed = newCost < oldCost;
-            boolean same = Math.abs(newCost - oldCost) <= samenessThreshold;
-            if (same || relaxed) {
-                updateVertex(v, edge, newCost, !same);
+            int compareResult = -1;
+            if (hasCost(v)) {
+                Weight oldCost = cost(v);
+                compareResult = newCost.compareTo(oldCost);
             }
-            return relaxed;
+
+            if (compareResult <= 0) {
+                updateVertex(v, edge, newCost, compareResult < 0);
+            }
+            return compareResult < 0;
         }
 
         /**
@@ -328,4 +314,16 @@
                       "Destination not in graph");
     }
 
+    @Override
+    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
+        checkArguments(graph, src, dst);
+
+        return internalSearch(graph, src, dst,
+                weigher != null ? weigher : new DefaultEdgeWeigher<>(),
+                maxPaths);
+    }
+
+    protected abstract Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                                          EdgeWeigher<V, E> weigher, int maxPaths);
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
index 88aca6b..9bd6c63 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
@@ -23,22 +23,21 @@
         extends AbstractGraphPathSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                               EdgeWeight<V, E> weight, int maxPaths) {
-        checkArguments(graph, src, dst);
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
 
         // Prepare the graph search result.
         DefaultResult result = new DefaultResult(src, dst, maxPaths);
 
         // The source vertex has cost 0, of course.
-        result.updateVertex(src, null, 0.0, true);
+        result.updateVertex(src, null, weigher.getInitialWeight(), true);
 
         int max = graph.getVertexes().size() - 1;
         for (int i = 0; i < max; i++) {
             // Relax, if possible, all egress edges of the current vertex.
             for (E edge : graph.getEdges()) {
                 if (result.hasCost(edge.src())) {
-                    result.relaxEdge(edge, result.cost(edge.src()), weight);
+                    result.relaxEdge(edge, result.cost(edge.src()), weigher);
                 }
             }
         }
@@ -46,7 +45,7 @@
         // Remove any vertexes reached by traversing edges with negative weights.
         for (E edge : graph.getEdges()) {
             if (result.hasCost(edge.src())) {
-                if (result.relaxEdge(edge, result.cost(edge.src()), weight)) {
+                if (result.relaxEdge(edge, result.cost(edge.src()), weigher)) {
                     result.removeVertex(edge.dst());
                 }
             }
@@ -56,5 +55,4 @@
         result.buildPaths();
         return result;
     }
-
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
index 48bfe03..c5b0f4f 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -25,16 +25,15 @@
         extends AbstractGraphPathSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                               EdgeWeight<V, E> weight, int maxPaths) {
-        checkArguments(graph, src, dst);
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
 
         // Prepare the graph result.
         DefaultResult result = new DefaultResult(src, dst, maxPaths);
 
         // Setup the starting frontier with the source as the sole vertex.
         Set<V> frontier = new HashSet<>();
-        result.updateVertex(src, null, 0.0, true);
+        result.updateVertex(src, null, weigher.getInitialWeight(), true);
         frontier.add(src);
 
         boolean reachedEnd = false;
@@ -44,14 +43,14 @@
 
             // Visit all vertexes in the current frontier.
             for (V vertex : frontier) {
-                double cost = result.cost(vertex);
+                Weight cost = result.cost(vertex);
 
                 // Visit all egress edges of the current frontier vertex.
                 for (E edge : graph.getEdgesFrom(vertex)) {
                     V nextVertex = edge.dst();
                     if (!result.hasCost(nextVertex)) {
                         // If this vertex has not been visited yet, update it.
-                        double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+                        Weight newCost = cost.merge(weigher.weight(edge));
                         result.updateVertex(nextVertex, edge, newCost, true);
                         // If we have reached our intended destination, bail.
                         if (nextVertex.equals(dst)) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java b/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java
new file mode 100644
index 0000000..e280391
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onlab.graph;
+
+/**
+ * Default weigher returns identical weight for every graph edge. Basically it
+ * is a hop count weigher.
+ * Produces weights of {@link ScalarWeight} type.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public class DefaultEdgeWeigher<V extends Vertex, E extends Edge<V>>
+        implements EdgeWeigher<V, E> {
+
+    /**
+     * Common weight value for any link.
+     */
+    protected static final double HOP_WEIGHT_VALUE = 1;
+    /**
+     * Weight value for null path (without links).
+     */
+    protected static final double NULL_WEIGHT_VALUE = 0;
+
+    @Override
+    public Weight weight(E edge) {
+        return new ScalarWeight(HOP_WEIGHT_VALUE);
+    }
+
+    @Override
+    public Weight getInitialWeight() {
+        return new ScalarWeight(NULL_WEIGHT_VALUE);
+    }
+
+    @Override
+    public Weight getNonViableWeight() {
+        return ScalarWeight.NON_VIABLE_WEIGHT;
+    }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
index b6c5e38..c8f8f86 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -31,7 +31,7 @@
 public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> {
 
     private final List<E> edges = new ArrayList<>();
-    private double cost = 0.0;
+    private Weight cost;
 
     /**
      * Creates a new empty path.
@@ -61,7 +61,7 @@
     }
 
     @Override
-    public double cost() {
+    public Weight cost() {
         return cost;
     }
 
@@ -71,7 +71,7 @@
     }
 
     @Override
-    public void setCost(double cost) {
+    public void setCost(Weight cost) {
         this.cost = cost;
     }
 
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
index c1aa802..4a29adf 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -33,15 +33,15 @@
     private final V src;
     private final V dst;
     private final List<E> edges;
-    private double cost = 0.0;
+    private Weight cost;
 
     /**
      * Creates a new path from the specified list of edges and cost.
      *
      * @param edges list of path edges
-     * @param cost  path cost as a unit-less number
+     * @param cost  path cost as a weight object
      */
-    public DefaultPath(List<E> edges, double cost) {
+    public DefaultPath(List<E> edges, Weight cost) {
         checkNotNull(edges, "Edges list must not be null");
         checkArgument(!edges.isEmpty(), "There must be at least one edge");
         this.edges = ImmutableList.copyOf(edges);
@@ -61,7 +61,7 @@
     }
 
     @Override
-    public double cost() {
+    public Weight cost() {
         return cost;
     }
 
diff --git a/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
index 218ce39..a5b33b3 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
@@ -35,15 +35,14 @@
     }
 
     @Override
-    public SpanningTreeResult search(Graph<V, E> graph, V src, V dst,
-                                     EdgeWeight<V, E> weight, int maxPaths) {
-        checkArguments(graph, src, dst);
+    protected SpanningTreeResult internalSearch(Graph<V, E> graph, V src, V dst,
+                                             EdgeWeigher<V, E> weigher, int maxPaths) {
 
         // Prepare the search result.
         SpanningTreeResult result = new SpanningTreeResult(src, dst, maxPaths);
 
         // The source vertex has cost 0, of course.
-        result.updateVertex(src, null, 0.0, true);
+        result.updateVertex(src, null, weigher.getInitialWeight(), true);
 
         // Track finished vertexes and keep a stack of vertexes that have been
         // started; start this stack with the source on it.
@@ -58,7 +57,7 @@
                 break;
             }
 
-            double cost = result.cost(vertex);
+            Weight cost = result.cost(vertex);
             boolean tangent = false;
 
             // Visit all egress edges of the current vertex.
@@ -74,7 +73,7 @@
                     // If this vertex have not finished this vertex yet,
                     // not started it, then start it as a tree-edge.
                     result.markEdge(edge, EdgeType.TREE_EDGE);
-                    double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+                    Weight newCost = cost.merge(weigher.weight(edge));
                     result.updateVertex(nextVertex, edge, newCost, true);
                     stack.push(nextVertex);
                     tangent = true;
diff --git a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
index 4990718..0dd1898 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -27,16 +27,15 @@
         extends AbstractGraphPathSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                               EdgeWeight<V, E> weight, int maxPaths) {
-        checkArguments(graph, src, dst);
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
 
         // Use the default result to remember cumulative costs and parent
         // edges to each each respective vertex.
         DefaultResult result = new DefaultResult(src, dst, maxPaths);
 
         // Cost to reach the source vertex is 0 of course.
-        result.updateVertex(src, null, 0.0, false);
+        result.updateVertex(src, null, weigher.getInitialWeight(), false);
 
         if (graph.getEdges().isEmpty()) {
             result.buildPaths();
@@ -56,11 +55,12 @@
             }
 
             // Find its cost and use it to determine if the vertex is reachable.
-            double cost = result.cost(nearest);
-            if (cost < Double.MAX_VALUE) {
+            if (result.hasCost(nearest)) {
+                Weight cost = result.cost(nearest);
+
                 // If the vertex is reachable, relax all its egress edges.
                 for (E e : graph.getEdgesFrom(nearest)) {
-                    result.relaxEdge(e, cost, weight, true);
+                    result.relaxEdge(e, cost, weigher, true);
                 }
             }
 
@@ -84,8 +84,16 @@
 
         @Override
         public int compare(V v1, V v2) {
-            double delta = result.cost(v2) - result.cost(v1);
-            return delta < 0 ? -1 : (delta > 0 ? 1 : 0);
+            //not accessed vertices should be pushed to the back of the queue
+            if (!result.hasCost(v1) && !result.hasCost(v2)) {
+                return 0;
+            } else if (!result.hasCost(v1)) {
+                return -1;
+            } else if (!result.hasCost(v2)) {
+                return 1;
+            }
+
+            return result.cost(v2).compareTo(result.cost(v1));
         }
     }
 
diff --git a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
index 1e8d3d6..6436ad4 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
@@ -73,8 +73,8 @@
     }
 
     @Override
-    public double cost() {
-        return hasBackup() ? primary.cost() + secondary.cost() : primary.cost();
+    public Weight cost() {
+        return hasBackup() ? primary.cost().merge(secondary.cost()) : primary.cost();
     }
 
     @Override
diff --git a/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java b/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java
new file mode 100644
index 0000000..f52c4dd
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2014-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onlab.graph;
+
+/**
+ * Abstraction of a graph edge weight function.
+ */
+public interface EdgeWeigher<V extends Vertex, E extends Edge<V>> {
+
+    /**
+     * Returns the weight of the given edge.
+     *
+     * @param edge edge to be weighed
+     * @return edge weight
+     */
+    Weight weight(E edge);
+
+    /**
+     * Returns initial weight value (i.e. weight of a "path" starting and
+     * terminating in the same vertex; typically 0 value is used).
+     *
+     * @return null path weight
+     */
+    Weight getInitialWeight();
+
+    /**
+     * Returns weight of a link/path that should be skipped
+     * (can be considered as an infinite weight).
+     *
+     * @return non viable weight
+     */
+    Weight getNonViableWeight();
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java b/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
deleted file mode 100644
index 5b1c806..0000000
--- a/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * Copyright 2014-present Open Networking Laboratory
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.onlab.graph;
-
-/**
- * Abstraction of a graph edge weight function.
- */
-public interface EdgeWeight<V extends Vertex, E extends Edge<V>> {
-
-    /**
-     * Returns the weight of the given edge as a unit-less number.
-     *
-     * @param edge edge to be weighed
-     * @return edge weight as a unit-less number
-     */
-    double weight(E edge);
-
-}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
index 4deed2fa..1384c9a 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
@@ -28,7 +28,7 @@
      *
      * @return fitness of organism
      */
-    double fitness();
+    Comparable fitness();
 
     /**
      * A method that slightly mutates an organism.
diff --git a/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
index 5f9dfcc..4017485 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
@@ -33,15 +33,8 @@
      * 25% (as well as some "random" newcomers).
      */
     void step() {
-        Collections.sort(this, (org1, org2) -> {
-            double d = org1.fitness() - org2.fitness();
-            if (d < 0) {
-                return -1;
-            } else if (d == 0) {
-                return 0;
-            }
-            return 1;
-        });
+        Collections.sort(this, (org1, org2) ->
+                org1.fitness().compareTo(org2.fitness()));
         int maxSize = size();
         for (int i = size() - 1; i > maxSize / 4; i--) {
             remove(i);
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
index d5513a7..1c1099d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
@@ -66,7 +66,7 @@
          *
          * @return map of vertex to path cost bindings
          */
-        Map<V, Double> costs();
+        Map<V, Weight> costs();
     }
 
     /**
@@ -76,12 +76,12 @@
      * @param src      optional source vertex
      * @param dst      optional destination vertex; if null paths to all vertex
      *                 destinations will be searched
-     * @param weight   optional edge-weight; if null cost of each edge will be
-     *                 assumed to be 1.0
+     * @param weigher  optional edge-weigher; if null, {@link DefaultEdgeWeigher}
+     *                 will be used (assigns equal weights to all links)
      * @param maxPaths limit on number of paths; {@link GraphPathSearch#ALL_PATHS} if no limit
      * @return search results
      */
     Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                        EdgeWeight<V, E> weight, int maxPaths);
+                        EdgeWeigher<V, E> weigher, int maxPaths);
 
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
index 4ef6e6d..6f0d606 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
@@ -32,12 +32,12 @@
     /**
      * Searches the specified graph.
      *
-     * @param graph  graph to be searched
-     * @param weight optional edge-weight; if null cost of each edge will be
-     *               assumed to be 1.0
+     * @param graph   graph to be searched
+     * @param weigher optional edge-weigher; if null, {@link DefaultEdgeWeigher}
+     *                will be used (assigns equal weights to all links)
      *
      * @return search results
      */
-    Result search(Graph<V, E> graph, EdgeWeight<V, E> weight);
+    Result search(Graph<V, E> graph, EdgeWeigher<V, E> weigher);
 
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
index c07b00a..00bda43 100644
--- a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
@@ -40,11 +40,9 @@
     private final Logger log = getLogger(getClass());
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) {
-        checkNotNull(src);
-        checkNotNull(dst);
-        //The modified edge weight removes any need to modify the original graph
-        InnerEdgeWeighter modifiedWeighter = new InnerEdgeWeighter(checkNotNull(weight));
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst, EdgeWeigher<V, E> weigher, int maxPaths) {
+        //The modified edge weigher removes any need to modify the original graph
+        InnerEdgeWeigher modifiedWeighter = new InnerEdgeWeigher(checkNotNull(weigher));
         checkArgument(maxPaths != ALL_PATHS, "KShortestPath search cannot" +
                 "be used with ALL_PATHS.");
         checkArgument(maxPaths > 0, "The max number of paths must be greater" +
@@ -87,11 +85,11 @@
                 if (!dijkstraResults.isEmpty()) {
                     Path<V, E> spurPath = dijkstraResults.iterator().next();
                     List<E> totalPath = new ArrayList<>(rootPathEdgeList);
-                    spurPath.edges().forEach(e -> totalPath.add(e));
-                    //The following line must use the original weighter not the modified weighter because the modified
-                    //weighter will count -1 values used for modifying the graph and return an inaccurate cost.
+                    spurPath.edges().forEach(totalPath::add);
+                    //The following line must use the original weigher not the modified weigher because the modified
+                    //weigher will count -1 values used for modifying the graph and return an inaccurate cost.
                     potentialPaths.add(new DefaultPath<V, E>(totalPath,
-                                                             calculatePathCost(weight, totalPath)));
+                            calculatePathCost(weigher, totalPath)));
                 }
 
                 //Restore all removed paths and nodes
@@ -125,10 +123,10 @@
         return true;
     }
 
-    private Double calculatePathCost(EdgeWeight<V, E> weighter, List<E> edges) {
-        Double totalCost = 0.0;
+    private Weight calculatePathCost(EdgeWeigher<V, E> weighter, List<E> edges) {
+        Weight totalCost = weighter.getInitialWeight();
         for (E edge : edges) {
-            totalCost += weighter.weight(edge);
+            totalCost = totalCost.merge(weighter.weight(edge));
         }
         return totalCost;
     }
@@ -136,23 +134,31 @@
     /**
      * Weights edges to make them inaccessible if set, otherwise returns the result of the original EdgeWeight.
      */
-    private class InnerEdgeWeighter implements EdgeWeight<V, E> {
+    private final class InnerEdgeWeigher implements EdgeWeigher<V, E> {
 
         private Set<E> removedEdges = Sets.newConcurrentHashSet();
-        private EdgeWeight<V, E> innerEdgeWeight;
+        private EdgeWeigher<V, E> innerEdgeWeigher;
 
-        public InnerEdgeWeighter(EdgeWeight<V, E> weight) {
-            this.innerEdgeWeight = weight;
+        private InnerEdgeWeigher(EdgeWeigher<V, E> weigher) {
+            this.innerEdgeWeigher = weigher;
         }
 
         @Override
-        public double weight(E edge) {
+        public Weight weight(E edge) {
             if (removedEdges.contains(edge)) {
-                //THIS RELIES ON THE LOCAL DIJKSTRA ALGORITHM AVOIDING NEGATIVES
-                return -1;
-            } else {
-                return innerEdgeWeight.weight(edge);
+                return innerEdgeWeigher.getNonViableWeight();
             }
+            return innerEdgeWeigher.weight(edge);
+        }
+
+        @Override
+        public Weight getInitialWeight() {
+            return innerEdgeWeigher.getInitialWeight();
+        }
+
+        @Override
+        public Weight getNonViableWeight() {
+            return innerEdgeWeigher.getNonViableWeight();
         }
     }
 
@@ -184,7 +190,7 @@
 
         @Override
         public int compare(Path<V, E> pathOne, Path<V, E> pathTwo) {
-            int comparisonValue = Double.compare(pathOne.cost(), pathTwo.cost());
+            int comparisonValue = pathOne.cost().compareTo(pathTwo.cost());
             if  (comparisonValue != 0) {
                 return comparisonValue;
             } else if (edgeListsAreEqual(pathOne.edges(), pathTwo.edges())) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
index 22412b1..3a3b479 100644
--- a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -46,11 +46,11 @@
     void removeEdge(E edge);
 
     /**
-     * Sets the total path cost as a unit-less double.
+     * Sets the total path cost as a weight object.
      *
      * @param cost new path cost
      */
-    void setCost(double cost);
+    void setCost(Weight cost);
 
     /**
      * Returns an immutable copy of this path.
diff --git a/utils/misc/src/main/java/org/onlab/graph/Path.java b/utils/misc/src/main/java/org/onlab/graph/Path.java
index 0f74aae..85ac420 100644
--- a/utils/misc/src/main/java/org/onlab/graph/Path.java
+++ b/utils/misc/src/main/java/org/onlab/graph/Path.java
@@ -36,10 +36,10 @@
     List<E> edges();
 
     /**
-     * Returns the total cost of the path as a unit-less number.
+     * Returns the total cost of the path as a weight object.
      *
-     * @return path cost as a unit-less number
+     * @return path cost as a weight object
      */
-    double cost();
+    Weight cost();
 
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java b/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java
new file mode 100644
index 0000000..ccf0c2a
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onlab.graph;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+import com.google.common.math.DoubleMath;
+
+import java.util.Objects;
+
+/**
+ * Weight implementation based on a double value.
+ */
+public class ScalarWeight implements Weight {
+
+    /**
+     * Instance of scalar weight to mark links/paths which
+     * can not be traversed.
+     */
+    public static final ScalarWeight NON_VIABLE_WEIGHT =
+            new ScalarWeight(Double.POSITIVE_INFINITY);
+
+    private static double samenessThreshold = Double.MIN_VALUE;
+
+    private double value;
+
+    /**
+     * Creates a new scalar weight with the given double value.
+     * @param value double value
+     */
+    public ScalarWeight(double value) {
+        this.value = value;
+    }
+
+    @Override
+    public Weight merge(Weight otherWeight) {
+        return new ScalarWeight(value + ((ScalarWeight) otherWeight).value);
+    }
+
+    @Override
+    public Weight subtract(Weight otherWeight) {
+        return new ScalarWeight(value - ((ScalarWeight) otherWeight).value);
+    }
+
+    @Override
+    public boolean isViable() {
+        return this != NON_VIABLE_WEIGHT;
+    }
+
+    @Override
+    public int compareTo(Weight otherWeight) {
+        //check equality with samenessThreshold
+        if (equals(otherWeight)) {
+            return 0;
+        }
+        return Double.compare(value, ((ScalarWeight) otherWeight).value);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        return ((obj instanceof ScalarWeight) &&
+                (DoubleMath.fuzzyEquals(value, ((ScalarWeight) obj).value,
+                        samenessThreshold)));
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(value);
+    }
+
+    @Override
+    public boolean isNegative() {
+        return value < 0;
+    }
+
+    @Override
+    public String toString() {
+        return toStringHelper(this).add("value", value).toString();
+    }
+
+    /**
+     * Returns inner double value.
+     *
+     * @return double value
+     */
+    public double value() {
+        return value;
+    }
+
+    /**
+     * Sets a new sameness threshold for comparing cost values; default is
+     * is {@link Double#MIN_VALUE}.
+     *
+     * @param threshold fractional double value
+     */
+    public static void setSamenessThreshold(double threshold) {
+        samenessThreshold = threshold;
+    }
+
+    /**
+     * Returns the current sameness threshold for comparing cost values.
+     *
+     * @return current threshold
+     */
+    public static double samenessThreshold() {
+        return samenessThreshold;
+    }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
index 5ac35a0..82107ca 100644
--- a/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
@@ -46,7 +46,7 @@
 
     Graph<V, E> orig;
     V src, dst;
-    EdgeWeight<V, E> weight;
+    EdgeWeigher<V, E> weigher;
 
     /**
      * Creates an SRLG graph search object with the given number
@@ -86,22 +86,18 @@
     }
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                               EdgeWeight<V, E> weight, int maxPaths) {
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
         if (maxPaths == ALL_PATHS) {
             maxPaths = POPSIZE;
         }
         if (useSuurballe) {
-            return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS);
+            return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weigher, ALL_PATHS);
         }
-        if (weight == null) {
-            weight = edge -> 1;
-        }
-        checkArguments(graph, src, dst);
         orig = graph;
         this.src = src;
         this.dst = dst;
-        this.weight = weight;
+        this.weigher = weigher;
         List<Subset> best = new GAPopulation<Subset>()
                 .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups]));
         Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>();
@@ -109,7 +105,7 @@
             dpps.addAll(s.buildPaths());
         }
         Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>()
-                .search(orig, src, dst, weight, 1);
+                .search(orig, src, dst, weigher, 1);
         return new Result<V, E>() {
             final DefaultResult search = (DefaultResult) firstDijkstra;
 
@@ -127,7 +123,7 @@
                 }
                 return pathsD;
             }
-            public Map<V, Double> costs() {
+            public Map<V, Weight> costs() {
                 return search.costs();
 
             }
@@ -141,15 +137,25 @@
     //finds the shortest path in the graph given a subset of edge types to use
     private Result<V, E> findShortestPathFromSubset(boolean[] subset) {
         Graph<V, E> graph = orig;
-        EdgeWeight<V, E> modified = new EdgeWeight<V, E>() {
+        EdgeWeigher<V, E> modified = new EdgeWeigher<V, E>() {
             final boolean[] subsetF = subset;
 
             @Override
-            public double weight(E edge) {
+            public Weight weight(E edge) {
                 if (subsetF[riskGrouping.get(edge)]) {
-                    return weight.weight(edge);
+                    return weigher.weight(edge);
                 }
-                return INF;
+                return weigher.getNonViableWeight();
+            }
+
+            @Override
+            public Weight getInitialWeight() {
+                return weigher.getInitialWeight();
+            }
+
+            @Override
+            public Weight getNonViableWeight() {
+                return weigher.getNonViableWeight();
             }
         };
 
@@ -181,13 +187,13 @@
         }
 
         @Override
-        public double fitness() {
+        public Comparable fitness() {
             Set<Path<V, E>> paths1 = findShortestPathFromSubset(subset).paths();
             Set<Path<V, E>> paths2 = findShortestPathFromSubset(not).paths();
             if (paths1.isEmpty() || paths2.isEmpty()) {
-                return INF;
+                return weigher.getNonViableWeight();
             }
-            return paths1.iterator().next().cost() + paths2.iterator().next().cost();
+            return paths1.iterator().next().cost().merge(paths2.iterator().next().cost());
         }
 
         @Override
@@ -236,13 +242,7 @@
         public Set<DisjointPathPair> buildPaths() {
             Set<DisjointPathPair> dpps = new HashSet<>();
             for (Path<V, E> path1: findShortestPathFromSubset(subset).paths()) {
-                if (path1.cost() >= INF) {
-                    continue;
-                }
                 for (Path<V, E> path2: findShortestPathFromSubset(not).paths()) {
-                    if (path2.cost() >= INF) {
-                        continue;
-                    }
                     DisjointPathPair<V, E> dpp = new DisjointPathPair<>(path1, path2);
                     dpps.add(dpp);
                 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
index f517d5a..d945192 100644
--- a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
@@ -34,8 +34,8 @@
 public class SuurballeGraphSearch<V extends Vertex, E extends Edge<V>> extends DijkstraGraphSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
-                               EdgeWeight<V, E> weight, int maxPaths) {
+    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+                               EdgeWeigher<V, E> weigher, int maxPaths) {
         // FIXME: This method needs to be refactored as it is difficult to follow and debug.
 
         // FIXME: There is a defect here triggered by 3+ edges between the same vertices,
@@ -46,13 +46,12 @@
         // This class needs to filter its own results to make sure that the
         // paths are indeed disjoint. Temporary fix for this is provided, but
         // the issue needs to be addressed through refactoring.
-        if (weight == null) {
-            weight = edge -> 1;
-        }
 
-        final EdgeWeight weightf = weight;
-        DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS);
-        DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS);
+        EdgeWeigher weightf = weigher;
+        DefaultResult firstDijkstraS = (DefaultResult) super.internalSearch(
+                graph, src, dst, weigher, ALL_PATHS);
+        DefaultResult firstDijkstra = (DefaultResult) super.internalSearch(
+                graph, src, null, weigher, ALL_PATHS);
 
         //choose an arbitrary shortest path to run Suurballe on
         Path<V, E> shortPath = null;
@@ -65,11 +64,43 @@
         for (Path p: firstDijkstraS.paths()) {
             shortPath = p;
             //transforms the graph so tree edges have 0 weight
-            EdgeWeight<V, E> modified = edge ->
-                edge instanceof ReverseEdge ? 0 :
-                    weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
-            EdgeWeight<V, E> modified2 = edge ->
-                    weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
+            EdgeWeigher<V, E> modified = new EdgeWeigher<V, E>() {
+                @Override
+                public Weight weight(E edge) {
+                    return edge instanceof ReverseEdge ?
+                            weightf.getInitialWeight() :
+                            weightf.weight(edge).merge(firstDijkstra.cost(edge.src()))
+                                    .subtract(firstDijkstra.cost(edge.dst()));
+                }
+
+                @Override
+                public Weight getInitialWeight() {
+                    return weightf.getInitialWeight();
+                }
+
+                @Override
+                public Weight getNonViableWeight() {
+                    return weightf.getNonViableWeight();
+                }
+            };
+
+            EdgeWeigher<V, E> modified2 = new EdgeWeigher<V, E>() {
+                @Override
+                public Weight weight(E edge) {
+                    return weightf.weight(edge).merge(firstDijkstra.cost(edge.src()))
+                            .subtract(firstDijkstra.cost(edge.dst()));
+                }
+
+                @Override
+                public Weight getInitialWeight() {
+                    return weightf.getInitialWeight();
+                }
+
+                @Override
+                public Weight getNonViableWeight() {
+                    return weightf.getNonViableWeight();
+                }
+            };
 
             //create a residual graph g' by removing all src vertices and reversing 0 length path edges
             MutableGraph<V, E> gt = mutableCopy(graph);
@@ -114,11 +145,13 @@
                     }
                 }
                 //Actually build the final result
-                DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS);
+                DefaultResult lastSearch = (DefaultResult)
+                        super.internalSearch(roundTrip, src, dst, weigher, ALL_PATHS);
                 Path<V, E> primary = lastSearch.paths().iterator().next();
                 primary.edges().forEach(roundTrip::removeEdge);
 
-                Set<Path<V, E>> backups = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths();
+                Set<Path<V, E>> backups = super.internalSearch(roundTrip, src, dst,
+                        weigher, ALL_PATHS).paths();
 
                 // Find first backup path that does not share any nodes with the primary
                 for (Path<V, E> backup : backups) {
@@ -220,7 +253,7 @@
         }
 
         @Override
-        public Map<V, Double> costs() {
+        public Map<V, Weight> costs() {
             return searchResult.costs();
         }
     }
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)) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/Weight.java b/utils/misc/src/main/java/org/onlab/graph/Weight.java
new file mode 100644
index 0000000..9f5326d
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Weight.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onlab.graph;
+
+/**
+ * Abstraction of a graph edge weight.
+ */
+public interface Weight extends Comparable<Weight> {
+
+    /**
+     * Merges the given weight with this one returning a new aggregated
+     * weight.
+     *
+     * @param otherWeight weight to add
+     * @return aggregated weight
+     */
+    Weight merge(Weight otherWeight);
+
+    /**
+     * Subtracts the given weight from this one and produces a new weight.
+     *
+     * @param otherWeight weight to subtract
+     * @return residual weight
+     */
+    Weight subtract(Weight otherWeight);
+
+    /**
+     * Returns true if the weighted subject (link/path) can be traversed; false otherwise.
+     *
+     * @return true if weight is adequate, false if weight is infinite
+     */
+    boolean isViable();
+
+    /**
+     * Returns true if the weight is negative (means that aggregated
+     * path cost will decrease if we add weighted subject to it).
+     *
+     * @return true if the weight is negative, false otherwise
+     */
+    boolean isNegative();
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
index 65bc741..dcf951e 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
@@ -28,9 +28,9 @@
         TestVertex v1 = new TestVertex("1");
         TestVertex v2 = new TestVertex("2");
         new EqualsTester()
-                .addEqualityGroup(new TestEdge(v1, v2, 1),
-                                  new TestEdge(v1, v2, 1))
-                .addEqualityGroup(new TestEdge(v2, v1, 1))
+                .addEqualityGroup(new TestEdge(v1, v2),
+                                  new TestEdge(v1, v2))
+                .addEqualityGroup(new TestEdge(v2, v1))
                 .testEquals();
     }
 
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
index e585449..fa0d522 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
@@ -18,7 +18,6 @@
 import org.junit.Test;
 
 import static com.google.common.collect.ImmutableSet.of;
-import static org.junit.Assert.assertEquals;
 
 /**
  * Base for all graph search tests.
@@ -35,27 +34,19 @@
     @Test(expected = IllegalArgumentException.class)
     public void noSuchSourceArgument() {
         graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
-                                                       of(new TestEdge(B, C, 1))),
-                             A, H, weight, 1);
+                                                       of(new TestEdge(B, C))),
+                             A, H, weigher, 1);
     }
 
     @Test(expected = NullPointerException.class)
     public void nullGraphArgument() {
-        graphSearch().search(null, A, H, weight, 1);
+        graphSearch().search(null, A, H, weigher, 1);
     }
 
     @Test(expected = NullPointerException.class)
     public void nullSourceArgument() {
         graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
-                                                       of(new TestEdge(B, C, 1))),
-                             null, H, weight, 1);
+                        of(new TestEdge(B, C))),
+                null, H, weigher, 1);
     }
-
-    @Test
-    public void samenessThreshold() {
-        AbstractGraphPathSearch<TestVertex, TestEdge> search = graphSearch();
-        search.setSamenessThreshold(0.3);
-        assertEquals("incorrect threshold", 0.3, search.samenessThreshold(), 0.01);
-    }
-
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
index 9089550..f795027 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
@@ -37,9 +37,11 @@
     private static final TestVertex G = new TestVertex("G");
 
     private final Set<TestEdge> edges =
-            ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(B, C, 1),
-                            new TestEdge(C, D, 1), new TestEdge(D, A, 1),
-                            new TestEdge(B, D, 1));
+            ImmutableSet.of(new TestEdge(A, B),
+                            new TestEdge(B, C),
+                            new TestEdge(C, D),
+                            new TestEdge(D, A),
+                            new TestEdge(B, D));
 
     @Test
     public void equality() {
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 cfa313c..0a36d77 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -36,13 +36,13 @@
     @Test
     @Override
     public void defaultGraphTest() {
-        executeDefaultTest(7, 5, 5.0);
+        executeDefaultTest(7, 5, new TestDoubleWeight(5.0));
     }
 
     @Test
     public void defaultHopCountWeight() {
-        weight = null;
-        executeDefaultTest(10, 3, 3.0);
+        weigher = null;
+        executeDefaultTest(10, 3, new ScalarWeight(3.0));
     }
 
     @Test
@@ -51,25 +51,25 @@
         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));
+        edges.add(new TestEdge(G, Z, new TestDoubleWeight(1.0)));
+        edges.add(new TestEdge(Z, G, new TestDoubleWeight(-2.0)));
 
         graph = new AdjacencyListsGraph<>(vertexes, edges);
 
         GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight, ALL_PATHS).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weigher, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 1, paths.size());
 
         Path p = paths.iterator().next();
         assertEquals("incorrect src", A, p.src());
         assertEquals("incorrect dst", H, p.dst());
         assertEquals("incorrect path length", 5, p.edges().size());
-        assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
+        assertEquals("incorrect path cost", new TestDoubleWeight(5), p.cost());
 
-        paths = search.search(graph, A, G, weight, ALL_PATHS).paths();
+        paths = search.search(graph, A, G, weigher, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 0, paths.size());
 
-        paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
+        paths = search.search(graph, A, null, weigher, ALL_PATHS).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 3d02dc1..c19268c 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -34,31 +34,31 @@
 
     @Test
     public void defaultGraphTest() {
-        executeDefaultTest(7, 3, 8.0);
+        executeDefaultTest(7, 3, new TestDoubleWeight(8.0));
     }
 
     @Test
     public void defaultHopCountWeight() {
-        weight = null;
-        executeDefaultTest(7, 3, 3.0);
+        weigher = null;
+        executeDefaultTest(7, 3, new ScalarWeight(3.0));
     }
 
     // Executes the default test
-    protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) {
+    protected void executeDefaultTest(int pathCount, int pathLength, Weight pathCost) {
         graph = new AdjacencyListsGraph<>(vertexes(), edges());
 
         GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
         Set<Path<TestVertex, TestEdge>> paths =
-                search.search(graph, A, H, weight, ALL_PATHS).paths();
+                search.search(graph, A, H, weigher, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 1, paths.size());
 
         Path p = paths.iterator().next();
         assertEquals("incorrect src", A, p.src());
         assertEquals("incorrect dst", H, p.dst());
         assertEquals("incorrect path length", pathLength, p.edges().size());
-        assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
+        assertEquals("incorrect path cost", pathCost, p.cost());
 
-        paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
+        paths = search.search(graph, A, null, weigher, ALL_PATHS).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", pathCount, paths.size());
     }
@@ -67,16 +67,16 @@
     protected void executeSearch(GraphPathSearch<TestVertex, TestEdge> search,
                                  Graph<TestVertex, TestEdge> graph,
                                  TestVertex src, TestVertex dst,
-                                 EdgeWeight<TestVertex, TestEdge> weight,
-                                 int pathCount, double pathCost) {
+                                 EdgeWeigher<TestVertex, TestEdge> weigher,
+                                 int pathCount, Weight pathCost) {
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                search.search(graph, src, dst, weight, ALL_PATHS);
+                search.search(graph, src, dst, weigher, ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         printPaths(paths);
         assertEquals("incorrect paths count", pathCount, paths.size());
         if (pathCount > 0) {
             Path<TestVertex, TestEdge> path = paths.iterator().next();
-            assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+            assertEquals("incorrect path cost", pathCost, path.cost());
         }
     }
 
@@ -84,16 +84,16 @@
     protected void executeSinglePathSearch(GraphPathSearch<TestVertex, TestEdge> search,
                                            Graph<TestVertex, TestEdge> graph,
                                            TestVertex src, TestVertex dst,
-                                           EdgeWeight<TestVertex, TestEdge> weight,
-                                           int pathCount, double pathCost) {
+                                           EdgeWeigher<TestVertex, TestEdge> weigher,
+                                           int pathCount, Weight pathCost) {
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                search.search(graph, src, dst, weight, 1);
+                search.search(graph, src, dst, weigher, 1);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         printPaths(paths);
         assertEquals("incorrect paths count", Math.min(pathCount, 1), paths.size());
         if (pathCount > 0) {
             Path<TestVertex, TestEdge> path = paths.iterator().next();
-            assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+            assertEquals("incorrect path cost", pathCost, path.cost());
         }
     }
 
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
index 89b7201..d196fa0 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
@@ -30,11 +30,13 @@
     @Test
     public void equality() {
         DefaultPath<TestVertex, TestEdge> p1 =
-                new DefaultPath<>(of(new TestEdge(A, B, 1),
-                                     new TestEdge(B, C, 1)), 2.0);
+                new DefaultPath<>(of(new TestEdge(A, B),
+                                     new TestEdge(B, C)),
+                        new TestDoubleWeight(2.0));
         DefaultPath<TestVertex, TestEdge> p2 =
-                new DefaultPath<>(of(new TestEdge(A, B, 1),
-                                     new TestEdge(B, D, 1)), 2.0);
+                new DefaultPath<>(of(new TestEdge(A, B),
+                                     new TestEdge(B, D)),
+                        new TestDoubleWeight(2.0));
         new EqualsTester().addEqualityGroup(new DefaultMutablePath<>(p1),
                                             new DefaultMutablePath<>(p1))
                 .addEqualityGroup(new DefaultMutablePath<>(p2))
@@ -47,61 +49,62 @@
         assertNull("src should be null", p.src());
         assertNull("dst should be null", p.dst());
         assertEquals("incorrect edge count", 0, p.edges().size());
-        assertEquals("incorrect path cost", 0.0, p.cost(), 0.1);
+        assertEquals("incorrect path cost", null, p.cost());
     }
 
     @Test
     public void pathCost() {
         MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
-        p.setCost(4);
-        assertEquals("incorrect path cost", 4.0, p.cost(), 0.1);
+        Weight weight = new TestDoubleWeight(4);
+        p.setCost(weight);
+        assertEquals("incorrect path cost", weight, p.cost());
     }
 
     private void validatePath(Path<TestVertex, TestEdge> p,
                               TestVertex src, TestVertex dst, int length) {
-        validatePath(p, src, dst, length, 0.0);
+        validatePath(p, src, dst, length, null);
     }
 
     @Test
     public void insertEdge() {
         MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
-        p.insertEdge(new TestEdge(B, C, 1));
-        p.insertEdge(new TestEdge(A, B, 1));
+        p.insertEdge(new TestEdge(B, C));
+        p.insertEdge(new TestEdge(A, B));
         validatePath(p, A, C, 2);
     }
 
     @Test
     public void appendEdge() {
         MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
-        p.appendEdge(new TestEdge(A, B, 1));
-        p.appendEdge(new TestEdge(B, C, 1));
+        p.appendEdge(new TestEdge(A, B));
+        p.appendEdge(new TestEdge(B, C));
         validatePath(p, A, C, 2);
     }
 
     @Test
     public void removeEdge() {
         MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
-        p.appendEdge(new TestEdge(A, B, 1));
-        p.appendEdge(new TestEdge(B, C, 1));
-        p.appendEdge(new TestEdge(C, C, 2));
-        p.appendEdge(new TestEdge(C, D, 1));
+        p.appendEdge(new TestEdge(A, B));
+        p.appendEdge(new TestEdge(B, C));
+        p.appendEdge(new TestEdge(C, C));
+        p.appendEdge(new TestEdge(C, D));
         validatePath(p, A, D, 4);
 
-        p.removeEdge(new TestEdge(A, B, 1));
+        p.removeEdge(new TestEdge(A, B));
         validatePath(p, B, D, 3);
 
-        p.removeEdge(new TestEdge(C, C, 2));
+        p.removeEdge(new TestEdge(C, C));
         validatePath(p, B, D, 2);
 
-        p.removeEdge(new TestEdge(C, D, 1));
+        p.removeEdge(new TestEdge(C, D));
         validatePath(p, B, C, 1);
     }
 
     @Test
     public void toImmutable() {
         MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
-        p.appendEdge(new TestEdge(A, B, 1));
-        p.appendEdge(new TestEdge(B, C, 1));
+        p.appendEdge(new TestEdge(A, B));
+        p.appendEdge(new TestEdge(B, C));
         validatePath(p, A, C, 2);
 
         assertEquals("immutables should equal", p.toImmutable(), p.toImmutable());
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
index bcfe35c..891a768 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
@@ -30,28 +30,29 @@
 
     @Test
     public void equality() {
-        List<TestEdge> edges = of(new TestEdge(A, B, 1), new TestEdge(B, C, 1));
-        new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, 2.0),
-                                            new DefaultPath<>(edges, 2.0))
-                .addEqualityGroup(new DefaultPath<>(edges, 3.0))
+        List<TestEdge> edges = of(new TestEdge(A, B), new TestEdge(B, C));
+        new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, new TestDoubleWeight(2.0)),
+                                            new DefaultPath<>(edges, new TestDoubleWeight(2.0)))
+                .addEqualityGroup(new DefaultPath<>(edges, new TestDoubleWeight(3.0)))
                 .testEquals();
     }
 
     @Test
     public void basics() {
-        Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B, 1),
-                                                            new TestEdge(B, C, 1)), 2.0);
-        validatePath(p, A, C, 2, 2.0);
+        Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B),
+                                                            new TestEdge(B, C)),
+                new TestDoubleWeight(2.0));
+        validatePath(p, A, C, 2, new TestDoubleWeight(2.0));
     }
 
     // Validates the path against expected attributes
     protected void validatePath(Path<TestVertex, TestEdge> p,
                                 TestVertex src, TestVertex dst,
-                                int length, double cost) {
+                                int length, Weight cost) {
         assertEquals("incorrect path length", length, p.edges().size());
         assertEquals("incorrect source", src, p.src());
         assertEquals("incorrect destination", dst, p.dst());
-        assertEquals("incorrect path cost", cost, p.cost(), 0.1);
+        assertEquals("incorrect path cost", cost, p.cost());
     }
 
 }
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 e164f7e..e855b33 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -36,24 +36,25 @@
 
     @Test
     public void defaultGraphTest() {
-        executeDefaultTest(3, 6, 5.0, 12.0);
+        executeDefaultTest(3, 6, new TestDoubleWeight(5.0), new TestDoubleWeight(12.0));
         executeBroadSearch();
     }
 
     @Test
     public void defaultHopCountWeight() {
-        weight = null;
-        executeDefaultTest(3, 6, 3.0, 6.0);
+        weigher = null;
+        executeDefaultTest(3, 6, new ScalarWeight(3.0), new ScalarWeight(6.0));
         executeBroadSearch();
     }
 
     protected void executeDefaultTest(int minLength, int maxLength,
-                                      double minCost, double maxCost) {
+                                      Weight minCost, Weight maxCost) {
         graph = new AdjacencyListsGraph<>(vertexes(), edges());
         DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
 
         DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
-                search.search(graph, A, H, weight, 1);
+                (DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult)
+                        search.search(graph, A, H, weigher, 1);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         assertEquals("incorrect path count", 1, paths.size());
 
@@ -66,7 +67,8 @@
         assertTrue("incorrect path length " + l,
                    minLength <= l && l <= maxLength);
         assertTrue("incorrect path cost " + path.cost(),
-                   minCost <= path.cost() && path.cost() <= maxCost);
+                   path.cost().compareTo(minCost) >= 0 &&
+                   path.cost().compareTo(maxCost) <= 0);
 
         System.out.println(result.edges());
         printPaths(paths);
@@ -78,7 +80,8 @@
 
         // Perform narrow path search to a specific destination.
         DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
-                search.search(graph, A, null, weight, ALL_PATHS);
+                (DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult)
+                        search.search(graph, A, null, weigher, ALL_PATHS);
         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 f2a19b8..cfd0a4b 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -37,99 +37,105 @@
     @Test
     @Override
     public void defaultGraphTest() {
-        executeDefaultTest(7, 5, 5.0);
+        executeDefaultTest(7, 5, new TestDoubleWeight(5.0));
     }
 
     @Test
     @Override
     public void defaultHopCountWeight() {
-        weight = null;
-        executeDefaultTest(10, 3, 3.0);
+        weigher = null;
+        executeDefaultTest(10, 3, new ScalarWeight(3.0));
     }
 
     @Test
     public void noPath() {
         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)));
+                                          of(new TestEdge(A, B, W1),
+                                             new TestEdge(B, A, W1),
+                                             new TestEdge(C, D, W1),
+                                             new TestEdge(D, C, W1)));
         GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight, 1).paths();
+        Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weigher, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 1, paths.size());
-        assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+        assertEquals("incorrect path cost", new TestDoubleWeight(1.0), paths.iterator().next().cost());
 
-        paths = gs.search(graph, A, D, weight, 1).paths();
+        paths = gs.search(graph, A, D, weigher, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 0, paths.size());
 
-        paths = gs.search(graph, A, null, weight, 1).paths();
+        paths = gs.search(graph, A, null, weigher, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 1, paths.size());
-        assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+        assertEquals("incorrect path cost", new TestDoubleWeight(1.0), paths.iterator().next().cost());
     }
 
     @Test
     public void simpleMultiplePath() {
         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);
-        executeSinglePathSearch(graphSearch(), graph, A, D, weight, 1, 2.0);
+                                          of(new TestEdge(A, B, W1),
+                                             new TestEdge(A, C, W1),
+                                             new TestEdge(B, D, W1),
+                                             new TestEdge(C, D, W1)));
+        executeSearch(graphSearch(), graph, A, D, weigher, 2, W2);
+        executeSinglePathSearch(graphSearch(), graph, A, D, weigher, 1, W2);
     }
 
     @Test
     public void denseMultiplePath() {
         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);
-        executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
+                                          of(new TestEdge(A, B, W1),
+                                             new TestEdge(A, C, W1),
+                                             new TestEdge(B, D, W1),
+                                             new TestEdge(C, D, W1),
+                                             new TestEdge(D, E, W1),
+                                             new TestEdge(D, F, W1),
+                                             new TestEdge(E, G, W1),
+                                             new TestEdge(F, G, W1),
+                                             new TestEdge(A, G, W4)));
+        executeSearch(graphSearch(), graph, A, G, weigher, 5, W4);
+        executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, W4);
     }
 
     @Test
     public void dualEdgeMultiplePath() {
         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);
-        executeSinglePathSearch(graphSearch(), graph, A, E, weight, 1, 3.0);
+                                          of(new TestEdge(A, B, W1),
+                                             new TestEdge(A, C, W3),
+                                             new TestEdge(B, D, W2),
+                                             new TestEdge(B, C, W1),
+                                             new TestEdge(B, E, W4),
+                                             new TestEdge(C, E, W1),
+                                             new TestEdge(D, H, W5),
+                                             new TestEdge(D, E, W1),
+                                             new TestEdge(E, F, W1),
+                                             new TestEdge(F, D, W1),
+                                             new TestEdge(F, G, W1),
+                                             new TestEdge(F, H, W1),
+                                             new TestEdge(A, E, W3),
+                                             new TestEdge(B, D, W1)));
+        executeSearch(graphSearch(), graph, A, E, weigher, 3, W3);
+        executeSinglePathSearch(graphSearch(), graph, A, E, weigher, 1, W3);
     }
 
     @Test
     public void negativeWeights() {
         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(D, A, -2),
-                                             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(G, A, -5),
-                                             new TestEdge(A, G, 4)));
-        executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
-        executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
+                                          of(new TestEdge(A, B, W1),
+                                             new TestEdge(A, C, NW1),
+                                             new TestEdge(B, D, W1),
+                                             new TestEdge(D, A, NW2),
+                                             new TestEdge(C, D, W1),
+                                             new TestEdge(D, E, W1),
+                                             new TestEdge(D, F, W1),
+                                             new TestEdge(E, G, W1),
+                                             new TestEdge(F, G, W1),
+                                             new TestEdge(G, A, NW5),
+                                             new TestEdge(A, G, W4)));
+        executeSearch(graphSearch(), graph, A, G, weigher, 3, new TestDoubleWeight(4.0));
+        executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, new TestDoubleWeight(4.0));
     }
 
-    @Test
     public void disconnectedPerf() {
         disconnected();
         disconnected();
@@ -143,8 +149,6 @@
         disconnected();
     }
 
-
-    @Test
     public void disconnected() {
         Set<TestVertex> vertexes = new HashSet<>();
         for (int i = 0; i < 200; i++) {
@@ -155,7 +159,7 @@
 
         long start = System.nanoTime();
         for (TestVertex src : vertexes) {
-            executeSearch(graphSearch(), graph, src, null, null, 0, 0);
+            executeSearch(graphSearch(), graph, src, null, null, 0, new TestDoubleWeight(0));
         }
         long end = System.nanoTime();
         DecimalFormat fmt = new DecimalFormat("#,###");
diff --git a/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java b/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
index b5a415f..4d49048 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
@@ -16,6 +16,7 @@
 package org.onlab.graph;
 
 import static org.junit.Assert.*;
+import static org.onlab.graph.GraphTest.W1;
 
 import org.junit.Test;
 
@@ -32,15 +33,15 @@
     private static final TestVertex C = new TestVertex("C");
     private static final TestVertex D = new TestVertex("D");
 
-    private static final TestEdge AB = new TestEdge(A, B, 1.0);
-    private static final TestEdge BC = new TestEdge(B, C, 1.0);
-    private static final TestEdge AD = new TestEdge(A, D, 1.0);
-    private static final TestEdge DC = new TestEdge(D, C, 1.0);
+    private static final TestEdge AB = new TestEdge(A, B);
+    private static final TestEdge BC = new TestEdge(B, C);
+    private static final TestEdge AD = new TestEdge(A, D);
+    private static final TestEdge DC = new TestEdge(D, C);
 
-    private static final Path<TestVertex, TestEdge> ABC
-                            = new DefaultPath<>(ImmutableList.of(AB, BC), 1.0);
-    private static final Path<TestVertex, TestEdge> ADC
-                            = new DefaultPath<>(ImmutableList.of(AD, DC), 1.0);
+    private static final Path<TestVertex, TestEdge> ABC =
+            new DefaultPath<>(ImmutableList.of(AB, BC), W1);
+    private static final Path<TestVertex, TestEdge> ADC =
+            new DefaultPath<>(ImmutableList.of(AD, DC), W1);
 
     @Test
     public void testSwappingPrimarySecondaryDoesntImpactHashCode() {
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 6acc986..d860928 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -34,14 +34,34 @@
     static final TestVertex H = new TestVertex("H");
     static final TestVertex Z = new TestVertex("Z");
 
+    static final TestDoubleWeight ZW = new TestDoubleWeight(0);
+    static final TestDoubleWeight NW5 = new TestDoubleWeight(-5);
+    static final TestDoubleWeight NW2 = new TestDoubleWeight(-2);
+    static final TestDoubleWeight NW1 = new TestDoubleWeight(-1);
+    static final TestDoubleWeight W1 = new TestDoubleWeight(1);
+    static final TestDoubleWeight W2 = new TestDoubleWeight(2);
+    static final TestDoubleWeight W3 = new TestDoubleWeight(3);
+    static final TestDoubleWeight W4 = new TestDoubleWeight(4);
+    static final TestDoubleWeight W5 = new TestDoubleWeight(5);
+
     protected Graph<TestVertex, TestEdge> graph;
 
-    protected EdgeWeight<TestVertex, TestEdge> weight =
-            new EdgeWeight<TestVertex, TestEdge>() {
+    protected EdgeWeigher<TestVertex, TestEdge> weigher =
+            new EdgeWeigher<TestVertex, TestEdge>() {
                 @Override
-                public double weight(TestEdge edge) {
+                public Weight weight(TestEdge edge) {
                     return edge.weight();
                 }
+
+                @Override
+                public Weight getInitialWeight() {
+                    return ZW;
+                }
+
+                @Override
+                public Weight getNonViableWeight() {
+                    return TestDoubleWeight.NON_VIABLE_WEIGHT;
+                }
             };
 
     protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) {
@@ -55,12 +75,18 @@
     }
 
     protected Set<TestEdge> edges() {
-        return 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));
+        return of(new TestEdge(A, B, W1),
+                  new TestEdge(A, C, W3),
+                  new TestEdge(B, D, W2),
+                  new TestEdge(B, C, W1),
+                  new TestEdge(B, E, W4),
+                  new TestEdge(C, E, W1),
+                  new TestEdge(D, H, W5),
+                  new TestEdge(D, E, W1),
+                  new TestEdge(E, F, W1),
+                  new TestEdge(F, D, W1),
+                  new TestEdge(F, G, W1),
+                  new TestEdge(F, H, W1));
     }
 
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
index 2b7c8d1..ed92be9 100644
--- a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
@@ -41,12 +41,12 @@
     @Test
     public void noPath() {
         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)));
+                                          of(new TestEdge(A, B),
+                                             new TestEdge(B, A),
+                                             new TestEdge(C, D),
+                                             new TestEdge(D, C)));
         KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>();
-        GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weight, 1);
+        GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weigher, 1);
         Set<Path<TestVertex, TestEdge>> resultPathSet = result.paths();
         assertTrue("There should not be any paths.", resultPathSet.isEmpty());
     }
@@ -55,11 +55,11 @@
     public void testSinglePath() {
         //Tests that there is only a single path possible between A and B
         graph = new AdjacencyListsGraph<>(vertexes(), edges());
-        this.result = kShortestPathsSearch.search(graph, A, B, weight, 2);
+        this.result = kShortestPathsSearch.search(graph, A, B, weigher, 2);
         Iterator<Path<TestVertex, TestEdge>> itr = result.paths().iterator();
         assertEquals("incorrect paths count", 1, result.paths().size());
         List<TestEdge> correctEdgeList = Lists.newArrayList();
-        correctEdgeList.add(new TestEdge(A, B, 1));
+        correctEdgeList.add(new TestEdge(A, B, W1));
         assertTrue("That wrong path was returned.",
                    edgeListsAreEqual(correctEdgeList, result.paths().iterator().next().edges()));
     }
@@ -67,16 +67,16 @@
     @Test
     public void testTwoPath() {
         //Tests that there are only two paths between A and C and that they are returned in the correct order
-        result = kShortestPathsSearch.search(graph, A, C, weight, 3);
+        result = kShortestPathsSearch.search(graph, A, C, weigher, 3);
         assertTrue("There are an unexpected number of paths.", result.paths().size() == 2);
         Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
         List<TestEdge> correctEdgeList = Lists.newArrayList();
-        correctEdgeList.add(new TestEdge(A, B, 1));
-        correctEdgeList.add(new TestEdge(B, C, 1));
+        correctEdgeList.add(new TestEdge(A, B, W1));
+        correctEdgeList.add(new TestEdge(B, C, W1));
         assertTrue("The first path from A to C was incorrect.",
                    edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
         correctEdgeList.clear();
-        correctEdgeList.add(new TestEdge(A, C, 3));
+        correctEdgeList.add(new TestEdge(A, C, W3));
         assertTrue("The second path from A to C was incorrect.",
                    edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
     }
@@ -85,23 +85,23 @@
     public void testFourPath() {
         //Tests that there are only four paths between A and E and that they are returned in the correct order
         //Also tests the special case where some correct solutions are equal
-        result = kShortestPathsSearch.search(graph, A, E, weight, 5);
+        result = kShortestPathsSearch.search(graph, A, E, weigher, 5);
         assertTrue("There are an unexpected number of paths.", result.paths().size() == 4);
         Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
         List<TestEdge> correctEdgeList = Lists.newArrayList();
-        correctEdgeList.add(new TestEdge(A, B, 1));
-        correctEdgeList.add(new TestEdge(B, C, 1));
-        correctEdgeList.add(new TestEdge(C, E, 1));
+        correctEdgeList.add(new TestEdge(A, B, W1));
+        correctEdgeList.add(new TestEdge(B, C, W1));
+        correctEdgeList.add(new TestEdge(C, E, W1));
         assertTrue("The first path from A to E was incorrect.",
                    edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
         correctEdgeList.clear();
         //There are two paths of equal length that should hold positions two and three
         List<TestEdge> alternateCorrectEdgeList = Lists.newArrayList();
-        correctEdgeList.add(new TestEdge(A, C, 3));
-        correctEdgeList.add(new TestEdge(C, E, 1));
-        alternateCorrectEdgeList.add(new TestEdge(A, B, 1));
-        alternateCorrectEdgeList.add(new TestEdge(B, D, 2));
-        alternateCorrectEdgeList.add(new TestEdge(D, E, 1));
+        correctEdgeList.add(new TestEdge(A, C, W3));
+        correctEdgeList.add(new TestEdge(C, E, W1));
+        alternateCorrectEdgeList.add(new TestEdge(A, B, W1));
+        alternateCorrectEdgeList.add(new TestEdge(B, D, W2));
+        alternateCorrectEdgeList.add(new TestEdge(D, E, W1));
         List<TestEdge> candidateOne = edgeListIterator.next().edges();
         List<TestEdge> candidateTwo = edgeListIterator.next().edges();
         if (candidateOne.size() == 2) {
@@ -116,8 +116,8 @@
                        edgeListsAreEqual(candidateTwo, correctEdgeList));
         }
         correctEdgeList.clear();
-        correctEdgeList.add(new TestEdge(A, B, 1));
-        correctEdgeList.add(new TestEdge(B, E, 4));
+        correctEdgeList.add(new TestEdge(A, B, W1));
+        correctEdgeList.add(new TestEdge(B, E, W4));
         assertTrue("The fourth path rom A to E was incorrect",
                    edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
 
@@ -128,16 +128,16 @@
         //H is a sink in this topology, insure there are no paths from it to any other location
         for (TestVertex vertex : vertexes()) {
             assertTrue("There should be no paths from vertex H to any other node.",
-                       kShortestPathsSearch.search(graph, H, vertex, weight, 1).paths().size() == 0);
+                       kShortestPathsSearch.search(graph, H, vertex, weigher, 1).paths().size() == 0);
         }
     }
 
     @Test
     public void testLimitPathSetSize() {
         //Checks to make sure that no more than K paths are returned
-        result = kShortestPathsSearch.search(graph, A, E, weight, 3);
+        result = kShortestPathsSearch.search(graph, A, E, weigher, 3);
         assertTrue("There are an unexpected number of paths.", result.paths().size() == 3);
-        result = kShortestPathsSearch.search(graph, A, G, weight, 1);
+        result = kShortestPathsSearch.search(graph, A, G, weigher, 1);
         assertTrue("There are an unexpected number of paths.", result.paths().size() == 1);
     }
 
@@ -157,47 +157,45 @@
          * +---+       +---+ +---+  +---+
          */
         graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), of(
-                new TestEdge(A, B, 1),
-                new TestEdge(B, A, 1),
-                new TestEdge(B, C, 1),
-                new TestEdge(C, B, 1),
-                new TestEdge(C, D, 1),
-                new TestEdge(D, C, 1),
-                new TestEdge(D, E, 1),
-                new TestEdge(E, D, 1),
-                new TestEdge(E, H, 1),
-                new TestEdge(H, E, 1),
-                new TestEdge(H, G, 1),
-                new TestEdge(G, H, 1),
-                new TestEdge(G, F, 1),
-                new TestEdge(F, G, 1),
-                new TestEdge(F, B, 1),
-                new TestEdge(B, F, 1)
+                new TestEdge(A, B),
+                new TestEdge(B, A),
+                new TestEdge(B, C),
+                new TestEdge(C, B),
+                new TestEdge(C, D),
+                new TestEdge(D, C),
+                new TestEdge(D, E),
+                new TestEdge(E, D),
+                new TestEdge(E, H),
+                new TestEdge(H, E),
+                new TestEdge(H, G),
+                new TestEdge(G, H),
+                new TestEdge(G, F),
+                new TestEdge(F, G),
+                new TestEdge(F, B),
+                new TestEdge(B, F)
         ));
 
-        weight = edge -> 1.0;
-
         //Tests that there are only two paths between A and G and that they are returned in the correct order
-        result = kShortestPathsSearch.search(graph, A, G, weight, 5);
+        result = kShortestPathsSearch.search(graph, A, G, weigher, 5);
 
         assertEquals("There are an unexpected number of paths.", 2, result.paths().size());
 
         Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
 
         List<TestEdge> correctEdgeList = Lists.newArrayList();
-        correctEdgeList.add(new TestEdge(A, B, 1));
-        correctEdgeList.add(new TestEdge(B, F, 1));
-        correctEdgeList.add(new TestEdge(F, G, 1));
+        correctEdgeList.add(new TestEdge(A, B));
+        correctEdgeList.add(new TestEdge(B, F));
+        correctEdgeList.add(new TestEdge(F, G));
         assertTrue("The first path from A to G was incorrect.",
                 edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
 
         correctEdgeList.clear();
-        correctEdgeList.add(new TestEdge(A, B, 1));
-        correctEdgeList.add(new TestEdge(B, C, 1));
-        correctEdgeList.add(new TestEdge(C, D, 1));
-        correctEdgeList.add(new TestEdge(D, E, 1));
-        correctEdgeList.add(new TestEdge(E, H, 1));
-        correctEdgeList.add(new TestEdge(H, G, 1));
+        correctEdgeList.add(new TestEdge(A, B));
+        correctEdgeList.add(new TestEdge(B, C));
+        correctEdgeList.add(new TestEdge(C, D));
+        correctEdgeList.add(new TestEdge(D, E));
+        correctEdgeList.add(new TestEdge(E, H));
+        correctEdgeList.add(new TestEdge(H, G));
         assertTrue("The second path from A to G was incorrect.",
                 edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
     }
diff --git a/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
index 98b014c..07e4d05 100644
--- a/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
@@ -39,7 +39,7 @@
     }
 
     public void setDefaultWeights() {
-        weight = null;
+        weigher = null;
     }
 
     @Override
@@ -53,10 +53,10 @@
     @Test
     public void onePathPair() {
         setDefaultWeights();
-        TestEdge aB = new TestEdge(A, B, 1);
-        TestEdge bC = new TestEdge(B, C, 1);
-        TestEdge aD = new TestEdge(A, D, 1);
-        TestEdge dC = new TestEdge(D, C, 1);
+        TestEdge aB = new TestEdge(A, B);
+        TestEdge bC = new TestEdge(B, C);
+        TestEdge aD = new TestEdge(A, D);
+        TestEdge dC = new TestEdge(D, C);
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
                                                                       of(aB, bC, aD, dC));
         Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -65,7 +65,7 @@
         riskProfile.put(aD, 1);
         riskProfile.put(dC, 1);
         SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths();
         System.out.println("\n\n\n" + paths + "\n\n\n");
         assertEquals("one disjoint path pair found", 1, paths.size());
         checkIsDisjoint(paths.iterator().next(), riskProfile);
@@ -90,12 +90,12 @@
     @Test
     public void complexGraphTest() {
         setDefaultWeights();
-        TestEdge aB = new TestEdge(A, B, 1);
-        TestEdge bC = new TestEdge(B, C, 1);
-        TestEdge aD = new TestEdge(A, D, 1);
-        TestEdge dC = new TestEdge(D, C, 1);
-        TestEdge cE = new TestEdge(C, E, 1);
-        TestEdge bE = new TestEdge(B, E, 1);
+        TestEdge aB = new TestEdge(A, B);
+        TestEdge bC = new TestEdge(B, C);
+        TestEdge aD = new TestEdge(A, D);
+        TestEdge dC = new TestEdge(D, C);
+        TestEdge cE = new TestEdge(C, E);
+        TestEdge bE = new TestEdge(B, E);
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
                                                                       of(aB, bC, aD, dC, cE, bE));
         Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -106,18 +106,18 @@
         riskProfile.put(cE, 2);
         riskProfile.put(bE, 3);
         SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(4, riskProfile);
-        search.search(graph, A, E, weight, ALL_PATHS).paths();
+        search.search(graph, A, E, weigher, ALL_PATHS).paths();
     }
 
     @Test
     public void multiplePathGraphTest() {
         setDefaultWeights();
-        TestEdge aB = new TestEdge(A, B, 1);
-        TestEdge bE = new TestEdge(B, E, 1);
-        TestEdge aD = new TestEdge(A, D, 1);
-        TestEdge dE = new TestEdge(D, E, 1);
-        TestEdge aC = new TestEdge(A, C, 1);
-        TestEdge cE = new TestEdge(C, E, 1);
+        TestEdge aB = new TestEdge(A, B);
+        TestEdge bE = new TestEdge(B, E);
+        TestEdge aD = new TestEdge(A, D);
+        TestEdge dE = new TestEdge(D, E);
+        TestEdge aC = new TestEdge(A, C);
+        TestEdge cE = new TestEdge(C, E);
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
                                                                       of(aB, bE, aD, dE, aC, cE));
         Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -128,7 +128,7 @@
         riskProfile.put(aC, 4);
         riskProfile.put(cE, 5);
         SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(6, riskProfile);
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths();
         assertTrue("> one disjoint path pair found", paths.size() >= 1);
         checkIsDisjoint(paths.iterator().next(), riskProfile);
     }
@@ -136,10 +136,10 @@
     @Test
     public void onePath() {
         setDefaultWeights();
-        TestEdge aB = new TestEdge(A, B, 1);
-        TestEdge bC = new TestEdge(B, C, 1);
-        TestEdge aD = new TestEdge(A, D, 1);
-        TestEdge dC = new TestEdge(D, C, 1);
+        TestEdge aB = new TestEdge(A, B);
+        TestEdge bC = new TestEdge(B, C);
+        TestEdge aD = new TestEdge(A, D);
+        TestEdge dC = new TestEdge(D, C);
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
                                                                       of(aB, bC, aD, dC));
         Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -148,7 +148,7 @@
         riskProfile.put(aD, 1);
         riskProfile.put(dC, 0);
         SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths();
         System.out.println(paths);
         assertTrue("no disjoint path pairs found", paths.size() == 0);
     }
@@ -156,10 +156,10 @@
     @Test
     public void noPath() {
         setDefaultWeights();
-        TestEdge aB = new TestEdge(A, B, 1);
-        TestEdge bC = new TestEdge(B, C, 1);
-        TestEdge aD = new TestEdge(A, D, 1);
-        TestEdge dC = new TestEdge(D, C, 1);
+        TestEdge aB = new TestEdge(A, B);
+        TestEdge bC = new TestEdge(B, C);
+        TestEdge aD = new TestEdge(A, D);
+        TestEdge dC = new TestEdge(D, C);
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
                                                                       of(aB, bC, aD, dC));
         Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -168,7 +168,7 @@
         riskProfile.put(aD, 1);
         riskProfile.put(dC, 0);
         SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths();
         assertTrue("no disjoint path pairs found", paths.size() == 0);
     }
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
index a86546a..5d0a032 100644
--- a/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
@@ -34,17 +34,6 @@
         return new SuurballeGraphSearch<>();
     }
 
-    public void setWeights() {
-        weight = new EdgeWeight<TestVertex, TestEdge>() {
-            @Override
-            public double weight(TestEdge edge) {
-                return edge.weight();
-            }
-        };
-    }
-    public void setDefaultWeights() {
-        weight = null;
-    }
     @Override
     public void defaultGraphTest() {
 
@@ -57,41 +46,38 @@
 
     @Test
     public void basicGraphTest() {
-        setDefaultWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, C, 1),
-                                                                         new TestEdge(A, D, 1),
-                                                                         new TestEdge(D, C, 1)));
-        executeSearch(graphSearch(), graph, A, C, weight, 1, 4.0);
+                                                                      of(new TestEdge(A, B),
+                                                                         new TestEdge(B, C),
+                                                                         new TestEdge(A, D),
+                                                                         new TestEdge(D, C)));
+        executeSearch(graphSearch(), graph, A, C, null, 1, new ScalarWeight(4.0));
     }
 
     @Test
     public void multiplePathOnePairGraphTest() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, C, 1),
-                                                                         new TestEdge(A, D, 1),
-                                                                         new TestEdge(D, C, 1),
-                                                                         new TestEdge(B, E, 2),
-                                                                         new TestEdge(C, E, 1)));
-        executeSearch(graphSearch(), graph, A, E, weight, 1, 6.0);
+                                                                      of(new TestEdge(A, B, W1),
+                                                                         new TestEdge(B, C, W1),
+                                                                         new TestEdge(A, D, W1),
+                                                                         new TestEdge(D, C, W1),
+                                                                         new TestEdge(B, E, W2),
+                                                                         new TestEdge(C, E, W1)));
+        executeSearch(graphSearch(), graph, A, E, weigher, 1, new TestDoubleWeight(6.0));
     }
 
     @Test
     public void multiplePathsMultiplePairs() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, E, 1),
-                                                                         new TestEdge(A, C, 1),
-                                                                         new TestEdge(C, E, 1),
-                                                                         new TestEdge(A, D, 1),
-                                                                         new TestEdge(D, E, 1),
-                                                                         new TestEdge(A, E, 2)));
+                                                                      of(new TestEdge(A, B, W1),
+                                                                         new TestEdge(B, E, W1),
+                                                                         new TestEdge(A, C, W1),
+                                                                         new TestEdge(C, E, W1),
+                                                                         new TestEdge(A, D, W1),
+                                                                         new TestEdge(D, E, W1),
+                                                                         new TestEdge(A, E, W2)));
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                graphSearch().search(graph, A, E, weight, GraphPathSearch.ALL_PATHS);
+                graphSearch().search(graph, A, E, weigher, GraphPathSearch.ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         System.out.println("\n\n" + paths + "\n\n\ndone\n");
         assertEquals("incorrect paths count", 3, paths.size());
@@ -101,27 +87,25 @@
 
     @Test
     public void differingPrimaryAndBackupPathLengths() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, C, 1),
-                                                                         new TestEdge(A, D, 1),
-                                                                         new TestEdge(D, C, 1),
-                                                                         new TestEdge(B, E, 1),
-                                                                         new TestEdge(C, E, 1)));
-        executeSearch(graphSearch(), graph, A, E, weight, 1, 5.0);
+                                                                      of(new TestEdge(A, B),
+                                                                         new TestEdge(B, C),
+                                                                         new TestEdge(A, D),
+                                                                         new TestEdge(D, C),
+                                                                         new TestEdge(B, E),
+                                                                         new TestEdge(C, E)));
+        executeSearch(graphSearch(), graph, A, E, weigher, 1, new TestDoubleWeight(5.0));
     }
 
     @Test
     public void onePath() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, C, 1),
-                                                                         new TestEdge(A, C, 4),
-                                                                         new TestEdge(C, D, 1)));
+                                                                      of(new TestEdge(A, B, W1),
+                                                                         new TestEdge(B, C, W1),
+                                                                         new TestEdge(A, C, W4),
+                                                                         new TestEdge(C, D, W1)));
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+                graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         assertEquals("incorrect paths count", 1, paths.size());
         DisjointPathPair<TestVertex, TestEdge> dpp = (DisjointPathPair<TestVertex, TestEdge>) paths.iterator().next();
@@ -130,24 +114,22 @@
 
     @Test
     public void noPath() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
-                                                                      of(new TestEdge(A, B, 1),
-                                                                         new TestEdge(B, C, 1),
-                                                                         new TestEdge(A, C, 4)));
+                                                                      of(new TestEdge(A, B, W1),
+                                                                         new TestEdge(B, C, W1),
+                                                                         new TestEdge(A, C, W4)));
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+                graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         assertEquals("incorrect paths count", paths.size(), 0);
     }
 
     @Test
     public void disconnected() {
-        setWeights();
         Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
                                                                       of());
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+                graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         assertEquals("incorrect paths count", 0, paths.size());
     }
diff --git a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
index 2b6dec0..a3f47f5 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
@@ -49,14 +49,14 @@
     @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)));
+                                          of(new TestEdge(A, B),
+                                             new TestEdge(B, C),
+                                             new TestEdge(C, D),
+                                             new TestEdge(D, E),
+                                             new TestEdge(E, F),
+                                             new TestEdge(F, G),
+                                             new TestEdge(G, H),
+                                             new TestEdge(H, A)));
 
         TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
         SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
@@ -67,14 +67,14 @@
     @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)));
+                                          of(new TestEdge(A, B),
+                                             new TestEdge(B, C),
+                                             new TestEdge(C, D),
+                                             new TestEdge(D, A),
+                                             new TestEdge(E, F),
+                                             new TestEdge(F, G),
+                                             new TestEdge(G, H),
+                                             new TestEdge(H, E)));
         TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
         SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
         validate(result, 2);
@@ -85,15 +85,15 @@
     @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)));
+                                          of(new TestEdge(A, B),
+                                             new TestEdge(B, C),
+                                             new TestEdge(C, D),
+                                             new TestEdge(D, A),
+                                             new TestEdge(E, F),
+                                             new TestEdge(F, G),
+                                             new TestEdge(G, H),
+                                             new TestEdge(H, E),
+                                             new TestEdge(B, E)));
         TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
         SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
         validate(result, 2);
@@ -104,19 +104,21 @@
     @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)));
+                                          of(new TestEdge(A, B),
+                                             new TestEdge(B, C),
+                                             new TestEdge(C, D),
+                                             new TestEdge(D, A),
+                                             new TestEdge(E, F),
+                                             new TestEdge(F, G),
+                                             new TestEdge(G, H),
+                                             new TestEdge(H, E),
+                                             new TestEdge(B, E,
+                                                     weigher.getNonViableWeight()),
+                                             new TestEdge(E, B,
+                                                     weigher.getNonViableWeight())));
 
         TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
-        SccResult<TestVertex, TestEdge> result = gs.search(graph, weight);
+        SccResult<TestVertex, TestEdge> result = gs.search(graph, weigher);
         validate(result, 2);
         validate(result, 0, 4, 4);
         validate(result, 1, 4, 4);
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
new file mode 100644
index 0000000..54f9f17
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onlab.graph;
+
+import com.google.common.math.DoubleMath;
+
+import java.util.Objects;
+
+/**
+ * Test weight (based on double).
+ */
+public class TestDoubleWeight implements Weight {
+
+    /**
+     * Instance of negative test weight.
+     */
+    public static final TestDoubleWeight NEGATIVE_WEIGHT = new TestDoubleWeight(-1);
+
+    /**
+     * Instance of test weight to mark links/paths which
+     * can not be traversed.
+     */
+    public static final TestDoubleWeight NON_VIABLE_WEIGHT =
+            new TestDoubleWeight(Double.POSITIVE_INFINITY);
+
+    private final double value;
+
+    /**
+     * Creates a new test weight with the given double value.
+     * @param value double weight
+     */
+    public TestDoubleWeight(double value) {
+        this.value = value;
+    }
+
+    @Override
+    public Weight merge(Weight otherWeight) {
+        return new TestDoubleWeight(value + ((TestDoubleWeight) otherWeight).value);
+    }
+
+    @Override
+    public Weight subtract(Weight otherWeight) {
+        return new TestDoubleWeight(value - ((TestDoubleWeight) otherWeight).value);
+    }
+
+    @Override
+    public boolean isViable() {
+        return this != NON_VIABLE_WEIGHT;
+    }
+
+    @Override
+    public int compareTo(Weight otherWeight) {
+        return Double.compare(value, ((TestDoubleWeight) otherWeight).value);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        return (DoubleMath.fuzzyEquals(value, ((TestDoubleWeight) obj).value, 0.1));
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(value);
+    }
+
+    @Override
+    public boolean isNegative() {
+        return value < 0;
+    }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
index 7b48767..874b5eb 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
@@ -18,32 +18,45 @@
 import java.util.Objects;
 
 import static com.google.common.base.MoreObjects.toStringHelper;
+import static org.onlab.graph.GraphTest.W1;
 
 /**
  * Test edge.
  */
 public class TestEdge extends AbstractEdge<TestVertex> {
 
-    private final double weight;
+    private final Weight weight;
 
     /**
-     * Creates a new edge between the specified source and destination vertexes.
+     * Creates a new edge between the specified source and destination vertexes
+     * with the given weight.
      *
      * @param src    source vertex
      * @param dst    destination vertex
      * @param weight edge weight
      */
-    public TestEdge(TestVertex src, TestVertex dst, double weight) {
+    public TestEdge(TestVertex src, TestVertex dst, Weight weight) {
         super(src, dst);
         this.weight = weight;
     }
 
     /**
+     * Creates a new edge between the specified source and destination vertexes
+     * with the default weight.
+     *
+     * @param src source vertex
+     * @param dst destination vertext
+     */
+    public TestEdge(TestVertex src, TestVertex dst) {
+        this(src, dst, W1);
+    }
+
+    /**
      * Returns the edge weight.
      *
      * @return edge weight
      */
-    public double weight() {
+    public Weight weight() {
         return weight;
     }