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:
Some of the routine names begin with a prefix that indicates the type of object it is associated with:
The computer code and data files described and made available on this web page are distributed under the MIT license
codepack is available in a FORTRAN90 version.
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.
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.