GRAPH_REPRESENTATION, a MATLAB library which can determine various representations of a graph.
Most of the routines take as input the number of nodes, the node coordinates, the number of edges, and the edges as a list of pairs of node indices. They then produce an object related to a representation of the graph.
Graphs are abstract models of a set of objects and some kind of pairwise relationship that exists between some pairs of the objects. The objects are called nodes and the relationships are called edges or links.
A graph is often depicted as a set of points (the nodes), some pairs of which are connected by lines (the edges or links).
A simple graph is a set of NV vertices V and a set of NE edges E, where each edge e in E is a set of two distinct nodes from V. By the conventions of set theory, no distinction is made between the edges (A,B) and (B,A). This corresponds to the idea that the relationship being represented is symmetric.
Perhaps the simplest description of a graph is the edge list. This representation consists of a list of the pairs of nodes that are joined by an edge. If (A,B) is given in the list, then the equivalent pair (B,A) is not listed. For convenience, it is often the case that the pair is chosen in which the first node has a lower numeric index than the second. Similarly, the order in which these edges appear in the edge list, while not specified, is often chosen to be ascending order.
Another representation of a graph is the adjacency matrix. This is an NV by NV matrix A in which A(I,J) is the number of edges between nodes I and J. Ordinarily, this value is either 0 or 1, although there are natural extensions to this idea.
Given an ordering of the edges as well as the nodes, we can represent the graph by an incidence matrix which is an NE by NV matrix, such that A(I,J) is 0 unless edge I uses node J as one of its two endpoints.
The adjacency structure of a graph is, ideally, a list of NV lists. For node I, the list contains all nodes joined by an edge to node I. The length of the list for each node may be anything from 0 to NV-1; in MATLAB this data structure can be represented by a cell array.
If the cell array or list-of-lists data type is not available, the information in the adjacency structure can also be constructed by a pair of vectors. The first, the adjacency list, is simply the list of all the node neighbors of node 1, followed by those for node 2, and so on. The adjacency pointer is a vector of length NV+1, which can be used to locate the data for a given node within the adjacency list. In particular, the neighbors of node I are listed in the adjacency list between the entry specified by pointer value I, up to, but not including, the entry specified by pointer I+1.
Since it is quite common to represent a graph as a drawing, or to abstract a graph from a physical situation in which the nodes have positions, it is also useful to have available the node coordinates, which are simply the (X,Y) coordinates of each node.
Similarly, it may be more suggestive to refer to nodes by letter or name or some other label. Thus a node label array can be an auxilliary item of data.
One format for storing graph information included the ability to store a numeric label, the node coordinates, and the neighbors of a node. This is called the grf format. There are a few utilities for displaying an image of a graph that has been represented in this format.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
GRAPH_REPRESENTATION is available in a MATLAB version.
FLOYD, a MATLAB library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
GRAFFITI, a dataset directory which contains 195 abstract graphs, with adjacency and embedding information, stored in the GRF format.
GRAPH_REPRESENTATION, a data directory of examples which representing abstract mathematical graphs in various ways.
GRF, a data directory which contains a description of the GRF format and some examples.
GRF_DISPLAY, a MATLAB program which reads a GRF file defining a mathematical graph and displays it in the MATLAB graphics window.
GRF_DISPLAY_OPENGL, a C++ program which reads a GRF file defining a mathematical graph and displays it in an OpenGL graphics window.
GRF_IO, a MATLAB library which reads and writes files in the GRF format.