<reponame>blake-harrison/access-graph
#!/usr/bin/env python3

__author__ = "<NAME>"
__copyright__ = "Copyright 2021"
__credits__ = [""]
__license__ = "GPLv3"
__version__ = "1.5.2"
__maintainer__ = ""
__email__ = "<EMAIL>"
__status__ = "Release"
#This program was built using python v3.9.0. It has not been tested with earlier versions

import sys
import os.path
import os
import copy
import contextlib

#note - numpy is used for array handling for the graph
#if you do not have this package installed, run:
#pip install numpy
#from a terminal
import numpy as np

#defines infinity as a global constant
#approximated at 9,999,999 because we assume no single 
#   path length will come close to this
#this can be adjusted to account for larger size values
INF = 9999999

#reads in the input file
#takes 5 parameters:
#   inFile - the name of the input file
#   G - list to hold the grocery stores (nodes)
#   R - list to hold the residential areas (nodes)
#   I - list to hold the intersections (nodes)
#   E - list to hold the roads (edges)
def readFile(inFile, G, R, I, E):
    #first checks if the file exists in the current folder
    if (os.path.exists(inFile)):
        #opens the input file
        with (open(inFile,'r')) as file:
            isNodes = True
            ln = 0
            for line in file:
                ln += 1
                
                #designates the start of the edges
                if line[0] == '<' and line[1] == 'E':
                    isNodes = False
                    
                #if nodes are being read in (default case)
                if isNodes:
                    #ignores the <NODES> designator
                    if line[0] == '<' and line[1] == 'N':
                        continue
                    #case: grocery store
                    elif line[0] == 'G':
                        G.append(line.replace("\n",""))
                    #case: residential area
                    elif line[0] == 'R':
                        R.append(line.replace("\n",""))
                    #case: intersection
                    elif line[0] == 'I':
                        I.append(line.replace("\n",""))
                    #case: invalid input
                    else: sys.exit("    Error: Invalid Input Detected on Line " + str(ln) + " in file '" + inFile + "'\n")
                
                #if edges are being read in
                else:
                    #ignores the <EDGES> designator
                    if line[0] == '<' and line[1] == 'E':
                        continue
                    #reads in a node
                    else: 
                        E.append(line.replace("\n",""))     
    else:
        os.system('cls' if os.name == 'nt' else 'clear') 
        sys.exit("    Error: Invalid Input File Name: '" + inFile + "' could not be found.")           

#prints the lists - used primarily for debugging purposes
#takes in 4 lists:
#   G (the grocery stores) 
#   R (residential areas) 
#   I (intersections) (our artificial nodes for connectivity purposes)
#   E (roads (edges))           
def printLists(G,R,I,E):
    print("\nG = ", G)
    print("R = ", R)
    print("I = ", I)
    print("E = ", E)
    print("\n")

#loads all of the nodes into one list:
#takes in 4 lists:
#   G (the grocery stores) 
#   R (residential areas) 
#   I (intersections) (our artificial nodes for connectivity purposes)
#   N (a list that will be filled all of the nodes)      
#       note: other functions require that the nodes be loaded in this order,
#       or they will not function correctly
def loadNodes(G,R,I,N):
    for x in range(len(G)):
        N.append(G[x][0])
    for x in range(len(R)):
        N.append(R[x][0])
    for x in range(len(I)):
        N.append(I[x][0])

#turns the lists of nodes and edges into one graph
#takes in 2 lists:
#   N (all the nodes)
#   E (all the edges)
#
#returns a two-dimensional list acting as the graph
def prepGraph(N,E):
    
    #sets up an empty array of correct dimensions
    #fills the array with the value nan as a placeholder
    graph=np.empty((int(len(N)),int(len(N)))) * np.nan
    
    #loops through the edges, initializing the graph
    for x in range(len(E)):
        start = E[x][0]
        stop = E[x][1]
        dist = E[x][2]
        graph[N.index(start)][N.index(stop)] = float(dist)
    #IMPORTANT: this is set up to treat every edge as undirected
    #   need to implement a fix to allow for directed nodes  
    for x in range(len(E)):
        start = E[x][1]
        stop = E[x][0]
        dist = E[x][2]
        graph[N.index(start)][N.index(stop)] = float(dist)
    return graph

#Computes the floyd-warshall algorithm with the given graph
#   the input graph should hold an adjacency matrix for all the nodes
#   returns path, the completed floyd-warshall matrix
#       each [x][y] holds the shortest distance from node x to node y
def pathGraph(graph):
    #creates a deep copy of graph to prevent shallow copy errors
    path = copy.deepcopy(graph)
    
    for x in range(len(path)):
        for y in range(len(path)):
            for z in range(len(path)):
                #shortest distance from node to itself will always be nan
                if(y==z):
                    continue
                else: 
                    
                    #sums the distances betwen the next two edges, treating nan as 0
                    #NOTE - this is probably going to cause errors if [y][x] is nan and 
                    #   [x][z] is not (or vice versa) - test this more
                    nextEdge = np.nansum(path[y][x]+path[x][z])
                    
                    #both of the next two edges are nan
                    if(not nextEdge):
                        nextEdge = INF
                        
                    #gets the minimum value between path[y][z] and nextEdge
                    hold = np.nanmin([path[y][z],nextEdge])
                    
                    #if hold is INF or nan, then no path exists between the two nodes
                    #otherwise, sets [y][z] to hold 
                    if(hold!=INF and hold!=np.nan):
                        path[y][z]=hold
    return path           

