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 graph_common
Uses:
avltree
list
set
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

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

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

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

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

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

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

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

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)