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.

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

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;

**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.