graphs.md

Graphs

Table of Contents

• Algorithms
  • Distance
  • Search
  • Connectivity
  • Cycle Detection
• Ways to Represent a Graph in Memory
  • Objects and Pointers
  • Matrix
  • Adjacency List
• Traversal Algorithms
  • Breadth-first Search
  • Depth-first Search

class graph.Graph(V, E, directed=True)

A Graph is a mathematical structure defined by a set of vertices V connected by edges E, where the distance from vertex u to vertex v is E[u][v]. A Graph can be directed or undirected. Graph objects support the following methods:

Algorithms

Distance

dijkstra(source, trace=False)

Apply Dijkstra's algorithm. Return a dictionary in the form of {u: distance} where there is some distance from vertex source to vertex u. If trace is True, instead return a dictionary in the form of {u: [[source...u]]} where each list in the value is a path from source to u.

Network Delay Time

import collections


def networkDelayTime(times, N, K):
    E = collections.defaultdict(dict)
    for u, v, w in times:
        E[u][v] = w
    time = max(Graph(set(range(1, N + 1)), E).dijkstra(K).values())
    return int(time) if time < float('inf') else -1

Bus Routes

import collections
import itertools


def numBusesToDestination(routes, S, T):
    E = collections.defaultdict(dict)
    for route in routes:
        for u, v in itertools.permutations(route, 2):
            if u != v:
                E[u][v] = 1
    dist = Graph(set(itertools.chain(*routes)), E).dijkstra(S)
    return dist[T] if T in dist and T < float('inf') else -1

Snakes and Ladders

import collections


def snakesAndLadders(board):
    arr = []
    while board:
        arr += board.pop()
        if board: arr += board.pop()[::-1]
    m = len(arr)
    V = set(range(m))
    E = collections.defaultdict(dict)
    for u in V:
        for i in range(1, 7):
            v = u + i
            if v < m:
                if arr[v] == -1:
                    E[u][v] = 1
                else: E[u][arr[v] - 1] = 1
    moves = Graph(V, E).dijkstra(0)[m - 1]
    return moves if moves < float('inf') else -1

Shortest Path Binary Matrix

def shortestPathBinaryMatrix(grid):
    dist = to_graph(grid, color=0, k=8).dijkstra((0, 0))
    m = len(grid) - 1
    k = m, m
    return dist[k] + 1 if k in dist and dist[k] < float('inf') else -1

Shortest Path with Alternating Colors

import collections


def shortestAlternatingPaths(n, red_edges, blue_edges):
    r = range(n)
    V = set()
    for X in r:
        V.add((X, 'red'))
        V.add((X, 'blue'))
    E = collections.defaultdict(dict)
    for u, v in red_edges:
        E[(u, 'red')][(v, 'blue')] = 1
    for u, v in blue_edges:
        E[(u, 'blue')][(v, 'red')] = 1
    graph = Graph(V, E)
    start_red, start_blue = graph.dijkstra((0, 'red')), graph.dijkstra((0, 'blue'))
    answer = []
    for X in r:
        u, v = (X, 'red'), (X, 'blue')
        length = min(start_red[u], start_red[v], start_blue[u], start_blue[v])
        answer += [length if length < float('inf') else -1]
    return answer

Jump Game III

import collections


def canReach(arr, start):
    E = collections.defaultdict(dict)
    for i, x in enumerate(arr):
        j = i + x
        if j < len(arr):
            E[i][j] = 1
        j = i - x
        if 0 <= j:
            E[i][j] = 1
    dist = Graph(set(range(len(arr))), E).dijkstra(start)
    return any(dist[i] < float('inf') and x == 0 for i, x in enumerate(arr))

Time Needed to Inform All Employees

import collections


def numOfMinutes(n, headID, manager, informTime):
    E = collections.defaultdict(dict)
    for i, x in enumerate(manager):
        E[x][i] = float('inf')
    for employee in V:
        for subordinate in E[employee]:
            E[employee][subordinate] = informTime[employee]
    return max(Graph(set(range(n)), E).dijkstra(headID).values())

bellman_ford(source)

Apply the Bellman-Ford algorithm. Return a collections.defaultdict(dict) object in the form of defaultdict(<class 'dict'>, {u: distance}) where there is some distance from vertex source to vertex u.

floyd_warshall()

Apply the Floyd-Warshall algorithm. Return a dictionary in the form of {u: {v: distance}} where there is some distance from vertex u to vertex v.

