Changeset ebbe941


Ignore:
Timestamp:
Dec 21, 2022, 2:46:01 PM (16 months 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:
1 edited

Legend:

Unmodified
Added
Removed
  • benchmark/convoy/genConvoyStats.py

    r1afda5a2 rebbe941  
    111111    global handoff, maxCycle, maxCycleSum
    112112
    113     # print("CurrNode: " + str(currNode))
     113    # print("CurrNode: " + str(currNode) + " StartNode: " + str(startNode))
    114114    # print(currCycle)
    115115    # if we visit a node from a previous call then return since we have already
     
    121121    # found a cycle
    122122    if visited[currNode]:
     123        # if currNode == startNode:
    123124        # print("LocalVisited, curr: " + str(currSum) + ", max: " + str(maxCycleSum) + ", Start: " + str(startNode) )
    124125        # if the cycle contains the start node check if it is our new max cycle
     
    130131
    131132    visited[currNode] = True
    132 
     133    # print(visited)
    133134    for idx, val in enumerate(handoff[currNode]):
    134135        # continue if no edge
    135         if val == 0:
    136             continue
     136        # if val == 0:
     137        #     continue
    137138
    138139        currCycle.append(currNode)
    139140        findLargestCycle(startNode, idx, visited, globalVisited, currSum + val, currCycle)
    140141        currCycle.pop()
    141 
     142    # print(currNode)
    142143    visited[currNode] = False
    143144
     
    147148    global handoff, sumPerRow, handoffTotal, maxCycle, maxCycleSum, minBound, maxBound, expected
    148149    currThds = len(handoff)
    149        
     150   
     151
     152    # This is NP-Hard and is currently not tractable so we just estimate the largest cycle
     153    # the code to do so is commented below
     154
    150155    # find largest cycle
    151     globalVisited = [False] * currThds
     156    # globalVisited = [False] * currThds
     157    # for i in range(currThds):
     158    #     # print(i)
     159    #     visited = [False] * currThds
     160    #     findLargestCycle(i, i, visited, globalVisited, 0, [])
     161    #     globalVisited[i] = True
     162
     163    # # calculate stats
     164    # cycleHandoffs = []
     165    # cycleHandoffs.append(handoff[maxCycle[-1]][maxCycle[0]])
     166    # sumOfMaxCycleRows = sumPerRow[maxCycle[0]]
     167
     168    # # expected handoff is MULT P( handoff ) for each handoff in max cycle
     169    # expectedConvoy = handoff[maxCycle[-1]][maxCycle[0]] / sumPerRow[maxCycle[-1]]
     170    # for idx, val in enumerate(maxCycle[1:]):
     171    #     cycleHandoffs.append(handoff[maxCycle[idx]][val])
     172    #     sumOfMaxCycleRows += sumPerRow[val]
     173    #     expectedConvoy = expectedConvoy * handoff[maxCycle[idx]][val] / sumPerRow[maxCycle[idx]]
     174
     175    # # adjust expected bound
     176    # # if max cycle contains all nodes, sumOfMaxCycleRows / handoffTotal == 1
     177    # # else this adjusts the expected bound to compensate for the cycle not visiting all nodes
     178    # # also mult by 100 to turn into percentage from decimal
     179    # expectedConvoy = expectedConvoy * sumOfMaxCycleRows * 100 / handoffTotal
     180
     181    ################################
     182
     183    #start of approximation code is here:
     184
     185    # instead we take the maximum handoff from each row and assume it is all a cycle as an approximation
     186    maxCycle = []
     187    maxCycleSum = 0
     188    cycleHandoffs = []
     189    expectedConvoy = 100
    152190    for i in range(currThds):
    153         visited = [False] * currThds
    154         findLargestCycle(i, i, visited, globalVisited, 0, [])
    155         globalVisited[i] = True
    156    
    157     # calculate stats
    158     cycleHandoffs = []
    159     cycleHandoffs.append(handoff[maxCycle[-1]][maxCycle[0]])
    160     sumOfMaxCycleRows = sumPerRow[maxCycle[0]]
    161 
    162     # expected handoff is MULT P( handoff ) for each handoff in max cycle
    163     expectedConvoy = handoff[maxCycle[-1]][maxCycle[0]] / sumPerRow[maxCycle[-1]]
    164     for idx, val in enumerate(maxCycle[1:]):
    165         cycleHandoffs.append(handoff[maxCycle[idx]][val])
    166         sumOfMaxCycleRows += sumPerRow[val]
    167         expectedConvoy = expectedConvoy * handoff[maxCycle[idx]][val] / sumPerRow[maxCycle[idx]]
    168 
    169     # adjust expected bound
    170     # if max cycle contains all nodes, sumOfMaxCycleRows / handoffTotal == 1
    171     # else this adjusts the expected bound to compensate for the cycle not visiting all nodes
    172     # also mult by 100 to turn into percentage from decimal
    173     expectedConvoy = expectedConvoy * sumOfMaxCycleRows * 100 / handoffTotal
     191        currMax = max(handoff[i])
     192        maxCycle.append(i)
     193        cycleHandoffs.append(currMax)
     194        maxCycleSum += currMax
     195        expectedConvoy = expectedConvoy * currMax / sumPerRow[i]
     196
     197    sumOfMaxCycleRows = handoffTotal
     198
     199    # end of approximation code
     200    ###################################################
    174201
    175202    # upper bound is the percentage of all handoffs that occur in the maximum possible cycle
Note: See TracChangeset for help on using the changeset viewer.