.. index:: single: directed_graph_protocol .. _directed_graph_protocol/0:

.. rst-class:: right

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 :ref:`graph_protocol <graph_protocol/0>`

| Remarks: | (none)

| Inherited public predicates: |  :ref:`graph_protocol/0::add_edges/3`  :ref:`graph_protocol/0::add_vertex/3`  :ref:`graph_protocol/0::add_vertices/3`  :ref:`graph_protocol/0::all_pairs_min_paths/2`  :ref:`graph_protocol/0::all_pairs_min_predecessors/2`  :ref:`graph_protocol/0::breadth_first_order/3`  :ref:`graph_protocol/0::delete_edges/3`  :ref:`graph_protocol/0::delete_vertex/3`  :ref:`graph_protocol/0::delete_vertices/3`  :ref:`graph_protocol/0::depth_first_order/3`  :ref:`graph_protocol/0::edges/2`  :ref:`graph_protocol/0::empty/1`  :ref:`graph_protocol/0::has_path/3`  :ref:`graph_protocol/0::is_bipartite/1`  :ref:`graph_protocol/0::is_complete/1`  :ref:`graph_protocol/0::is_sparse/1`  :ref:`graph_protocol/0::max_path/5`  :ref:`graph_protocol/0::min_distances/3`  :ref:`graph_protocol/0::min_path/5`  :ref:`graph_protocol/0::min_predecessors/3`  :ref:`graph_protocol/0::neighbors/3`  :ref:`graph_protocol/0::new/1`  :ref:`graph_protocol/0::new/2`  :ref:`graph_protocol/0::new/3`  :ref:`graph_protocol/0::number_of_edges/2`  :ref:`graph_protocol/0::number_of_vertices/2`  :ref:`graph_protocol/0::path/3`  :ref:`graph_protocol/0::reachable/3`  :ref:`graph_protocol/0::vertices/2`  

.. contents:: :local: :backlinks: top

Public predicates

.. index:: transpose/2 .. _directed_graph_protocol/0::transpose/2:

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

---

.. index:: transitive_closure/2 .. _directed_graph_protocol/0::transitive_closure/2:

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

---

.. index:: symmetric_closure/2 .. _directed_graph_protocol/0::symmetric_closure/2:

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

---

.. index:: topological_sort/2 .. _directed_graph_protocol/0::topological_sort/2:

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

---

.. index:: in_degree/3 .. _directed_graph_protocol/0::in_degree/3:

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

---

.. index:: out_degree/3 .. _directed_graph_protocol/0::out_degree/3:

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

---

.. index:: is_acyclic/1 .. _directed_graph_protocol/0::is_acyclic/1:

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

---

.. index:: has_cycle/1 .. _directed_graph_protocol/0::has_cycle/1:

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

---

.. index:: cycle/2 .. _directed_graph_protocol/0::cycle/2:

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

---

.. index:: strongly_connected_components/2 .. _directed_graph_protocol/0::strongly_connected_components/2:

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

---

.. index:: weakly_connected_components/2 .. _directed_graph_protocol/0::weakly_connected_components/2:

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)