Graph (abstract data type)

In a 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 a math.
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 "arrows". 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:
Structures that associate values to the edges usually also provide:
Common Data Structures for Graph Representation.
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 because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges |"E" | is close to the number of vertices squared, |"V" |2, or if one must be able to quickly look up if there is an edge connecting two vertices.
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.
Distributed memory.
In the distributed memory model, the usual approach is to partition the vertex set formula_1 of the graph into formula_2 sets formula_3. Here, formula_2 is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own subgraph representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like MPI, the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.
Partitioning the graph needs to be done carefully - there is a trade-off between low communication and even size partitioning But partitioning a graph is a NP-hard problem, so it is not feasible to calculate them. Instead, the following heuristics are used.
1D partitioning: Every processor gets formula_5 vertices and the corresponding outgoing edges. This can be understood as a row-wise or column-wise decomposition of the adjacency matrix. For algorithms operating on this representation, this requires an All-to-All communication step as well as formula_6 message buffer sizes, as each PE potentially has outgoing edges to every other PE.
2D partitioning: Every processor gets a submatrix of the adjacency matrix. Assume the processors are aligned in a rectangle formula_7, where formula_8 and formula_9 are the amount of processing elements in each row and column, respectively. Then each processor gets a submatrix of the adjacency matrix of dimension formula_10. This can be visualized as a checkerboard pattern in a matrix. Therefore, each processing unit can only have outgoing edges to PEs in the same row and column. This bounds the amount of communication partners for each PE to formula_11 out of formula_7 possible ones.
Compressed representations.
Graphs with trillions of edges occur in machine learning, social network analysis, and other areas. Compressed graph representations have been developed to reduce I/O and memory requirements. General techniques such as Huffman coding are applicable, but the adjacency list or adjacency matrix can be processed in specific ways to increase efficiency.