is_bipartite

Contents

is_bipartite#

graph_tool.topology.is_bipartite(g, partition=False, find_odd_cycle=False)[source]#

Test if the graph is bipartite.

Parameters:
gGraph

Graph to be used.

partitionbool (optional, default: False)

If True, return the two partitions in case the graph is bipartite.

find_odd_cyclebool (optional, default: False)

If True, return an odd cycle if the graph is not bipartite.

Returns:
is_bipartitebool

Whether or not the graph is bipartite.

partitionVertexPropertyMap (only if partition=True)

A vertex property map with the graph partitioning (or None) if the graph is not bipartite.

odd_cyclelist of vertices (only if find_odd_cycle=True)

A list of vertices corresponding to an odd cycle, or None if none is found.

Notes

An undirected graph is bipartite if one can partition its set of vertices into two sets, such that all edges go from one set to the other.

This algorithm runs in \(O(V + E)\) time.

References

Examples

>>> g = gt.lattice([10, 10])
>>> is_bi, part = gt.is_bipartite(g, partition=True)
>>> print(is_bi)
True
>>> gt.graph_draw(g, vertex_fill_color=part, output="bipartite.pdf")
<...>
../_images/bipartite.png

Bipartition of a 2D lattice.#

Contents