<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>GraphBase</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_GraphBase.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">ghc-7.4.2: The GHC API</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>None</td></tr></table><p class="caption">GraphBase</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Types for the general graph colorer.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">type</span> <a href="#t:Triv">Triv</a> k cls color = cls -> <a href="UniqSet.html#t:UniqSet">UniqSet</a> k -> <a href="UniqSet.html#t:UniqSet">UniqSet</a> color -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><span class="keyword">data</span> <a href="#t:Graph">Graph</a> k cls color = <a href="#v:Graph">Graph</a> {<ul class="subs"><li><a href="#v:graphMap">graphMap</a> :: <a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color)</li></ul>}</li><li class="src short"><a href="#v:initGraph">initGraph</a> :: <a href="GraphBase.html#t:Graph">Graph</a> k cls color</li><li class="src short"><a href="#v:graphMapModify">graphMapModify</a> :: (<a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color) -> <a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color)) -> <a href="GraphBase.html#t:Graph">Graph</a> k cls color -> <a href="GraphBase.html#t:Graph">Graph</a> k cls color</li><li class="src short"><span class="keyword">data</span> <a href="#t:Node">Node</a> k cls color = <a href="#v:Node">Node</a> {<ul class="subs"><li><a href="#v:nodeId">nodeId</a> :: k</li><li><a href="#v:nodeClass">nodeClass</a> :: cls</li><li><a href="#v:nodeColor">nodeColor</a> :: <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> color</li><li><a href="#v:nodeConflicts">nodeConflicts</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> k</li><li><a href="#v:nodeExclusions">nodeExclusions</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> color</li><li><a href="#v:nodePreference">nodePreference</a> :: [color]</li><li><a href="#v:nodeCoalesce">nodeCoalesce</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> k</li></ul>}</li><li class="src short"><a href="#v:newNode">newNode</a> :: k -> cls -> <a href="GraphBase.html#t:Node">Node</a> k cls color</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Triv" class="def">Triv</a> k cls color = cls -> <a href="UniqSet.html#t:UniqSet">UniqSet</a> k -> <a href="UniqSet.html#t:UniqSet">UniqSet</a> color -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p>A fn to check if a node is trivially colorable
For graphs who's color classes are disjoint then a node is 'trivially colorable'
when it has less neighbors and exclusions than available colors for that node.
</p><p>For graph's who's color classes overlap, ie some colors alias other colors, then
this can be a bit more tricky. There is a general way to calculate this, but
it's likely be too slow for use in the code. The coloring algorithm takes
a canned function which can be optimised by the user to be specific to the
specific graph being colored.
</p><p>for details, see <a href="A Generalised Algorithm for Graph-Coloring Register Allocation.html">A Generalised Algorithm for Graph-Coloring Register Allocation</a>
Smith, Ramsey, Holloway - PLDI 2004.
</p></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Graph" class="def">Graph</a> k cls color </p><div class="doc"><p>The Interference graph.
There used to be more fields, but they were turfed out in a previous revision.
maybe we'll want more later..
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:Graph" class="def">Graph</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div class="subs fields"><p class="caption">Fields</p><dl><dt class="src"><a name="v:graphMap" class="def">graphMap</a> :: <a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color)</dt><dd class="doc"><p>All active nodes in the graph.
</p></dd></dl><div class="clear"></div></div></td></tr></table></div></div><div class="top"><p class="src"><a name="v:initGraph" class="def">initGraph</a> :: <a href="GraphBase.html#t:Graph">Graph</a> k cls color</p><div class="doc"><p>An empty graph.
</p></div></div><div class="top"><p class="src"><a name="v:graphMapModify" class="def">graphMapModify</a> :: (<a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color) -> <a href="UniqFM.html#t:UniqFM">UniqFM</a> (<a href="GraphBase.html#t:Node">Node</a> k cls color)) -> <a href="GraphBase.html#t:Graph">Graph</a> k cls color -> <a href="GraphBase.html#t:Graph">Graph</a> k cls color</p><div class="doc"><p>Modify the finite map holding the nodes in the graph.
</p></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Node" class="def">Node</a> k cls color </p><div class="doc"><p>Graph nodes.
Represents a thing that can conflict with another thing.
For the register allocater the nodes represent registers.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:Node" class="def">Node</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div class="subs fields"><p class="caption">Fields</p><dl><dt class="src"><a name="v:nodeId" class="def">nodeId</a> :: k</dt><dd class="doc"><p>A unique identifier for this node.
</p></dd><dt class="src"><a name="v:nodeClass" class="def">nodeClass</a> :: cls</dt><dd class="doc"><p>The class of this node,
determines the set of colors that can be used.
</p></dd><dt class="src"><a name="v:nodeColor" class="def">nodeColor</a> :: <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> color</dt><dd class="doc"><p>The color of this node, if any.
</p></dd><dt class="src"><a name="v:nodeConflicts" class="def">nodeConflicts</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> k</dt><dd class="doc"><p>Neighbors which must be colored differently to this node.
</p></dd><dt class="src"><a name="v:nodeExclusions" class="def">nodeExclusions</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> color</dt><dd class="doc"><p>Colors that cannot be used by this node.
</p></dd><dt class="src"><a name="v:nodePreference" class="def">nodePreference</a> :: [color]</dt><dd class="doc"><p>Colors that this node would prefer to be, in decending order.
</p></dd><dt class="src"><a name="v:nodeCoalesce" class="def">nodeCoalesce</a> :: <a href="UniqSet.html#t:UniqSet">UniqSet</a> k</dt><dd class="doc"><p>Neighbors that this node would like to be colored the same as.
</p></dd></dl><div class="clear"></div></div></td></tr></table></div></div><div class="top"><p class="src"><a name="v:newNode" class="def">newNode</a> :: k -> cls -> <a href="GraphBase.html#t:Node">Node</a> k cls color</p><div class="doc"><p>An empty node.
</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.11.0</p></div></body></html>
distrib
>
Mageia
>
5
>
x86_64
>
media
>
core-release
>
by-pkgid
>
956c458aa5fe9afc4d2c00cb7b491287
>
files
>
2890
