Data.Graph.Indexed.Util.Bipartite

Definitions

bipartite : IGraph k e n -> Maybe (IArray k Bool)

  Tries to color a graph with only two colors, so that all
  edges in the graph connect nodes of distinct colors.
  
  Returns the coloring in case of a success and `Nothing` otherwise.

Totality: total
Visibility: export

match : IGraph k e n -> Maybe (IArray k (Maybe (Fin k)))

  Finds a maximal matching for a bipartite graph. Returns `Nothing`
  in case the graph is not bipartite.

Totality: total
Visibility: export

perfectMatch : IGraph k e n -> Maybe (IArray k (Fin k))

  Tries to find a perfect matching for a bipartite graph.
  Returns `Nothing` in case the graph is not bipartite or no
  perfect matching exists.

Totality: total
Visibility: export

matchEdges : IGraph k e n -> List (Edge k e)

  Finds the edges of a maximal matching in a graph.

Totality: total
Visibility: export

matchEdgesWhere : IGraph k e n -> (Fin k -> Bool) -> List (Edge k e)

  Finds the edges of a maximal matching in a subgraph.

Totality: total
Visibility: export