codepack

codepack, a FORTRAN90 code which computes and compares "codes" for graphs, directed graphs, multigraphs, and other generalizations of an abstract graph.

The codes are a form of "signature". Two graphs are isomorphic (essentially the same object) if and only if their signatures are equal. The codes are numeric, and hence determining whether two graphs are isomorphic is reduced to the problem of whether two sequences of integers are identical.

It is important to understand that the kind of problem being considered here is HARD and EXPENSIVE. The time and space requirements increase very rapidly as the number of nodes in the graph increase. Graphs with 10 nodes can be handled, but graphs with 20 nodes may be difficult, and graphs with 40 or 50 nodes may be impossible to handle. This is partly because we are looking at permutations of the nodes, and this number grows as the factorial function.

Although graph codes are expensive to compute, it is often not difficult to detect that two graphs are not isomorphic. A determination can be made very quickly if the number of nodes, number of edges, or the degree sequence does not match. These techniques can often produce a "No" answer quickly. But if two graphs do happen to be isomorphic, then there is no rapid way to determine this. The only thing a graph code offers is a systematic (but slow) way to go about this computation.

The kinds of graphs considered here include:

• Graphs in which any two nodes may or may not be connected.
• Digraphs or "directed graphs", in which the edges between two nodes have a direction.
• Color graphs in which each node has a color.
• Multigraphs in which the number of (undirected) edges between two nodes may be more than 1; this may also be thought of as a single edge with an integer weight.
• Weighted graphs in which each (undirected) edge is assigned a (real number) weight, or distance.

Some of the routine names begin with a prefix that indicates the type of object it is associated with:

• G is a graph;
• DG is a directed graph (edges have a direction);
• CG is a color graph (nodes have a color);
• MG is a multigraph (edges have multiplicity);
• CDG is a color directed graph (edges have direction, nodes have a color);
• DMG is a dimultigraph (edges have direction and multiplicity);
• CDMG is a color dimultigraph (edges have direction and multiplicity, nodes have color);
• WG is a weighted graph;

Licensing:

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

Languages:

codepack is available in a FORTRAN90 version.

Related Data and Programs:

CITIES, a FORTRAN90 code which handles various problems associated with a set of "cities" on a map.

CITIES, a dataset directory which contains a number of city distance datasets.

codepack_test

GRAFPACK, a FORTRAN90 code which performs various calculations involving mathematical graphs. This code originally included the routines in CODEPACK, but as that package grew too large, these routines were extracted.

GRAPH_REPRESENTATION, a data directory which contains examples of ways of representing abstract mathematical graphs

SUBSET, a FORTRAN90 code which handles combinatorial calculations.

Source Code:

• codepack.f90, the source code;
• codepack.sh, compiles the source code;