protocol

directed_graph_protocol

Protocol for directed graph predicates such as transpose, closures, topological sorting, degree queries, and strongly connected components.

Availability:
logtalk_load(graphs(loader))
Author: Paulo Moura
Version: 1:0:0
Date: 2026-02-25
Compilation flags:
static
Extends:
public graph_protocol
Remarks:
(none)
Inherited public predicates:
 add_edges/3  add_vertex/3  add_vertices/3  all_pairs_min_paths/2  all_pairs_min_predecessors/2  breadth_first_order/3  delete_edges/3  delete_vertex/3  delete_vertices/3  depth_first_order/3  edges/2  empty/1  has_path/3  is_bipartite/1  is_complete/1  is_sparse/1  max_path/5  min_distances/3  min_path/5  min_predecessors/3  neighbors/3  new/1  new/2  new/3  number_of_edges/2  number_of_vertices/2  path/3  reachable/3  vertices/2

Public predicates

transpose/2

Unifies NewGraph with a graph obtained by reversing all edges.

Compilation flags:
static
Template:
transpose(Graph,NewGraph)
Mode and number of proofs:
transpose(+graph,-graph) - one

transitive_closure/2

Generates the transitive closure of the graph.

Compilation flags:
static
Template:
transitive_closure(Graph,Closure)
Mode and number of proofs:
transitive_closure(+graph,-graph) - one

symmetric_closure/2

Generates the symmetric closure of the graph.

Compilation flags:
static
Template:
symmetric_closure(Graph,Closure)
Mode and number of proofs:
symmetric_closure(+graph,-graph) - one

topological_sort/2

Unifies Sorted with a topological sort of the vertices in the graph. Assumes the graph is a DAG.

Compilation flags:
static
Template:
topological_sort(Graph,Sorted)
Mode and number of proofs:
topological_sort(+graph,-list(vertex)) - one

in_degree/3

Unifies Degree with the number of incoming edges to Vertex. Fails if Vertex is not in the graph.

Compilation flags:
static
Template:
in_degree(Vertex,Graph,Degree)
Mode and number of proofs:
in_degree(+vertex,+graph,-integer) - zero_or_one

out_degree/3

Unifies Degree with the number of outgoing edges from Vertex. Fails if Vertex is not in the graph.

Compilation flags:
static
Template:
out_degree(Vertex,Graph,Degree)
Mode and number of proofs:
out_degree(+vertex,+graph,-integer) - zero_or_one

is_acyclic/1

True iff the graph is a directed acyclic graph (DAG).

Compilation flags:
static
Template:
is_acyclic(Graph)
Mode and number of proofs:
is_acyclic(+graph) - zero_or_one

has_cycle/1

True iff the graph contains at least one directed cycle.

Compilation flags:
static
Template:
has_cycle(Graph)
Mode and number of proofs:
has_cycle(+graph) - zero_or_one

cycle/2

Enumerates directed cycles as lists of vertices where the first and last vertices are the same.

Compilation flags:
static
Template:
cycle(Graph,Cycle)
Mode and number of proofs:
cycle(+graph,-list(vertex)) - zero_or_more

strongly_connected_components/2

Computes the strongly connected components of the graph using Tarjan’s algorithm. Each component is a sorted list of vertices. Components are returned in topological order.

Compilation flags:
static
Template:
strongly_connected_components(Graph,SCCs)
Mode and number of proofs:
strongly_connected_components(+graph,-list(list(vertex))) - one

weakly_connected_components/2

Computes the weakly connected components of the graph by considering edge directions as undirected. Each component is returned as a sorted list of vertices.

Compilation flags:
static
Template:
weakly_connected_components(Graph,Components)
Mode and number of proofs:
weakly_connected_components(+graph,-list(list(vertex))) - one

Protected predicates

(no local declarations; see entity ancestors if any)

Private predicates

(no local declarations; see entity ancestors if any)

Operators

(none)