<!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>Digraph</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_Digraph.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">Digraph</p></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">data</span> <a href="#t:Graph">Graph</a> node</li><li class="src short"><a href="#v:graphFromVerticesAndAdjacency">graphFromVerticesAndAdjacency</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key)] -> [(key, key)] -> <a href="Digraph.html#t:Graph">Graph</a> (node, key)</li><li class="src short"><a href="#v:graphFromEdgedVertices">graphFromEdgedVertices</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> <a href="Digraph.html#t:Graph">Graph</a> (<a href="Digraph.html#t:Node">Node</a> key payload)</li><li class="src short"><span class="keyword">data</span> <a href="#t:SCC">SCC</a> vertex<ul class="subs"><li>= <a href="#v:AcyclicSCC">AcyclicSCC</a> vertex </li><li>| <a href="#v:CyclicSCC">CyclicSCC</a> [vertex] </li></ul></li><li class="src short"><span class="keyword">type</span> <a href="#t:Node">Node</a> key payload = (payload, key, [key])</li><li class="src short"><a href="#v:flattenSCC">flattenSCC</a> :: <a href="Digraph.html#t:SCC">SCC</a> a -> [a]</li><li class="src short"><a href="#v:flattenSCCs">flattenSCCs</a> :: [<a href="Digraph.html#t:SCC">SCC</a> a] -> [a]</li><li class="src short"><a href="#v:stronglyConnCompG">stronglyConnCompG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [<a href="Digraph.html#t:SCC">SCC</a> node]</li><li class="src short"><a href="#v:topologicalSortG">topologicalSortG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [node]</li><li class="src short"><a href="#v:dfsTopSortG">dfsTopSortG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</li><li class="src short"><a href="#v:verticesG">verticesG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [node]</li><li class="src short"><a href="#v:edgesG">edgesG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [Edge node]</li><li class="src short"><a href="#v:hasVertexG">hasVertexG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:reachableG">reachableG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> [node]</li><li class="src short"><a href="#v:transposeG">transposeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> <a href="Digraph.html#t:Graph">Graph</a> node</li><li class="src short"><a href="#v:outdegreeG">outdegreeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:indegreeG">indegreeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:vertexGroupsG">vertexGroupsG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</li><li class="src short"><a href="#v:emptyG">emptyG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:componentsG">componentsG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</li><li class="src short"><a href="#v:findCycle">findCycle</a> :: <span class="keyword">forall</span> payload key. <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> [payload]</li><li class="src short"><a href="#v:stronglyConnCompFromEdgedVertices">stronglyConnCompFromEdgedVertices</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> [<a href="Digraph.html#t:SCC">SCC</a> payload]</li><li class="src short"><a href="#v:stronglyConnCompFromEdgedVerticesR">stronglyConnCompFromEdgedVerticesR</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> [<a href="Digraph.html#t:SCC">SCC</a> (<a href="Digraph.html#t:Node">Node</a> key payload)]</li><li class="src short"><a href="#v:tabulate">tabulate</a> :: Bounds -> [Vertex] -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:preArr">preArr</a> :: Bounds -> Forest Vertex -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:components">components</a> :: IntGraph -> Forest Vertex</li><li class="src short"><a href="#v:undirected">undirected</a> :: IntGraph -> IntGraph</li><li class="src short"><a href="#v:back">back</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</li><li class="src short"><a href="#v:cross">cross</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</li><li class="src short"><a href="#v:forward">forward</a> :: IntGraph -> IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</li><li class="src short"><a href="#v:path">path</a> :: IntGraph -> Vertex -> Vertex -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:bcc">bcc</a> :: IntGraph -> Forest [Vertex]</li><li class="src short"><a href="#v:do_label">do_label</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> Tree Vertex -> Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>)</li><li class="src short"><a href="#v:bicomps">bicomps</a> :: Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> Forest [Vertex]</li><li class="src short"><a href="#v:collect">collect</a> :: Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, Tree [Vertex])</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Graph" class="def">Graph</a> node </p><div class="subs instances"><p id="control.i:Graph" class="caption collapser" onclick="toggleSection('i:Graph')">Instances</p><div id="section.i:Graph" class="show"><table><tr><td class="src"><a href="Outputable.html#t:Outputable">Outputable</a> node => <a href="Outputable.html#t:Outputable">Outputable</a> (<a href="Digraph.html#t:Graph">Graph</a> node)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:graphFromVerticesAndAdjacency" class="def">graphFromVerticesAndAdjacency</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key)] -> [(key, key)] -> <a href="Digraph.html#t:Graph">Graph</a> (node, key)</p></div><div class="top"><p class="src"><a name="v:graphFromEdgedVertices" class="def">graphFromEdgedVertices</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> <a href="Digraph.html#t:Graph">Graph</a> (<a href="Digraph.html#t:Node">Node</a> key payload)</p></div><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:SCC" class="def">SCC</a> vertex </p><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:AcyclicSCC" class="def">AcyclicSCC</a> vertex</td><td class="doc empty"> </td></tr><tr><td class="src"><a name="v:CyclicSCC" class="def">CyclicSCC</a> [vertex]</td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><p id="control.i:SCC" class="caption collapser" onclick="toggleSection('i:SCC')">Instances</p><div id="section.i:SCC" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Functor">Functor</a> <a href="Digraph.html#t:SCC">SCC</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="Outputable.html#t:PlatformOutputable">PlatformOutputable</a> a => <a href="Outputable.html#t:PlatformOutputable">PlatformOutputable</a> (<a href="Digraph.html#t:SCC">SCC</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="Outputable.html#t:Outputable">Outputable</a> a => <a href="Outputable.html#t:Outputable">Outputable</a> (<a href="Digraph.html#t:SCC">SCC</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Node" class="def">Node</a> key payload = (payload, key, [key])</p></div><div class="top"><p class="src"><a name="v:flattenSCC" class="def">flattenSCC</a> :: <a href="Digraph.html#t:SCC">SCC</a> a -> [a]</p></div><div class="top"><p class="src"><a name="v:flattenSCCs" class="def">flattenSCCs</a> :: [<a href="Digraph.html#t:SCC">SCC</a> a] -> [a]</p></div><div class="top"><p class="src"><a name="v:stronglyConnCompG" class="def">stronglyConnCompG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [<a href="Digraph.html#t:SCC">SCC</a> node]</p></div><div class="top"><p class="src"><a name="v:topologicalSortG" class="def">topologicalSortG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [node]</p></div><div class="top"><p class="src"><a name="v:dfsTopSortG" class="def">dfsTopSortG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</p></div><div class="top"><p class="src"><a name="v:verticesG" class="def">verticesG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [node]</p></div><div class="top"><p class="src"><a name="v:edgesG" class="def">edgesG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [Edge node]</p></div><div class="top"><p class="src"><a name="v:hasVertexG" class="def">hasVertexG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p></div><div class="top"><p class="src"><a name="v:reachableG" class="def">reachableG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> [node]</p></div><div class="top"><p class="src"><a name="v:transposeG" class="def">transposeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> <a href="Digraph.html#t:Graph">Graph</a> node</p></div><div class="top"><p class="src"><a name="v:outdegreeG" class="def">outdegreeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p></div><div class="top"><p class="src"><a name="v:indegreeG" class="def">indegreeG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> node -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p></div><div class="top"><p class="src"><a name="v:vertexGroupsG" class="def">vertexGroupsG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</p></div><div class="top"><p class="src"><a name="v:emptyG" class="def">emptyG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p></div><div class="top"><p class="src"><a name="v:componentsG" class="def">componentsG</a> :: <a href="Digraph.html#t:Graph">Graph</a> node -> [[node]]</p></div><div class="top"><p class="src"><a name="v:findCycle" class="def">findCycle</a> :: <span class="keyword">forall</span> payload key. <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> [payload]</p><div class="doc"><p>Find a reasonably short cycle a->b->c->a, in a strongly
connected component. The input nodes are presumed to be
a SCC, so you can start anywhere.
</p></div></div><div class="top"><p class="src"><a name="v:stronglyConnCompFromEdgedVertices" class="def">stronglyConnCompFromEdgedVertices</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> [<a href="Digraph.html#t:SCC">SCC</a> payload]</p></div><div class="top"><p class="src"><a name="v:stronglyConnCompFromEdgedVerticesR" class="def">stronglyConnCompFromEdgedVerticesR</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [<a href="Digraph.html#t:Node">Node</a> key payload] -> [<a href="Digraph.html#t:SCC">SCC</a> (<a href="Digraph.html#t:Node">Node</a> key payload)]</p></div><div class="top"><p class="src"><a name="v:tabulate" class="def">tabulate</a> :: Bounds -> [Vertex] -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p></div><div class="top"><p class="src"><a name="v:preArr" class="def">preArr</a> :: Bounds -> Forest Vertex -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p></div><div class="top"><p class="src"><a name="v:components" class="def">components</a> :: IntGraph -> Forest Vertex</p></div><div class="top"><p class="src"><a name="v:undirected" class="def">undirected</a> :: IntGraph -> IntGraph</p></div><div class="top"><p class="src"><a name="v:back" class="def">back</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</p></div><div class="top"><p class="src"><a name="v:cross" class="def">cross</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</p></div><div class="top"><p class="src"><a name="v:forward" class="def">forward</a> :: IntGraph -> IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> IntGraph</p></div><div class="top"><p class="src"><a name="v:path" class="def">path</a> :: IntGraph -> Vertex -> Vertex -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p></div><div class="top"><p class="src"><a name="v:bcc" class="def">bcc</a> :: IntGraph -> Forest [Vertex]</p></div><div class="top"><p class="src"><a name="v:do_label" class="def">do_label</a> :: IntGraph -> Table <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> Tree Vertex -> Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>)</p></div><div class="top"><p class="src"><a name="v:bicomps" class="def">bicomps</a> :: Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> Forest [Vertex]</p></div><div class="top"><p class="src"><a name="v:collect" class="def">collect</a> :: Tree (Vertex, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, Tree [Vertex])</p></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
>
i586
>
media
>
core-release
>
by-pkgid
>
6e204a966e8c42d976f99a1700ce5f20
>
files
>
2850
