<commit_before>{-| 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:
<NAME>.; <NAME>. (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:
<NAME>. (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:
<NAME>. (2002). Graph coloring algorithms. Mathematics Report, Technical
University Clausthal, 1-9.
<http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung
/publications/2002/gca.pdf>

-}

{-

Copyright (C) 2012, Google Inc.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.

-}

module Ganeti.HTools.Graph
  ( -- * Types
    Color
  , VertColorMap
  , ColorVertMap
    -- * Creation
  , emptyVertColorMap
    -- * Coloring
  , colorInOrder
  , colorLF
  , colorDsatur
  , colorDcolor
  , isColorable
    -- * Color map transformations
  , colorVertMap
    -- * Vertex characteristics
  , verticesByDegreeDesc
  , verticesByDegreeAsc
  , neighbors
  , hasLoop
  , isUndirected
  ) where

import Data.Maybe
import Data.Ord
import Data.List

import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Graph as Graph
import qualified Data.Array as Array

-- * Type declarations

-- | Node colors.
type Color = Int

-- | Saturation: number of colored neighbors.
type Satur = Int

-- | Vertex to Color association.
type VertColorMap = IntMap.IntMap Color

-- | Color to Vertex association.
type ColorVertMap = IntMap.IntMap [Int]

-- * Vertices characteristics

-- | (vertex, degree) tuples on a graph.
verticesDegree :: Graph.Graph -> [(Graph.Vertex, Int)]
verticesDegree g = Array.assocs $ Graph.outdegree g

-- | vertices of a graph, sorted by ascending degree.
verticesByDegreeDesc :: Graph.Graph -> [Graph.Vertex]
verticesByDegreeDesc g =
  map fst . sortBy (flip (comparing snd)) $ verticesDegree g

-- | vertices of a graph, sorted by descending degree.
verticesByDegreeAsc :: Graph.Graph -> [Graph.Vertex]
verticesByDegreeAsc g = map fst . sortBy (comparing snd) $ verticesDegree g

-- | Get the neighbors of a vertex.
neighbors :: Graph.Graph -> Graph.Vertex -> [Graph.Vertex]
neighbors g v = g Array.! v

-- | Check whether a graph has no loops.
-- (vertices connected to themselves)
hasLoop :: Graph.Graph -> Bool
hasLoop g = any vLoops $ Graph.vertices g
    where vLoops v = v `elem` neighbors g v

-- | Check whether a graph is undirected
isUndirected :: Graph.Graph -> Bool
isUndirected g =
  (sort . Graph.edges) g == (sort . Graph.edges . Graph.transposeG) g

-- * Coloring

-- | Empty color map.
emptyVertColorMap :: VertColorMap
emptyVertColorMap = IntMap.empty

-- | Check whether a graph is colorable.
isColorable :: Graph.Graph -> Bool
isColorable g = isUndirected g && not (hasLoop g)

-- | Get the colors of a list of vertices.
-- Any uncolored vertices are ignored.
verticesColors :: VertColorMap -> [Graph.Vertex] -> [Color]
verticesColors cMap = mapMaybe (`IntMap.lookup` cMap)

-- | Get the colors of a list of vertices.
-- Any uncolored vertices are ignored.
verticesColorSet :: VertColorMap -> [Graph.Vertex] -> IntSet.IntSet
verticesColorSet cMap = IntSet.fromList . mapMaybe (`IntMap.lookup` cMap)

-- | Get the colors of the neighbors of a vertex.
neighColors :: Graph.Graph -> VertColorMap -> Graph.Vertex -> [Color]
neighColors g cMap v = verticesColors cMap $ neighbors g v

-- | Color one node.
colorNode :: Graph.Graph -> VertColorMap -> Graph.Vertex -> Color
-- use of "head" is A-ok as the source is an infinite list
colorNode g cMap v = head $ filter notNeighColor [0..]
    where notNeighColor = (`notElem` neighColors g cMap v)

-- | Color a node returning the updated color map.
colorNodeInMap :: Graph.Graph -> Graph.Vertex -> VertColorMap -> VertColorMap
colorNodeInMap g v cMap = IntMap.insert v newcolor cMap
    where newcolor = colorNode g cMap v

-- | Color greedily all nodes in the given order.
colorInOrder :: Graph.Graph -> [Graph.Vertex] -> VertColorMap<commit_msg>remove duplicate code in Graph.hs<commit_after>{-| 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:
<NAME>.; <NAME>. (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:
<NAME>. (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:
<NAME>. (2002). Graph coloring algorithms. Mathematics Report, Technical
University Clausthal, 1-9.
<http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung
/publications/2002/gca.pdf>

-}

{-

Copyright (C) 2012, Google Inc.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.

-}

module Ganeti.HTools.Graph
  ( -- * Types
    Color
  , VertColorMap
  , ColorVertMap
    -- * Creation
  , emptyVertColorMap
    -- * Coloring
  , colorInOrder
  , colorLF
  , colorDsatur
  , colorDcolor
  , isColorable
    -- * Color map transformations
  , colorVertMap
    -- * Vertex characteristics
  , verticesByDegreeDesc
  , verticesByDegreeAsc
  , neighbors
  , hasLoop
  , isUndirected
  ) where

import Data.Maybe
import Data.Ord
import Data.List

import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Graph as Graph
import qualified Data.Array as Array

-- * Type declarations

-- | Node colors.
type Color = Int

-- | Saturation: number of colored neighbors.
type Satur = Int

-- | Vertex to Color association.
type VertColorMap = IntMap.IntMap Color

-- | Color to Vertex association.
type ColorVertMap = IntMap.IntMap [Int]

-- * Vertices characteristics

-- | (vertex, degree) tuples on a graph.
verticesDegree :: Graph.Graph -> [(Graph.Vertex, Int)]
verticesDegree g = Array.assocs $ Graph.outdegree g

-- | vertices of a graph, sorted by ascending degree.
verticesByDegreeDesc :: Graph.Graph -> [Graph.Vertex]
verticesByDegreeDesc g =
  map fst . sortBy (flip (comparing snd)) $ verticesDegree g

-- | vertices of a graph, sorted by descending degree.
verticesByDegreeAsc :: Graph.Graph -> [Graph.Vertex]
verticesByDegreeAsc g = map fst . sortBy (comparing snd) $ verticesDegree g

-- | Get the neighbors of a vertex.
neighbors :: Graph.Graph -> Graph.Vertex -> [Graph.Vertex]
neighbors g v = g Array.! v

-- | Check whether a graph has no loops.
-- (vertices connected to themselves)
hasLoop :: Graph.Graph -> Bool
hasLoop g = any vLoops $ Graph.vertices g
    where vLoops v = v `elem` neighbors g v

-- | Check whether a graph is undirected
isUndirected :: Graph.Graph -> Bool
isUndirected g =
  (sort . Graph.edges) g == (sort . Graph.edges . Graph.transposeG) g

-- * Coloring

-- | Empty color map.
emptyVertColorMap :: VertColorMap
emptyVertColorMap = IntMap.empty

-- | Check whether a graph is colorable.
isColorable :: Graph.Graph -> Bool
isColorable g = isUndirected g && not (hasLoop g)

-- | Get the colors of a list of vertices.
-- Any uncolored vertices are ignored.
verticesColors :: VertColorMap -> [Graph.Vertex] -> [Color]
verticesColors cMap = mapMaybe (`IntMap.lookup` cMap)

-- | Get the set of colors of a list of vertices.
-- Any uncolored vertices are ignored.
verticesColorSet :: VertColorMap -> [Graph.Vertex] -> IntSet.IntSet
verticesColorSet cMap = IntSet.fromList . verticesColors cMap

-- | Get the colors of the neighbors of a vertex.
neighColors :: Graph.Graph -> VertColorMap -> Graph.Vertex -> [Color]
neighColors g cMap v = verticesColors cMap $ neighbors g v

-- | Color one node.
colorNode :: Graph.Graph -> VertColorMap -> Graph.Vertex -> Color
-- use of "head" is A-ok as the source is an infinite list
colorNode g cMap v = head $ filter notNeighColor [0..]
    where notNeighColor = (`notElem` neighColors g cMap v)

-- | Color a node returning the updated color map.
colorNodeInMap :: Graph.Graph -> Graph.Vertex -> VertColorMap -> VertColorMap
colorNodeInMap g v cMap = IntMap.insert v newcolor cMap
    where newcolor = colorNode g cMap v

-- | Color greedily all nodes in the given order.
colorInOrder :: Graph.Graph -> [Graph.Vertex] -> VertColorMap
{'fraction_non_alphanumeric': 0.09711982699302074, 'fraction_numerical': 0.020446279366951734, 'mean_word_length': 3.749766573295985, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 67, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6513450', 'n_tokens_mistral': 3289, 'n_tokens_neox': 3068, 'n_words': 1180}