check_bipatrite.py

fromcollectionsimportdefaultdict, deque


defis_bipartite_dfs(graph: defaultdict[int, list[int]]) ->bool:
"""
 Check if a graph is bipartite using depth-first search (DFS).

 Args:
 `graph`: Adjacency list representing the graph.

 Returns:
 ``True`` if bipartite, ``False`` otherwise.

 Checks if the graph can be divided into two sets of vertices, such that no two
 vertices within the same set are connected by an edge.

 Examples:

 >>> # FIXME: This test should pass.
 >>> is_bipartite_dfs(defaultdict(list, {0: [1, 2], 1: [0, 3], 2: [0, 4]}))
 Traceback (most recent call last):
 ...
 RuntimeError: dictionary changed size during iteration
 >>> is_bipartite_dfs(defaultdict(list, {0: [1, 2], 1: [0, 3], 2: [0, 1]}))
 False
 >>> is_bipartite_dfs({})
 True
 >>> is_bipartite_dfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]})
 True
 >>> is_bipartite_dfs({0: [1, 2, 3], 1: [0, 2], 2: [0, 1, 3], 3: [0, 2]})
 False
 >>> is_bipartite_dfs({0: [4], 1: [], 2: [4], 3: [4], 4: [0, 2, 3]})
 True
 >>> is_bipartite_dfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]})
 False
 >>> is_bipartite_dfs({7: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]})
 Traceback (most recent call last):
 ...
 KeyError: 0

 >>> # FIXME: This test should fails with KeyError: 4.
 >>> is_bipartite_dfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 9: [0]})
 False
 >>> is_bipartite_dfs({0: [-1, 3], 1: [0, -2]})
 Traceback (most recent call last):
 ...
 KeyError: -1
 >>> is_bipartite_dfs({-1: [0, 2], 0: [-1, 1], 1: [0, 2], 2: [-1, 1]})
 True
 >>> is_bipartite_dfs({0.9: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]})
 Traceback (most recent call last):
 ...
 KeyError: 0

 >>> # FIXME: This test should fails with
 >>> # TypeError: list indices must be integers or...
 >>> is_bipartite_dfs({0: [1.0, 3.0], 1.0: [0, 2.0], 2.0: [1.0, 3.0], 3.0: [0, 2.0]})
 True
 >>> is_bipartite_dfs({"a": [1, 3], "b": [0, 2], "c": [1, 3], "d": [0, 2]})
 Traceback (most recent call last):
 ...
 KeyError: 1
 >>> is_bipartite_dfs({0: ["b", "d"], 1: ["a", "c"], 2: ["b", "d"], 3: ["a", "c"]})
 Traceback (most recent call last):
 ...
 KeyError: 'b'
 """

defdepth_first_search(node: int, color: int) ->bool:
"""
 Perform Depth-First Search (DFS) on the graph starting from a node.

 Args:
 node: The current node being visited.
 color: The color assigned to the current node.

 Returns:
 True if the graph is bipartite starting from the current node,
 False otherwise.
 """
ifvisited[node] ==-1:
visited[node] =color
forneighboringraph[node]:
ifnotdepth_first_search(neighbor, 1-color):
returnFalse
returnvisited[node] ==color

visited: defaultdict[int, int] =defaultdict(lambda: -1)
fornodeingraph:
ifvisited[node] ==-1andnotdepth_first_search(node, 0):
returnFalse
returnTrue


defis_bipartite_bfs(graph: defaultdict[int, list[int]]) ->bool:
"""
 Check if a graph is bipartite using a breadth-first search (BFS).

 Args:
 `graph`: Adjacency list representing the graph.

 Returns:
 ``True`` if bipartite, ``False`` otherwise.

 Check if the graph can be divided into two sets of vertices, such that no two
 vertices within the same set are connected by an edge.

 Examples:

 >>> # FIXME: This test should pass.
 >>> is_bipartite_bfs(defaultdict(list, {0: [1, 2], 1: [0, 3], 2: [0, 4]}))
 Traceback (most recent call last):
 ...
 RuntimeError: dictionary changed size during iteration
 >>> is_bipartite_bfs(defaultdict(list, {0: [1, 2], 1: [0, 2], 2: [0, 1]}))
 False
 >>> is_bipartite_bfs({})
 True
 >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]})
 True
 >>> is_bipartite_bfs({0: [1, 2, 3], 1: [0, 2], 2: [0, 1, 3], 3: [0, 2]})
 False
 >>> is_bipartite_bfs({0: [4], 1: [], 2: [4], 3: [4], 4: [0, 2, 3]})
 True
 >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]})
 False
 >>> is_bipartite_bfs({7: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]})
 Traceback (most recent call last):
 ...
 KeyError: 0

 >>> # FIXME: This test should fails with KeyError: 4.
 >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 9: [0]})
 False
 >>> is_bipartite_bfs({0: [-1, 3], 1: [0, -2]})
 Traceback (most recent call last):
 ...
 KeyError: -1
 >>> is_bipartite_bfs({-1: [0, 2], 0: [-1, 1], 1: [0, 2], 2: [-1, 1]})
 True
 >>> is_bipartite_bfs({0.9: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]})
 Traceback (most recent call last):
 ...
 KeyError: 0

 >>> # FIXME: This test should fails with
 >>> # TypeError: list indices must be integers or...
 >>> is_bipartite_bfs({0: [1.0, 3.0], 1.0: [0, 2.0], 2.0: [1.0, 3.0], 3.0: [0, 2.0]})
 True
 >>> is_bipartite_bfs({"a": [1, 3], "b": [0, 2], "c": [1, 3], "d": [0, 2]})
 Traceback (most recent call last):
 ...
 KeyError: 1
 >>> is_bipartite_bfs({0: ["b", "d"], 1: ["a", "c"], 2: ["b", "d"], 3: ["a", "c"]})
 Traceback (most recent call last):
 ...
 KeyError: 'b'
 """
visited: defaultdict[int, int] =defaultdict(lambda: -1)
fornodeingraph:
ifvisited[node] ==-1:
queue: deque[int] =deque()
queue.append(node)
visited[node] =0
whilequeue:
curr_node=queue.popleft()
forneighboringraph[curr_node]:
ifvisited[neighbor] ==-1:
visited[neighbor] =1-visited[curr_node]
queue.append(neighbor)
elifvisited[neighbor] ==visited[curr_node]:
returnFalse
returnTrue


if__name__=="__main":
importdoctest

result=doctest.testmod()
ifresult.failed:
print(f"{result.failed} test(s) failed.")
else:
print("All tests passed!")