/usr/lib/swi-prolog/doc/Manual/ugraphs.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

<HTML>
<HEAD>
<TITLE>SWI-Prolog 5.11.18 Reference Manual: Section A.25</TITLE><LINK REL=home HREF="index.html">
<LINK REL=contents HREF="Contents.html">
<LINK REL=index HREF="DocIndex.html">
<LINK REL=summary HREF="summary.html">
<LINK REL=previous HREF="threadpool.html">
<LINK REL=next HREF="url.html">
<STYLE type="text/css">
/* Style sheet for SWI-Prolog latex2html
*/

dd.defbody
{ margin-bottom: 1em;
}

dt.pubdef
{ background-color: #c5e1ff;
}

dt.multidef
{ background-color: #c8ffc7;
}

.bib dd
{ margin-bottom: 1em;
}

.bib dt
{ float: left;
margin-right: 1.3ex;
}

pre.code
{ margin-left: 1.5em;
margin-right: 1.5em;
border: 1px dotted;
padding-top: 5px;
padding-left: 5px;
padding-bottom: 5px;
background-color: #f8f8f8;
}

div.navigate
{ text-align: center;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
}

div.title
{ text-align: center;
padding-bottom: 1em;
font-size: 200%;
font-weight: bold;
}

div.author
{ text-align: center;
font-style: italic;
}

div.abstract
{ margin-top: 2em;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
margin-left: 10%; margin-right:10%;
}

div.abstract-title
{ text-align: center;
padding: 5px;
font-size: 120%;
font-weight: bold;
}

div.toc-h1
{ font-size: 200%;
font-weight: bold;
}

div.toc-h2
{ font-size: 120%;
font-weight: bold;
margin-left: 2em;
}

div.toc-h3
{ font-size: 100%;
font-weight: bold;
margin-left: 4em;
}

div.toc-h4
{ font-size: 100%;
margin-left: 6em;
}

span.sec-nr
{
}

span.sec-title
{
}

span.pred-ext
{ font-weight: bold;
}

span.pred-tag
{ float: right;
padding-top: 0.2em;
font-size: 80%;
font-style: italic;
color: #202020;
}

/* Footnotes */

sup.fn { color: blue; text-decoration: underline; }
span.fn-text { display: none; }
sup.fn span {display: none;}
sup:hover span
{ display: block !important;
position: absolute; top: auto; left: auto; width: 80%;
color: #000; background: white;
border: 2px solid;
padding: 5px; margin: 10px; z-index: 100;
font-size: smaller;
}
</STYLE>
</HEAD>
<BODY BGCOLOR="white">
<DIV class="navigate"><A class="nav" href="index.html"><IMG SRC="home.gif" BORDER=0 ALT="Home"></A>
<A class="nav" href="Contents.html"><IMG SRC="index.gif" BORDER=0 ALT="Contents"></A>
<A class="nav" href="DocIndex.html"><IMG SRC="yellow_pages.gif" BORDER=0 ALT="Index"></A>
<A class="nav" href="summary.html"><IMG SRC="info.gif" BORDER=0 ALT="Summary"></A>
<A class="nav" href="threadpool.html"><IMG SRC="prev.gif" BORDER=0 ALT="Previous"></A>
<A class="nav" href="url.html"><IMG SRC="next.gif" BORDER=0 ALT="Next"></A>
</DIV>

<H2><A NAME="sec:A.25"><SPAN class="sec-nr">A.25</SPAN> <SPAN class="sec-title">library(ugraphs): 
Unweighted Graphs</SPAN></A></H2>

<A NAME="ugraphs"></A>
<A NAME="sec:lib:ugraphs"></A> Authors: <EM>Richard O'Keefe &amp; Vitor 
Santos Costa</EM>
<BLOCKQUOTE><I>Implementation and documentation are copied from YAP 
5.0.1. The
<CODE>library(ugraph)</CODE> library is based on code originally written 
by Richard O'Keefe. The code was then extended to be compatible with the 
SICStus Prolog ugraphs library. Code and documentation have been cleaned 
and style has been changed to be more in line with the rest of 
SWI-Prolog.</I>

<P><I>The ugraphs library was originally released in the public domain. 
YAP is convered by the Perl artistic license, which does not imply 
further restrictions on the SWI-Prolog LGPL license.</I>
</BLOCKQUOTE>

<P>The routines assume directed graphs, undirected graphs may be 
implemented by using two edges.

