CODEPACK
Graph Codes


CODEPACK is a FORTRAN90 library 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:

Other kinds of graphs can have various combinations of these properties. For instance, we are interested in color dimultigraphs.

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

Licensing:

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

Languages:

CODEPACK is available in a FORTRAN90 version.

Related Data and Programs:

CITIES, a FORTRAN90 library 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 library which performs various calculations involving mathematical graphs. This library 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 library which handles combinatorial calculations.

TABLE_GRAPH_CODE, a FORTRAN90 program which reads a TABLE file describing a graph, and computes its graph code.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 27 November 2006.