00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2006--2007 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUGRA_ALGO_H 00019 #define CUGRA_ALGO_H 00020 00021 #include <cugra/fwd.h> 00022 #include <cu/clos.h> 00023 #include <cucon/fwd.h> 00024 #include <stdio.h> 00025 00026 CU_BEGIN_DECLARATIONS 00027 /*!\defgroup cugra_graph_algo_h cugra/graph_algo.h: Graph Algorithms 00028 *@{\ingroup cugra_mod */ 00029 00030 /*!Copy \a G_src into \a G_dst, and insert into \a vsrc_to_vdst and \a 00031 * vdst_to_vsrc, if non-\c NULL, the vertex-mappings. */ 00032 void cugra_graph_copy(cugra_graph_t G_src, cugra_graph_t G_dst, 00033 cucon_pmap_t vsrc_to_vdst, cucon_pmap_t vdst_to_vsrc); 00034 00035 /*!True iff \a G is acyclic. */ 00036 cu_bool_t cugra_graph_is_acyclic(cugra_graph_t G); 00037 00038 /*!Erase all isolated vertices in \a G. */ 00039 void cugra_graph_erase_isolated(cugra_graph_t G); 00040 00041 /*!Erase all arcs which connect \a v to a vertex not in \a V. */ 00042 void cugra_erase_vertex_to_vsetcompl_arcs(cugra_graph_t G, cugra_vertex_t v, 00043 cucon_pmap_t V); 00044 00045 /*!Move vertices in \a V_move from \a G_src to \a G_dst, cutting all arcs 00046 * between \a V_move and its complement. */ 00047 void cugra_move_induced_subgraph(cucon_pmap_t V_move, 00048 cugra_graph_t G_src, cugra_graph_t G_dst); 00049 00050 /*!Finds the maximally connected subgraphs of \a G and report them in two 00051 * ways as follows. 00052 * If \a KV is non-\c NULL, push a \c cucon_pset_t for each subgraph where the 00053 * keys are the vertices of the subgraph. 00054 * If \a M is non-\c NULL, associate each vertex which is part of a loop with 00055 * an index identifying the maximally connected subgraph to which it belongs. 00056 * \deprecated Use \ref cugra_walk_SCC */ 00057 void cugra_identify_MSC(cugra_graph_t G, cucon_stack_t KV, cucon_pmap_t M) 00058 CU_ATTR_DEPRECATED; 00059 00060 /*!Move all maximally connected subgraphs of \a G into separate graphs and 00061 * push them onto \a KG. 00062 * \deprecated Use \ref cugra_walk_SCC */ 00063 void cugra_move_MSC_subgraphs(cugra_graph_t G, cucon_stack_t KG) 00064 CU_ATTR_DEPRECATED; 00065 00066 #ifdef CUCONF_HAVE_BUDDY 00067 /*!Inserts a minimum feedback vertex set of \a G into \a V. Only available if 00068 * culibs is linked with BuDDY. */ 00069 void cugra_MFVS(cugra_graph_t G, cucon_pset_t V); 00070 #endif 00071 00072 /*!Write \a G in Graphviz .dot format to \a fout, with labels for vertices and 00073 * arcs as given by \a vertex_label and \a arc_label, repectively, unless \ref 00074 * cu_clop_null. */ 00075 void cugra_graph_fwrite_dot(cugra_graph_t G, 00076 cu_clop(vertex_label, cu_str_t, cugra_vertex_t), 00077 cu_clop(arc_label, cu_str_t, cugra_arc_t), 00078 FILE *fout); 00079 00080 /*!Write \a G in Graphviz .dot format to \a path, with labels for vertices and 00081 * arcs as given by \a vertex_label and \a arc_label, respectively, unless 00082 * \ref cu_clop_null. */ 00083 cu_bool_t cugra_graph_save_dot(cugra_graph_t G, 00084 cu_clop(vertex_label, cu_str_t, cugra_vertex_t), 00085 cu_clop(arc_label, cu_str_t, cugra_arc_t), 00086 char const *path); 00087 00088 /*!Searches shortest path, according to distances given by \a arc_distance, 00089 * from \a v_start to a vertex for which \a vertex_test returns true. If 00090 * found, call \a notify_path_unwind with arcs of the shortest path in revese 00091 * order and return the path's distance. Otherwise, return \c INFINITY. */ 00092 double 00093 cugra_shortest_path(cugra_direction_t dir, cugra_vertex_t v_start, 00094 cu_clop(vertex_test, cu_bool_t, cugra_vertex_t), 00095 cu_clop(arc_distance, double, cugra_arc_t), 00096 cu_clop(notify_path_unwind, void, cugra_arc_t)); 00097 00098 /*!@}*/ 00099 CU_END_DECLARATIONS 00100 00101 #endif