Find the City With the Smallest Number of Neighbors at a Threshold Distance

import collections


def findTheCity(n, edges, distanceThreshold):
    V = set(range(n))
    E = collections.defaultdict(dict)
    for from_, to_, weight in edges:
        E[from_][to_] = weight
    dist = Graph(V, E, directed=False).floyd_warshall()
    return min(V, key = lambda y: (sum(map(
        lambda x: x <= distanceThreshold, dist[y].values()
    )), -y))

Search

Connectivity

count_components()

Return the number of connected components.

Number of Islands

def numIslands(grid):
    return to_graph(grid, color='1').count_components()

Friend Circles

import collections
import itertools


def findCircleNum(M):
    V = set(range(len(M)))
    E = collections.defaultdict(dict)
    for i, j in itertools.permutations(V, 2):
        if M[i][j]:
            E[i][j] = 1
    return Graph(V, E, directed=False).count_components()

kruskal()

Apply Kruskal's algorithm to an undirected graph. Return a minimum spanning tree MST in the form of a collections.defaultdict(dict) object, where the distance from vertex u to vertex v is MST[u][v].

prim()

Apply Prim's algorithm to an undirected graph. Return a minimum spanning tree MST in the form of a collections.defaultdict(dict) object MST.

Cheapest Flights Within K Stops

import collections

def findCheapestPrice(n, flights):
    E = collections.defaultdict(dict)
    for u, v, w in flights:
        E[u][v] = w
    ordering = Graph(set(range(n)), E, False).prim()
    return sum(ordering.values())

Cycle Detection

bipartite()

Return whether the graph is bipartite.

Is Graph Bipartite?

import collections


def isBipartite(graph):
    E = collections.defaultdict(dict)
    for u, x in enumerate(graph):
        for v in x:
            E[u][v] = 1
    return Graph(set(range(len(graph))), E, directed=False).bipartite()

Possible Bipartition

import collections


def possibleBipartition(N, dislikes):
    E = collections.defaultdict(dict)
    for u, v in dislikes:
        E[u][v] = 1
    return Graph(set(range(1, N + 1)), E, directed=False).bipartite()

Ways to Represent a Graph in Memory

Objects and Pointers

Matrix

graph.to_graph(matrix, color=1, k=4)

Convert a matrix to a Graph. Each node is marked color and are k-directionally connected to its neighbors, where k can be 4 or 8.

Adjacency List

graph.get_neighbors(matrix, i, j, color=None, k=4)]

In a matrix, nodes are marked color and are k-directionally connected to their neighbors, where k can be 4 or 8. Given a node at (i, j), return its neighbors.

Minesweeper

def updateBoard(board, click):
    i, j = click
    if board[i][j] == 'M':
        board[i][j] = 'X'
    elif board[i][j] == 'E':
        stack = [(i, j)]
        visited = set()
        while stack:
            i, j = stack.pop()
            visited.add((i, j))
            m = len(get_neighbors(board, i, j, color='M', k=8))
            if m:
                board[i][j] = str(m)
            else:
                board[i][j] = 'B'
                for u in get_neighbors(board, i, j, color='E', k=8):
                    if u not in visited:
                        stack += [u]
    return board

Traversal Algorithms

Breadth-first Search

Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s[1] -> s[2] -> ... -> s[k] such that:

• Every adjacent pair of words differs by a single letter.
• Every s[i] for 1 <= i <= k is in wordList. beginWord does not need to be in wordList.
• s[k] == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

import itertools

class Tree:
    def __init__(self, index):
        self.root = index
        self.nodes, self.leaves = {index}, {index}

    def intersect(self, other):
        return self.nodes & other.nodes

    def expand(self, adjacency, other):
        self.leaves = set(itertools.chain(*(adjacency[i]
            for i in self.leaves))) - self.nodes
        self.nodes.update(self.leaves)
        return not self.leaves or self.intersect(other)

