In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
Operations
The basic operations provided by a graph data structure G usually include:
adjacent(G, x, y): tests whether there is an edge from the vertex x to the vertex y; neighbors(G, x): lists all vertices y such that there is an edge from the vertex x to the vertex y; add_vertex(G, x): adds the vertex x, if it is not there; remove_vertex(G, x): removes the vertex x, if it is there; add_edge(G, x, y, z): adds the edge z from the vertex x to the vertex y, if it is not there; remove_edge(G, x, y): removes the edge from the vertex x to the vertex y, if it is there; get_vertex_value(G, x): returns the value associated with the vertex x; set_vertex_value(G, x, v): sets the value associated with the vertex x to v. Structures that associate values to the edges usually also provide:
get_edge_value(G, x, y): returns the value associated with the edge (x, y); set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
Common data structures for graph representation Adjacency list Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices. Adjacency matrix A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices. Incidence matrix A two-dimensional matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate the incidence relation between the vertex at a row and edge at a column. The following table gives the time complexity cost of performing various operations on graphs, for each of these representations, with |V| the number of vertices and |E| the number of edges. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be ∞.
Adjacency lists are generally preferred for the representation of sparse graphs, while an adjacency matrix is preferred if the graph is dense; that is, the number of edges | E | {\displaystyle |E|} is close to the number of vertices squared, | V | 2 {\displaystyle |V|^{2}} , or if one must be able to quickly look up if there is an edge connecting two vertices.
More efficient representation of adjacency sets The time complexity of operations in the adjacency list representation can be improved by storing the sets of adjacent vertices in more efficient data structures, such as hash tables or balanced binary search trees (the latter representation requires that vertices are identified by elements of a linearly ordered set, such as integers or character strings). A representation of adjacent vertices via hash tables leads to an amortized average time complexity of O ( 1 ) {\displaystyle O(1)} to test adjacency of two given vertices and to remove an edge and an amortized average time complexity of O ( deg ( x ) ) {\displaystyle O(\deg(x))} to remove a given vertex x of degree deg ( x ) {\displaystyle \deg(x)} . The time complexity of the other operations and the asymptotic space requirement do not change.
Parallel representations The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio. The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its scalability. In the following, shared and distributed memory architectures are considered.
Shared memory In the case of a shared memory model, the graph representations used for parallel processing are the same as in the sequential case, since parallel read-only access to the graph representation (e.g. an adjacency list) is efficient in shared memory.
… excerpt ends here. Continue reading the full article.
