Safe Haskell | Safe |
---|

Algorithms on Graphs.

This module contains a few graph algorithms and the transoformations needed for them to be used on nodes.

For more information about Graph Coloring see: http://en.wikipedia.org/wiki/Graph_coloring http://en.wikipedia.org/wiki/Greedy_coloring

LF-coloring is described in:
Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number
of a graph and its application to timetabling problems", The Computer Journal
10 (1): 85-86, doi:10.1093*comjnl*10.1.85
http://comjnl.oxfordjournals.org/content/10/1/85

DSatur is described in: Brelaz, D. (1979), "New methods to color the vertices of a graph", Communications of the ACM 22 (4): 251-256, doi:10.1145/359094.359101 http://dx.doi.org/10.1145%2F359094.359101

Also interesting:
Klotz, W. (2002). Graph coloring algorithms. Mathematics Report, Technical
University Clausthal, 1-9.
<http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung
*publications*2002/gca.pdf>

## Synopsis

- type Color = Int
- type VertColorMap = IntMap Color
- type ColorVertMap = IntMap [Int]
- verticesByDegreeDesc :: Graph -> [Vertex]
- verticesByDegreeAsc :: Graph -> [Vertex]
- neighbors :: Graph -> Vertex -> [Vertex]
- hasLoop :: Graph -> Bool
- isUndirected :: Graph -> Bool
- emptyVertColorMap :: VertColorMap
- isColorable :: Graph -> Bool
- colorInOrder :: Graph -> [Vertex] -> VertColorMap
- colorLF :: Graph -> VertColorMap
- colorDcolor :: Graph -> VertColorMap
- colorDsatur :: Graph -> VertColorMap
- colorVertMap :: VertColorMap -> ColorVertMap

# Type declarations

type VertColorMap = IntMap Color Source #

Vertex to Color association.

type ColorVertMap = IntMap [Int] Source #

Color to Vertex association.

# Vertices characteristics

verticesByDegreeDesc :: Graph -> [Vertex] Source #

vertices of a graph, sorted by ascending degree.

verticesByDegreeAsc :: Graph -> [Vertex] Source #

vertices of a graph, sorted by descending degree.

hasLoop :: Graph -> Bool Source #

Check whether a graph has no loops. (vertices connected to themselves)

isUndirected :: Graph -> Bool Source #

Check whether a graph is undirected

# Coloring

emptyVertColorMap :: VertColorMap Source #

Empty color map.

isColorable :: Graph -> Bool Source #

Check whether a graph is colorable.

colorInOrder :: Graph -> [Vertex] -> VertColorMap Source #

Color greedily all nodes in the given order.

colorLF :: Graph -> VertColorMap Source #

Color greedily all nodes, larger first.

colorDcolor :: Graph -> VertColorMap Source #

Color greedily all nodes, highest number of colored neighbors, then highest degree. This is slower than "colorLF" as we must dynamically recalculate which node to color next among all remaining ones but produces better results.

colorDsatur :: Graph -> VertColorMap Source #

Color greedily all nodes, highest saturation, then highest degree. This is slower than "colorLF" as we must dynamically recalculate which node to color next among all remaining ones but produces better results.

colorVertMap :: VertColorMap -> ColorVertMap Source #

ColorVertMap from VertColorMap.