graphs.check_bipatrite

Attributes

result

Functions

is_bipartite_bfs(→ bool)	Check if a graph is bipartite using a breadth-first search (BFS).
is_bipartite_dfs(→ bool)	Check if a graph is bipartite using depth-first search (DFS).

Module Contents

graphs.check_bipatrite.is_bipartite_bfs(graph: collections.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'

graphs.check_bipatrite.is_bipartite_dfs(graph: collections.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'

graphs.check_bipatrite.result