CODEPACK - Graph Codes

CODEPACK includes routines to compute and compare codes for various kinds of graphs. 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.

The graph codes are expensice to compute. In the most common case, where two graphs are not isomorphic, a determination can usually be made much more cheaply, by counting edges, looking at the degree sequence, and so on. A number of these "weeding out" functions are available, and a sample process for graph comparison is available in the COMPARE routines.

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 edges between two nodes may be more than 1; this may also be thought of as a single edge with an integer weight.

The CODEPACK routines were originally part of GRAFPACK but as that package grew too large, these routines were extracted.

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);

Files you may copy include:

• codepack.f90, the source code;
• codepack_prb.f90, the calling program;
• codepack_prb.out, the sample output.

The list of routines includes:

• BACKTRACK supervises a backtrack search.
• 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.
• GET_SEED returns a random seed for the random number generator.
• 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 up the adjacency information 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.
• I_RANDOM returns a random integer in a given range.
• I_SWAP switches two integer values.
• IMAT_COPY copies a rectangular integer matrix.
• IMAT_PERM permutes the rows and columns of a square integer matrix.
• IMAT_PERM_RANDOM selects a random permutation of an integer matrix.
• IMAT_ROW_COMPARE compares two arrays of row vectors.
• IROW_COMPARE compares two rows of a integer array.
• IROW_SORT_D descending sorts the rows of an integer array.
• IROW_SORT2_D descending sorts the elements of each row of an integer array.
• IROW_SWAP swaps two rows of an integer array.
• IVEC_COMPARE compares two integer vectors.
• IVEC_COPY copies an integer vector
• IVEC_HEAP_A reorders an array of integers into an ascending heap.
• IVEC_NONZERO counts the nonzero entries in an integer vector
• IVEC_ORDER_TYPE determines if an integer array is (non)strictly ascending/des
• IVEC_PERM_RANDOM selects a random permutation of an integer vector.
• IVEC_RANDOM returns a random integer vector in a given range.
• IVEC_SORT_HEAP_D descending sorts an integer array using heap sort.
• IVEC_UNIQ finds the number of unique elements in a sorted integer array.
• IVEC2_COMP compares pairs of integers stored in two vectors.
• IVEC2_SORT_D descending sorts a vector of pairs of integers.
• IVEC2_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_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.
• R_RANDOM returns a random real in a given range.
• RMAT_PRINT prints out a portion of a dense matrix.
• RVEC_RANDOM returns a random real vector in a given range.
• SORT_HEAP_EXTERNAL externally sorts a list of items into linear order.
• TREE_ARC_RANDOM selects a random labeled tree and its Pruefer code.
• UNIFORM_01_SAMPLE is a portable random number generator.
• VEC_RANDOM selects a random N-vector of integers modulo a given base.

Back to the FORTRAN software page.