Package smile.graph

package smile.graph

Graphs are mathematical structures used to model pairwise relations between objects from a certain collection. A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called lines). The edges may be directed (asymmetric) or undirected (symmetric).

There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory.

List structures

Incidence list The edges are represented by an array containing pairs (tuples if directed) of vertices (that the edge connects) and possibly weight and other data. Vertices connected by an edge are said to be adjacent.

Adjacency list Much like the incidence list, each vertex has a list of which vertices it is adjacent to. This causes redundancy in an undirected graph. Adjacency queries are faster, at the cost of extra storage space.

Matrix structures

Incidence matrix The graph is represented by a matrix of size |V| (number of vertices) by |E| (number of edges) where the entry [vertex, edge] contains the edge's endpoint data (simplest case: 1 - incident, 0 - not incident).

Adjacency matrix This is an n by n matrix A, where n is the number of vertices in the graph. If there is an edge from a vertex x to a vertex y, then the element A(x,y) is 1 (or in general the number of edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.

Laplacian matrix or "Kirchhoff matrix" or "Admittance matrix" This is defined as D - A, where D is the diagonal degree matrix. It explicitly contains both adjacency information and degree information. (However, there are other, similar matrices that are also called "Laplacian matrices" of a graph.)

Distance matrix A symmetric n by n matrix D, where n is the number of vertices in the graph. The element D(x,y) is the length of a shortest path between x and y; if there is no such path D(x,y) = infinity. It can be derived from powers of A.

Class	Description
AdjacencyList	An adjacency list representation of a graph.
AdjacencyMatrix	An adjacency matrix representation of a graph.
Graph	A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links.
Graph.Edge	Graph edge.
Visitor	A visitor is encapsulation of some operation on graph vertices during traveling graph (DFS or BFS).