#finds the average distance from a node to a range of other nodes
#takes in the graph and 3 integers (graph indicies):
#   start is the index of the first element in the range
#   stop is the index of the last element in the range
#   num is the number of elements to take from the range,
#       prioritizing the nearest nodes
#   node is the point of origin
#   returns the average distance from node to a number of nodes (num)
#       from graph, in that range (start,stop)
#   If 
def avgDist(graph,start,stop,num,node):
    hold = []
    short = []
    nanCount = 0
    pathSum = 0
    
    #if num is not a valid input
    if(num > stop-start or num <= 0):
        sys.exit("    Error: Improper Number of Nodes Requested. You must request a numer of nodes greater than 0 but less than or equal to the amount of G-nodes the graph has.\n Your graph has " + str(stop-start) + " G-nodes.\n You requrested " + str(num) + " G-nodes.\n")  
    
    #appends hold with the lengths of all existing paths
    for x in range(start,stop):
        if(graph[node][x]!=np.nan):
            hold.append(graph[node][x])
    
    #appends short with each length in order from shortest to longest
    #after a value has been added, it is set to our infinity approximation
    val = INF
    hold.append(val)
    for y in range(len(hold)):
        val = np.nanmin(hold)
        if(val!=INF and val!=np.nan):
            short.append(val)
        if(val == np.nan or val=='nan'):
            continue
        else:
            hold[hold.index(val)]=INF
        
    #handles if the amount of added path lengths are less than the requested number
    # (this should only be true if the node does not have a path to some of the nodes
    #  in the start-stop range)
    if(len(short)<=num):
        num = len(short)
    
    if(num == 0):
        return 0    
    #sums the num smallest lengths
    for z in range(num):
        pathSum += short[z]
    return pathSum/num

#returns an ordered list of all the nodes R ranked by average distance to G nodes
#takes in:
#   graph, a the final shortest path matrix
#   G, the number of nodes that correspond to grocery stores
#   R, the number of nodes that correspond to residential areas
#   num, the number of grocery stores to get for each residential area
#       (prioritizing the nearest grocery stores)
#   top, the number of elements to return
#   close, a boolean that returns the nodes with the farthest avg distance if false, and 
#       the least average distance if true.
#       By default, this value is set to false
def getIsol(graph,G,R,num,close = False):
    hold = []
    order = []
    
    #calculates the average distance to the grocery stores for each residential node
    for i in range(G,G+R):
        hold.append([avgDist(graph,0,G,num,i),i])
    
    #orders the nodes by the shortest avg distance to num grocery stores
    for j in range(len(hold)):
        val = hold[j][0]
        sIndex = j
        for k in range(len(hold)):
            if(val>hold[k][0] and hold[k][0]!=INF):
                val=hold[k][0]
                sIndex = k
        order.append(copy.deepcopy(hold[sIndex]))
        hold[sIndex][0] = INF
        
    #if the user wants the closest instead of farthest
    if(close):
        rev = []
        #copies the list in reverse
        #probably more efficient ways to do this, maybe fix it later
        for x in range(len(order)):
            rev.append(copy.deepcopy(order[len(order)-1-x]))
        return rev
    #default setting
    else:
        return order

#outputs a number of results
#takes in several parameters:
#   R is the list of residential area nodes
#   order is a list containing each residential node
#       and its average distance to a set number of G-nodes
#       Order is obtained from the getIsol function
#   gNum is the number of G-nodes
#   top is the number of results to output
#       by default this is set to the length of order (printing all results)
def getTop(R, order, gNum, top = INF):
    print("Residential Area     Average Distance to Grocery Store")
    
    #default setting, prints all 
    if top > len(order):
        top = len(order)
    for x in range(top):
        printStr = ""
        numStr = ""
        
        #takes the length of each string in R, ignores the R### code
        for y in range(1,len(R[order[x][1]-gNum])):
            printStr += str(R[order[x][1]-gNum][y])
            printStr += " "
        printStr = printStr.ljust(30) 
        #adds the average distance
        numStr += str("{:.4f}".format(order[x][0]/1000))
        numStr += " km"
        printStr += numStr.rjust(5)
        print(printStr)       

