1 /* 2 * graphtheory.h 3 * 4 * (c) 2018 Luka Marohnić 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program. If not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 #ifndef GRAPHTHEORY_H 21 #define GRAPHTHEORY_H 22 #ifdef HAVE_CONFIG_H 23 #include "config.h" 24 #endif 25 #include "first.h" 26 #include "graphe.h" 27 28 #ifndef NO_NAMESPACE_GIAC 29 namespace giac { 30 #endif // ndef NO_NAMESPACE_GIAC 31 32 enum gt_error_code { 33 _GT_ERR_UNKNOWN = 0, 34 _GT_ERR_NOT_A_GRAPH = 1, 35 _GT_ERR_WEIGHTED_GRAPH_REQUIRED = 2, 36 _GT_ERR_UNWEIGHTED_GRAPH_REQUIRED = 3, 37 _GT_ERR_DIRECTED_GRAPH_REQUIRED = 4, 38 _GT_ERR_UNDIRECTED_GRAPH_REQUIRED = 5, 39 _GT_ERR_INVALID_EDGE = 6, 40 _GT_ERR_INVALID_EDGE_ARC_MIX = 7, 41 _GT_ERR_MATRIX_NOT_SYMMETRIC = 8, 42 _GT_ERR_READING_FAILED = 9, 43 _GT_ERR_EDGE_NOT_FOUND = 10, 44 _GT_ERR_VERTEX_NOT_FOUND = 11, 45 _GT_ERR_NOT_A_TREE=12, 46 _GT_ERR_INVALID_NUMBER_OF_ROOTS=13, 47 _GT_ERR_INVALID_ROOT=14, 48 _GT_ERR_NOT_PLANAR=15, 49 _GT_ERR_CONNECTED_GRAPH_REQUIRED=16, 50 _GT_ERR_INVALID_DRAWING_METHOD=17, 51 _GT_ERR_NOT_A_CYCLE=18, 52 _GT_ERR_CYCLE_NOT_FOUND=19, 53 _GT_ERR_NAME_NOT_RECOGNIZED=20, 54 _GT_ERR_NOT_A_SUBGRAPH=21, 55 _GT_ERR_GRAPH_IS_NULL=22, 56 _GT_ERR_TAGVALUE_PAIR_EXPECTED=23, 57 _GT_ERR_NOT_A_GRAPHIC_SEQUENCE=24, 58 _GT_ERR_NOT_ACYCLIC_GRAPH=25, 59 _GT_ERR_BICONNECTED_GRAPH_REQUIRED=26, 60 _GT_ERR_NOT_BIPARTITE=27, 61 _GT_ERR_WRONG_NUMBER_OF_ARGS=28, 62 _GT_ERR_POSITIVE_INTEGER_REQUIRED=29, 63 _GT_ERR_BAD_VERTICES=30 64 }; 65 66 enum distribution_type { 67 _DISTR_UNIFORM, 68 _DISTR_POISSON, 69 _DISTR_EXPONENTIAL, 70 _DISTR_GEOMETRIC, 71 _DISTR_NORMAL, 72 _DISTR_FISHER, 73 _DISTR_CHISQUARE, 74 _DISTR_CAUCHY, 75 _DISTR_STUDENT, 76 _DISTR_MULTINOMIAL, 77 _DISTR_BINOMIAL, 78 _DISTR_GAMMA, 79 _DISTR_BETA, 80 _DISTR_WEIBULL, 81 _DISTR_DISCRETE 82 }; 83 84 bool is_graphe(const gen &g,std::string &disp_out,GIAC_CONTEXT); 85 gen gt_command(gen (*gtfunc)(const gen &,const context *),const char *args,GIAC_CONTEXT); 86 87 // GRAPH THEORY GIAC COMMANDS 88 89 gen _graph(const gen &g,GIAC_CONTEXT); 90 gen _digraph(const gen &g,GIAC_CONTEXT); 91 gen _export_graph(const gen &g,GIAC_CONTEXT); 92 gen _import_graph(const gen &g,GIAC_CONTEXT); 93 gen _trail(const gen &g,GIAC_CONTEXT); 94 gen _trail2edges(const gen &g,GIAC_CONTEXT); 95 gen _draw_graph(const gen &g,GIAC_CONTEXT); 96 gen _graph_complement(const gen &g,GIAC_CONTEXT); 97 gen _induced_subgraph(const gen &g,GIAC_CONTEXT); 98 gen _make_directed(const gen &g,GIAC_CONTEXT); 99 gen _seidel_switch(const gen &g,GIAC_CONTEXT); 100 gen _complete_graph(const gen &g,GIAC_CONTEXT); 101 gen _make_weighted(const gen &g,GIAC_CONTEXT); 102 gen _subgraph(const gen &g,GIAC_CONTEXT); 103 gen _underlying_graph(const gen &g,GIAC_CONTEXT); 104 gen _cycle_graph(const gen &g,GIAC_CONTEXT); 105 gen _path_graph(const gen &g,GIAC_CONTEXT); 106 gen _lcf_graph(const gen &g,GIAC_CONTEXT); 107 gen _add_arc(const gen &g,GIAC_CONTEXT); 108 gen _add_edge(const gen &g,GIAC_CONTEXT); 109 gen _add_vertex(const gen &g,GIAC_CONTEXT); 110 gen _delete_arc(const gen &g,GIAC_CONTEXT); 111 gen _delete_edge(const gen &g,GIAC_CONTEXT); 112 gen _delete_vertex(const gen &g,GIAC_CONTEXT); 113 gen _contract_edge(const gen &g,GIAC_CONTEXT); 114 gen _set_graph_attribute(const gen &g,GIAC_CONTEXT); 115 gen _get_graph_attribute(const gen &g,GIAC_CONTEXT); 116 gen _discard_graph_attribute(const gen &g,GIAC_CONTEXT); 117 gen _list_graph_attributes(const gen &g,GIAC_CONTEXT); 118 gen _set_vertex_attribute(const gen &g,GIAC_CONTEXT); 119 gen _get_vertex_attribute(const gen &g,GIAC_CONTEXT); 120 gen _discard_vertex_attribute(const gen &g,GIAC_CONTEXT); 121 gen _list_vertex_attributes(const gen &g,GIAC_CONTEXT); 122 gen _set_node_attribute(const gen &g,GIAC_CONTEXT); 123 gen _get_node_attribute(const gen &g,GIAC_CONTEXT); 124 gen _discard_node_attribute(const gen &g,GIAC_CONTEXT); 125 gen _list_edge_attributes(const gen &g,GIAC_CONTEXT); 126 gen _adjacency_matrix(const gen &g,GIAC_CONTEXT); 127 gen _incidence_matrix(const gen &g,GIAC_CONTEXT); 128 gen _biconnected_components(const gen &g,GIAC_CONTEXT); 129 gen _connected_components(const gen &g,GIAC_CONTEXT); 130 gen _departures(const gen &g,GIAC_CONTEXT); 131 gen _incident_edges(const gen &g,GIAC_CONTEXT); 132 gen _number_of_triangles(const gen &g,GIAC_CONTEXT); 133 gen _is_connected(const gen &g,GIAC_CONTEXT); 134 gen _is_biconnected(const gen &g,GIAC_CONTEXT); 135 gen _is_triconnected(const gen &g,GIAC_CONTEXT); 136 gen _is_weighted(const gen &g,GIAC_CONTEXT); 137 gen _is_forest(const gen &g,GIAC_CONTEXT); 138 gen _is_tournament(const gen &g,GIAC_CONTEXT); 139 gen _is_planar(const gen &g,GIAC_CONTEXT); 140 gen _is_tree(const gen &g,GIAC_CONTEXT); 141 gen _tree_height(const gen &g,GIAC_CONTEXT); 142 gen _maximum_matching(const gen &g,GIAC_CONTEXT); 143 gen _bipartite_matching(const gen &g,GIAC_CONTEXT); 144 gen _number_of_edges(const gen &g,GIAC_CONTEXT); 145 gen _edges(const gen &g,GIAC_CONTEXT); 146 gen _has_arc(const gen &g,GIAC_CONTEXT); 147 gen _arrivals(const gen &g,GIAC_CONTEXT); 148 gen _articulation_points(const gen &g,GIAC_CONTEXT); 149 gen _vertex_in_degree(const gen &g,GIAC_CONTEXT); 150 gen _vertex_out_degree(const gen &g,GIAC_CONTEXT); 151 gen _vertex_degree(const gen &g,GIAC_CONTEXT); 152 gen _get_edge_weight(const gen &g,GIAC_CONTEXT); 153 gen _set_edge_weight(const gen &g,GIAC_CONTEXT); 154 gen _has_edge(const gen &g,GIAC_CONTEXT); 155 gen _is_directed(const gen &g,GIAC_CONTEXT); 156 gen _minimum_degree(const gen &g,GIAC_CONTEXT); 157 gen _maximum_degree(const gen &g,GIAC_CONTEXT); 158 gen _is_regular(const gen &g,GIAC_CONTEXT); 159 gen _is_strongly_regular(const gen &g,GIAC_CONTEXT); 160 gen _neighbors(const gen &g,GIAC_CONTEXT); 161 gen _number_of_vertices(const gen &g,GIAC_CONTEXT); 162 gen _graph_vertices(const gen &g,GIAC_CONTEXT); 163 gen _relabel_vertices(const gen &g,GIAC_CONTEXT); 164 gen _permute_vertices(const gen &g,GIAC_CONTEXT); 165 gen _isomorphic_copy(const gen &g,GIAC_CONTEXT); 166 gen _weight_matrix(const gen &g,GIAC_CONTEXT); 167 gen _hypercube_graph(const gen &g,GIAC_CONTEXT); 168 gen _sierpinski_graph(const gen &g,GIAC_CONTEXT); 169 gen _petersen_graph(const gen &g,GIAC_CONTEXT); 170 gen _complete_binary_tree(const gen &g,GIAC_CONTEXT); 171 gen _complete_kary_tree(const gen &g,GIAC_CONTEXT); 172 gen _prism_graph(const gen &g,GIAC_CONTEXT); 173 gen _antiprism_graph(const gen &g,GIAC_CONTEXT); 174 gen _star_graph(const gen &g,GIAC_CONTEXT); 175 gen _grid_graph(const gen &g,GIAC_CONTEXT); 176 gen _torus_grid_graph(const gen &g,GIAC_CONTEXT); 177 gen _web_graph(const gen &g,GIAC_CONTEXT); 178 gen _wheel_graph(const gen &g,GIAC_CONTEXT); 179 gen _kneser_graph(const gen &g,GIAC_CONTEXT); 180 gen _odd_graph(const gen &g,GIAC_CONTEXT); 181 gen _random_graph(const gen &g,GIAC_CONTEXT); 182 gen _random_digraph(const gen &g,GIAC_CONTEXT); 183 gen _random_regular_graph(const gen &g,GIAC_CONTEXT); 184 gen _random_sequence_graph(const gen &g,GIAC_CONTEXT); 185 gen _random_bipartite_graph(const gen &g,GIAC_CONTEXT); 186 gen _random_tournament(const gen &g,GIAC_CONTEXT); 187 gen _random_tree(const gen &g,GIAC_CONTEXT); 188 gen _random_planar_graph(const gen &g,GIAC_CONTEXT); 189 gen _assign_edge_weights(const gen &g,GIAC_CONTEXT); 190 gen _cartesian_product(const gen &g,GIAC_CONTEXT); 191 gen _tensor_product(const gen &g,GIAC_CONTEXT); 192 gen _is_eulerian(const gen &g,GIAC_CONTEXT); 193 gen _highlight_vertex(const gen &g,GIAC_CONTEXT); 194 gen _highlight_edges(const gen &g,GIAC_CONTEXT); 195 gen _highlight_subgraph(const gen &g,GIAC_CONTEXT); 196 gen _highlight_trail(const gen &g,GIAC_CONTEXT); 197 gen _disjoint_union(const gen &g,GIAC_CONTEXT); 198 gen _graph_union(const gen &g,GIAC_CONTEXT); 199 gen _graph_join(const gen &g,GIAC_CONTEXT); 200 gen _graph_equal(const gen &g,GIAC_CONTEXT); 201 gen _reverse_graph(const gen &g,GIAC_CONTEXT); 202 gen _interval_graph(const gen &g,GIAC_CONTEXT); 203 gen _subdivide_edges(const gen &g,GIAC_CONTEXT); 204 gen _graph_power(const gen &g,GIAC_CONTEXT); 205 gen _vertex_distance(const gen &g,GIAC_CONTEXT); 206 gen _shortest_path(const gen &g,GIAC_CONTEXT); 207 gen _dijkstra(const gen &g,GIAC_CONTEXT); 208 gen _bellman_ford(const gen &g,GIAC_CONTEXT); 209 gen _allpairs_distance(const gen &g,GIAC_CONTEXT); 210 gen _graph_diameter(const gen &g,GIAC_CONTEXT); 211 gen _is_clique(const gen &g,GIAC_CONTEXT); 212 gen _maximum_clique(const gen &g,GIAC_CONTEXT); 213 gen _clique_number(const gen &g,GIAC_CONTEXT); 214 gen _clique_cover(const gen &g,GIAC_CONTEXT); 215 gen _clique_cover_number(const gen &g,GIAC_CONTEXT); 216 gen _chromatic_number(const gen &g,GIAC_CONTEXT); 217 gen _maximum_independent_set(const gen &g,GIAC_CONTEXT); 218 gen _independence_number(const gen &g,GIAC_CONTEXT); 219 gen _strongly_connected_components(const gen &g,GIAC_CONTEXT); 220 gen _is_strongly_connected(const gen &g,GIAC_CONTEXT); 221 gen _condensation(const gen &g,GIAC_CONTEXT); 222 gen _degree_sequence(const gen &g,GIAC_CONTEXT); 223 gen _is_graphic_sequence(const gen &g,GIAC_CONTEXT); 224 gen _sequence_graph(const gen &g,GIAC_CONTEXT); 225 gen _girth(const gen &g,GIAC_CONTEXT); 226 gen _odd_girth(const gen &g,GIAC_CONTEXT); 227 gen _topologic_sort(const gen &g,GIAC_CONTEXT); 228 gen _is_acyclic(const gen &g,GIAC_CONTEXT); 229 gen _is_arborescence(const gen &g,GIAC_CONTEXT); 230 gen _graph_spectrum(const gen &g,GIAC_CONTEXT); 231 gen _graph_charpoly(const gen &g,GIAC_CONTEXT); 232 gen _seidel_spectrum(const gen &g,GIAC_CONTEXT); 233 gen _is_integer_graph(const gen &g,GIAC_CONTEXT); 234 gen _spanning_tree(const gen &g,GIAC_CONTEXT); 235 gen _number_of_spanning_trees(const gen &g,GIAC_CONTEXT); 236 gen _minimal_spanning_tree(const gen &g,GIAC_CONTEXT); 237 gen _graph_rank(const gen &g,GIAC_CONTEXT); 238 gen _lowest_common_ancestor(const gen &g,GIAC_CONTEXT); 239 gen _st_ordering(const gen &g,GIAC_CONTEXT); 240 gen _is_bipartite(const gen &g,GIAC_CONTEXT); 241 gen _greedy_color(const gen &g,GIAC_CONTEXT); 242 gen _is_vertex_colorable(const gen &g,GIAC_CONTEXT); 243 gen _plane_dual(const gen &g,GIAC_CONTEXT); 244 gen _set_vertex_positions(const gen &g,GIAC_CONTEXT); 245 gen _clique_stats(const gen &g,GIAC_CONTEXT); 246 gen _minimal_vertex_coloring(const gen &g,GIAC_CONTEXT); 247 gen _transitive_closure(const gen &g,GIAC_CONTEXT); 248 gen _line_graph(const gen &g,GIAC_CONTEXT); 249 gen _is_isomorphic(const gen &g,GIAC_CONTEXT); 250 gen _graph_automorphisms(const gen &g,GIAC_CONTEXT); 251 gen _canonical_labeling(const gen &g,GIAC_CONTEXT); 252 gen _minimal_edge_coloring(const gen &g,GIAC_CONTEXT); 253 gen _chromatic_index(const gen &g,GIAC_CONTEXT); 254 gen _is_hamiltonian(const gen &g,GIAC_CONTEXT); 255 gen _traveling_salesman(const gen &g,GIAC_CONTEXT); 256 gen _maxflow(const gen &g,GIAC_CONTEXT); 257 gen _minimum_cut(const gen &g,GIAC_CONTEXT); 258 gen _is_cut_set(const gen &g,GIAC_CONTEXT); 259 gen _is_network(const gen &g,GIAC_CONTEXT); 260 gen _random_network(const gen &g,GIAC_CONTEXT); 261 gen _tutte_polynomial(const gen &g,GIAC_CONTEXT); 262 gen _chromatic_polynomial(const gen &g,GIAC_CONTEXT); 263 gen _flow_polynomial(const gen &g,GIAC_CONTEXT); 264 gen _reliability_polynomial(const gen &g,GIAC_CONTEXT); 265 gen _laplacian_matrix(const gen &g,GIAC_CONTEXT); 266 gen _fundamental_cycle(const gen &g,GIAC_CONTEXT); 267 gen _cycle_basis(const gen &g,GIAC_CONTEXT); 268 gen _mycielski(const gen &g,GIAC_CONTEXT); 269 gen _clustering_coefficient(const gen &g,GIAC_CONTEXT); 270 gen _network_transitivity(const gen &g,GIAC_CONTEXT); 271 gen _two_edge_connected_components(const gen &g,GIAC_CONTEXT); 272 gen _is_two_edge_connected(const gen &g,GIAC_CONTEXT); 273 gen _edge_connectivity(const gen &g,GIAC_CONTEXT); 274 gen _vertex_connectivity(const gen &g,GIAC_CONTEXT); 275 gen _tonnetz(const gen &g,GIAC_CONTEXT); 276 gen _truncate_graph(const gen &g,GIAC_CONTEXT); 277 gen _find_cycles(const gen &g,GIAC_CONTEXT); 278 gen _kspaths(const gen &g,GIAC_CONTEXT); 279 280 // GENERAL GIAC COMMANDS 281 282 gen _foldl(const gen &g,GIAC_CONTEXT); 283 gen _foldr(const gen &g,GIAC_CONTEXT); 284 gen _randvar(const gen &g,GIAC_CONTEXT); 285 gen _icomp(const gen &g,GIAC_CONTEXT); 286 287 // FUNCTION POINTERS 288 289 extern const unary_function_ptr * const at_trail; 290 291 #ifndef NO_NAMESPACE_GIAC 292 } // namespace giac 293 #endif // ndef NO_NAMESPACE_GIAC 294 #endif // GRAPHTHEORY_H 295