Kursy Online

Lekcja – Czy istnieje ścieżka (BFS)

V = {
    'P' : ['K', 'Q', 'H'],
    'D1': ['D2','E'],
    'D2': ['D1',],
    'K' : ['P', 'Q'],
    'Q' : ['P', 'K', 'H'],
    'H' : ['P', 'Q'],
    'E' : ['D1']
}

def is_path_between(V, source, dest):

    list_to_check = [source]
    list_visited = []

    while list_to_check:

        current_node = list_to_check.pop(0)
        if current_node == dest:
            return True
        else:
            if current_node not in list_visited:
                list_visited.append(current_node)
                list_to_check.extend(V[current_node])

    return False

for s in V.keys():
    for d in V.keys():
        if s != d:
            print(f'Path {s} - {d} - {is_path_between(V, s, d)}')    

#%%
V = {
    'P' : ['K', 'Q', 'H'],
    'D1': ['D2','E'],
    'D2': ['D1',],
    'K' : ['P', 'Q'],
    'Q' : ['P', 'K', 'H'],
    'H' : ['P', 'Q'],
    'E' : ['D1']
}

def is_path_between(V, source, dest):

    list_to_check = [source]
    list_visited = []

    while list_to_check:

        current_node = list_to_check.pop(0)
        # optimization 1 - if the destination is in the current node's neighbours
        if current_node == dest or dest in V[current_node]:
            return True
        else:
            if current_node not in list_visited:
                list_visited.append(current_node)
                list_to_check.extend(V[current_node])
                # optimization 2 - add to "list_to_check" only nodes 
                list_to_check.extend( [x for x in V[current_node] if x not in list_visited] )

    return False

for s in V.keys():
    for d in V.keys():
        if s != d:
            print(f'Path {s} - {d} - {is_path_between(V, s, d)}')

Lab

import csv

network = {}
select_month = 1

with open('data/usa-domestic-flight-2019.csv') as csv_file:
    csv_reader = csv.reader(csv_file, delimiter=',')
    line_count = 0
    for row in csv_reader:
        if line_count == 0:
            print(f'Column names are {", ".join(row)}')
            line_count += 1
        else:
            line_count += 1
            origin = row[8]
            destination = row[11]
            month = int(row[12])

            if month != select_month:# or passengers == 0:
                continue

            if origin not in network.keys():
                network[origin] = [destination]
            else:
                if destination not in network[origin]:
                    network[origin].append(destination)

               
current_keys = list(network.keys())
for origin in current_keys:
    for destination in network[origin]:
        if destination not in network.keys():
            network[destination] = []

print(f'Processed {line_count} lines.')
#print(network.keys())

def is_path_between(V, source, dest):

    list_to_check = [source]
    list_visited = []

    while list_to_check:

        current_node = list_to_check.pop(0)
        if current_node == dest:
            return True
        else:
            if current_node not in list_visited:
                list_visited.append(current_node)
                list_to_check.extend(V[current_node])

    return False


start = 'San Francisco, CA'
stop = 'Vernal, UT'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")

start = 'Vernal, UT'
stop = 'San Francisco, CA'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")

start = 'Kotzebue, AK'
stop = 'Danger Bay, AK'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")