.. 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 ` | **Uses:** | :ref:`avltree ` | :ref:`list ` | :ref:`set ` | **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)