<P>Originally graphs where represented in two formats. The SICStus 
library and this version of <CODE>library(ugraphs.pl)</CODE> only uses 
the
<EM>S-representation</EM>. The S-representation of a graph is a list of 
(vertex-neighbors) pairs, where the pairs are in standard order (as 
produced by keysort) and the neighbors of each vertex are also in 
standard order (as produced by sort). This form is convenient for many 
calculations. Each vertex appears in the S-representation, also if it 
has no neighbors.

<DL class="latex">
<DT class="pubdef"><A NAME="vertices_edges_to_ugraph/3"><STRONG>vertices_edges_to_ugraph</STRONG>(<VAR>+Vertices, 
+Edges, -Graph</VAR>)</A></DT>
<DD class="defbody">
Given a graph with a set of <VAR>Vertices</VAR> and a set of <VAR>Edges</VAR>,
<VAR>Graph</VAR> must unify with the corresponding S-representation. 
Note that the vertices without edges will appear in <VAR>Vertices</VAR> 
but not in
<VAR>Edges</VAR>. Moreover, it is sufficient for a vertice to appear in
<VAR>Edges</VAR>.

<PRE class="code">
?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]
</PRE>

<P>In this case all vertices are defined implicitly. The next example 
shows three unconnected vertices:

<PRE class="code">
?- vertices_edges_to_ugraph([6,7,8],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[], 6-[], 7-[], 8-[]] ? 
</PRE>

