GRAPH_REPRESENTATION
Abstract Graph Representation

GRAPH_REPRESENTATION is a data directory which contains examples of a variety of representations for a few mathematical or abstract graphs.

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 vertices V and a set of 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.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

CITIES, a dataset directory which contains sets of information about cities and the distances between them;

CODEPACK, a FORTRAN90 library which computes "codes" that can determine if two graphs are isomorphic.

DIJKSTRA, a C program which runs a simple example of Dijkstra's minimum distance algorithm for graphs.

FLOYD, a C++ 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.

GRAFPACK, a FORTRAN90 library which carries out operations on abstract graphs.

GRAPH_REPRESENTATION, a MATLAB library which can express the representation of an abstract mathematical graph in several ways.

GRF, a data directory which contains examples of GRF files, an abstract graph file format, 2D graphics;

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 C++ library which reads or writes a GRF file;

LAUPACK, a FORTRAN90 library which carries out various operations on graphs.

TABLE_GRAPH_CODE, a FORTRAN90 program which reads a TABLE file representing the adjacency matrix of a graph, and computes the graph code.

XYL, a data directory which contains examples of XYL files, a simple 2D graphics point and line format;

Sample Files:

DISCONNECTED is an example of a disconnected graph. It includes 8 nodes, and 6 edges.

• disconnected.grf, a GRF file;
• disconnected.png, a PNG image.
• disconnected_adjacency_matrix.txt, the adjacency matrix;
• disconnected_adjacency_structure.txt, the adjacency structure;
• disconnected_edges.txt, the edge list;
• disconnected_incidence_matrix.txt, the incidence matrix;
• disconnected_node_components.txt, indicates the connected subcomponent to which each node belongs.
• disconnected_node_coordinates.txt, node coordinates.
• disconnected_node_labels.txt, node labels.

KN57 is an example of an edge-weighted graph. It includes 57 nodes, and 1,596 = (57*56)/2 edges. These are represented by a distance matrix.

• kn57_distance_matrix.txt, the distance matrix.
• kn57_node_coordinates.txt, the node coordinates.

MST is an example of an edge-weighted graph. It includes 10 nodes, and 17 edges.

• mst.grf, a GRF file;
• mst.png, a PNG image.
• mst_adjacency_matrix.txt, the adjacency matrix;
• mst_adjacency_structure.txt, the adjacency structure;
• mst_distance_matrix.txt, the distance matrix;
• mst_edges.txt, the edge list;
• mst_edge_weights.txt, the edge weights;
• mst_incidence_matrix.txt, the incidence matrix;
• mst_node_coordinates.txt, node coordinates.
• mst_node_labels.txt, node labels.

MST2 is an example of an edge-weighted graph. It includes 13 nodes, and 21 edges.

• mst2.grf, a GRF file;
• mst2.png, a PNG image.
• mst2_adjacency_matrix.txt, the adjacency matrix;
• mst2_adjacency_structure.txt, the adjacency structure;
• mst2_distance_matrix.txt, the distance matrix;
• mst2_edges.txt, the edge list;
• mst2_edge_weights.txt, the edge weights;
• mst2_incidence_matrix.txt, the incidence matrix;
• mst2_node_coordinates.txt, node coordinates.
• mst2_node_labels.txt, node labels.

MUSEUM is an example of a simple, connected graph. It is actually a tree (a graph with no circuits). It includes 18 nodes, and 17 edges.

• museum.grf, a GRF file;
• museum.png, a PNG image.
• museum_adjacency_matrix.txt, the adjacency matrix;
• museum_adjacency_structure.txt, the adjacency structure;
• museum_edges.txt, the edge list;
• museum_incidence_matrix.txt, the incidence matrix;
• museum_node_coordinates.txt, node coordinates.
• museum_node_labels.txt, node labels.

PATHS is an example of a simple, unconnected graph. It includes 20 nodes and 22 edges.

• paths.grf, a GRF file;
• paths.png, a PNG image.
• paths_adjacency_matrix.txt, the adjacency matrix;
• paths_adjacency_structure.txt, the adjacency structure;
• paths_edges.txt, the edge list;
• paths_incidence_matrix.txt, the incidence matrix;
• paths_node_coordinates.txt, node coordinates.
• pathscd _node_labels.txt, node labels.

SIMPLE is an example of a simple graph. It includes 5 nodes, and 4 edges.

• simple.grf, a GRF file;
• simple.png, a PNG image.
• simple_adjacency_matrix.txt, the adjacency matrix;
• simple_adjacency_structure.txt, the adjacency structure;
• simple_edges.txt, the edge list;
• simple_incidence_matrix.txt, the incidence matrix;
• simple_node_coordinates.txt, node coordinates.
• simple_node_labels.txt, node labels.

TSP is an example of an edge-weighted complete graph. It includes 5 nodes, and 10 edges.

• tsp.grf, a GRF file;
• tsp.png, a PNG image.
• tsp_adjacency_matrix.txt, the adjacency matrix;
• tsp_adjacency_structure.txt, the adjacency structure;
• tsp_distance_matrix.txt, the distance matrix;
• tsp_edges.txt, the edge list;
• tsp_edge_weights.txt, the edge weights;
• tsp_incidence_matrix.txt, the incidence matrix;
• tsp_node_coordinates.txt, node coordinates.
• tsp_node_labels.txt, node labels.

USA is an example of a simple graph of three components, two of which are single isolated nodes. It includes 51 nodes and 107 edges.

• usa.grf, a GRF file;
• usa.png, a PNG image based on the GRF file.
• usa_knuth.png, a PNG image of the data (omitting Alaska and Hawaii) by Knuth.
• usa_adjacency_matrix.txt, the adjacency matrix;
• usa_adjacency_structure.txt, the adjacency structure;
• usa_edges.txt, the edge list;
• usa_incidence_matrix.txt, the incidence matrix;
• usa_node_coordinates.txt, node coordinates.
• usa_node_labels.txt, node labels.

WALTHER is an example of a simple, connected graph. It includes 25 nodes, and 31 edges.

• walther.grf, a GRF file;
• walther.png, a PNG image.
• walther_adjacency_matrix.txt, the adjacency matrix;
• walther_adjacency_structure.txt, the adjacency structure;
• walther_edges.txt, the edge list;
• walther_incidence_matrix.txt, the incidence matrix;
• walther_node_coordinates.txt, node coordinates.
• walther_node_labels.txt, node labels.

You can go up one level to the DATA directory.