def main():
    run = True
    badInput = False    
    inFile = ""
    #creates lists to hold each set of nodes
    G = [] #holds grocery stores
    R = [] #holds residential areas
    I = [] #holds intersections
    E = [] #holds edges
    opt = [False,True,INF,'5']
    optInput = '5'
    oFile = "output.txt"
    
    while(run):
        userIn = printMenu(badInput,inFile)
        if(userIn == '1'):
            G.clear()
            R.clear()
            I.clear()
            E.clear()
            badInput = False
            os.system('cls' if os.name == 'nt' else 'clear')
            
            #reads the input file in
            inFile = input("\n    Please Enter the Name of Your Datafile:\n\n\n\n")
            readFile(inFile,G,R,I,E)
        
            #splits each item in each list on spaces
            #i.e. ["R001 RA One"] becomes ["R001","RA","One"] 
            for x in range(0,len(G)):
                G[x] = G[x].split()
            for x in range(0,len(R)):
                R[x] = R[x].split()
            for x in range(0,len(I)):
                I[x] = I[x].split()
            for x in range(0,len(E)):
                E[x] = E[x].split()
                
            #adds a list that holds N, which contains all the nodes
            N=[]
            N.clear()
            loadNodes(G,R,I,N)
    
            #gets the adjacency matrix
            graph=prepGraph(N,E) 
    
            #gets the Floyd-Warshall matrix from the adjacency matrix
            path = pathGraph(graph)
            
            print("\n\n\n    File Loaded Successfully")
            print("\n\n\n\n\n\n\n")
            input("    Press Enter to Continue...")
                
        elif(userIn == '2'):
            os.system('cls' if os.name == 'nt' else 'clear')
            if(inFile == ""):
                print("\n    Error: No Input File Specified\n\n\n\n")
                input("    Press Enter to Continue...")
                continue
            
            #gets the average distance to a number of grocery stores for each node,
            #   then orders them from most avg dist to greatest
            num = int(opt[3])
            #if the requested number of grocery stores is greater than the number
            #   present in the data set, sets it to all
            if(num > len(G)):
                num = len(G)
            order = []
            order.clear()
            #print(len(G),len(R),num,opt[1])
            order = getIsol(path,len(G),len(R),num,opt[1])
            
            #prints the output
            if(not opt[0]):
                print("\n")
                getTop(R,order,len(G),int(opt[2]))
                print("\n\n\n")
                input("    Press Enter to Continue...")
            else:
                #creates file if it doesn't exist:
                with open(oFile,'w') as file:
                    with contextlib.redirect_stdout(file):
                        getTop(R,order,len(G),int(opt[2]))
                print("\n    Output Sent to file: " + oFile + "\n\n\n")
                print("\n\n\n")
                input("    Press Enter to Continue...")
        
        elif(userIn == '3'):
            optInput = '6'
            bad = False
            while(optInput != '5'):
                os.system('cls' if os.name == 'nt' else 'clear')
                optInput = optionsMenu(opt,oFile,bad)
                if(optInput == '1'):
                    bad = False
                    if(opt[0] == False):
                        opt[0] = True
                        os.system('cls' if os.name == 'nt' else 'clear')
                        oFile = input("\n    Please enter a name for the output file:\n\n\n")
                    else:
                        opt[0] = False
                elif(optInput == '2'):
                    bad = False
                    if(opt[1] == False):
                        opt[1] = True
                    else:
                        opt[1] = False
                elif(optInput == '3'):
                    bad = False
                    setOptNum = True
                    setOpt = '0'
                    while(setOptNum):
                        if(not setOpt.isnumeric()):
                            print("Error: You Must Input a Number")
                        os.system('cls' if os.name == 'nt' else 'clear')
                        setOpt = input("\n    Input a numeric value, or 'all':\n\n\n")
                        if(not setOpt.isnumeric() or setOpt.lower() != 'all'):
                            setOptNum = False
                        if(setOpt.isnumeric()):
                            opt[2] = setOpt
                        elif(setOpt.lower() == 'all'):
                            opt[2] = INF
                elif(optInput == '4'):
                    bad = False
                    setOptNum = True
                    while(setOptNum):
                        if(not opt[3].isnumeric()):
                            print("Error: You Must Input a Number")
                        os.system('cls' if os.name == 'nt' else 'clear')
                        setOpt = input("\n    Input a numeric value:\n\n\n")
                        if(not setOpt.isnumeric()):
                            setOptNum = True
                        if(setOpt.isnumeric()):
                            opt[3] = setOpt
                            setOptNum = False
                elif(optInput == '5'):
                    bad = False
                else:
                    bad = True
        
        elif(userIn == '4'):
            os.system('cls' if os.name == 'nt' else 'clear')
            run = False
        
        elif(userIn == '13'):
            debugNow = True
            os.system('cls' if os.name == 'nt' else 'clear')
            while(debugNow):
                getNum = devMenu()
                os.system('cls' if os.name == 'nt' else 'clear')
                if(getNum == '0'):
                    print("\n\n\n   G = \n")
                    print(G)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '1'):
                    print("\n\n\n   R = \n")
                    print(R)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '2'):
                    print("\n\n\n   I = \n")
                    print(I)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '3'):
                    print("\n\n\n   E = \n")
                    print(E)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '4'):
                    print("\n\n\n   N = \n")
                    print(N)
                elif(getNum == '5'):
                    print("\n\n\n   graph = \n")
                    print(graph)
                    input("\n    Press Enter to Continue...")
                elif(getNum == '6'):
                    print("\n\n\n   path = \n")
                    print(path)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '7'):
                    debugNow = False
        
        else:
            badInput = True
    
#prints the user menu
#   badInput is a boolean triggered if the user sends bad input
#   inFile is the current input file
#   if not called with a file name, assumes there is no loaded file
def printMenu(badInput = False, inFile = ""):
    if inFile == "":
        inFile = "No File Loaded"
    os.system('cls' if os.name == 'nt' else 'clear')
    print("""   
              _____ _____ ______  _____ _____ 
        /\   / ____/ ____|  ____|/ ____/ ____|
       /  \ | |   | |    | |__  | (___| (___  
      / /\ \| |   | |    |  __|  \___ \\___  \ 
     / ____ | |___| |____| |____ ____) ____) |
    /______\_______\_____|____________|_____/ 
     / ____|  __ \    /\   |  __ \| |  | |    
    | |  __| |__) |  /  \  | |__) | |__| |    
    | | |_ |  _  /  / /\ \ |  ___/|  __  |    
    | |__| | | \ \ / ____ \| |    | |  | |    
     \_____|_|  \_/_/    \_|_|    |_|  |_|                                          
                                                  """)
    print("""\
    WELCOME TO ACCESS GRAPH, v1.5.2
    https://github.com/blake-harrison/access-graph
        
    Please select:
            
    1) Read New File
        
    2) Get Output
        
    3) Settings
        
    4) Quit
        
        """)
    print("\n    Current Input File: " + inFile + "\n\n")
    
    if(badInput):
        print("\n   Error: Invalid Input. Please Try Again\n\n")
    
    return input()

