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).
logtalk_load(graphs(loader))staticPublic predicates
new/1
Creates a new empty graph.
staticnew(Graph)new(-graph) - onenew/2
Creates a new graph from a list of edges. Vertices are defined implicitly by edges.
staticnew(Edges,Graph)new(+list(edge),-graph) - onenew/3
Creates a new graph from a list of vertices and a list of edges. Vertices may also be defined implicitly by edges.
staticnew(Vertices,Edges,Graph)new(+list(vertex),+list(edge),-graph) - oneempty/1
True iff the given graph is empty.
staticempty(Graph)empty(@graph) - zero_or_onevertices/2
Unifies Vertices with a sorted list of all vertices in the graph.
staticvertices(Graph,Vertices)vertices(+graph,-list(vertex)) - oneedges/2
Unifies Edges with a list of all edges in the graph.
staticedges(Graph,Edges)edges(+graph,-list(edge)) - oneadd_vertex/3
Adds a vertex to the graph. If the vertex already exists, the graph is unchanged.
staticadd_vertex(Graph,Vertex,NewGraph)add_vertex(+graph,+vertex,-graph) - oneadd_vertices/3
Adds a list of vertices to the graph.
staticadd_vertices(Graph,Vertices,NewGraph)add_vertices(+graph,+list(vertex),-graph) - onedelete_vertex/3
Deletes a vertex and all edges incident to it from the graph. If the vertex does not exist, the graph is unchanged.
staticdelete_vertex(Graph,Vertex,NewGraph)delete_vertex(+graph,+vertex,-graph) - onedelete_vertices/3
Deletes a list of vertices and all edges incident to them from the graph.
staticdelete_vertices(Graph,Vertices,NewGraph)delete_vertices(+graph,+list(vertex),-graph) - oneadd_edges/3
Adds a list of edges to the graph. Vertices referenced by edges are added implicitly.
staticadd_edges(Graph,Edges,NewGraph)add_edges(+graph,+list(edge),-graph) - onedelete_edges/3
Deletes a list of edges from the graph. Vertices are not deleted. Non-existing edges are silently ignored.
staticdelete_edges(Graph,Edges,NewGraph)delete_edges(+graph,+list(edge),-graph) - oneneighbors/3
Unifies Neighbors with a sorted list of the neighbors of Vertex in the graph. Fails if Vertex is not in the graph.
staticneighbors(Vertex,Graph,Neighbors)neighbors(+vertex,+graph,-list(vertex)) - zero_or_onereachable/3
Unifies Vertices with a sorted list of vertices reachable from Vertex (including Vertex itself). Fails if Vertex is not in the graph.
staticreachable(Vertex,Graph,Vertices)reachable(+vertex,+graph,-list(vertex)) - zero_or_onebreadth_first_order/3
Unifies Vertices with the breadth-first traversal order rooted at Vertex. Fails if Vertex is not in the graph.
staticbreadth_first_order(Vertex,Graph,Vertices)breadth_first_order(+vertex,+graph,-list(vertex)) - zero_or_onedepth_first_order/3
Unifies Vertices with the depth-first traversal order rooted at Vertex. Fails if Vertex is not in the graph.
staticdepth_first_order(Vertex,Graph,Vertices)depth_first_order(+vertex,+graph,-list(vertex)) - zero_or_onenumber_of_vertices/2
Unifies N with the number of vertices in the graph.
staticnumber_of_vertices(Graph,N)number_of_vertices(+graph,-integer) - onenumber_of_edges/2
Unifies N with the number of edges in the graph.
staticnumber_of_edges(Graph,N)number_of_edges(+graph,-integer) - onepath/3
Returns a maximal path (list of vertices) rooted at Vertex, enumerating different paths on backtracking. Fails if Vertex is not in the graph.
staticpath(Vertex,Graph,Path)path(+vertex,+graph,-list(vertex)) - zero_or_morehas_path/3
True iff there is a path from Vertex1 to Vertex2 in the graph.
statichas_path(Vertex1,Vertex2,Graph)has_path(+vertex,+vertex,+graph) - zero_or_onemin_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.
staticmin_path(Vertex1,Vertex2,Graph,Path,Cost)min_path(+vertex,+vertex,+graph,-list(vertex),-number) - zero_or_onemax_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.
staticmax_path(Vertex1,Vertex2,Graph,Path,Cost)max_path(+vertex,+vertex,+graph,-list(vertex),-number) - zero_or_onemin_distances/3
Computes minimum path costs from Vertex to all reachable vertices. Returns a list of Target-Cost pairs including Vertex-0.
staticmin_distances(Vertex,Graph,Distances)min_distances(+vertex,+graph,-list(pair)) - zero_or_onemin_predecessors/3
Computes predecessor links for minimum paths rooted at Vertex. Returns a list of Target-Predecessor pairs; the source predecessor is none.
staticmin_predecessors(Vertex,Graph,Predecessors)min_predecessors(+vertex,+graph,-list(pair)) - zero_or_oneall_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.
staticall_pairs_min_paths(Graph,Pairs)all_pairs_min_paths(+graph,-list(pair)) - oneall_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.
staticall_pairs_min_predecessors(Graph,Pairs)all_pairs_min_predecessors(+graph,-list(pair)) - oneis_complete/1
True iff every pair of distinct vertices in the graph is connected by an edge.
staticis_complete(Graph)is_complete(+graph) - zero_or_oneis_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.
staticis_bipartite(Graph)is_bipartite(+graph) - zero_or_oneis_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).
staticis_sparse(Graph)is_sparse(+graph) - zero_or_oneProtected predicates
(none)
Private predicates
(none)
Operators
(none)