python-algorithms/algorithms/graph/clone_graph.py at master · plumnx/python-algorithms · GitHub

History

123 lines (104 loc) · 3.36 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

r"""

Clone an undirected graph. Each node in the graph contains a label and a list

of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and

each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as

separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.

Second node is labeled as 1. Connect node 1 to node 2.

Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a

self-cycle.

Visually, the graph looks like the following:

/ \

0 --- 2

/ \

\_/

"""

import collections

class UndirectedGraphNode:

"""

A node in an undirected graph. Contains a label and a list of neighbouring

nodes (initially empty).

"""

def __init__(self, label):

self.label = label

self.neighbors = []

def shallow_copy(self):

"""

Return a shallow copy of this node (ignoring any neighbors)

"""

return UndirectedGraphNode(self.label)

def add_neighbor(self, node):

"""

Adds a new neighbor

"""

self.neighbors.append(node)

def clone_graph1(node):

"""

Returns a new graph as seen from the given node using a breadth first search (BFS).

"""

if not node:

return None

node_copy = node.shallow_copy()

dic = {node: node_copy}

queue = collections.deque([node])

while queue:

node = queue.popleft()

for neighbor in node.neighbors:

if neighbor not in dic: # neighbor is not visited

neighbor_copy = neighbor.shallow_copy()

dic[neighbor] = neighbor_copy

dic[node].add_neighbor(neighbor_copy)

queue.append(neighbor)

else:

dic[node].add_neighbor(dic[neighbor])

return node_copy

def clone_graph2(node):

"""

Returns a new graph as seen from the given node using an iterative depth first search (DFS).

"""

if not node:

return None

node_copy = node.shallow_copy()

dic = {node: node_copy}

stack = [node]

while stack:

node = stack.pop()

for neighbor in node.neighbors:

if neighbor not in dic:

neighbor_copy = neighbor.shallow_copy()

dic[neighbor] = neighbor_copy

dic[node].add_neighbor(neighbor_copy)

stack.append(neighbor)

else:

dic[node].add_neighbor(dic[neighbor])

return node_copy

def clone_graph(node):

"""

Returns a new graph as seen from the given node using a recursive depth first search (DFS).

"""

if not node:

return None

node_copy = node.shallow_copy()

dic = {node: node_copy}

dfs(node, dic)

return node_copy

def dfs(node, dic):

"""

Clones a graph using a recursive depth first search. Stores the clones in

the dictionary, keyed by the original nodes.

"""

for neighbor in node.neighbors:

if neighbor not in dic:

neighbor_copy = neighbor.shallow_copy()

dic[neighbor] = neighbor_copy

dic[node].add_neighbor(neighbor_copy)

dfs(neighbor, dic)

else:

dic[node].add_neighbor(dic[neighbor])

python-algorithms/algorithms/graph/clone_graph.py at master · plumnx/python-algorithms · GitHub

Expand file tree

Breadcrumbs

clone_graph.py

Latest commit

History

Breadcrumbs

clone_graph.py

File metadata and controls