Changeset ebbe941

Timestamp:

Dec 21, 2022, 2:46:01 PM (2 years ago)

Author:

caparsons <caparson@…>

Branches:

ADT, ast-experimental, master

Children:

df9e412

Parents:

1afda5a2

Message:

changed algorithm to approximation since max cycle finding is NP-hard

File:

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

benchmark/convoy/genConvoyStats.py

@@ -111 +111 @@
     global handoff, maxCycle, maxCycleSum
 
-    # print("CurrNode: " + str(currNode))
+    # print("CurrNode: " + str(currNode) + " StartNode: " + str(startNode))
     # 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
@@ -130 +131 @@
 
     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
 
@@ -147 +148 @@
     global handoff, sumPerRow, handoffTotal, maxCycle, maxCycleSum, minBound, maxBound, expected
     currThds = len(handoff)
-        
+    
+
+    # 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
+    # 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
+    cycleHandoffs = []
+    expectedConvoy = 100
     for i in range(currThds):
-        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
+        currMax = max(handoff[i])
+        maxCycle.append(i)
+        cycleHandoffs.append(currMax)
+        maxCycleSum += currMax
+        expectedConvoy = expectedConvoy * currMax / sumPerRow[i]
+
+    sumOfMaxCycleRows = handoffTotal
+
+    # end of approximation code
+    ###################################################
 
     # upper bound is the percentage of all handoffs that occur in the maximum possible cycle