.. index:: single: undirected_graph_common .. _undirected_graph_common/0:

.. rst-class:: right

category

undirected_graph_common

Common predicates shared by undirected graph objects. Uses self-dispatch to call object-specific predicates such as is_connected/1, vertices/2, edges/2, and neighbors/3.

| Availability: | logtalk_load(graphs(loader))

| Author: Paulo Moura | Version: 1:0:0 | Date: 2026-02-25

| Compilation flags: | static

| Extends: | public :ref:`graph_common <graph_common/0>` | Uses: | :ref:`avltree <avltree/0>` | :ref:`list <list/0>` | :ref:`set <set/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:: is_tree/1 .. _undirected_graph_common/0::is_tree/1:

is_tree/1 ^^^^^^^^^^^^^

True iff the graph is a tree, i.e. it is connected and has exactly |V| - 1 edges.

| Compilation flags: | static

| Template: | is_tree(Graph) | Mode and number of proofs: | is_tree(+graph) - zero_or_one

---

.. index:: has_cycle/1 .. _undirected_graph_common/0::has_cycle/1:

has_cycle/1 ^^^^^^^^^^^^^^^

True iff the graph contains at least one cycle.

| Compilation flags: | static

| Template: | has_cycle(Graph) | Mode and number of proofs: | has_cycle(+graph) - zero_or_one

---

.. index:: cycle/2 .. _undirected_graph_common/0::cycle/2:

cycle/2 ^^^^^^^^^^^

Enumerates 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:: graph_coloring/3 .. _undirected_graph_common/0::graph_coloring/3:

graph_coloring/3 ^^^^^^^^^^^^^^^^^^^^

Computes a greedy vertex coloring of the graph. Coloring is a list of Vertex-Color pairs where colors are integers starting from 1. NumberOfColors is the total number of colors used.

| Compilation flags: | static

| Template: | graph_coloring(Graph,Coloring,NumberOfColors) | Mode and number of proofs: | graph_coloring(+graph,-list(pair),-integer) - one

---

.. index:: articulation_points/2 .. _undirected_graph_common/0::articulation_points/2:

articulation_points/2 ^^^^^^^^^^^^^^^^^^^^^^^^^

Computes all articulation points (cut vertices) of the graph. The result is a sorted list of vertices.

| Compilation flags: | static

| Template: | articulation_points(Graph,Points) | Mode and number of proofs: | articulation_points(+graph,-list(vertex)) - one

---

.. index:: bridges/2 .. _undirected_graph_common/0::bridges/2:

bridges/2 ^^^^^^^^^^^^^

Computes all bridges (cut edges) of the graph. Each bridge is returned once as Vertex1-Vertex2 with Vertex1 @< Vertex2.

| Compilation flags: | static

| Template: | bridges(Graph,Bridges) | Mode and number of proofs: | bridges(+graph,-list(edge)) - one

---

.. index:: maximal_cliques/2 .. _undirected_graph_common/0::maximal_cliques/2:

maximal_cliques/2 ^^^^^^^^^^^^^^^^^^^^^

Computes all maximal cliques of the graph using the Bron-Kerbosch algorithm with pivoting. A maximal clique is a clique that cannot be extended by adding another adjacent vertex. Each clique is a sorted list of vertices. The list of cliques is sorted in standard order.

| Compilation flags: | static

| Template: | maximal_cliques(Graph,Cliques) | Mode and number of proofs: | maximal_cliques(+graph,-list(list(vertex))) - one

---

.. index:: maximum_cliques/2 .. _undirected_graph_common/0::maximum_cliques/2:

maximum_cliques/2 ^^^^^^^^^^^^^^^^^^^^^

Computes all maximum cliques of the graph, i.e. the largest maximal cliques. Each clique is a sorted list of vertices. The list of cliques is sorted in standard order. For an empty graph, returns an empty list.

| Compilation flags: | static

| Template: | maximum_cliques(Graph,Cliques) | Mode and number of proofs: | maximum_cliques(+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)