July 27, 2021

GIL

Daily Global New Media

Algorithms Course – Graph Theory Tutorial from a Google Engineer

1 min read

27 thoughts on “Algorithms Course – Graph Theory Tutorial from a Google Engineer

  1. Hi William,

    Could you please explain how you've arrived at these 2 time complexities?

    (1) max flow via Edmonds-Karp algo using BFS — O(E^2.V)

    (2) max flow via Capacity Scaling algo using DFS — O(E^2.logU)

    or cud u pls point at some doc where I can read?

  2. Sharing my python code
    With few modifications can create a random dungion and solve
    It makes the adjacency list also by supplying number of rows and columns
    Excludes rock cells
    Finds start and end node on its own

    import numpy as np

    rows=5

    columns=7

    number_of_nodes=rows*columns

    def create_dungeon():

    '''

    This method creates the dungeon

    It returns a numpy array

    The below are the representations of the cell

    0-EMPTY CELL

    1-START

    2-END

    3-ROCK

    Arguments : –

    rows :- Number of rows

    columns :- Number of columns

    start node

    end node

    number of rocks

    '''

    dungeon_arr = np.zeros([rows,columns])

    dungeon_arr[0,0]=1

    dungeon_arr[4,3]=2

    dungeon_arr[4,0]=3

    dungeon_arr[1,1]=3

    dungeon_arr[2,1]=3

    dungeon_arr[3,2]=3

    dungeon_arr[4,2]=3

    dungeon_arr[0,3]=3

    dungeon_arr[3,3]=3

    dungeon_arr[1,5]=3

    dungeon_arr[4,5]=3

    dungeon_arr[4,5]=3

    return dungeon_arr

    dungeon_arr=create_dungeon()

    def get_adjacent_cells(curr_row,curr_col,dungeon_arr):

    '''

    This function is used to get the

    adjacent cells assuming we can cannot move diagonally

    Arguments :-

    Current Row

    Current Column

    Dungeon Array

    '''

    dr = [-1,1,0,0]

    dc = [0,0,1,-1]

    adjacent_cells=[]

    for i in range(4):

    rr=curr_row+dr[i]

    cc=curr_col+dc[i]

    if cc < 0 or rr < 0 or rr >= rows or cc >= columns or dungeon_arr[rr,cc]==3:

    continue

    else:

    adjacent_cells.append((rr,cc))

    return adjacent_cells

    def graph_to_adjacency_list(rows,columns,dungeon_arr):

    '''

    This function will convert the graph to an adjacency list

    '''

    graph_dict={}

    graph_rev_dict={}

    cnt=0

    adjacency_list={}

    for curr_row in range(rows):

    for curr_col in range(columns):

    graph_dict[(curr_row,curr_col)]=cnt

    graph_rev_dict[cnt]=(curr_row,curr_col)

    cnt += 1

    for curr_row in range(rows):

    for curr_col in range(columns):

    adj_neb_idx =[]

    adjacent_cells=get_adjacent_cells(curr_row,curr_col,dungeon_arr)

    for cell in adjacent_cells:

    adj_neb_idx.append(graph_dict[cell])

    adjacency_list[graph_dict[curr_row,curr_col]]=adj_neb_idx

    result=np.where(dungeon_arr == 1)

    start_node=list(zip(result[0], result[1]))

    start_node=graph_dict[start_node[0]]

    result=np.where(dungeon_arr == 2)

    end_node=list(zip(result[0], result[1]))

    end_node=graph_dict[end_node[0]]

    return adjacency_list,start_node,end_node,graph_rev_dict

    adjacency_list,start_node,end_node,graph_rev_dict=graph_to_adjacency_list(rows,columns,dungeon_arr)

    def solve(start_node):

    global number_of_nodes

    global adjacency_list

    graph_queue=[]

    graph_queue.append(start_node)

    visited=[False for i in range(number_of_nodes+1)]

    prev=[False for i in range(number_of_nodes+1)]

    visited[start_node]=True

    while len(graph_queue)!= 0:

    curr_node=graph_queue.pop()

    neighbours= adjacency_list[curr_node]

    for next_node in neighbours:

    if not visited[next_node]:

    graph_queue.append(next_node)

    visited[next_node]=True

    prev[next_node]=curr_node

    return prev

    def reconstrucpath(start_node,end_node,prev):

    path=[]

    node_at=end_node

    while type(node_at) != bool:

    path.append(node_at)

    node_at=prev[node_at]

    return [node for node in reversed(path)]

    def bredth_first_search(start_node,end_node):

    prev = solve(start_node)

    path=reconstrucpath(start_node,end_node,prev)

    return path

    path = bredth_first_search(start_node,end_node)

    for index in path:

    print(graph_rev_dict[index])

    Output :-

    (0, 0)

    (0, 1)

    (0, 2)

    (1, 2)

    (1, 3)

    (1, 4)

    (2, 4)

    (3, 4)

    (4, 4)

    (4, 3)

  3. A good content is here, but what's the point in making almost 7hr video? It's better divide video on smaller parts and make a playlist with them, than clicking on a timestamp every time.

  4. Bridges algo — these also seem to be working? Why can't we do these and further simplify the algo?

    (1) if ! visited[to] == true
    { low[at] = min( low[at], ==> low[to] <== ) }
    (i.e. same min stmt for 'to' being a visited or an unvisited node)

    (2) if ( ==> low[at] <== < low[to] )
    to determine if at->lo is a bridge

    Point is low[] array is sufficient, and ids[] array seems to be redundant

    COMMENTS?

  5. Great content sir i just want to ask you like what type of questions could i get in big tech companies like Google or Facebook interview about graphs because it's such a big topic ?

  6. Thank you so much William, for your kind attention to details. I did not receive any teaching on Graph Theory in the 90s when I thought I had graduated. Your patience has made it possible for me to understand a topic that has tremendous value, I believe both for other advanced topics and implementing real-world solutions right away! Thank you, again William!

  7. yay just coded the first algo here is the ouput

    =============================at=============================

    0

    =============================path=============================

    0

    =============================at=============================

    1

    =============================path=============================

    0 1

    =============================at=============================

    8

    =============================path=============================

    0 1 8

    =============================at=============================

    7

    =============================path=============================

    0 1 8 7

    =============================at=============================

    10

    =============================path=============================

    0 1 8 7 10

    =============================at=============================

    11

    =============================path=============================

    0 1 8 7 10 11

    =============================at=============================

    3

    =============================path=============================

    0 1 8 7 3

    =============================at=============================

    2

    =============================path=============================

    0 1 8 7 3 2

    =============================at=============================

    4

    =============================path=============================

    0 1 8 7 3 4

    =============================at=============================

    5

    =============================path=============================

    0 1 8 7 3 5

    =============================at=============================

    6

    =============================path=============================

    0 1 8 7 3 5 6

    =============================at=============================

    9

    =============================path=============================

    0 9

  8. Thank you for good content! The only thing I want to note is that at 26:50 you have only "visited[at] = true" but you never set it to false, so it will never actually "back track". I believe there is missing "visited[at] = false" right at the end of the function, so we unmark the node when leaving the function.

Leave a Reply

Your email address will not be published. Required fields are marked *

15 − eight =