- Documentation
- Reference manual
- The SWI-Prolog library
- library(aggregate): Aggregation operators on backtrackable predicates
- library(ansi_term): Print decorated text to ANSI consoles
- library(apply): Apply predicates on a list
- library(assoc): Association lists
- library(broadcast): Broadcast and receive event notifications
- library(charsio): I/O on Lists of Character Codes
- library(check): Consistency checking
- library(clpb): CLP(B): Constraint Logic Programming over Boolean Variables
- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
- library(clpqr): Constraint Logic Programming over Rationals and Reals
- library(csv): Process CSV (Comma-Separated Values) data
- library(dcg/basics): Various general DCG utilities
- library(dcg/high_order): High order grammar operations
- library(debug): Print debug messages and test assertions
- library(dicts): Dict utilities
- library(error): Error generating support
- library(gensym): Generate unique identifiers
- library(intercept): Intercept and signal interface
- library(iostream): Utilities to deal with streams
- library(listing): List programs and pretty print clauses
- library(lists): List Manipulation
- library(main): Provide entry point for scripts
- library(nb_set): Non-backtrackable set
- library(www_browser): Activating your Web-browser
- library(occurs): Finding and counting sub-terms
- library(option): Option list processing
- library(optparse): command line parsing
- library(ordsets): Ordered set manipulation
- library(pairs): Operations on key-value lists
- library(persistency): Provide persistent dynamic predicates
- library(pio): Pure I/O
- library(predicate_options): Declare option-processing of predicates
- library(prolog_jiti): Just In Time Indexing (JITI) utilities
- library(prolog_pack): A package manager for Prolog
- library(prolog_xref): Prolog cross-referencer data collection
- library(quasi_quotations): Define Quasi Quotation syntax
- library(random): Random numbers
- library(readutil): Read utilities
- library(record): Access named fields in a term
- library(registry): Manipulating the Windows registry
- library(settings): Setting management
- library(strings): String utilities
- library(simplex): Solve linear programming problems
- library(solution_sequences): Modify solution sequences
- library(tables): XSB interface to tables
- library(thread): High level thread primitives
- library(thread_pool): Resource bounded thread management
- library(ugraphs): Unweighted Graphs
- library(url): Analysing and constructing URL
- library(varnumbers): Utilities for numbered terms
- library(yall): Lambda expressions

- The SWI-Prolog library
- Packages

- Reference manual

## A.49 library(ugraphs): Unweighted Graphs

Authors:*Richard O'Keefe & Vitor Santos Costa*

Implementation and documentation are copied from YAP 5.0.1. The`library(ugraph)`

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.

The ugraphs library was originally released in the public domain. The YAP version is covered by the Perl Artistic license, version 2.0. This code is dual-licensed under the modified GPL as used for all SWI-Prolog libraries or the Perl Artistic license, version 2.0.

The routines assume directed graphs; undirected graphs may be implemented by using two edges.

Originally graphs were represented in two formats. The SICStus
library and this version of `library(ugraphs.pl)`

only use
the
*S-representation*. 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, even if it
has no neighbors.

**vertices_edges_to_ugraph**(`+Vertices, +Edges, -Graph`)- Given a graph with a set of
`Vertices`and a set of`Edges`,`Graph`must unify with the corresponding S-representation. Note that vertices without edges will appear in`Vertices`but not in`Edges`. Moreover, it is sufficient for a vertex to appear in`Edges`.?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L). L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]

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

?- 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-[]] ?

**vertices**(`+Graph, -Vertices`)- Unify
`Vertices`with all vertices appearing in`Graph`. Example:?- vertices([1-[3,5],2-[4],3-[],4-[5],5-[]], L). L = [1, 2, 3, 4, 5]

**edges**(`+Graph, -Edges`)- Unify
`Edges`with all edges appearing in`Graph`. Example:?- edges([1-[3,5],2-[4],3-[],4-[5],5-[]], L). L = [1-3, 1-5, 2-4, 4-5]

**add_vertices**(`+Graph, +Vertices, -NewGraph`)- Unify
`NewGraph`with a new graph obtained by adding the list of`Vertices`to`Graph`. Example:?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG). NG = [0-[], 1-[3,5], 2-[], 9-[]]

**del_vertices**(`+Graph, +Vertices, -NewGraph`)- Unify
`NewGraph`with a new graph obtained by deleting the list of`Vertices`and all edges that start from or go to a vertex in`Vertices`from`Graph`. Example:?- 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-[]]

**add_edges**(`+Graph, +Edges, -NewGraph`)- Unify
`NewGraph`with a new graph obtained by adding the list of`Edges`to`Graph`. Example:?- 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-[]]

**del_edges**(`+Graph, +Edges, -NewGraph`)- Unify
`NewGraph`with a new graph obtained by removing the list of`Edges`from`Graph`. Notice that no vertices are deleted. Example:?- 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-[]]

**transpose_ugraph**(`+Graph, -NewGraph`)- Unify
`NewGraph`with a new graph obtained from`Graph`by replacing all edges of the form V1-V2 by edges of the form V2-V1. The cost is`O(|V|^2)`. Notice that an undirected graph is its own transpose. Example:?- transpose_ugraph([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-[]]

**neighbours**(`+Vertex, +Graph, -Vertices`)- Unify
`Vertices`with the list of neighbours of vertex`Vertex`in`Graph`. Example:?- neighbours(4,[1-[3,5],2-[4],3-[], 4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL). NL = [1,2,7,5]

**neighbors**(`+Vertex, +Graph, -Vertices`)- American version of neighbours/3.
**complement**(`+Graph, -NewGraph`)- Unify
`NewGraph`with the graph complementary to`Graph`. Example:?- 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]]

**compose**(`+LeftGraph, +RightGraph, -NewGraph`)- Compose
`NewGraph`by connecting the*drains*of`LeftGraph`to the*sources*of`RightGraph`. Example:?- compose([1-[2],2-[3]],[2-[4],3-[1,2,4]],L). L = [1-[4], 2-[1,2,4], 3-[]]

**ugraph_union**(`+Graph1, +Graph2, -NewGraph`)`NewGraph`is the union of`Graph1`and`Graph2`. Example:?- ugraph_union([1-[2],2-[3]],[2-[4],3-[1,2,4]],L). L = [1-[2], 2-[3,4], 3-[1,2,4]]

**top_sort**(`+Graph, -Sort`)- Generate the set of nodes
`Sort`as a topological sorting of`Graph`, 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:?- top_sort([1-[2], 2-[3], 3-[]], L). L = [1, 2, 3]

**top_sort**(`+Graph, -Sort0, -Sort`)- Generate the difference list Sort-Sort0 as a topological sorting of
`Graph`, if one is possible. **transitive_closure**(`+Graph, -Closure`)- Generate the graph Closure as the transitive closure of
`Graph`. Example:?- transitive_closure([1-[2,3],2-[4,5],4-[6]],L). L = [1-[2,3,4,5,6], 2-[4,5,6], 4-[6]]

**reachable**(`+Vertex, +Graph, -Vertices`)- Unify
`Vertices`with the set of all vertices in`Graph`that are reachable from`Vertex`. Example:?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V). V = [1, 3, 5]