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:

• 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 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:

• codepack.f90, the source code;

Examples and Tests:

• codepack_test.f90, the calling program;
• codepack_test.txt, the output file.

List of Routines:

• CDG_CODE_BACK computes a color digraph code via backtracking.
• CDG_CODE_BRUTE computes the color digraph code via brute force.
• CDG_CODE_CAND finds candidates for a maximal color digraph code ordering.
• CDG_CODE_COMPARE compares two (partial) color graph codes.
• CDG_CODE_PRINT prints a color digraph code.
• CDG_COLOR_COUNT counts the number of colors in a color digraph.
• CDG_COLOR_SEQUENCE computes the color sequence of a color digraph.
• CDG_COMPARE determines if color digraphs G1 and G2 are isomorphic.
• CDG_DEGREE computes the indegree and outdegree of each node.
• CDG_DEGREE_SEQ computes the degree sequence of a color digraph.
• CDG_EDGE_COUNT counts the number of edges in a color digraph.
• CDG_EXAMPLE_CUBE sets up the cube color digraph.
• CDG_EXAMPLE_OCTO sets up an 8 node example color digraph.
• CDG_ORDER_CODE returns the color digraph code for a specific node ordering.
• CDG_PRINT prints out the adjacency matrix of a color digraph.
• CDG_RANDOM generates a random color graph.
• CDMG_ADJ_MAX_MAX computes the adjacency maximum maximum of a color dimultigraph.
• CDMG_ADJ_MAX_SEQ computes the adjacency maximum sequence of a color dimultigraph.
• CDMG_ADJ_SEQ_U computes the unweighted adjacency sequence of a color dimultigraph.
• CDMG_ADJ_SEQ_W computes the weighted adjacency sequence of a color dimultigraph.
• CDMG_CODE_BACK computes a color dimultigraph code via backtracking.
• CDMG_CODE_BRUTE computes a color dimultigraph code via brute force.
• CDMG_CODE_CAND finds candidates for a maximal color dimultigraph code ordering.
• CDMG_CODE_COMPARE compares two (partial) color dimultigraph codes.
• CDMG_CODE_PRINT prints out a color dimultigraph code.
• CDMG_COLOR_COUNT counts the number of colors in a color dimultigraph.
• CDMG_COLOR_SEQUENCE computes the color sequence of a color dimultigraph.
• CDMG_COMPARE determines if color dimultigraphs G1 and G2 are isomorphic.
• CDMG_DEGREE_SEQ_U: unweighted directed degree sequence of color dimultigraph.
• CDMG_DEGREE_SEQ_W: weighted directed degree sequence of a color dimultigraph.
• CDMG_DEGREE_U computes the unweighted degrees of a color dimultigraph.
• CDMG_DEGREE_W computes the weighted degrees of a color dimultigraph.
• CDMG_EDGE_COUNT counts the number of edges in a color dimultigraph.
• CDMG_EXAMPLE_OCTO sets up an 8 node example color dimultigraph.
• CDMG_ORDER_CODE returns the color dimultigraph code for a specific node ordering.
• CDMG_PRINT prints out an adjacency matrix for a color dimultigraph.
• CDMG_RANDOM generates a random color dimultigraph.
• CG_CODE_BACK computes a color graph code via backtracking.
• CG_CODE_BRUTE computes the color graph code via brute force.
• CG_CODE_CAND finds candidates for a maximal color graph code ordering.
• CG_CODE_COMPARE compares two (partial) color graph codes.
• CG_CODE_PRINT prints a color graph code.
• CG_COLOR_COUNT counts the number of colors in a color graph.
• CG_COLOR_SEQUENCE computes the color sequence of a color graph.
• CG_COMPARE determines if color graphs G1 and G2 are isomorphic.
• CG_CONNECT_RANDOM generates a random connected color graph.
• CG_DEGREE computes the degree of each node.
• CG_DEGREE_SEQ computes the degree sequence of a color graph.
• CG_EDGE_COUNT counts the number of edges in a color graph.
• CG_EXAMPLE_BUSH sets up the bush color graph.
• CG_EXAMPLE_CUBE sets up the cube color graph.
• CG_EXAMPLE_OCTO sets up an 8 node example color graph.
• CG_EXAMPLE_TWIG sets up the twig color graph.
• CG_ORDER_CODE returns the color graph code for a specific node ordering.
• CG_PRINT prints out the adjacency matrix of a color graph.
• CG_RANDOM generates a random color graph.
• DG_CODE_BACK computes a digraph code via backtracking.
• DG_CODE_BRUTE computes a digraph code via brute force.
• DG_CODE_CAND finds candidates for a maximal digraph code ordering.
• DG_CODE_COMPARE compares two partial digraph codes.
• DG_CODE_PRINT prints out a digraph code.
• DG_COMPARE determines if digraphs G1 and G2 are isomorphic.
• DG_DEGREE computes the indegree and outdegree of each node.
• DG_DEGREE_MAX computes the maximum degrees of a digraph.
• DG_DEGREE_SEQ computes the directed degree sequence.
• DG_EDGE_COUNT counts the number of edges in a digraph.
• DG_EXAMPLE_CYCLER sets up the adjacency information for the cycler digraph.
• DG_EXAMPLE_OCTO sets up an 8 node example digraph.
• DG_EXAMPLE_SIXTY sets up the adjacency information for the sixty digraph.
• DG_ORDER_CODE returns the digraph code for a specific node ordering.
• DG_RANDOM generates a random digraph.
• DMG_ADJ_MAX_MAX computes the adjacency maximum maximum of a dimultigraph.
• DMG_ADJ_MAX_SEQ computes the adjacency maximum sequence of a dimultigraph.
• DMG_ADJ_SEQ_U computes the unweighted adjacency sequence of a dimultigraph.
• DMG_ADJ_SEQ_W computes the weighted adjacency sequence of a dimultigraph.
• DMG_CODE_BACK computes a dimultigraph code via backtracking.
• DMG_CODE_BRUTE computes a dimultigraph code via brute force.
• DMG_CODE_CAND finds candidates for a maximal dimultigraph code ordering.
• DMG_CODE_COMPARE compares two partial dimultigraph codes.
• DMG_CODE_PRINT prints out a dimultigraph code.
• DMG_COMPARE determines if dimultigraphs G1 and G2 are isomorphic.
• DMG_DEGREE_SEQ_U: the unweighted directed degree sequence of a dimultigraph.
• DMG_DEGREE_SEQ_W: weighted directed degree sequence of a dimultigraph.
• DMG_DEGREE_U computes the unweighted degrees of a dimultigraph.
• DMG_DEGREE_W computes the weighted degrees of a dimultigraph.
• DMG_EDGE_COUNT counts the number of edges in a dimultigraph.
• DMG_EXAMPLE_OCTO sets up an 8 node example dimultigraph.
• DMG_ORDER_CODE returns the dimultigraph code for a specific node ordering.
• DMG_PRINT prints out an adjacency matrix for a dimultigraph.
• DMG_RANDOM generates a random dimultigraph on NNODE nodes with NEDGE edges.
• G_ARC_NODE_COUNT counts the number of nodes in a graph.
• G_ARC_TO_G_ADJ converts an arc list graph to an adjacency graph.
• G_CODE_BACK computes a graph code via backtracking.
• G_CODE_BRUTE computes a graph code via brute force.
• G_CODE_CAND finds candidates for a maximal graph code ordering.
• G_CODE_COMPARE compares two partial graph codes.
• G_CODE_PRINT prints out a graph code.
• G_COMPARE determines if graphs G1 and G2 are isomorphic.
• G_CONNECT_RANDOM generates a random connected graph.
• G_DEGREE computes the degree of each node in a graph.
• G_DEGREE_MAX computes the maximum node degree of a graph.
• G_DEGREE_SEQ computes the degree sequence of a graph.
• G_EDGE_COUNT counts the number of edges in a graph.
• G_EXAMPLE_BUSH sets up the adjacency information for the bush graph.
• G_EXAMPLE_CUBE sets up the adjacency information for the cube graph.
• G_EXAMPLE_DODECAHEDRON sets adjacency for the dodecahedron graph.
• G_EXAMPLE_OCTO sets up an 8 node example graph.
• G_EXAMPLE_TWIG sets up the adjacency information for the twig graph.
• G_ORDER_CODE returns the graph code for a specific node ordering.
• G_PRINT prints out an adjacency matrix.
• G_RANDOM generates a random graph on NNODE nodes with NEDGE edges.
• I4_SWAP switches two I4's.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4MAT_PERM permutes the rows and columns of a square integer matrix.
• I4MAT_PERM_RANDOM selects a random permutation of an integer matrix.
• I4MAT_PRINT prints an integer matrix.
• I4MAT_PRINT_SOME prints some of an integer matrix.
• I4MAT_ROW_COMPARE compares two arrays of row vectors.
• I4ROW_COMPARE compares two rows of a integer array.
• I4ROW_SORT_D descending sorts the rows of an integer array.
• I4ROW_SORT2_D descending sorts the elements of each row of an integer array.
• I4ROW_SWAP swaps two rows of an integer array.
• I4VEC_BACKTRACK supervises a backtrack search for an integer vector.
• I4VEC_COMPARE compares two integer vectors.
• I4VEC_HEAP_A reorders an array of integers into an ascending heap.
• I4VEC_HEAP_D reorders an array of integers into an descending heap.
• I4VEC_INDICATOR sets an integer vector to the indicator vector.
• I4VEC_NONZERO_COUNT counts the nonzero entries in an integer vector
• I4VEC_ORDER_TYPE determines if an integer array is (non)strictly ascending/descending.
• I4VEC_PERM_RANDOM selects a random permutation of an integer vector.
• I4VEC_PRINT prints an integer vector.
• I4VEC_SORT_HEAP_A ascending sorts an integer array using heap sort.
• I4VEC_SORT_HEAP_D descending sorts an integer array using heap sort.
• I4VEC_SORTED_UNIQUE_COUNT counts unique elements in a sorted integer array.
• I4VEC_UNIFORM returns a vector of integer pseudorandom numbers.
• I4VEC2_COMP compares pairs of integers stored in two vectors.
• I4VEC2_SORT_D descending sorts a vector of pairs of integers.
• I4VEC2_UNIQ keeps the unique elements in a array of pairs of integers.
• KSUB_RANDOM selects a random subset of size K from a set of size N.
• MG_ADJ_MAX_MAX computes the adjacency maximum maximum of a multigraph.
• MG_ADJ_MAX_SEQ computes the adjacency maximum sequence of a multigraph.
• MG_ADJ_SEQ computes the adjacency sequence of a multigraph.
• MG_CODE_BACK computes a multigraph code via backtracking.
• MG_CODE_BRUTE computes a multigraph code via brute force.
• MG_CODE_CAND finds candidates for a maximal multigraph code ordering.
• MG_CODE_COMPARE compares two partial multigraph codes.
• MG_CODE_PRINT prints out a multigraph code.
• MG_COMPARE determines if multigraphs G1 and G2 are isomorphic.
• MG_DEGREE computes the degree of each node of a multigraph.
• MG_DEGREE_MAX computes the maximum node degree of a multigraph.
• MG_DEGREE_SEQ computes the degree sequence of a multigraph.
• MG_EDGE_COUNT counts the number of edges in a multigraph.
• MG_EXAMPLE_OCTO sets up an 8 node example multigraph.
• MG_ORDER_CODE returns the multigraph code for a specific node ordering.
• MG_PRINT prints out an adjacency matrix for a multigraph.
• MG_RANDOM generates a random multigraph on NNODE nodes with NEDGE edges.
• NODE_ORDER_PRINT prints out a node ordering.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_CYCLE analyzes a permutation.
• PERM_FREE reports the number of unused items in a partial permutation.
• PERM_NEXT computes all of the permutations on N objects, one at a time.
• PERM_RANDOM selects a random permutation of N objects.
• PRUEFER_TO_TREE_ARC is given a Pruefer code, and computes the tree.
• R4_UNIFORM_01 returns a unit pseudorandom R4.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8_NORMAL_01 returns a unit pseudonormal R8.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TREE_ARC_RANDOM selects a random labeled tree and its Pruefer code.
• WG_RANDOM generates a random weighted graph.

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