| Did you know ... | Search Documentation: |
 | Pack logtalk -- logtalk-3.98.0/docs/apis/_sources/graph_protocol_0.rst.txt |
- HOME
- DOWNLOAD
- DOCUMENTATION
- TUTORIALS
- Beginner▶
- Advanced▶
- Web applications▶
- Semantic web▶
- Graphics▶
- Machine learning▶
- External collections▶
- For packagers▶
- COMMUNITY
- COMMERCIAL
- WIKI
.. index:: single: graph_protocol .. _graph_protocol/0:
.. rst-class:: right
protocol
graph_protocol
Common protocol for all types of graphs. Graphs are represented using a dictionary where keys are vertices and values are sorted lists of neighbors (implicitly defining edges).
| Availability:
| logtalk_load(graphs(loader))
| Author: Paulo Moura | Version: 1:0:0 | Date: 2026-02-25
| Compilation flags:
| static
| Dependencies: | (none)
| Remarks: | (none)
| Inherited public predicates: | (none)
.. contents:: :local: :backlinks: top
Public predicates
.. index:: new/1 .. _graph_protocol/0::new/1:
new/1 ^^^^^^^^^
Creates a new empty graph.
| Compilation flags:
| static
| Template:
| new(Graph)
| Mode and number of proofs:
| new(-graph) - one
.. index:: new/2 .. _graph_protocol/0::new/2:
new/2 ^^^^^^^^^
Creates a new graph from a list of edges. Vertices are defined implicitly by edges.
| Compilation flags:
| static
| Template:
| new(Edges,Graph)
| Mode and number of proofs:
| new(+list(edge),-graph) - one
.. index:: new/3 .. _graph_protocol/0::new/3:
new/3 ^^^^^^^^^
Creates a new graph from a list of vertices and a list of edges. Vertices may also be defined implicitly by edges.
| Compilation flags:
| static
| Template:
| new(Vertices,Edges,Graph)
| Mode and number of proofs:
| new(+list(vertex),+list(edge),-graph) - one
.. index:: empty/1 .. _graph_protocol/0::empty/1:
empty/1 ^^^^^^^^^^^
True iff the given graph is empty.
| Compilation flags:
| static
| Template:
| empty(Graph)
| Mode and number of proofs:
| empty(@graph) - zero_or_one
.. index:: vertices/2 .. _graph_protocol/0::vertices/2:
vertices/2 ^^^^^^^^^^^^^^
Unifies Vertices with a sorted list of all vertices in the graph.
| Compilation flags:
| static
| Template:
| vertices(Graph,Vertices)
| Mode and number of proofs:
| vertices(+graph,-list(vertex)) - one
.. index:: edges/2 .. _graph_protocol/0::edges/2:
edges/2 ^^^^^^^^^^^
Unifies Edges with a list of all edges in the graph.
| Compilation flags:
| static
| Template:
| edges(Graph,Edges)
| Mode and number of proofs:
| edges(+graph,-list(edge)) - one
.. index:: add_vertex/3 .. _graph_protocol/0::add_vertex/3:
add_vertex/3 ^^^^^^^^^^^^^^^^
Adds a vertex to the graph. If the vertex already exists, the graph is unchanged.
| Compilation flags:
| static
| Template:
| add_vertex(Graph,Vertex,NewGraph)
| Mode and number of proofs:
| add_vertex(+graph,+vertex,-graph) - one
.. index:: add_vertices/3 .. _graph_protocol/0::add_vertices/3:
add_vertices/3 ^^^^^^^^^^^^^^^^^^
Adds a list of vertices to the graph.
| Compilation flags:
| static
| Template:
| add_vertices(Graph,Vertices,NewGraph)
| Mode and number of proofs:
| add_vertices(+graph,+list(vertex),-graph) - one
.. index:: delete_vertex/3 .. _graph_protocol/0::delete_vertex/3:
delete_vertex/3 ^^^^^^^^^^^^^^^^^^^
Deletes a vertex and all edges incident to it from the graph. If the vertex does not exist, the graph is unchanged.
| Compilation flags:
| static
| Template:
| delete_vertex(Graph,Vertex,NewGraph)
| Mode and number of proofs:
| delete_vertex(+graph,+vertex,-graph) - one
.. index:: delete_vertices/3 .. _graph_protocol/0::delete_vertices/3:
delete_vertices/3 ^^^^^^^^^^^^^^^^^^^^^
Deletes a list of vertices and all edges incident to them from the graph.
| Compilation flags:
| static
| Template:
| delete_vertices(Graph,Vertices,NewGraph)
| Mode and number of proofs:
| delete_vertices(+graph,+list(vertex),-graph) - one
.. index:: add_edges/3 .. _graph_protocol/0::add_edges/3:
add_edges/3 ^^^^^^^^^^^^^^^
Adds a list of edges to the graph. Vertices referenced by edges are added implicitly.
| Compilation flags:
| static
| Template:
| add_edges(Graph,Edges,NewGraph)
| Mode and number of proofs:
| add_edges(+graph,+list(edge),-graph) - one
.. index:: delete_edges/3 .. _graph_protocol/0::delete_edges/3:
delete_edges/3 ^^^^^^^^^^^^^^^^^^
Deletes a list of edges from the graph. Vertices are not deleted. Non-existing edges are silently ignored.
| Compilation flags:
| static
| Template:
| delete_edges(Graph,Edges,NewGraph)
| Mode and number of proofs:
| delete_edges(+graph,+list(edge),-graph) - one
.. index:: neighbors/3 .. _graph_protocol/0::neighbors/3:
neighbors/3 ^^^^^^^^^^^^^^^
Unifies Neighbors with a sorted list of the neighbors of Vertex in the graph. Fails if Vertex is not in the graph.
| Compilation flags:
| static
| Template:
| neighbors(Vertex,Graph,Neighbors)
| Mode and number of proofs:
| neighbors(+vertex,+graph,-list(vertex)) - zero_or_one
.. index:: reachable/3 .. _graph_protocol/0::reachable/3:
reachable/3 ^^^^^^^^^^^^^^^
Unifies Vertices with a sorted list of vertices reachable from Vertex (including Vertex itself). Fails if Vertex is not in the graph.
| Compilation flags:
| static
| Template:
| reachable(Vertex,Graph,Vertices)
| Mode and number of proofs:
| reachable(+vertex,+graph,-list(vertex)) - zero_or_one
.. index:: breadth_first_order/3 .. _graph_protocol/0::breadth_first_order/3:
breadth_first_order/3 ^^^^^^^^^^^^^^^^^^^^^^^^^
Unifies Vertices with the breadth-first traversal order rooted at Vertex. Fails if Vertex is not in the graph.
| Compilation flags:
| static
| Template:
| breadth_first_order(Vertex,Graph,Vertices)
| Mode and number of proofs:
| breadth_first_order(+vertex,+graph,-list(vertex)) - zero_or_one
.. index:: depth_first_order/3 .. _graph_protocol/0::depth_first_order/3:
depth_first_order/3 ^^^^^^^^^^^^^^^^^^^^^^^
Unifies Vertices with the depth-first traversal order rooted at Vertex. Fails if Vertex is not in the graph.
| Compilation flags:
| static
| Template:
| depth_first_order(Vertex,Graph,Vertices)
| Mode and number of proofs:
| depth_first_order(+vertex,+graph,-list(vertex)) - zero_or_one
.. index:: number_of_vertices/2 .. _graph_protocol/0::number_of_vertices/2:
number_of_vertices/2 ^^^^^^^^^^^^^^^^^^^^^^^^
Unifies N with the number of vertices in the graph.
| Compilation flags:
| static
| Template:
| number_of_vertices(Graph,N)
| Mode and number of proofs:
| number_of_vertices(+graph,-integer) - one
.. index:: number_of_edges/2 .. _graph_protocol/0::number_of_edges/2:
number_of_edges/2 ^^^^^^^^^^^^^^^^^^^^^
Unifies N with the number of edges in the graph.
| Compilation flags:
| static
| Template:
| number_of_edges(Graph,N)
| Mode and number of proofs:
| number_of_edges(+graph,-integer) - one
.. index:: path/3 .. _graph_protocol/0::path/3:
path/3 ^^^^^^^^^^
Returns a maximal path (list of vertices) rooted at Vertex, enumerating different paths on backtracking. Fails if Vertex is not in the graph.
| Compilation flags:
| static
| Template:
| path(Vertex,Graph,Path)
| Mode and number of proofs:
| path(+vertex,+graph,-list(vertex)) - zero_or_more
.. index:: has_path/3 .. _graph_protocol/0::has_path/3:
has_path/3 ^^^^^^^^^^^^^^
True iff there is a path from Vertex1 to Vertex2 in the graph.
| Compilation flags:
| static
| Template:
| has_path(Vertex1,Vertex2,Graph)
| Mode and number of proofs:
| has_path(+vertex,+vertex,+graph) - zero_or_one
.. index:: min_path/5 .. _graph_protocol/0::min_path/5:
min_path/5 ^^^^^^^^^^^^^^
Finds the minimum cost path from Vertex1 to Vertex2. For unweighted graphs, cost is the number of edges. Fails if no path exists.
| Compilation flags:
| static
| Template:
| min_path(Vertex1,Vertex2,Graph,Path,Cost)
| Mode and number of proofs:
| min_path(+vertex,+vertex,+graph,-list(vertex),-number) - zero_or_one
.. index:: max_path/5 .. _graph_protocol/0::max_path/5:
max_path/5 ^^^^^^^^^^^^^^
Finds the maximum cost acyclic path from Vertex1 to Vertex2. For unweighted graphs, cost is the number of edges. Fails if no path exists.
| Compilation flags:
| static
| Template:
| max_path(Vertex1,Vertex2,Graph,Path,Cost)
| Mode and number of proofs:
| max_path(+vertex,+vertex,+graph,-list(vertex),-number) - zero_or_one
.. index:: min_distances/3 .. _graph_protocol/0::min_distances/3:
min_distances/3 ^^^^^^^^^^^^^^^^^^^
Computes minimum path costs from Vertex to all reachable vertices. Returns a list of Target-Cost pairs including Vertex-0.
| Compilation flags:
| static
| Template:
| min_distances(Vertex,Graph,Distances)
| Mode and number of proofs:
| min_distances(+vertex,+graph,-list(pair)) - zero_or_one
.. index:: min_predecessors/3 .. _graph_protocol/0::min_predecessors/3:
min_predecessors/3 ^^^^^^^^^^^^^^^^^^^^^^
Computes predecessor links for minimum paths rooted at Vertex. Returns a list of Target-Predecessor pairs; the source predecessor is none.
| Compilation flags:
| static
| Template:
| min_predecessors(Vertex,Graph,Predecessors)
| Mode and number of proofs:
| min_predecessors(+vertex,+graph,-list(pair)) - zero_or_one
.. index:: all_pairs_min_paths/2 .. _graph_protocol/0::all_pairs_min_paths/2:
all_pairs_min_paths/2 ^^^^^^^^^^^^^^^^^^^^^^^^^
Computes minimum path costs for all ordered pairs of vertices with a path between them. Returns a list of (Vertex1-Vertex2)-Cost terms.
| Compilation flags:
| static
| Template:
| all_pairs_min_paths(Graph,Pairs)
| Mode and number of proofs:
| all_pairs_min_paths(+graph,-list(pair)) - one
.. index:: all_pairs_min_predecessors/2 .. _graph_protocol/0::all_pairs_min_predecessors/2:
all_pairs_min_predecessors/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Computes predecessor links for minimum paths for all ordered source-target pairs with a path. Returns a list of (Vertex1-Vertex2)-Predecessor terms.
| Compilation flags:
| static
| Template:
| all_pairs_min_predecessors(Graph,Pairs)
| Mode and number of proofs:
| all_pairs_min_predecessors(+graph,-list(pair)) - one
.. index:: is_complete/1 .. _graph_protocol/0::is_complete/1:
is_complete/1 ^^^^^^^^^^^^^^^^^
True iff every pair of distinct vertices in the graph is connected by an edge.
| Compilation flags:
| static
| Template:
| is_complete(Graph)
| Mode and number of proofs:
| is_complete(+graph) - zero_or_one
.. index:: is_bipartite/1 .. _graph_protocol/0::is_bipartite/1:
is_bipartite/1 ^^^^^^^^^^^^^^^^^^
True iff the graph is bipartite, i.e. its vertices can be partitioned into two sets such that every edge connects a vertex in one set to a vertex in the other.
| Compilation flags:
| static
| Template:
| is_bipartite(Graph)
| Mode and number of proofs:
| is_bipartite(+graph) - zero_or_one
.. index:: is_sparse/1 .. _graph_protocol/0::is_sparse/1:
is_sparse/1 ^^^^^^^^^^^^^^^
True iff the graph is sparse, i.e. the number of edges is at most |V| * log2(|V|). The cutoff |E| = |V| * log2(|V|) separates sparse graphs (where adjacency lists are efficient) from dense graphs (where adjacency matrix representations may be preferable).
| Compilation flags:
| static
| Template:
| is_sparse(Graph)
| Mode and number of proofs:
| is_sparse(+graph) - zero_or_one
Protected predicates
(none)
Private predicates
(none)
Operators
(none)