Changes in / [df9e412:49db841]

File:

• benchmark/convoy/genConvoyStats.py (modified) (4 diffs)

benchmark/convoy/genConvoyStats.py

@@ -111 +111 @@
     global handoff, maxCycle, maxCycleSum
 
-    # print("CurrNode: " + str(currNode) + " StartNode: " + str(startNode))
+    # print("CurrNode: " + str(currNode))
     # print(currCycle)
     # if we visit a node from a previous call then return since we have already
@@ -121 +121 @@
     # found a cycle
     if visited[currNode]:
-        # if currNode == startNode:
         # print("LocalVisited, curr: " + str(currSum) + ", max: " + str(maxCycleSum) + ", Start: " + str(startNode) )
         # if the cycle contains the start node check if it is our new max cycle
@@ -131 +130 @@
 
     visited[currNode] = True
-    # print(visited)
+
     for idx, val in enumerate(handoff[currNode]):
         # continue if no edge
-        # if val == 0:
-        #     continue
+        if val == 0:
+            continue
 
         currCycle.append(currNode)
         findLargestCycle(startNode, idx, visited, globalVisited, currSum + val, currCycle)
         currCycle.pop()
-    # print(currNode)
+
     visited[currNode] = False
 
@@ -148 +147 @@
     global handoff, sumPerRow, handoffTotal, maxCycle, maxCycleSum, minBound, maxBound, expected
     currThds = len(handoff)
+        
+    # find largest cycle
+    globalVisited = [False] * currThds
+    for i in range(currThds):
+        visited = [False] * currThds
+        findLargestCycle(i, i, visited, globalVisited, 0, [])
+        globalVisited[i] = True
     
-
-    # This is NP-Hard and is currently not tractable so we just estimate the largest cycle
-    # the code to do so is commented below
-
-    # find largest cycle
-    # globalVisited = [False] * currThds
-    # for i in range(currThds):
-    #     # print(i)
-    #     visited = [False] * currThds
-    #     findLargestCycle(i, i, visited, globalVisited, 0, [])
-    #     globalVisited[i] = True
-
-    # # calculate stats
-    # cycleHandoffs = []
-    # cycleHandoffs.append(handoff[maxCycle[-1]][maxCycle[0]])
-    # sumOfMaxCycleRows = sumPerRow[maxCycle[0]]
-
-    # # expected handoff is MULT P( handoff ) for each handoff in max cycle
-    # expectedConvoy = handoff[maxCycle[-1]][maxCycle[0]] / sumPerRow[maxCycle[-1]]
-    # for idx, val in enumerate(maxCycle[1:]):
-    #     cycleHandoffs.append(handoff[maxCycle[idx]][val])
-    #     sumOfMaxCycleRows += sumPerRow[val]
-    #     expectedConvoy = expectedConvoy * handoff[maxCycle[idx]][val] / sumPerRow[maxCycle[idx]]
-
-    # # adjust expected bound
-    # # if max cycle contains all nodes, sumOfMaxCycleRows / handoffTotal == 1
-    # # else this adjusts the expected bound to compensate for the cycle not visiting all nodes
-    # # also mult by 100 to turn into percentage from decimal
-    # expectedConvoy = expectedConvoy * sumOfMaxCycleRows * 100 / handoffTotal
-
-    ################################
-
-    #start of approximation code is here:
-
-    # instead we take the maximum handoff from each row and assume it is all a cycle as an approximation
-    maxCycle = []
-    maxCycleSum = 0
+    # calculate stats
     cycleHandoffs = []
-    expectedConvoy = 100
-    for i in range(currThds):
-        currMax = max(handoff[i])
-        maxCycle.append(i)
-        cycleHandoffs.append(currMax)
-        maxCycleSum += currMax
-        expectedConvoy = expectedConvoy * currMax / sumPerRow[i]
-
-    sumOfMaxCycleRows = handoffTotal
-
-    # end of approximation code
-    ###################################################
+    cycleHandoffs.append(handoff[maxCycle[-1]][maxCycle[0]])
+    sumOfMaxCycleRows = sumPerRow[maxCycle[0]]
+
+    # expected handoff is MULT P( handoff ) for each handoff in max cycle
+    expectedConvoy = handoff[maxCycle[-1]][maxCycle[0]] / sumPerRow[maxCycle[-1]]
+    for idx, val in enumerate(maxCycle[1:]):
+        cycleHandoffs.append(handoff[maxCycle[idx]][val])
+        sumOfMaxCycleRows += sumPerRow[val]
+        expectedConvoy = expectedConvoy * handoff[maxCycle[idx]][val] / sumPerRow[maxCycle[idx]]
+
+    # adjust expected bound
+    # if max cycle contains all nodes, sumOfMaxCycleRows / handoffTotal == 1
+    # else this adjusts the expected bound to compensate for the cycle not visiting all nodes
+    # also mult by 100 to turn into percentage from decimal
+    expectedConvoy = expectedConvoy * sumOfMaxCycleRows * 100 / handoffTotal
 
     # upper bound is the percentage of all handoffs that occur in the maximum possible cycle