#prints the user's options for settings
#   opts is a list of options
#   each corresponds to an option in the menu below
#   default values for opt are:
#       opt[0] = false
#       opt[1] = false
#       opt[2] = INF (All)
#   oFile is the output file specified (defaults to output.txt)
#   bad is True if the user input does not correspond to one of the options
def optionsMenu(opt, oFile = "output.txt", bad = False):
    print("\n    Options:\n")
    print("\n    Select Number to Toggle, and Press Enter to Confirm:\n\n")
    
    print("    1) Output Format:\n")
    if(not opt[0]):
        print("      [X] To User         [ ] To File ")
    else:
        print("      [ ] To User         [X] To File ")
        print("                              (Current Output File: " + oFile + ")")
    print("\n\n    2) Rank Output By:\n")
    if(opt[1]):
        print("      [X] Longest First   [ ] Shortest First ")
    else:
        print("      [ ] Longest First   [X] Shortest First ")
    print("\n\n    3) Number of Top Nodes to Output\n")
    if(opt[2] == INF):
        print("      All")
    elif(str(opt[2]).isnumeric()):
        print("      " + str(opt[2]))
    else:
        sys.exit("    An Error Occured. Value of Opt[2] not set properly. See function optionsMenu.\n")
    print("\n\n    4) Nearest Number of Grocery Stores to Check\n")
    print("      " + str(opt[3]))
    print("\n\n    5) Return to Menu\n\n\n")
    
    if(bad):
        print("    Error: Invalid Input Detected. Enter a Number Corresponding to One of the Options Above\n\n")
    
    return input()

def devMenu():
    
    print("""
    
    This is the debug menu.
    
    You're not supposed to be in here.
    
    Unless you are.
    
    In which case, carry on.
    
    0. Print G
    
    1. Print R
    
    2. Print I
    
    3. Print E
    
    4. Print N
    
    5. Print graph
    
    6. Print path
    
    7. Return to Menu    
          
          """)
    
    return input()

#executes main function
if __name__ == "__main__":
    main()
#!/usr/bin/env python3

__author__ = "<NAME>"
__copyright__ = "Copyright 2021"
__credits__ = [""]
__license__ = "GPLv3"
__version__ = "1.5.2"
__maintainer__ = ""
__email__ = "<EMAIL>"
__status__ = "Release"
#This program was built using python v3.9.0. It has not been tested with earlier versions

import sys
import os.path
import os
import copy
import contextlib

#note - numpy is used for array handling for the graph
#if you do not have this package installed, run:
#pip install numpy
#from a terminal
import numpy as np

#defines infinity as a global constant
#approximated at 9,999,999 because we assume no single 
#   path length will come close to this
#this can be adjusted to account for larger size values
INF = 9999999

#reads in the input file
#takes 5 parameters:
#   inFile - the name of the input file
#   G - list to hold the grocery stores (nodes)
#   R - list to hold the residential areas (nodes)
#   I - list to hold the intersections (nodes)
#   E - list to hold the roads (edges)
def readFile(inFile, G, R, I, E):
    #first checks if the file exists in the current folder
    if (os.path.exists(inFile)):
        #opens the input file
        with (open(inFile,'r')) as file:
            isNodes = True
            ln = 0
            for line in file:
                ln += 1
                
                #designates the start of the edges
                if line[0] == '<' and line[1] == 'E':
                    isNodes = False
                    
                #if nodes are being read in (default case)
                if isNodes:
                    #ignores the <NODES> designator
                    if line[0] == '<' and line[1] == 'N':
                        continue
                    #case: grocery store
                    elif line[0] == 'G':
                        G.append(line.replace("\n",""))
                    #case: residential area
                    elif line[0] == 'R':
                        R.append(line.replace("\n",""))
                    #case: intersection
                    elif line[0] == 'I':
                        I.append(line.replace("\n",""))
                    #case: invalid input
                    else: sys.exit("    Error: Invalid Input Detected on Line " + str(ln) + " in file '" + inFile + "'\n")
                
                #if edges are being read in
                else:
                    #ignores the <EDGES> designator
                    if line[0] == '<' and line[1] == 'E':
                        continue
                    #reads in a node
                    else: 
                        E.append(line.replace("\n",""))     
    else:
        os.system('cls' if os.name == 'nt' else 'clear') 
        sys.exit("    Error: Invalid Input File Name: '" + inFile + "' could not be found.")           

#prints the lists - used primarily for debugging purposes
#takes in 4 lists:
#   G (the grocery stores) 
#   R (residential areas) 
#   I (intersections) (our artificial nodes for connectivity purposes)
#   E (roads (edges))           
def printLists(G,R,I,E):
    print("\nG = ", G)
    print("R = ", R)
    print("I = ", I)
    print("E = ", E)
    print("\n")

#loads all of the nodes into one list:
#takes in 4 lists:
#   G (the grocery stores) 
#   R (residential areas) 
#   I (intersections) (our artificial nodes for connectivity purposes)
#   N (a list that will be filled all of the nodes)      
#       note: other functions require that the nodes be loaded in this order,
#       or they will not function correctly
def loadNodes(G,R,I,N):
    for x in range(len(G)):
        N.append(G[x][0])
    for x in range(len(R)):
        N.append(R[x][0])
    for x in range(len(I)):
        N.append(I[x][0])

