Quelle  bliss_C.h   Sprache: C

#ifndef bliss_digraphs_C_H
#define bliss_digraphs_C_H

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.

  This file is part of bliss.

  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

/**
 * \file
 * \brief The bliss C API.
 *
 * This is the C language API to
 * <A href="http://www.tcs.hut.fi/Software/bliss/">bliss</A>.
 * Note that this C API is only a subset of the C++ API;
 * please consider using the C++ API whenever possible.
 */

#include <stdlib.h>
#include <stdio.h>


/**
 * \brief The true bliss graph is hiding behind this typedef.
 */
typedef struct bliss_digraphs_graph_struct BlissGraph;


/**
 * \brief The C API version of the statistics returned by
 * the bliss search algorithm.
 */
typedef struct bliss_digraphs_stats_struct
{

  /* The true size of the group */
  /* This is a list of integers of length group_size_len */
  /* This is only used when BLISS_IN_GAP is defined */
  int* group_size;
  int group_size_len;

  /**
   * An approximation (due to possible rounding errors) of
   * the size of the automorphism group.
   */
  long double group_size_approx;
  /** The number of nodes in the search tree. */
  long unsigned int nof_nodes;
  /** The number of leaf nodes in the search tree. */
  long unsigned int nof_leaf_nodes;
  /** The number of bad nodes in the search tree. */
  long unsigned int nof_bad_nodes;
  /** The number of canonical representative updates. */
  long unsigned int nof_canupdates;
  /** The number of generator permutations. */
  long unsigned int nof_generators;
  /** The maximal depth of the search tree. */
  unsigned long int max_level;
} BlissStats;


/**
 * Create a new graph instance with \a N vertices and no edges.
 * \a N can be zero and bliss_digraphs_add_vertex() called afterwards
 * to add new vertices on-the-fly.
 */
BlissGraph *bliss_digraphs_new(const unsigned int N);


/**
 * Read an undirected graph from a file in the DIMACS format into a new bliss
 * instance.
 * Returns 0 if an error occurred.
 * Note that in the DIMACS file the vertices are numbered from 1 to N while
 * in the bliss C API they are from 0 to N-1.
 * Thus the vertex n in the file corresponds to the vertex n-1 in the API.
 */
BlissGraph *bliss_digraphs_read_dimacs(FILE *fp);


/**
 * Output the graph in the file stream \a fp in the DIMACS format.
 * See the User's Guide for the file format details.
 * Note that in the DIMACS file the vertices are numbered from 1 to N while
 * in bliss they are from 0 to N-1.
 */
void bliss_digraphs_write_dimacs(BlissGraph *graph, FILE *fp);


/**
 * Release the graph.
 * Note that the memory pointed by the arguments of hook functions for
 * bliss_digraphs_find_automorphisms() and bliss_digraphs_find_canonical_labeling()
 * is deallocated and thus should not be accessed after calling this function.
 */
void bliss_digraphs_release(BlissGraph *graph);

void bliss_digraphs_clear(BlissGraph *graph);
void bliss_digraphs_change_color(BlissGraph* graph, const unsigned int vertex, const unsigned int color);

/**
 * Print the graph in graphviz dot format.
 */
void bliss_digraphs_write_dot(BlissGraph *graph, FILE *fp);


/**
 * Return the number of vertices in the graph.
 */
unsigned int bliss_digraphs_get_nof_vertices(BlissGraph *graph);


/**
 * Add a new vertex with color \a c in the graph \a graph and return its index.
 * The vertex indices are always in the range
 * [0,bliss::bliss_digraphs_get_nof_vertices(\a bliss)-1].
 */
unsigned int bliss_digraphs_add_vertex(BlissGraph *graph, unsigned int c);


/**
 * Add a new undirected edge in the graph.
 * \a v1 and \a v2 are vertex indices returned by bliss_digraphs_add_vertex().
 * If duplicate edges are added, they will be ignored (however, they are not
 * necessarily physically ignored immediately but may consume memory for
 * a while so please try to avoid adding duplicate edges whenever possible).
 */
void bliss_digraphs_add_edge(BlissGraph *graph, unsigned int v1, unsigned int v2);


/**
 * Compare two graphs according to a total order.
 * Return -1, 0, or 1 if the first graph was smaller than, equal to,
 * or greater than, resp., the other graph.
 * If 0 is returned, then the graphs have the same number vertices,
 * the vertices in them are colored in the same way, and they contain
 * the same edges; that is, the graphs are equal.
 */
int bliss_digraphs_cmp(BlissGraph *graph1, BlissGraph *graph2);


/**
 * Get a hash value for the graph.
 */
unsigned int bliss_digraphs_hash(BlissGraph *graph);


/**
 * Permute the graph with the given permutation \a perm.
 * Returns the permuted graph, the original graph is not modified.
 * The argument \a perm should be an array of
 * N=bliss::bliss_digraphs_get_nof_vertices(\a graph) elements describing
 * a bijection on {0,...,N-1}.
 */
BlissGraph *bliss_digraphs_permute(BlissGraph *graph, const unsigned int *perm);


/**
 * Find a set of generators for the automorphism group of the graph.
 * The hook function \a hook (if non-null) is called each time a new generator
 * for the automorphism group is found.
 * The first argument \a user_param for the hook function is
 * the \a hook_user_param argument,
 * the second argument \a N is the length of the automorphism (equal to
 * bliss::bliss_digraphs_get_nof_vertices(\a graph)) and
 * the third argument \a aut is the automorphism (a bijection on {0,...,N-1}).
 * The memory for the automorphism \a aut will be invalidated immediately
 * after the return from the hook;
 * if you want to use the automorphism later, you have to take a copy of it.
 * Do not call bliss_digraphs_* functions in the hook.
 * If \a stats is non-null, then some search statistics are copied there.
 */
void
bliss_digraphs_find_automorphisms(BlissGraph *graph,
    void (*hook)(void *user_param,
          unsigned int N,
          const unsigned int *aut),
    void *hook_user_param,
    BlissStats *stats);


/**
 * Otherwise the same as bliss_digraphs_find_automorphisms() except that
 * a canonical labeling for the graph (a bijection on {0,...,N-1}) is returned.
 * The returned canonical labeling will remain valid only until
 * the next call to a bliss_digraphs_* function with the exception that
 * bliss_digraphs_permute() can be called without invalidating the labeling.
 * To compute the canonical version of a graph, call this function and
 * then bliss_digraphs_permute() with the returned canonical labeling.
 * Note that the computed canonical version may depend on the applied version
 * of bliss.
 */
const unsigned int *
bliss_digraphs_find_canonical_labeling(BlissGraph *graph,
         void (*hook)(void *user_param,
        unsigned int N,
        const unsigned int *aut),
         void *hook_user_param,
         BlissStats *stats);


// Clean up memory allocated by a used BlissStats
void bliss_digraphs_free_blissstats(BlissStats *stats);

#endif