Directed Graphs

The following graph manipulation routines use the red-black tree library to try to avoid linear-time scans of the graph for all graph operations. More...

Detailed Description

The following graph manipulation routines use the red-black tree library to try to avoid linear-time scans of the graph for all graph operations.

Graphs are represented as a red-black tree, where the key is the vertex, and the associated value is a list of vertices reachable from that vertex through an edge (ie, a list of edges)

---

Class Documentation

dgraph_new/1

class dgraph_new/1

dgraph_new(+ Graph)

Create a new directed graph This operation must be performed before trying to use the graph

dgraph_add_edge/4

class dgraph_add_edge/4

dgraph_add_edge(+ Graph, + N1, + N2, - NewGraph)

Unify NewGraph with a new graph obtained by adding the edge N1- N2 to the graph Graph

dgraph_add_edges/3

class dgraph_add_edges/3

dgraph_add_edges(+ Graph, + Edges, - NewGraph)

Unify NewGraph with a new graph obtained by adding the list of edges Edges to the graph Graph

dgraph_add_vertices/3

class dgraph_add_vertices/3

dgraph_add_vertices(+ Graph, + Vertices, - NewGraph)

Unify NewGraph with a new graph obtained by adding the list of vertices Vertices to the graph Graph

dgraph_add_vertex/3

class dgraph_add_vertex/3

dgraph_add_vertex(+ Graph, + Vertex, - NewGraph)

Unify NewGraph with a new graph obtained by adding vertex Vertex to the graph Graph

dgraph_edges/2

class dgraph_edges/2

dgraph_edges(+ Graph, - Edges)

Unify Edges with all edges appearing in graph Graph

dgraph_vertices/2

class dgraph_vertices/2

dgraph_vertices(+ Graph, - Vertices)

Unify Vertices with all vertices appearing in graph Graph

dgraph_neighbours/3

class dgraph_neighbours/3

dgraph_neighbours(+ Vertex, + Graph, - Vertices)

Unify Vertices with the list of neighbours of vertex Vertex in Graph

dgraph_neighbors/3

class dgraph_neighbors/3

dgraph_neighbors(+ Vertex, + Graph, - Vertices)

Unify Vertices with the list of neighbors of vertex Vertex in Graph If the vertice is not in the graph fail

dgraph_complement/2

class dgraph_complement/2

dgraph_complement(+ Graph, - NewGraph)

Unify NewGraph with the graph complementary to Graph

dgraph_del_edge/4

class dgraph_del_edge/4

dgraph_del_edge(+ Graph, + N1, + N2, - NewGraph)

Succeeds if NewGraph unifies with a new graph obtained by removing the edge N1- N2 from the graph Graph Notice that no vertices are deleted

dgraph_del_edges/3

class dgraph_del_edges/3

dgraph_del_edges(+ Graph, + Edges, - NewGraph)

Unify NewGraph with a new graph obtained by removing the list of edges Edges from the graph Graph Notice that no vertices are deleted

dgraph_del_vertex/3

class dgraph_del_vertex/3

dgraph_del_vertex(+ Graph, + Vertex, - NewGraph)

Unify NewGraph with a new graph obtained by deleting vertex Vertex and all the edges that start from or go to Vertex to the graph Graph

dgraph_del_vertices/3

class dgraph_del_vertices/3

dgraph_del_vertices(+ Graph, + Vertices, - NewGraph)

Unify NewGraph with a new graph obtained by deleting the list of vertices Vertices and all the edges that start from or go to a vertex in Vertices to the graph Graph

dgraph_transpose/2

class dgraph_transpose/2

dgraph_transpose(+ Graph, - Transpose)

Unify NewGraph with a new graph obtained from Graph by replacing all edges of the form V1-V2 by edges of the form V2-V1

dgraph_transitive_closure/2

class dgraph_transitive_closure/2

dgraph_transitive_closure(+ Graph, - Closure)

Unify Closure with the transitive closure of graph Graph

dgraph_symmetric_closure/2

class dgraph_symmetric_closure/2

dgraph_symmetric_closure(+ Graph, - Closure)

Unify Closure with the symmetric closure of graph Graph, that is, if Closure contains an edge U-V it must also contain the edge V-U

dgraph_top_sort/2

class dgraph_top_sort/2

dgraph_top_sort(+ Graph, - Vertices)

Unify Vertices with the topological sort of graph Graph

dgraph_top_sort/3

class dgraph_top_sort/3

dgraph_top_sort(+ Graph, - Vertices, ? Vertices0)

Unify the difference list Vertices- Vertices0 with the topological sort of graph Graph

ugraph_to_dgraph/2

class ugraph_to_dgraph/2

ugraph_to_dgraph( +_UGraph_, -_Graph_)

Unify Graph with the directed graph obtain from UGraph, represented in the form used in the ugraphs unweighted graphs library

dgraph_to_ugraph/2

class dgraph_to_ugraph/2

dgraph_to_ugraph(+ Graph, - UGraph)

Unify UGraph with the representation used by the ugraphs unweighted graphs library, that is, a list of the form V-Neighbors, where V is a node and Neighbors the nodes children

dgraph_edge/3

class dgraph_edge/3

dgraph_edge(+ N1, + N2, + Graph)

Edge N1- N2 is an edge in directed graph Graph

dgraph_min_path/5

class dgraph_min_path/5

dgraph_min_path(+ V1, + V1, + Graph, - Path, ? Costt)

Unify the list Path with the minimal cost path between nodes N1 and N2 in graph Graph Path Path has cost Cost

dgraph_max_path/5

class dgraph_max_path/5

dgraph_max_path(+ V1, + V1, + Graph, - Path, ? Costt)

Unify the list Path with the maximal cost path between nodes N1 and N2 in graph Graph Path Path has cost Cost

dgraph_min_paths/3

class dgraph_min_paths/3

dgraph_min_paths(+ V1, + Graph, - Paths)

Unify the list Paths with the minimal cost paths from node N1 to the nodes in graph Graph

dgraph_path/4

class dgraph_path/4

dgraph_path(+ Vertex, + Vertex1, + Graph, ? Path)

The path Path is a path starting at vertex Vertex in graph Graph and ending at path Vertex2

dgraph_path/3

class dgraph_path/3

dgraph_path(+ Vertex, + Graph, ? Path)

The path Path is a path starting at vertex Vertex in graph Graph

dgraph_isomorphic/4

class dgraph_isomorphic/4

dgraph_isomorphic(+ Vs, + NewVs, + G0, - GF)

Unify the list GF with the graph isomorphic to G0 where vertices in Vs map to vertices in NewVs

dgraph_reachable/3

class dgraph_reachable/3

dgraph_reachable(+ Vertex, + Graph, ? Edges)

The path Path is a path starting at vertex Vertex in graph Graph

dgraph_leaves/2

class dgraph_leaves/2

dgraph_leaves(+ Graph, ? Vertices)

The vertices Vertices have no outgoing edge in graph Graph