#turns the lists of nodes and edges into one graph
#takes in 2 lists:
#   N (all the nodes)
#   E (all the edges)
#
#returns a two-dimensional list acting as the graph
def prepGraph(N,E):
    
    #sets up an empty array of correct dimensions
    #fills the array with the value nan as a placeholder
    graph=np.empty((int(len(N)),int(len(N)))) * np.nan
    
    #loops through the edges, initializing the graph
    for x in range(len(E)):
        start = E[x][0]
        stop = E[x][1]
        dist = E[x][2]
        graph[N.index(start)][N.index(stop)] = float(dist)
    #IMPORTANT: this is set up to treat every edge as undirected
    #   need to implement a fix to allow for directed nodes  
    for x in range(len(E)):
        start = E[x][1]
        stop = E[x][0]
        dist = E[x][2]
        graph[N.index(start)][N.index(stop)] = float(dist)
    return graph

#Computes the floyd-warshall algorithm with the given graph
#   the input graph should hold an adjacency matrix for all the nodes
#   returns path, the completed floyd-warshall matrix
#       each [x][y] holds the shortest distance from node x to node y
def pathGraph(graph):
    #creates a deep copy of graph to prevent shallow copy errors
    path = copy.deepcopy(graph)
    
    for x in range(len(path)):
        for y in range(len(path)):
            for z in range(len(path)):
                #shortest distance from node to itself will always be nan
                if(y==z):
                    continue
                else: 
                    
                    #sums the distances betwen the next two edges, treating nan as 0
                    #NOTE - this is probably going to cause errors if [y][x] is nan and 
                    #   [x][z] is not (or vice versa) - test this more
                    nextEdge = np.nansum(path[y][x]+path[x][z])
                    
                    #both of the next two edges are nan
                    if(not nextEdge):
                        nextEdge = INF
                        
                    #gets the minimum value between path[y][z] and nextEdge
                    hold = np.nanmin([path[y][z],nextEdge])
                    
                    #if hold is INF or nan, then no path exists between the two nodes
                    #otherwise, sets [y][z] to hold 
                    if(hold!=INF and hold!=np.nan):
                        path[y][z]=hold
    return path           

#finds the average distance from a node to a range of other nodes
#takes in the graph and 3 integers (graph indicies):
#   start is the index of the first element in the range
#   stop is the index of the last element in the range
#   num is the number of elements to take from the range,
#       prioritizing the nearest nodes
#   node is the point of origin
#   returns the average distance from node to a number of nodes (num)
#       from graph, in that range (start,stop)
#   If 
def avgDist(graph,start,stop,num,node):
    hold = []
    short = []
    nanCount = 0
    pathSum = 0
    
    #if num is not a valid input
    if(num > stop-start or num <= 0):
        sys.exit("    Error: Improper Number of Nodes Requested. You must request a numer of nodes greater than 0 but less than or equal to the amount of G-nodes the graph has.\n Your graph has " + str(stop-start) + " G-nodes.\n You requrested " + str(num) + " G-nodes.\n")  
    
    #appends hold with the lengths of all existing paths
    for x in range(start,stop):
        if(graph[node][x]!=np.nan):
            hold.append(graph[node][x])
    
    #appends short with each length in order from shortest to longest
    #after a value has been added, it is set to our infinity approximation
    val = INF
    hold.append(val)
    for y in range(len(hold)):
        val = np.nanmin(hold)
        if(val!=INF and val!=np.nan):
            short.append(val)
        if(val == np.nan or val=='nan'):
            continue
        else:
            hold[hold.index(val)]=INF
        
    #handles if the amount of added path lengths are less than the requested number
    # (this should only be true if the node does not have a path to some of the nodes
    #  in the start-stop range)
    if(len(short)<=num):
        num = len(short)
    
    if(num == 0):
        return 0    
    #sums the num smallest lengths
    for z in range(num):
        pathSum += short[z]
    return pathSum/num

#returns an ordered list of all the nodes R ranked by average distance to G nodes
#takes in:
#   graph, a the final shortest path matrix
#   G, the number of nodes that correspond to grocery stores
#   R, the number of nodes that correspond to residential areas
#   num, the number of grocery stores to get for each residential area
#       (prioritizing the nearest grocery stores)
#   top, the number of elements to return
#   close, a boolean that returns the nodes with the farthest avg distance if false, and 
#       the least average distance if true.
#       By default, this value is set to false
def getIsol(graph,G,R,num,close = False):
    hold = []
    order = []
    
    #calculates the average distance to the grocery stores for each residential node
    for i in range(G,G+R):
        hold.append([avgDist(graph,0,G,num,i),i])
    
    #orders the nodes by the shortest avg distance to num grocery stores
    for j in range(len(hold)):
        val = hold[j][0]
        sIndex = j
        for k in range(len(hold)):
            if(val>hold[k][0] and hold[k][0]!=INF):
                val=hold[k][0]
                sIndex = k
        order.append(copy.deepcopy(hold[sIndex]))
        hold[sIndex][0] = INF
        
    #if the user wants the closest instead of farthest
    if(close):
        rev = []
        #copies the list in reverse
        #probably more efficient ways to do this, maybe fix it later
        for x in range(len(order)):
            rev.append(copy.deepcopy(order[len(order)-1-x]))
        return rev
    #default setting
    else:
        return order

