<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="previous" href="Path.Dijkstra.html">
<link rel="Up" href="Path.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Sig" rel="Chapter" href="Sig.html">
<link title="Sig_pack" rel="Chapter" href="Sig_pack.html">
<link title="Dot_ast" rel="Chapter" href="Dot_ast.html">
<link title="Util" rel="Chapter" href="Util.html">
<link title="Persistent" rel="Chapter" href="Persistent.html">
<link title="Imperative" rel="Chapter" href="Imperative.html">
<link title="Delaunay" rel="Chapter" href="Delaunay.html">
<link title="Builder" rel="Chapter" href="Builder.html">
<link title="Classic" rel="Chapter" href="Classic.html">
<link title="Rand" rel="Chapter" href="Rand.html">
<link title="Oper" rel="Chapter" href="Oper.html">
<link title="Path" rel="Chapter" href="Path.html">
<link title="Traverse" rel="Chapter" href="Traverse.html">
<link title="Coloring" rel="Chapter" href="Coloring.html">
<link title="Topological" rel="Chapter" href="Topological.html">
<link title="Components" rel="Chapter" href="Components.html">
<link title="Kruskal" rel="Chapter" href="Kruskal.html">
<link title="Flow" rel="Chapter" href="Flow.html">
<link title="Graphviz" rel="Chapter" href="Graphviz.html">
<link title="Gml" rel="Chapter" href="Gml.html">
<link title="Dot" rel="Chapter" href="Dot.html">
<link title="Pack" rel="Chapter" href="Pack.html">
<link title="Gmap" rel="Chapter" href="Gmap.html">
<link title="Minsep" rel="Chapter" href="Minsep.html">
<link title="Cliquetree" rel="Chapter" href="Cliquetree.html">
<link title="Mcs_m" rel="Chapter" href="Mcs_m.html">
<link title="Md" rel="Chapter" href="Md.html">
<link title="Strat" rel="Chapter" href="Strat.html"><title>Path.Check</title>
</head>
<body>
<div class="navbar"><a href="Path.Dijkstra.html">Previous</a>
<a href="Path.html">Up</a>
</div>
<center><h1>Functor <a href="type_Path.Check.html">Path.Check</a></h1></center>
<br>
<pre><span class="keyword">module</span> Check: <div class="sig_block"><code class="code">functor (</code><code class="code">G</code><code class="code"> : </code><code class="code">sig</code><div class="sig_block"><pre><span class="keyword">type</span> <a name="TYPEt"></a><code class="type"></code>t </pre>
<pre><span class="keyword">module</span> <a href="Path.Check.V.html">V</a>: <code class="type"><a href="Sig.COMPARABLE.html">Sig.COMPARABLE</a></code><code class="type"> </code></pre><pre><span class="keyword">val</span> <a name="VALiter_succ"></a>iter_succ : <code class="type">(V.t -> unit) -> t -> V.t -> unit</code></pre></div><code class="code">end</code><code class="code">) -> </code><code class="code">sig</code> <a href="Path.Check.html">..</a> <code class="code">end</code></div></pre>Check for a path.<br>
<table border="0" cellpadding="3" width="100%">
<tr>
<td align="left" valign="top" width="1%%"><b>Parameters: </b></td>
<td>
<table class="paramstable">
<tr>
<td align="center" valign="top" width="15%">
<code>G</code></td>
<td align="center" valign="top">:</td>
<td><code class="type">sig
type t
module V : <a href="Sig.COMPARABLE.html">Sig.COMPARABLE</a>
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end</code>
</table>
</td>
</tr>
</table>
<hr width="100%">
<pre><span class="keyword">type</span> <a name="TYPEpath_checker"></a><code class="type"></code>path_checker </pre>
<div class="info">
the abstract data type of a path checker; this is a mutable data
structure<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcreate"></a>create : <code class="type"><a href="Path.G.html#TYPEt">Path.G.t</a> -> <a href="Path.Check.html#TYPEpath_checker">path_checker</a></code></pre><div class="info">
<code class="code">create g</code> builds a new path checker for the graph <code class="code">g</code>;
if the graph is mutable, it must not be mutated while this path
checker is in use (through the function <code class="code">check_path</code> below).<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcheck_path"></a>check_path : <code class="type"><a href="Path.Check.html#TYPEpath_checker">path_checker</a> -> G.V.t -> G.V.t -> bool</code></pre><div class="info">
<code class="code">check_path pc v1 v2</code> checks whether there is a path from <code class="code">v1</code> to
<code class="code">v2</code> in the graph associated to the path checker <code class="code">pc</code>.
<p>
Complexity: The path checker contains a cache of all results computed
so far. This cache is implemented with a hash table so access in this
cache is usually O(1). When the result is not in the cache, Dijkstra's
algorithm is run to check for the path, and all intermediate results
are cached.
<p>
Note: if checks are to be done for almost all pairs of vertices, it
may be more efficient to compute the transitive closure of the graph
(see module <code class="code">Oper</code>).<br>
</div>
</body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
1280a9d763ea6574bb6098d1ca3767c9
>
files
>
123
