<!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>Data.Graph</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_Data-Graph.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">containers-0.4.2.1: Assorted concrete container types</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>portable</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Maintainer</th><td>libraries@haskell.org</td></tr><tr><th>Safe Haskell</th><td>Trustworthy</td></tr></table><p class="caption">Data.Graph</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">External interface
</a></li><li><a href="#g:2">Graphs
</a><ul><li><a href="#g:3">Building graphs
</a></li><li><a href="#g:4">Graph properties
</a></li></ul></li><li><a href="#g:5">Algorithms
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A version of the graph algorithms described in:
</p><p><em>Lazy Depth-First Search and Linear Graph Algorithms in Haskell</em>,
by David King and John Launchbury.
</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"><a href="#v:stronglyConnComp">stronglyConnComp</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> [<a href="Data-Graph.html#t:SCC">SCC</a> node]</li><li class="src short"><a href="#v:stronglyConnCompR">stronglyConnCompR</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> [<a href="Data-Graph.html#t:SCC">SCC</a> (node, key, [key])]</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"><a href="#v:flattenSCC">flattenSCC</a> :: <a href="Data-Graph.html#t:SCC">SCC</a> vertex -> [vertex]</li><li class="src short"><a href="#v:flattenSCCs">flattenSCCs</a> :: [<a href="Data-Graph.html#t:SCC">SCC</a> a] -> [a]</li><li class="src short"><span class="keyword">type</span> <a href="#t:Graph">Graph</a> = <a href="Data-Graph.html#t:Table">Table</a> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</li><li class="src short"><span class="keyword">type</span> <a href="#t:Table">Table</a> a = <a href="../array-0.4.0.0/Data-Array.html#t:Array">Array</a> <a href="Data-Graph.html#t:Vertex">Vertex</a> a</li><li class="src short"><span class="keyword">type</span> <a href="#t:Bounds">Bounds</a> = (<a href="Data-Graph.html#t:Vertex">Vertex</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a>)</li><li class="src short"><span class="keyword">type</span> <a href="#t:Edge">Edge</a> = (<a href="Data-Graph.html#t:Vertex">Vertex</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a>)</li><li class="src short"><span class="keyword">type</span> <a href="#t:Vertex">Vertex</a> = <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:graphFromEdges">graphFromEdges</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> (<a href="Data-Graph.html#t:Graph">Graph</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a> -> (node, key, [key]), key -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="Data-Graph.html#t:Vertex">Vertex</a>)</li><li class="src short"><a href="#v:graphFromEdges-39-">graphFromEdges'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> (<a href="Data-Graph.html#t:Graph">Graph</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a> -> (node, key, [key]))</li><li class="src short"><a href="#v:buildG">buildG</a> :: <a href="Data-Graph.html#t:Bounds">Bounds</a> -> [<a href="Data-Graph.html#t:Edge">Edge</a>] -> <a href="Data-Graph.html#t:Graph">Graph</a></li><li class="src short"><a href="#v:transposeG">transposeG</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Graph">Graph</a></li><li class="src short"><a href="#v:vertices">vertices</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</li><li class="src short"><a href="#v:edges">edges</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Edge">Edge</a>]</li><li class="src short"><a href="#v:outdegree">outdegree</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Table">Table</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:indegree">indegree</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Table">Table</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:dfs">dfs</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>] -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></li><li class="src short"><a href="#v:dff">dff</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></li><li class="src short"><a href="#v:topSort">topSort</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</li><li class="src short"><a href="#v:components">components</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></li><li class="src short"><a href="#v:scc">scc</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></li><li class="src short"><a href="#v:bcc">bcc</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</li><li class="src short"><a href="#v:reachable">reachable</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</li><li class="src short"><a href="#v:path">path</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short">module <a href="Data-Tree.html">Data.Tree</a></li></ul></div><div id="interface"><h1 id="g:1">External interface
</h1><div class="top"><p class="src"><a name="v:stronglyConnComp" class="def">stronglyConnComp</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key</td><td class="doc empty"> </td></tr><tr><td class="src">=> [(node, key, [key])]</td><td class="doc"><p>The graph: a list of nodes uniquely identified by keys,
with a list of keys of nodes this node has edges to.
The out-list may contain keys that don't correspond to
nodes of the graph; such edges are ignored.
</p></td></tr><tr><td class="src">-> [<a href="Data-Graph.html#t:SCC">SCC</a> node]</td><td class="doc empty"> </td></tr></table></div><div class="doc"><p>The strongly connected components of a directed graph, topologically
sorted.
</p></div></div><div class="top"><p class="src"><a name="v:stronglyConnCompR" class="def">stronglyConnCompR</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key</td><td class="doc empty"> </td></tr><tr><td class="src">=> [(node, key, [key])]</td><td class="doc"><p>The graph: a list of nodes uniquely identified by keys,
with a list of keys of nodes this node has edges to.
The out-list may contain keys that don't correspond to
nodes of the graph; such edges are ignored.
</p></td></tr><tr><td class="src">-> [<a href="Data-Graph.html#t:SCC">SCC</a> (node, key, [key])]</td><td class="doc"><p>Topologically sorted
</p></td></tr></table></div><div class="doc"><p>The strongly connected components of a directed graph, topologically
sorted. The function is the same as <code><a href="Data-Graph.html#v:stronglyConnComp">stronglyConnComp</a></code>, except that
all the information about each node retained.
This interface is used when you expect to apply <code><a href="Data-Graph.html#t:SCC">SCC</a></code> to
(some of) the result of <code><a href="Data-Graph.html#t:SCC">SCC</a></code>, so you don't want to lose the
dependency information.
</p></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:SCC" class="def">SCC</a> vertex </p><div class="doc"><p>Strongly connected component.
</p></div><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"><p>A single vertex that is not
in any cycle.
</p></td></tr><tr><td class="src"><a name="v:CyclicSCC" class="def">CyclicSCC</a> [vertex]</td><td class="doc"><p>A maximal set of mutually
reachable vertices.
</p></td></tr></table></div></div><div class="top"><p class="src"><a name="v:flattenSCC" class="def">flattenSCC</a> :: <a href="Data-Graph.html#t:SCC">SCC</a> vertex -> [vertex]</p><div class="doc"><p>The vertices of a strongly connected component.
</p></div></div><div class="top"><p class="src"><a name="v:flattenSCCs" class="def">flattenSCCs</a> :: [<a href="Data-Graph.html#t:SCC">SCC</a> a] -> [a]</p><div class="doc"><p>The vertices of a list of strongly connected components.
</p></div></div><h1 id="g:2">Graphs
</h1><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Graph" class="def">Graph</a> = <a href="Data-Graph.html#t:Table">Table</a> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</p><div class="doc"><p>Adjacency list representation of a graph, mapping each vertex to its
list of successors.
</p></div></div><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Table" class="def">Table</a> a = <a href="../array-0.4.0.0/Data-Array.html#t:Array">Array</a> <a href="Data-Graph.html#t:Vertex">Vertex</a> a</p><div class="doc"><p>Table indexed by a contiguous set of vertices.
</p></div></div><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Bounds" class="def">Bounds</a> = (<a href="Data-Graph.html#t:Vertex">Vertex</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a>)</p><div class="doc"><p>The bounds of a <code><a href="Data-Graph.html#t:Table">Table</a></code>.
</p></div></div><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Edge" class="def">Edge</a> = (<a href="Data-Graph.html#t:Vertex">Vertex</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a>)</p><div class="doc"><p>An edge from the first vertex to the second.
</p></div></div><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Vertex" class="def">Vertex</a> = <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p>Abstract representation of vertices.
</p></div></div><h2 id="g:3">Building graphs
</h2><div class="top"><p class="src"><a name="v:graphFromEdges" class="def">graphFromEdges</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> (<a href="Data-Graph.html#t:Graph">Graph</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a> -> (node, key, [key]), key -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="Data-Graph.html#t:Vertex">Vertex</a>)</p><div class="doc"><p>Build a graph from a list of nodes uniquely identified by keys,
with a list of keys of nodes this node should have edges to.
The out-list may contain keys that don't correspond to
nodes of the graph; they are ignored.
</p></div></div><div class="top"><p class="src"><a name="v:graphFromEdges-39-" class="def">graphFromEdges'</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> key => [(node, key, [key])] -> (<a href="Data-Graph.html#t:Graph">Graph</a>, <a href="Data-Graph.html#t:Vertex">Vertex</a> -> (node, key, [key]))</p><div class="doc"><p>Identical to <code><a href="Data-Graph.html#v:graphFromEdges">graphFromEdges</a></code>, except that the return value
does not include the function which maps keys to vertices. This
version of <code><a href="Data-Graph.html#v:graphFromEdges">graphFromEdges</a></code> is for backwards compatibility.
</p></div></div><div class="top"><p class="src"><a name="v:buildG" class="def">buildG</a> :: <a href="Data-Graph.html#t:Bounds">Bounds</a> -> [<a href="Data-Graph.html#t:Edge">Edge</a>] -> <a href="Data-Graph.html#t:Graph">Graph</a></p><div class="doc"><p>Build a graph from a list of edges.
</p></div></div><div class="top"><p class="src"><a name="v:transposeG" class="def">transposeG</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Graph">Graph</a></p><div class="doc"><p>The graph obtained by reversing all edges.
</p></div></div><h2 id="g:4">Graph properties
</h2><div class="top"><p class="src"><a name="v:vertices" class="def">vertices</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</p><div class="doc"><p>All vertices of a graph.
</p></div></div><div class="top"><p class="src"><a name="v:edges" class="def">edges</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Edge">Edge</a>]</p><div class="doc"><p>All edges of a graph.
</p></div></div><div class="top"><p class="src"><a name="v:outdegree" class="def">outdegree</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Table">Table</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p>A table of the count of edges from each node.
</p></div></div><div class="top"><p class="src"><a name="v:indegree" class="def">indegree</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Table">Table</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p>A table of the count of edges into each node.
</p></div></div><h1 id="g:5">Algorithms
</h1><div class="top"><p class="src"><a name="v:dfs" class="def">dfs</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>] -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></p><div class="doc"><p>A spanning forest of the part of the graph reachable from the listed
vertices, obtained from a depth-first search of the graph starting at
each of the listed vertices in order.
</p></div></div><div class="top"><p class="src"><a name="v:dff" class="def">dff</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></p><div class="doc"><p>A spanning forest of the graph, obtained from a depth-first search of
the graph starting from each vertex in an unspecified order.
</p></div></div><div class="top"><p class="src"><a name="v:topSort" class="def">topSort</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</p><div class="doc"><p>A topological sort of the graph.
The order is partially specified by the condition that a vertex <em>i</em>
precedes <em>j</em> whenever <em>j</em> is reachable from <em>i</em> but not vice versa.
</p></div></div><div class="top"><p class="src"><a name="v:components" class="def">components</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></p><div class="doc"><p>The connected components of a graph.
Two vertices are connected if there is a path between them, traversing
edges in either direction.
</p></div></div><div class="top"><p class="src"><a name="v:scc" class="def">scc</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> <a href="Data-Graph.html#t:Vertex">Vertex</a></p><div class="doc"><p>The strongly connected components of a graph.
</p></div></div><div class="top"><p class="src"><a name="v:bcc" class="def">bcc</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Tree.html#t:Forest">Forest</a> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</p><div class="doc"><p>The biconnected components of a graph.
An undirected graph is biconnected if the deletion of any vertex
leaves it connected.
</p></div></div><div class="top"><p class="src"><a name="v:reachable" class="def">reachable</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> [<a href="Data-Graph.html#t:Vertex">Vertex</a>]</p><div class="doc"><p>A list of vertices reachable from a given vertex.
</p></div></div><div class="top"><p class="src"><a name="v:path" class="def">path</a> :: <a href="Data-Graph.html#t:Graph">Graph</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> <a href="Data-Graph.html#t:Vertex">Vertex</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p>Is the second vertex reachable from the first?
</p></div></div><div class="top"><p class="src">module <a href="Data-Tree.html">Data.Tree</a></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
>
2589