#outputs a number of results
#takes in several parameters:
#   R is the list of residential area nodes
#   order is a list containing each residential node
#       and its average distance to a set number of G-nodes
#       Order is obtained from the getIsol function
#   gNum is the number of G-nodes
#   top is the number of results to output
#       by default this is set to the length of order (printing all results)
def getTop(R, order, gNum, top = INF):
    print("Residential Area     Average Distance to Grocery Store")
    
    #default setting, prints all 
    if top > len(order):
        top = len(order)
    for x in range(top):
        printStr = ""
        numStr = ""
        
        #takes the length of each string in R, ignores the R### code
        for y in range(1,len(R[order[x][1]-gNum])):
            printStr += str(R[order[x][1]-gNum][y])
            printStr += " "
        printStr = printStr.ljust(30) 
        #adds the average distance
        numStr += str("{:.4f}".format(order[x][0]/1000))
        numStr += " km"
        printStr += numStr.rjust(5)
        print(printStr)       

def main():
    run = True
    badInput = False    
    inFile = ""
    #creates lists to hold each set of nodes
    G = [] #holds grocery stores
    R = [] #holds residential areas
    I = [] #holds intersections
    E = [] #holds edges
    opt = [False,True,INF,'5']
    optInput = '5'
    oFile = "output.txt"
    
    while(run):
        userIn = printMenu(badInput,inFile)
        if(userIn == '1'):
            G.clear()
            R.clear()
            I.clear()
            E.clear()
            badInput = False
            os.system('cls' if os.name == 'nt' else 'clear')
            
            #reads the input file in
            inFile = input("\n    Please Enter the Name of Your Datafile:\n\n\n\n")
            readFile(inFile,G,R,I,E)
        
            #splits each item in each list on spaces
            #i.e. ["R001 RA One"] becomes ["R001","RA","One"] 
            for x in range(0,len(G)):
                G[x] = G[x].split()
            for x in range(0,len(R)):
                R[x] = R[x].split()
            for x in range(0,len(I)):
                I[x] = I[x].split()
            for x in range(0,len(E)):
                E[x] = E[x].split()
                
            #adds a list that holds N, which contains all the nodes
            N=[]
            N.clear()
            loadNodes(G,R,I,N)
    
            #gets the adjacency matrix
            graph=prepGraph(N,E) 
    
            #gets the Floyd-Warshall matrix from the adjacency matrix
            path = pathGraph(graph)
            
            print("\n\n\n    File Loaded Successfully")
            print("\n\n\n\n\n\n\n")
            input("    Press Enter to Continue...")
                
        elif(userIn == '2'):
            os.system('cls' if os.name == 'nt' else 'clear')
            if(inFile == ""):
                print("\n    Error: No Input File Specified\n\n\n\n")
                input("    Press Enter to Continue...")
                continue
            
            #gets the average distance to a number of grocery stores for each node,
            #   then orders them from most avg dist to greatest
            num = int(opt[3])
            #if the requested number of grocery stores is greater than the number
            #   present in the data set, sets it to all
            if(num > len(G)):
                num = len(G)
            order = []
            order.clear()
            #print(len(G),len(R),num,opt[1])
            order = getIsol(path,len(G),len(R),num,opt[1])
            
            #prints the output
            if(not opt[0]):
                print("\n")
                getTop(R,order,len(G),int(opt[2]))
                print("\n\n\n")
                input("    Press Enter to Continue...")
            else:
                #creates file if it doesn't exist:
                with open(oFile,'w') as file:
                    with contextlib.redirect_stdout(file):
                        getTop(R,order,len(G),int(opt[2]))
                print("\n    Output Sent to file: " + oFile + "\n\n\n")
                print("\n\n\n")
                input("    Press Enter to Continue...")
        
        elif(userIn == '3'):
            optInput = '6'
            bad = False
            while(optInput != '5'):
                os.system('cls' if os.name == 'nt' else 'clear')
                optInput = optionsMenu(opt,oFile,bad)
                if(optInput == '1'):
                    bad = False
                    if(opt[0] == False):
                        opt[0] = True
                        os.system('cls' if os.name == 'nt' else 'clear')
                        oFile = input("\n    Please enter a name for the output file:\n\n\n")
                    else:
                        opt[0] = False
                elif(optInput == '2'):
                    bad = False
                    if(opt[1] == False):
                        opt[1] = True
                    else:
                        opt[1] = False
                elif(optInput == '3'):
                    bad = False
                    setOptNum = True
                    setOpt = '0'
                    while(setOptNum):
                        if(not setOpt.isnumeric()):
                            print("Error: You Must Input a Number")
                        os.system('cls' if os.name == 'nt' else 'clear')
                        setOpt = input("\n    Input a numeric value, or 'all':\n\n\n")
                        if(not setOpt.isnumeric() or setOpt.lower() != 'all'):
                            setOptNum = False
                        if(setOpt.isnumeric()):
                            opt[2] = setOpt
                        elif(setOpt.lower() == 'all'):
                            opt[2] = INF
                elif(optInput == '4'):
                    bad = False
                    setOptNum = True
                    while(setOptNum):
                        if(not opt[3].isnumeric()):
                            print("Error: You Must Input a Number")
                        os.system('cls' if os.name == 'nt' else 'clear')
                        setOpt = input("\n    Input a numeric value:\n\n\n")
                        if(not setOpt.isnumeric()):
                            setOptNum = True
                        if(setOpt.isnumeric()):
                            opt[3] = setOpt
                            setOptNum = False
                elif(optInput == '5'):
                    bad = False
                else:
                    bad = True
        
        elif(userIn == '4'):
            os.system('cls' if os.name == 'nt' else 'clear')
            run = False
        
        elif(userIn == '13'):
            debugNow = True
            os.system('cls' if os.name == 'nt' else 'clear')
            while(debugNow):
                getNum = devMenu()
                os.system('cls' if os.name == 'nt' else 'clear')
                if(getNum == '0'):
                    print("\n\n\n   G = \n")
                    print(G)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '1'):
                    print("\n\n\n   R = \n")
                    print(R)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '2'):
                    print("\n\n\n   I = \n")
                    print(I)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '3'):
                    print("\n\n\n   E = \n")
                    print(E)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '4'):
                    print("\n\n\n   N = \n")
                    print(N)
                elif(getNum == '5'):
                    print("\n\n\n   graph = \n")
                    print(graph)
                    input("\n    Press Enter to Continue...")
                elif(getNum == '6'):
                    print("\n\n\n   path = \n")
                    print(path)
                    input("\n\n    Press Enter to Continue...")
                elif(getNum == '7'):
                    debugNow = False
        
        else:
            badInput = True
    
