@graphty/algorithms / index / indexed / isBipartite
Function: isBipartite() ​
isBipartite(
s,options?):BipartiteResult
Defined in: indexed/bipartite.ts:41
Two-colour the graph by BFS, one BFS per component in index order. A self-loop makes a graph non-bipartite; parallel arcs change nothing. Arc direction plays no part in bipartiteness, so on a directed snapshot every node is coloured against its in-neighbours (over s.reverse()) as well as its out-neighbours. Following out-arcs only -- as the legacy bipartitePartition does -- makes the answer depend on node order: with the single arc a -> b, a walk that starts at b never meets a, colours it as a new root and then finds the arc inside one side. options.arcs: "out" gives that legacy answer.
Parameters ​
s ​
GraphSnapshot
The snapshot to test
options? ​
BipartiteOptions = {}
Which arcs to follow on a directed snapshot
Returns ​
Whether the graph is bipartite and, when it is, its two sides