graphs.check_bipatrite¶
Attributes¶
Functions¶
|
Check if a graph is bipartite using a breadth-first search (BFS). |
|
Check if a graph is bipartite using depth-first search (DFS). |
Module Contents¶
- graphs.check_bipatrite.is_bipartite_bfs(graph: dict[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:
>>> is_bipartite_bfs({0: [1, 2], 1: [0, 3], 2: [0, 4]}) True >>> is_bipartite_bfs({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]}) False
>>> # 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]}) False >>> 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]}) True
>>> # 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]}) True >>> is_bipartite_bfs({0: ["b", "d"], 1: ["a", "c"], 2: ["b", "d"], 3: ["a", "c"]}) True
- graphs.check_bipatrite.is_bipartite_dfs(graph: dict[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:
>>> is_bipartite_dfs({0: [1, 2], 1: [0, 3], 2: [0, 4]}) True >>> is_bipartite_dfs({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]}) False
>>> # 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]}) False >>> 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]}) True
>>> # 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]}) True >>> is_bipartite_dfs({0: ["b", "d"], 1: ["a", "c"], 2: ["b", "d"], 3: ["a", "c"]}) True
- graphs.check_bipatrite.result¶