#prints the user menu
#   badInput is a boolean triggered if the user sends bad input
#   inFile is the current input file
#   if not called with a file name, assumes there is no loaded file
def printMenu(badInput = False, inFile = ""):
    if inFile == "":
        inFile = "No File Loaded"
    os.system('cls' if os.name == 'nt' else 'clear')
    print("""   
              _____ _____ ______  _____ _____ 
        /\   / ____/ ____|  ____|/ ____/ ____|
       /  \ | |   | |    | |__  | (___| (___  
      / /\ \| |   | |    |  __|  \___ \\___  \ 
     / ____ | |___| |____| |____ ____) ____) |
    /______\_______\_____|____________|_____/ 
     / ____|  __ \    /\   |  __ \| |  | |    
    | |  __| |__) |  /  \  | |__) | |__| |    
    | | |_ |  _  /  / /\ \ |  ___/|  __  |    
    | |__| | | \ \ / ____ \| |    | |  | |    
     \_____|_|  \_/_/    \_|_|    |_|  |_|                                          
                                                  """)
    print("""\
    WELCOME TO ACCESS GRAPH, v1.5.2
    https://github.com/blake-harrison/access-graph
        
    Please select:
            
    1) Read New File
        
    2) Get Output
        
    3) Settings
        
    4) Quit
        
        """)
    print("\n    Current Input File: " + inFile + "\n\n")
    
    if(badInput):
        print("\n   Error: Invalid Input. Please Try Again\n\n")
    
    return input()

#prints the user's options for settings
#   opts is a list of options
#   each corresponds to an option in the menu below
#   default values for opt are:
#       opt[0] = false
#       opt[1] = false
#       opt[2] = INF (All)
#   oFile is the output file specified (defaults to output.txt)
#   bad is True if the user input does not correspond to one of the options
def optionsMenu(opt, oFile = "output.txt", bad = False):
    print("\n    Options:\n")
    print("\n    Select Number to Toggle, and Press Enter to Confirm:\n\n")
    
    print("    1) Output Format:\n")
    if(not opt[0]):
        print("      [X] To User         [ ] To File ")
    else:
        print("      [ ] To User         [X] To File ")
        print("                              (Current Output File: " + oFile + ")")
    print("\n\n    2) Rank Output By:\n")
    if(opt[1]):
        print("      [X] Longest First   [ ] Shortest First ")
    else:
        print("      [ ] Longest First   [X] Shortest First ")
    print("\n\n    3) Number of Top Nodes to Output\n")
    if(opt[2] == INF):
        print("      All")
    elif(str(opt[2]).isnumeric()):
        print("      " + str(opt[2]))
    else:
        sys.exit("    An Error Occured. Value of Opt[2] not set properly. See function optionsMenu.\n")
    print("\n\n    4) Nearest Number of Grocery Stores to Check\n")
    print("      " + str(opt[3]))
    print("\n\n    5) Return to Menu\n\n\n")
    
    if(bad):
        print("    Error: Invalid Input Detected. Enter a Number Corresponding to One of the Options Above\n\n")
    
    return input()

def devMenu():
    
    print("""
    
    This is the debug menu.
    
    You're not supposed to be in here.
    
    Unless you are.
    
    In which case, carry on.
    
    0. Print G
    
    1. Print R
    
    2. Print I
    
    3. Print E
    
    4. Print N
    
    5. Print graph
    
    6. Print path
    
    7. Return to Menu    
          
          """)
    
    return input()

#executes main function
if __name__ == "__main__":
    main()