def ladderLength(beginWord, endWord, wordList):
    indexBegin = indexEnd = -1
    for i, word in enumerate(wordList):
        if word == beginWord: indexBegin = i
        elif word == endWord: indexEnd = i
    if indexBegin == -1:
        indexBegin = len(wordList)
        wordList.append(beginWord)
    if indexEnd == -1: return 0
    n, m = len(wordList), len(beginWord)
    adjacency = [set() for _ in range(n)]
    for i, word in enumerate(wordList):
        for j in range(i + 1, n):
            k = diff = 0
            while k < m: 
                diff += word[k] != wordList[j][k]
                if diff > 1: break
                k += 1
            else:
                adjacency[i].add(j)
                adjacency[j].add(i)
    begin, end = Tree(indexBegin), Tree(indexEnd)
    ladder_length = 2
    while True:
        if begin.expand(adjacency, end): break
        ladder_length += 1
        if end.expand(adjacency, begin): break
        ladder_length += 1
    return ladder_length if begin.intersect(end) else 0
    

Return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s[1], s[2], ..., s[k]].

from collections import defaultdict

class Tree:
    def __init__(self, index):
        self.root = index
        self.parent_children = defaultdict(set)
        self.child_parents = defaultdict(set)
        self.nodes, self.leaves = {index}, {index}

    def intersect(self, other):
        return self.nodes & other.nodes

    def expand(self, adjacency, other):
        parent_children = defaultdict(set)
        for i in self.leaves:
            for j in adjacency[i]:
                if j not in self.nodes: parent_children[i].add(j)
        self.leaves = set()
        for i, children in parent_children.items():
            self.parent_children[i].update(children)
            for j in children: self.child_parents[j].add(i)
            self.leaves.update(children)
        self.nodes.update(self.leaves)
        return not self.leaves or self.intersect(other)

    def prefixes(self, other):
        stack = [[j] for j in self.intersect(other)]
        prefixes = []
        while stack:
            current = stack.pop()
            if current[0] == self.root: prefixes.append(current)
            for i in self.child_parents[current[0]]:
                stack.append([i] + current)
        return prefixes

def findLadders(beginWord, endWord, wordList):
    indexBegin = indexEnd = -1
    for i, word in enumerate(wordList):
        if word == beginWord: indexBegin = i
        elif word == endWord: indexEnd = i
    if indexBegin == -1:
        indexBegin = len(wordList)
        wordList.append(beginWord)
    if indexEnd == -1: return []
    n, m = len(wordList), len(beginWord)
    adjacency = [set() for _ in range(n)]
    for i, word in enumerate(wordList):
        for j in range(i + 1, n):
            k = diff = 0
            while k < m: 
                diff += word[k] != wordList[j][k]
                if diff > 1: break
                k += 1
            else:
                adjacency[i].add(j)
                adjacency[j].add(i)
    begin, end = Tree(indexBegin), Tree(indexEnd)
    while True:
        if begin.expand(adjacency, end): break
        if end.expand(adjacency, begin): break
    ladders = set()
    for suffix in end.prefixes(begin):
        suffix.reverse()
        for prefix in begin.prefixes(end):
            for index, x in enumerate(suffix):
                if x == prefix[-1]:
                    ladders.add(tuple(prefix + suffix[index + 1:]))
                    break
    return [[wordList[i] for i in ladder] for ladder in ladders]

Minimum Genetic Mutation

def minMutation(start, end, bank):
    mutations = word_ladder(start, end, bank)
    return mutations if mutations < float('inf') else -1

Depth-first Search

toposort()

Return a topological sort of the graph. If the graph has cycles, return None.

Course Schedule

import collections


def canFinish(numCourses, prerequisites):
    E = collections.defaultdict(dict)
    for v, u in prerequisites:
        E[u][v] = 1
    return Graph(set(range(numCourses)), E).toposort() != None

Course Schedule II

import collections


def findOrder(numCourses, prerequisites):
    E = collections.defaultdict(dict)
    for v, u in prerequisites:
        E[u][v] = 1
    ordering = Graph(set(range(numCourses)), E).toposort()
    return ordering if ordering != None else []

graph.flood_fill(matrix, i, j, color, k=4)

Flood fill a matrix in-place at coordinate (i, j) with color. Update (i, j) with color. Recursively update all k-directionally connected neighbors of (i, j) of the original color with color.

Flood Fill

def floodFill(image, sr, sc, newColor):
    flood_fill(image, sr, sc, newColor)
    return image

graph.flood_fill_border(matrix, color, k=4)

Flood fill the border of a matrix with color, where the nodes are k-directionally connected.

Number of Enclaves

def numEnclaves(A):
    flood_fill_border(A, 0)
    return sum(map(sum, A))

Number of Closed Islands

def closedIsland(grid):
    flood_fill_border(grid, 1)
    return to_graph(grid, color=0).count_components()