PathComputation { public List<RouteViewerPath> maxBandwidth(Graph<String, RouteViewerPath> networkGraph, String src, String dst, Long maxHop) { Map<String, Long> hopCount = new HashMap<>(); Map<String, RouteViewerPath> pre = new HashMap<>(); hopCount.put(src, (long) 0); List<RouteViewerPath> paths = new ArrayList<>(networkGraph.getEdges()); Collections.sort(paths, new Comparator<RouteViewerPath>() { @Override public int compare(RouteViewerPath x, RouteViewerPath y) { return (Objects.equals(x.bandwidth, y.bandwidth) ? 0 : (x.bandwidth > y.bandwidth ? -1 : 1)); } }); Graph<String, RouteViewerPath> graph = new SparseMultigraph<>(); for (String eachNode : networkGraph.getVertices()) graph.addVertex(eachNode); for (RouteViewerPath eachPath : paths) { String srcNode = extractNodeId(eachPath.src.getValue()); String dstNode = extractNodeId(eachPath.dst.getValue()); graph.addEdge(eachPath, srcNode, dstNode, EdgeType.DIRECTED); if (hopCount.containsKey(srcNode)) { LinkedList<String> queue = new LinkedList<>(); queue.add(srcNode); while (!queue.isEmpty()) { srcNode = queue.pop(); if (graph.getOutEdges(srcNode) != null) { for (RouteViewerPath outPath : graph.getOutEdges(srcNode)) { dstNode = extractNodeId(outPath.dst.getValue()); if (!hopCount.containsKey(dstNode) || (hopCount.get(dstNode) > hopCount.get(srcNode) + 1)) { queue.push(dstNode); hopCount.put(dstNode, hopCount.get(srcNode) + 1); pre.put(dstNode, outPath); } } } } if (hopCount.containsKey(dst) && hopCount.get(dst) <= maxHop) { List<RouteViewerPath> output = new LinkedList<>(); output.add(0, pre.get(dst)); while (!extractNodeId(output.get(0).src.getValue()).equals(src)) { dst = extractNodeId(output.get(0).src.getValue()); output.add(0, pre.get(dst)); } return output; } } } return null; } PathComputation(NetworkTrackerService networkTrackerService); List<TpId> shortestPath(TpId srcTpId, TpId dstTpId, Topology topology,
                                   final List<ConstraintMetric> constraintMetrics); List<TpId> maxBandwidthPath(TpId srcTpId, TpId dstTpId, Topology topology,
                                       final List<ConstraintMetric> constraintMetrics); List<TpId> shortestPathOpti(TpId srcTpId, TpId dstTpId, Topology topology, List<ConstraintMetric> constraintMetrics); List<TpId> maxBandwidthPathOpti(TpId srcTpId, TpId dstTpId, Topology topology, List<ConstraintMetric> constraintMetrics); List<RouteViewerPath> maxBandwidth(Graph<String, RouteViewerPath> networkGraph, String src, String dst, Long maxHop); static String extractNodeId(String nodeConnectorId);  }
@Test public void onTestMaxBandwidth() { Graph<String, RouteViewerPath> networkGraph = new SparseMultigraph<>(); for (int i = 0; i < 5; ++i) { networkGraph.addVertex("openflow:"+i); } addEdge(networkGraph, getTp(0, 0), getTp(1, 0), (long) 10); addEdge(networkGraph, getTp(1, 1), getTp(2, 0), (long) 100); addEdge(networkGraph, getTp(2, 1), getTp(3, 0), (long) 100); addEdge(networkGraph, getTp(3, 1), getTp(4, 0), (long) 100); addEdge(networkGraph, getTp(4, 1), getTp(5, 0), (long) 10); addEdge(networkGraph, getTp(1, 2), getTp(6, 0), (long) 5); addEdge(networkGraph, getTp(6, 1), getTp(4, 2), (long) 5); List<RouteViewerPath> output = pathComputer.maxBandwidth(networkGraph, getNode(0), getNode(5), (long) 4); LinkedList<String> result = new LinkedList<>(); result.add(getTp(0, 0)); result.add(getTp(1, 2)); result.add(getTp(6, 1)); result.add(getTp(4, 1)); Assert.assertEquals(4, output.size()); for (int i = 0; i < 4; ++i) { Assert.assertEquals(result.get(i), output.get(i).src.getValue()); } }