#!/usr/bin/env python3 #This program was built using python v3.9.0. It has not been tested with earlier versions #note - numpy is used for array handling for the graph #if you do not have this package installed, run: #pip install numpy #from a terminal #defines infinity as a global constant #approximated at 9,999,999 because we assume no single #   path length will come close to this #this can be adjusted to account for larger size values #reads in the input file #takes 5 parameters: #   inFile - the name of the input file #   G - list to hold the grocery stores (nodes) #   R - list to hold the residential areas (nodes) #   I - list to hold the intersections (nodes) #   E - list to hold the roads (edges) #first checks if the file exists in the current folder #opens the input file #designates the start of the edges #if nodes are being read in (default case) #ignores the <NODES> designator #case: grocery store #case: residential area #case: intersection #case: invalid input #if edges are being read in #ignores the <EDGES> designator #reads in a node #prints the lists - used primarily for debugging purposes #takes in 4 lists: #   G (the grocery stores) #   R (residential areas) #   I (intersections) (our artificial nodes for connectivity purposes) #   E (roads (edges)) #loads all of the nodes into one list: #takes in 4 lists: #   G (the grocery stores) #   R (residential areas) #   I (intersections) (our artificial nodes for connectivity purposes) #   N (a list that will be filled all of the nodes) #       note: other functions require that the nodes be loaded in this order, #       or they will not function correctly #turns the lists of nodes and edges into one graph #takes in 2 lists: #   N (all the nodes) #   E (all the edges) # #returns a two-dimensional list acting as the graph #sets up an empty array of correct dimensions #fills the array with the value nan as a placeholder #loops through the edges, initializing the graph #IMPORTANT: this is set up to treat every edge as undirected #   need to implement a fix to allow for directed nodes #Computes the floyd-warshall algorithm with the given graph #   the input graph should hold an adjacency matrix for all the nodes #   returns path, the completed floyd-warshall matrix #       each [x][y] holds the shortest distance from node x to node y #creates a deep copy of graph to prevent shallow copy errors #shortest distance from node to itself will always be nan #sums the distances betwen the next two edges, treating nan as 0 #NOTE - this is probably going to cause errors if [y][x] is nan and #   [x][z] is not (or vice versa) - test this more #both of the next two edges are nan #gets the minimum value between path[y][z] and nextEdge #if hold is INF or nan, then no path exists between the two nodes #otherwise, sets [y][z] to hold #finds the average distance from a node to a range of other nodes #takes in the graph and 3 integers (graph indicies): #   start is the index of the first element in the range #   stop is the index of the last element in the range #   num is the number of elements to take from the range, #       prioritizing the nearest nodes #   node is the point of origin #   returns the average distance from node to a number of nodes (num) #       from graph, in that range (start,stop) #   If #if num is not a valid input #appends hold with the lengths of all existing paths #appends short with each length in order from shortest to longest #after a value has been added, it is set to our infinity approximation #handles if the amount of added path lengths are less than the requested number # (this should only be true if the node does not have a path to some of the nodes #  in the start-stop range) #sums the num smallest lengths #returns an ordered list of all the nodes R ranked by average distance to G nodes #takes in: #   graph, a the final shortest path matrix #   G, the number of nodes that correspond to grocery stores #   R, the number of nodes that correspond to residential areas #   num, the number of grocery stores to get for each residential area #       (prioritizing the nearest grocery stores) #   top, the number of elements to return #   close, a boolean that returns the nodes with the farthest avg distance if false, and #       the least average distance if true. #       By default, this value is set to false #calculates the average distance to the grocery stores for each residential node #orders the nodes by the shortest avg distance to num grocery stores #if the user wants the closest instead of farthest #copies the list in reverse #probably more efficient ways to do this, maybe fix it later #default setting #outputs a number of results #takes in several parameters: #   R is the list of residential area nodes #   order is a list containing each residential node #       and its average distance to a set number of G-nodes #       Order is obtained from the getIsol function #   gNum is the number of G-nodes #   top is the number of results to output #       by default this is set to the length of order (printing all results) #default setting, prints all #takes the length of each string in R, ignores the R### code #adds the average distance #creates lists to hold each set of nodes #holds grocery stores #holds residential areas #holds intersections #holds edges #reads the input file in #splits each item in each list on spaces #i.e. ["R001 RA One"] becomes ["R001","RA","One"] #adds a list that holds N, which contains all the nodes #gets the adjacency matrix #gets the Floyd-Warshall matrix from the adjacency matrix #gets the average distance to a number of grocery stores for each node, #   then orders them from most avg dist to greatest #if the requested number of grocery stores is greater than the number #   present in the data set, sets it to all #print(len(G),len(R),num,opt[1]) #prints the output #creates file if it doesn't exist: #prints the user menu #   badInput is a boolean triggered if the user sends bad input #   inFile is the current input file #   if not called with a file name, assumes there is no loaded file _____ _____ ______  _____ _____ 
         /\   / ____/ ____|  ____|/ ____/ ____|
        /  \ | |   | |    | |__  | (___| (___  
       / /\ \| |   | |    |  __|  \___ \\___  \ 
      / ____ | |___| |____| |____ ____) ____) |
     /______\_______\_____|____________|_____/ 
      / ____|  __ \    /\   |  __ \| |  | |    
     | |  __| |__) |  /  \  | |__) | |__| |    
     | | |_ |  _  /  / /\ \ |  ___/|  __  |    
     | |__| | | \ \ / ____ \| |    | |  | |    
      \_____|_|  \_/_/    \_|_|    |_|  |_| \
     WELCOME TO ACCESS GRAPH, v1.5.2
     https://github.com/blake-harrison/access-graph
         
     Please select:
             
     1) Read New File
         
     2) Get Output
         
     3) Settings
         
     4) Quit #prints the user's options for settings #   opts is a list of options #   each corresponds to an option in the menu below #   default values for opt are: #       opt[0] = false #       opt[1] = false #       opt[2] = INF (All) #   oFile is the output file specified (defaults to output.txt) #   bad is True if the user input does not correspond to one of the options This is the debug menu.
     
     You're not supposed to be in here.
     
     Unless you are.
     
     In which case, carry on.
     
     0. Print G
     
     1. Print R
     
     2. Print I
     
     3. Print E
     
     4. Print N
     
     5. Print graph
     
     6. Print path
     
     7. Return to Menu #executes main function