</DD>
<DT class="pubdef"><A NAME="vertices/2"><STRONG>vertices</STRONG>(<VAR>+Graph, 
-Vertices</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>Vertices</VAR> with all vertices appearing in graph <VAR>Graph</VAR>. 
Example:

<PRE class="code">
?- vertices([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1, 2, 3, 4, 5]
</PRE>

</DD>
<DT class="pubdef"><A NAME="edges/2"><STRONG>edges</STRONG>(<VAR>+Graph, 
-Edges</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>Edges</VAR> with all edges appearing in <VAR>Graph</VAR>. In 
the next example:

<PRE class="code">
?- edges([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1-3, 1-5, 2-4, 4-5]
</PRE>

</DD>
<DT class="pubdef"><A NAME="add_vertices/3"><STRONG>add_vertices</STRONG>(<VAR>+Graph, 
+Vertices, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with a new graph obtained by adding the list 
of
<VAR>Vertices</VAR> to the <VAR>Graph</VAR>. Example:

<PRE class="code">
?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG).
NG = [0-[], 1-[3,5], 2-[], 9-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="del_vertices/3"><STRONG>del_vertices</STRONG>(<VAR>+Graph, 
+Vertices, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with a new graph obtained by deleting the list 
of
<VAR>Vertices</VAR> and all the edges that start from or go to a vertex 
in
<VAR>Vertices</VAR> to the <VAR>Graph</VAR>. Example:

<PRE class="code">
?- del_vertices([2,1],
                [1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[2,6],8-[]],
                NL).
NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="add_edges/3"><STRONG>add_edges</STRONG>(<VAR>+Graph, 
+Edges, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with a new graph obtained by adding the list 
of edges
<VAR>Edges</VAR> to the graph <VAR>Graph</VAR>. Example:

<PRE class="code">
?- add_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
             [1-6,2-3,3-2,5-7,3-2,4-5],
             NL).
NL = [1-[3,5,6], 2-[3,4], 3-[2], 4-[5], 5-[7], 6-[], 7-[], 8-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="del_edges/3"><STRONG>del_edges</STRONG>(<VAR>+Graph, 
+Edges, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with a new graph obtained by removing the list 
of
<VAR>Edges</VAR> from the <VAR>Graph</VAR>. Notice that no vertices are 
deleted. In the next example:

<PRE class="code">
?- del_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
             [1-6,2-3,3-2,5-7,3-2,4-5,1-3],
             NL).
NL = [1-[5],2-[4],3-[],4-[],5-[],6-[],7-[],8-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="transpose/2"><STRONG>transpose</STRONG>(<VAR>+Graph, 
-NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with a new graph obtained from <VAR>Graph</VAR> 
by replacing all edges of the form V1-V2 by edges of the form V2-V1. The 
cost is <VAR>O(|V|^2)</VAR>. Notice that an undirected graph is its own 
transpose. Example:

<PRE class="code">
?- transpose([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[],2-[],3-[1],4-[2],5-[1,4],6-[],7-[],8-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="neighbours/3"><STRONG>neighbours</STRONG>(<VAR>+Vertex, 
+Graph, -Vertices</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>Vertices</VAR> with the list of neighbours of vertex <VAR>Vertex</VAR> 
in <VAR>Graph</VAR>. Example:

<PRE class="code">
?- neighbours(4,[1-[3,5],2-[4],3-[],
                 4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1,2,7,5]
</PRE>

</DD>
<DT class="pubdef"><A NAME="neighbors/3"><STRONG>neighbors</STRONG>(<VAR>+Vertex, 
+Graph, -Vertices</VAR>)</A></DT>
<DD class="defbody">
American version of <A NAME="idx:neighbours3:1628"></A><A class="pred" href="ugraphs.html#neighbours/3">neighbours/3</A>.</DD>
<DT class="pubdef"><A NAME="complement/2"><STRONG>complement</STRONG>(<VAR>+Graph, 
-NewGraph</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>NewGraph</VAR> with the graph complementary to <VAR>Graph</VAR>. 
Example:

<PRE class="code">
?- complement([1-[3,5],2-[4],3-[],
               4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[2,4,6,7,8],2-[1,3,5,6,7,8],3-[1,2,4,5,6,7,8],
      4-[3,5,6,8],5-[1,2,3,4,6,7,8],6-[1,2,3,4,5,7,8],
      7-[1,2,3,4,5,6,8],8-[1,2,3,4,5,6,7]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="compose/3"><STRONG>compose</STRONG>(<VAR>+LeftGraph, 
+RightGraph, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
Compose, by connecting the <EM>drains</EM> of <VAR>LeftGraph</VAR> to 
the <EM>sources</EM> of <VAR>RightGraph</VAR>. Example:

<PRE class="code">
?- compose([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[4], 2-[1,2,4], 3-[]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="ugraph_union/3"><STRONG>ugraph_union</STRONG>(<VAR>+Graph1, 
+Graph2, -NewGraph</VAR>)</A></DT>
<DD class="defbody">
<VAR>NewGraph</VAR> is the union of <VAR>Graph1</VAR> and <VAR>Graph2</VAR>. 
Example:

<PRE class="code">
?- ugraph_union([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[2], 2-[3,4], 3-[1,2,4]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="top_sort/2"><STRONG>top_sort</STRONG>(<VAR>+Graph, 
-Sort</VAR>)</A></DT>
<DD class="defbody">
Generate the set of nodes <VAR>Sort</VAR> as a topological sorting of 
graph
<VAR>Graph</VAR>, if one is possible. A toplogical sort is possible if 
the graph is connected and acyclic. In the example we show how 
topological sorting works for a linear graph:

<PRE class="code">
?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]
</PRE>

</DD>
<DT class="pubdef"><A NAME="top_sort/3"><STRONG>top_sort</STRONG>(<VAR>+Graph, 
-Sort0, -Sort</VAR>)</A></DT>
<DD class="defbody">
Generate the difference list Sort-Sort0 as a topological sorting of 
graph <VAR>Graph</VAR>, if one is possible.</DD>
<DT class="pubdef"><A NAME="transitive_closure/2"><STRONG>transitive_closure</STRONG>(<VAR>+Graph, 
-Closure</VAR>)</A></DT>
<DD class="defbody">
Generate the graph Closure as the transitive closure of graph
<VAR>Graph</VAR>. Example:

<PRE class="code">
 ?- transitive_closure([1-[2,3],2-[4,5],4-[6]],L).
L = [1-[2,3,4,5,6], 2-[4,5,6], 4-[6]]
</PRE>

</DD>
<DT class="pubdef"><A NAME="reachable/3"><STRONG>reachable</STRONG>(<VAR>+Vertex, 
+Graph, -Vertices</VAR>)</A></DT>
<DD class="defbody">
Unify <VAR>Vertices</VAR> with the set of all vertices in graph <VAR>Graph</VAR> 
that are reachable from <VAR>Vertex</VAR>. Example:

<PRE class="code">
?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V).
V = [1, 3, 5]
</PRE>

<P></DD>
</DL>

<P></BODY></HTML>
swi-prolog-nox 5.10.4-3ubuntu1 / usr / lib / swi-prolog / doc / Manual / ugraphs.html
