1 /* 2 * graphe.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 __GRAPHE_H 21 #define __GRAPHE_H 22 #ifdef HAVE_CONFIG_H 23 #include "config.h" 24 #endif 25 #include "first.h" 26 #include "gen.h" 27 #include "unary.h" 28 #include "moyal.h" 29 #include <string> 30 #include <iostream> 31 #include <fstream> 32 #include <queue> 33 #include <stack> 34 #include <set> 35 #ifdef HAVE_LIBGLPK 36 #include <glpk.h> 37 #endif 38 39 #ifndef DBL_MAX 40 #define DBL_MAX 1.79769313486e+308 41 #endif 42 #define PLASTIC_NUMBER 1.32471795724 43 #define PLASTIC_NUMBER_2 1.75487766625 44 #define PLASTIC_NUMBER_3 2.32471795724 45 #define MARGIN_FACTOR 0.139680581996 // pow(PLASTIC_NUMBER,-7) 46 47 #ifndef NO_NAMESPACE_GIAC 48 namespace giac { 49 #endif // ndef NO_NAMESPACE_GIAC 50 51 typedef unsigned long ulong; 52 53 enum gt_dot_token_type { 54 _GT_DOT_TOKEN_TYPE_IDENTIFIER = 1, 55 _GT_DOT_TOKEN_TYPE_NUMBER = 2, 56 _GT_DOT_TOKEN_TYPE_OPERATOR = 3, 57 _GT_DOT_TOKEN_TYPE_STRING = 4, 58 _GT_DOT_TOKEN_TYPE_DELIMITER = 5 59 }; 60 61 enum gt_attribute { 62 _GT_ATTRIB_LABEL, 63 _GT_ATTRIB_WEIGHT, 64 _GT_ATTRIB_COLOR, 65 _GT_ATTRIB_SHAPE, 66 _GT_ATTRIB_STYLE, 67 _GT_ATTRIB_DIRECTED, 68 _GT_ATTRIB_WEIGHTED, 69 _GT_ATTRIB_POSITION, 70 _GT_ATTRIB_NAME, 71 _GT_ATTRIB_TEMPORARY, 72 //add more here 73 _GT_ATTRIB_USER // this one must be the last 74 }; 75 76 enum gt_layout_style { 77 _GT_STYLE_DEFAULT, 78 _GT_STYLE_SPRING, 79 _GT_STYLE_PLANAR, 80 _GT_STYLE_3D, 81 _GT_STYLE_CIRCLE, 82 _GT_STYLE_TREE, 83 _GT_STYLE_BIPARTITE 84 }; 85 86 class graphe { 87 public: 88 typedef std::vector<int> ivector; 89 typedef std::vector<ivector> ivectors; 90 typedef std::map<int,gen> attrib; 91 typedef std::pair<int,int> ipair; 92 typedef std::vector<ipair> ipairs; 93 typedef std::pair<double,double> dpair; 94 typedef std::vector<dpair> dpairs; 95 typedef std::vector<double> point; 96 typedef std::vector<point> layout; 97 typedef std::map<int,std::map<int,ipair> > sparsemat; 98 typedef std::set<ipair> edgeset; 99 typedef std::vector<std::map<int,int> > edgemap; 100 typedef std::vector<std::map<int,double> > edgemapd; 101 typedef std::map<ipair,int> intpoly; 102 typedef std::vector<double> dvector; 103 typedef std::set<int> iset; 104 105 class vertex { // vertex class 106 int m_subgraph; 107 // used for traversing 108 bool m_visited; 109 int m_low; 110 int m_disc; 111 int m_ancestor; 112 int m_color; 113 // used for planar embedding 114 bool m_embedded; 115 int m_number; 116 std::map<int,int> m_faces; 117 // * 118 attrib *m_attributes; 119 ivector m_neighbors; 120 std::map<int,attrib> *m_neighbor_attributes; 121 std::map<int,int> m_multiedges; 122 void assign_defaults(); 123 void assign(const vertex &other); 124 public: 125 vertex(bool support_attributes=true); 126 vertex(const vertex &other); 127 vertex(const gen &lab,const attrib &attr); 128 ~vertex(); 129 vertex& operator =(const vertex &other); 130 gen label() const; supports_attributes()131 inline bool supports_attributes() const { return m_attributes!=NULL; } unsupport_attributes()132 inline void unsupport_attributes() { m_attributes=NULL; m_neighbor_attributes=NULL; } set_label(const gen & s)133 inline void set_label(const gen &s) { assert(supports_attributes()); (*m_attributes)[_GT_ATTRIB_LABEL]=s; } set_subgraph(int s)134 inline void set_subgraph(int s) { m_subgraph=s; } subgraph()135 inline int subgraph() const { return m_subgraph; } set_embedded(bool yes)136 inline void set_embedded(bool yes) { m_embedded=yes; } is_embedded()137 inline bool is_embedded() const { return m_embedded; } set_number(int n)138 inline void set_number(int n) { m_number=n; } number()139 inline int number() const { return m_number; } set_visited(bool yes)140 inline void set_visited(bool yes) { m_visited=yes; } is_visited()141 inline bool is_visited() const { return m_visited; } set_low(int l)142 inline void set_low(int l) { m_low=l; } low()143 inline int low() const { return m_low; } set_disc(int t)144 inline void set_disc(int t) { m_disc=t; } disc()145 inline int disc() const { return m_disc; } set_ancestor(int i)146 inline void set_ancestor(int i) { m_ancestor=i; } unset_ancestor()147 inline void unset_ancestor() { m_ancestor=-1; } ancestor()148 inline int ancestor() const { return m_ancestor; } set_color(int c)149 inline void set_color(int c) { m_color=c; } color()150 inline int color() const { return m_color; } attributes()151 inline const attrib &attributes() const { assert(supports_attributes()); return *m_attributes; } attributes()152 inline attrib &attributes() { assert(supports_attributes()); return *m_attributes; } set_attribute(int key,const gen & val)153 inline void set_attribute(int key,const gen &val) { assert(supports_attributes()); (*m_attributes)[key]=val; } set_attributes(const attrib & attr)154 inline void set_attributes(const attrib &attr) { assert(supports_attributes()); copy_attributes(attr,*m_attributes); } neighbors()155 inline const ivector &neighbors() const { return m_neighbors; } degree()156 inline int degree() const { return m_neighbors.size(); } 157 void add_neighbor(int i,const attrib &attr=attrib()); 158 bool is_temporary(int i) const; 159 attrib &neighbor_attributes(int i); 160 const attrib &neighbor_attributes(int i) const; has_neighbor(int i)161 inline bool has_neighbor(int i) const { return binary_search(m_neighbors.begin(),m_neighbors.end(),i); } 162 void remove_neighbor(int i); 163 inline void clear_neighbors(); 164 void incident_faces(ivector &F) const; add_edge_face(int nb,int f)165 inline void add_edge_face(int nb,int f) { assert(m_faces.find(nb)==m_faces.end()); m_faces[nb]=f+1; } clear_edge_faces()166 inline void clear_edge_faces() { m_faces.clear(); } edge_face(int nb)167 inline int edge_face(int nb) { return m_faces[nb]-1; } edge_faces()168 inline const std::map<int,int> &edge_faces() const { return m_faces; } 169 void set_multiedge(int v,int k); 170 int multiedges(int v) const; 171 int multiedge_count() const; clear_multiedges()172 inline void clear_multiedges() { m_multiedges.clear(); } has_multiedges()173 inline bool has_multiedges() const { return !m_multiedges.empty(); } 174 }; 175 176 class dotgraph { // temporary structure used in dot parsing 177 int m_index; 178 attrib vertex_attr,edge_attr,chain_attr; 179 ivector m_chain; 180 int pos; 181 public: 182 dotgraph(); 183 dotgraph(const dotgraph &other); 184 dotgraph(int i); 185 dotgraph& operator =(const dotgraph &other); 186 void assign(const dotgraph &other); index()187 inline int index() const { return m_index; } set_index(int i)188 inline void set_index(int i) { m_chain[pos]=i; } vertex_attributes()189 inline const attrib &vertex_attributes() const { return vertex_attr; } edge_attributes()190 inline const attrib &edge_attributes() const { return edge_attr; } chain_attributes()191 inline const attrib &chain_attributes() const { return chain_attr; } vertex_attributes()192 inline attrib &vertex_attributes() { return vertex_attr; } edge_attributes()193 inline attrib &edge_attributes() { return edge_attr; } chain_attributes()194 inline attrib &chain_attributes() { return chain_attr; } chain()195 inline const ivector &chain() const { return m_chain; } chain()196 inline ivector &chain() { return m_chain; } position()197 inline int position() const { return pos; } incr()198 inline void incr() { ++pos; if (int(m_chain.size())<=pos) m_chain.resize(pos+1,0); } clear_chain()199 inline void clear_chain() { pos=0; m_chain.resize(1); m_chain.front()=0; chain_attr.clear(); } chain_completed()200 inline bool chain_completed() { return m_chain.back()!=0; } chain_empty()201 inline bool chain_empty() { return pos==0 && m_chain.front()==0; } 202 }; 203 204 class walker { // tree node positioner 205 graphe *G; 206 layout *x; 207 double hsep,vsep; 208 ivectors levels; 209 ivector node_counters,gap_counters,position,prelim,modifier,gaps,children; 210 std::queue<int> placed; 211 int depth; 212 void walk(int i,int pass,int level=0,double modsum=0); 213 void process_level(int i); 214 public: 215 walker(graphe *gr,layout *ly,double hs,double vs); 216 void positioning(int apex); 217 }; 218 219 class circ_enum { // circuit enumeration in digraphs 220 graphe *G; 221 ivector point_stack; 222 std::stack<int> marked_stack; 223 ivectors A,res; 224 std::vector<bool> mark; 225 int s,lb,ub; 226 void backtrack(int v,bool &f); 227 public: 228 circ_enum(graphe *gr,int lo=-1,int hi=-1); 229 ivectors find_cycles(); 230 }; 231 232 #ifdef HAVE_LIBGLPK 233 class painter { // vertex painter 234 graphe *G; 235 ivectors values; 236 ipairs col2ij; 237 std::vector<bool> iscliq,fracts; 238 ivector cover_number,initially_colored,branch_candidates,temp_colors,ordering; 239 std::set<int> used_colors; 240 int lb,ub,maxiter,nxcols; 241 bool generate_clique_cuts; 242 glp_prob *mip; 243 double timeout,*heur,*row_coeffs,*best_coeffs; 244 int *row_indices,*best_indices; 245 void compute_bounds(const ivector &icol,int max_colors); 246 void make_values(); 247 void formulate_mip(); 248 void fixed_coloring(glp_tree *tree); 249 int assign_heur(glp_tree *tree); 250 void generate_rows(glp_tree *tree); 251 void add_row(glp_prob *prob,int len,int *indices,double *coeffs,double rh); 252 static void callback(glp_tree *tree,void *info); 253 public: painter(graphe * gr)254 painter(graphe *gr) { G=gr; } 255 int color_vertices(ivector &colors,const ivector &icol,int max_colors=0); 256 int select_branching_variable(glp_tree *tree); 257 void heur_solution(glp_tree *tree); 258 }; 259 260 class tsp { // traveling salesman 261 struct arc { 262 /* arc struct holds only the edge information relevant for TSP */ 263 int head; 264 int tail; 265 int sg_index; 266 }; 267 enum solution_status { 268 _GT_TSP_OPTIMAL, 269 _GT_TSP_NOT_HAMILTONIAN, 270 _GT_TSP_ERROR 271 }; 272 enum heuristic_type { 273 _GT_TSP_NO_HEUR = 0, 274 _GT_TSP_CHRISTOFIDES_SA = 1, 275 _GT_TSP_FARTHEST_INSERTION_HEUR = 2, 276 _GT_TSP_FARTHEST_INSERTION_RANDOM = 3 277 }; 278 graphe *G; // the graph 279 glp_prob *mip; // integer programming problem 280 bool isdirected; // true iff G is directed 281 bool isweighted; // true iff G is weighted 282 int sg; // current subgraph index 283 std::set<ivector> subtours; // subtours collected in during solving the last MIP 284 ivectors clustering_forest; // hierarchical clustering forest of subgraphs 285 ivector tour,old_sol; // a tour, old mip solution 286 double *coeff; // coefficients to be passed to MIP solver 287 int *indices; // indices of row entries to be passed to MIP solver 288 bool *visited; // used to mark vertices as visited 289 arc *arcs; // arcs of G 290 int *sg_vertices; // list of sg_nv vertices of subgraph with index sg 291 int *sg_edges; // indices of edges belonging to the subgraph with index sg 292 int sg_nv; // number of vertices in subgraph with index sg 293 int sg_ne; // number of edges in subgraph with index sg 294 int nv; // total number of vertices 295 int ne; // total number of edges 296 int heur_type; // the type of heuristic to be applied 297 bool is_undir_weighted; // true iff G is undirected and weighted 298 bool is_symmetric_tsp; // true if G is undirected weighted clique 299 int num_nodes; // counting the hierarhical clustering forest nodes 300 solution_status status; // status of the solution 301 std::map<int,std::map<int,double> > weight_map; 302 std::map<int,std::map<int,double> > rlx_sol_map; 303 std::map<int,std::map<int,int> > loc_map; 304 dvector xev; 305 dvector obj; 306 std::vector<bool> can_branch; 307 void formulate_mip(); 308 bool get_subtours(); 309 void add_subtours(const ivectors &sv); 310 void lift_subtours(ivectors &sv) const; 311 bool find_subgraph_subtours(ivectors &sv,solution_status &status); 312 bool subtours_equal(const ivector &st1,const ivector &st2); 313 ivector canonical_subtour(const ivector &subtour); 314 void append_sce(const ivector &subtour); 315 void make_hierarchical_clustering_forest(); 316 void hierarchical_clustering_dfs(int i,ivectors &considered_sec,ivectors &relevant_sec); 317 ipair make_edge(int i,int j) const; 318 void make_sg_edges(); 319 int edge_index(const ipair &e); 320 int vertex_index(int i); 321 double weight(int i,int j); weight(const ipair & e)322 double weight(const ipair &e) { return weight(e.first,e.second); } 323 double lower_bound(); 324 void perform_3opt_moves(ivector &hc); 325 void straighten(ivector &hc); 326 bool is_move_feasible(int k,const ivector &t,const ipairs &x); 327 void lin_kernighan(ivector &hc); 328 bool make_3opt_moves(ivector &hc); 329 void improve_tour(ivector &hc); 330 void farthest_insertion(int index,ivector &hc); 331 void christofides(ivector &hc); 332 static void sample_mean_stddev(const dvector &sample,double &mean,double &stddev); 333 void min_weight_matching_bipartite(const ivector &eind,const dvector &weights,ivector &matched_arcs); 334 void select_branching_variable(glp_tree *tree); 335 void rowgen(glp_tree *tree); 336 void heur(glp_tree *tree); 337 static void callback(glp_tree *tree,void *info); 338 void min_wpm_heur(glp_tree *tree,const ivector &eind); 339 static void min_wpm_callback(glp_tree *tree,void *info); 340 /* min-cut routines, originally written by Andrew Makhorin (<mao@gnu.org>) */ 341 ivectors mincut_data; 342 int max_flow(int nn,int nedg,const ivector &beg, 343 const ivector &end,const ivector &cap,int s,int t, 344 ivector &x); 345 int min_st_cut(int nn, int nedg,const ivector &beg, 346 const ivector &end,const ivector &cap,int s,int t, 347 const ivector &x,ivector &cut); 348 int minimal_cut(int nn,int nedg,const ivector &beg, 349 const ivector &end,const ivector &cap,ivector &cut); 350 public: 351 tsp(graphe *gr); 352 ~tsp(); 353 int solve(ivector &hc,double &cost); 354 double approx(ivector &hc); 355 double tour_cost(const ivector &hc); 356 }; 357 358 class atsp { // asymmetric traveling salesman problem 359 graphe *G; 360 glp_prob *mip; 361 ipairs mia; // must include arcs 362 ivectors ft; // forbidden tours 363 bool isweighted; 364 void formulate_mip(); 365 public: 366 atsp(graphe *gr,const ipairs &must_include_arcs); 367 ~atsp(); 368 bool solve(ivector &hc,double &cost); // find shortest tour 369 void ksolve(int k,ivectors &hcv,dvector &costs); // find k shortest tours 370 }; 371 #endif 372 373 class rectangle { // simple rectangle class 374 double m_x,m_y,m_width,m_height; 375 bool m_locked_above,m_locked_right; 376 layout *L; 377 public: 378 struct comparator { operatorcomparator379 bool operator()(const rectangle &r1,const rectangle &r2) const { 380 return r1.height()>r2.height(); 381 } 382 }; 383 rectangle(); 384 rectangle(double X,double Y,double W,double H,layout *ly=NULL); 385 rectangle(const rectangle &rect); 386 rectangle& operator =(const rectangle &other); 387 void assign(const rectangle &other); set_anchor(double x,double y)388 inline void set_anchor(double x,double y) { m_x=x; m_y=y; } x()389 inline double x() const { return m_x; } y()390 inline double y() const { return m_y; } width()391 inline double width() const { return m_width; } height()392 inline double height() const { return m_height; } set_locked_above(bool yes)393 inline void set_locked_above(bool yes) { m_locked_above=yes; } set_locked_right(bool yes)394 inline void set_locked_right(bool yes) { m_locked_right=yes; } is_locked_above()395 inline bool is_locked_above() const { return m_locked_above; } is_locked_right()396 inline bool is_locked_right() const { return m_locked_right; } 397 bool intersects(const rectangle &other) const; 398 bool intersects(const std::vector<rectangle> &rectangles) const; 399 bool intersects(std::vector<rectangle>::const_iterator first,std::vector<rectangle>::const_iterator last) const; get_layout()400 layout *get_layout() const { return L; } 401 }; 402 403 class cpol { 404 void assign(const cpol &other); 405 public: 406 int nv; 407 #if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H 408 ulong *cg; 409 int *col; 410 #else 411 int *adj; 412 #endif 413 size_t sz; 414 int frq; 415 intpoly poly; 416 #if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H cpol()417 cpol() { nv=0; cg=NULL; col=NULL; sz=0; frq=0; } 418 #else cpol()419 cpol() { nv=0; adj=NULL; sz=0; frq=0; } 420 #endif 421 #if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H 422 cpol(int n,ulong *g,int *c,size_t s,const intpoly &p); 423 #else 424 cpol(int n,int *a,size_t s,const intpoly &p); 425 #endif 426 cpol(const cpol &other); ~cpol()427 ~cpol() { } 428 cpol& operator =(const cpol &other); 429 #if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H 430 bool match(int n,ulong *g,int *c) const; 431 #else 432 bool match(int n,int *a,int adj_sz) const; 433 #endif 434 }; 435 436 class ransampl { // random sampling from a given degree distribution 437 int n; 438 vecteur prob; 439 ivector alias; 440 const context *ctx; 441 public: 442 ransampl(const vecteur &p,GIAC_CONTEXT); 443 gen data() const; 444 int generate() const; 445 }; 446 447 class bucketsampler { // random sampling from a dynamic distribution 448 const context *ctx; 449 ivector weights; 450 long total_weight; 451 std::map<int,int> max_weight,level_weight; 452 std::map<int,ivector> levels; 453 ipairs positions; nearest_pow2(double a)454 inline int nearest_pow2(double a) { return std::floor(0.5+std::log(a)/M_LN2); } 455 public: 456 bucketsampler(const ivector &W,GIAC_CONTEXT); 457 int generate(); 458 void insert(int w); 459 void update(int i,int w); increment(int i)460 inline void increment(int i) { update(i,weights[i]+1); } 461 }; 462 463 class unionfind { // disjoint-set data structure 464 struct element { 465 int id,parent,rank; elementelement466 element() { id=-1; } 467 }; 468 int sz; 469 element *elements; 470 public: unionfind(int n)471 unionfind(int n) { sz=n; elements=new element[n]; } ~unionfind()472 ~unionfind() { delete[] elements; } 473 void make_set(int id); 474 bool is_stored(int id); 475 int find(int id); 476 void unite(int id1,int id2); 477 }; 478 479 class ostergard { // clique maximizer 480 graphe *G; 481 int maxsize; 482 bool found; 483 double timeout; // seconds 484 ivector c,incumbent,clique_nodes; 485 clock_t start; 486 bool timed_out; 487 void recurse(ivector &U,int size,ivector &position); 488 public: 489 ostergard(graphe *gr,double max_time=0) { G=gr; timeout=max_time; } 490 int maxclique(ivector &clique); 491 }; 492 493 class yen { // Yen's k shortest paths algorithm 494 typedef struct tree_node { 495 int i; 496 bool selected; 497 tree_node *parent; 498 std::vector<tree_node*> children; 499 } tree_node; 500 struct kspaths_comparator { operatorkspaths_comparator501 bool operator()(const std::pair<gen,tree_node*> &a,const std::pair<gen,tree_node*> &b) { 502 if (is_zero(a.first-b.first)) 503 return a.second<b.second; 504 return is_strictly_greater(b.first,a.first,context0); 505 } 506 }; 507 graphe *G; 508 tree_node *root; 509 int src, dest, K; 510 std::vector<tree_node*> kspaths; 511 tree_node *add_tree_node(tree_node *p); 512 tree_node *store_path(const ivector &path,tree_node *r); 513 void select_path(tree_node *p); 514 void restore_path(tree_node *p,ivector &path); 515 void delete_children(tree_node *r); 516 public: yen(graphe * gr,int s,int d,int k)517 yen(graphe *gr,int s,int d,int k) { G=gr; src=s; dest=d; K=k; root=NULL; } 518 ~yen(); 519 void find_kspaths(ivectors &paths); 520 }; 521 522 struct edges_comparator { // for sorting edges by their weight 523 graphe *G; operatoredges_comparator524 bool operator()(const ipair &a,const ipair &b) { 525 return is_strictly_greater(G->weight(b),G->weight(a),G->giac_context()); 526 } edges_comparatoredges_comparator527 edges_comparator(graphe *gr) { G=gr; } 528 }; 529 530 struct ivectors_comparator { // for sorting ivectors by their length operatorivectors_comparator531 bool operator()(const ivector &a,const ivector &b) { 532 return a.size()<b.size(); 533 } 534 }; 535 536 struct degree_comparator { // for sorting vertices by their degrees 537 graphe *G; 538 bool asc; operatordegree_comparator539 bool operator()(int v,int w) { 540 return (asc && G->degree(v)<G->degree(w)) || 541 (!asc && G->degree(v)>G->degree(w)); 542 } 543 degree_comparator(graphe *gr,bool ascending=true) { G=gr; asc=ascending; } 544 }; 545 546 struct ivectors_degree_comparator { // for sorting sets of vertices by ascending total degree 547 graphe *G; operatorivectors_degree_comparator548 bool operator()(const ivector &a,const ivector &b) { 549 int deg_a,deg_b; 550 for (ivector_iter it=a.begin();it!=a.end();++it) { 551 deg_a+=G->degree(*it); 552 } 553 for (ivector_iter it=b.begin();it!=b.end();++it) { 554 deg_b+=G->degree(*it); 555 } 556 return deg_a*b.size()>=deg_b*a.size(); 557 } ivectors_degree_comparatorivectors_degree_comparator558 ivectors_degree_comparator(graphe *gr) { G=gr; } 559 }; 560 561 typedef std::vector<vertex>::const_iterator node_iter; 562 typedef std::map<int,attrib>::const_iterator neighbor_iter; 563 typedef attrib::const_iterator attrib_iter; 564 typedef std::vector<point>::const_iterator layout_iter; 565 typedef ivector::const_iterator ivector_iter; 566 typedef ivectors::const_iterator ivectors_iter; 567 typedef ipairs::const_iterator ipairs_iter; 568 typedef edgeset::const_iterator edgeset_iter; 569 typedef intpoly::const_iterator intpoly_iter; 570 typedef dvector::const_iterator dvector_iter; 571 typedef iset::const_iterator iset_iter; 572 573 static const gen FAUX; 574 static const gen VRAI; 575 static bool verbose; 576 static int default_vertex_color; 577 static int default_edge_color; 578 static int default_vertex_label_color; 579 static int default_highlighted_edge_color; 580 static int default_highlighted_vertex_color; 581 static int default_edge_width; 582 static int bold_edge_width; 583 static std::map<ivector,std::vector<cpol> > cache; 584 // special graphs 585 static const int clebsch_graph[]; 586 static const char* coxeter_graph[]; 587 static const int dodecahedron_graph[]; 588 static const int dyck_graph[]; 589 static const int grinberg_graph[]; 590 static const int grotzsch_graph[]; 591 static const int harries_graph_lcf[]; 592 static const int harries_wong_graph_lcf[]; 593 static const int balaban_10cage_lcf[]; 594 static const int balaban_11cage_lcf[]; 595 static const int heawood_graph[]; 596 static const int herschel_graph[]; 597 static const int mcgee_graph[]; 598 static const int pappus_graph[]; 599 static const int robertson_graph[]; 600 static const int soccer_ball_graph[]; 601 static const int tetrahedron_graph[]; 602 static const int octahedron_graph[]; 603 static const int icosahedron_graph[]; 604 static const int ljubljana_graph_lcf[]; 605 static const int foster_graph_lcf[]; 606 static const int blanusa_graph[]; 607 static const int bidiakis_cube_graph_lcf[]; 608 static const int bull_graph[]; 609 static const int butterfly_graph[]; 610 static const int diamond_graph[]; 611 static const int chvatal_graph[]; 612 static const int franklin_graph_lcf[]; 613 static const int frucht_graph_lcf[]; 614 static const int biggs_smith_graph_lcf[]; 615 static const int moser_spindle_graph[]; 616 static const int errera_graph[]; 617 static const int goldner_harary_graph[]; 618 static const int golomb_graph[]; 619 static const int hoffman_graph_matrix[8][8]; 620 static const int poussin_graph[]; 621 static const int wagner_graph[]; 622 static const int folkman_graph_lcf[]; 623 static const int gray_graph_lcf[]; 624 static const int tutte_12cage_lcf[]; 625 static const int tutte_8cage_lcf[]; 626 static const int f26a_graph_lcf[]; 627 static const int tietze_graph[]; 628 static const int tutte_fragment_graph[]; 629 630 private: 631 const context *ctx; 632 std::vector<vertex> nodes; 633 attrib attributes; 634 std::vector<std::string> user_tags; 635 ivector marked_nodes; 636 int disc_time; 637 ivector disc_nodes; 638 std::stack<ipair> edge_stack; 639 std::stack<int> node_stack; 640 std::queue<int> node_queue; 641 ivectors visited_edges; 642 ivectors maxcliques; 643 std::stack<ivector> saved_subgraphs; 644 bool m_supports_attributes; 645 void clear_node_stack(); 646 void clear_node_queue(); 647 void message(const char *str) const; 648 void message(const char *format,int a) const; 649 void message(const char *format,int a,int b) const; 650 void message(const char *format,int a,int b,int c) const; 651 std::string giac_version() const; node(int i)652 inline vertex &node(int i) { return nodes[i]; } 653 bool dot_parse_attributes(std::ifstream &dotfile,attrib &attr); 654 static bool insert_attribute(attrib &attr,int key,const gen &val,bool overwrite=true); 655 static bool remove_attribute(attrib &attr,int key); 656 static bool genmap2attrib(const gen_map &m,attrib &attr); 657 static void attrib2genmap(const attrib &attr,gen_map &m); 658 static void copy_attributes(const attrib &src,attrib &dest); 659 void write_attrib(std::ofstream &dotfile,const attrib &attr) const; 660 static ivector_iter binsearch(ivector_iter first,ivector_iter last,int a); 661 static size_t sets_union(const iset &A,const iset &B,iset &U); 662 static size_t sets_intersection(const iset &A,const iset &B,iset &I); 663 static size_t sets_intersection(const ivector &A,const iset &B,iset &I); 664 static size_t sets_difference(const iset &A,const iset &B,iset &D); 665 static size_t sets_difference(const iset &A,const ivector &B,iset &D); make_point(double x,double y)666 static point make_point(double x,double y) { point p(2,x); p.back()=y; return p; } make_point(double x,double y,double z)667 static point make_point(double x,double y,double z) { point p(3,x); p[1]=y; p.back()=z; return p; } 668 static void add_point(point &a,const point &b); 669 static void subtract_point(point &a,const point &b); 670 static void scale_point(point &p,double s); 671 static double point_vecprod2d(const point &v,const point &w); 672 static double point_dotprod(const point &p,const point &q); 673 static void clear_point_coords(point &p); 674 static double point_displacement(const point &p,bool sqroot=true); 675 static double point_distance(const point &p,const point &q,point &pq); 676 static void point_mirror(double a,double b,double c,const point &src,point &dest); 677 static void point_lincomb(const point &p,const point &q,double d1,double d2,point &res); 678 static void copy_point(const point &src,point &dest); 679 void rand_point(point &p,double radius=1.0); 680 static vecteur point2vecteur(const point &p); 681 static bool points_coincide(const point &p,const point &q,double tol); 682 static void copy_layout(const layout &src,layout &dest); 683 static void rotate_layout(layout &x,double phi); 684 static double layout_min(const layout &x,int d); 685 static double layout_diameter(const layout &x); 686 static void point2polar(point &p,double &r,double &phi); 687 static bool sparse_matrix_element(const sparsemat &A,int i,int j,ipair &val); 688 static void multiply_sparse_matrices(const sparsemat &A,const sparsemat &B,sparsemat &P,int ncols,bool symmetric=false); 689 static void transpose_sparsemat(const sparsemat &A,sparsemat &T); 690 void multilevel_recursion(layout &x,int d,double R,double K,double tol,int depth=0); 691 int mdeg(const ivector &V,int i) const; 692 void coarsening(graphe &G,const sparsemat &P,const ivector &V) const; 693 void tomita(iset &R,iset &P,iset &X,std::map<int,int> &m,int mode=0); 694 int cp_maxclique(ivector &clique); 695 void cp_recurse(ivector &C,ivector &P,ivector &incumbent); 696 int ost_maxclique(ivector &clique); 697 void ost_recursive(ivector &U,int size,int &maxsize,ivector &incumbent,bool &found); 698 void find_cut_vertices_dfs(int i,std::set<int> &ap,int sg); 699 void find_blocks_dfs(int i,std::vector<ipairs> &blocks,int sg); 700 void find_bridges_dfs(int i,ipairs &B,int sg); 701 int find_cycle_dfs(int i,int sg); 702 bool find_path_dfs(int dest,int i,int sg,bool skip_embedded); 703 static void sort_rectangles(std::vector<rectangle> &rectangles); 704 static bool embed_rectangles(std::vector<rectangle> &rectangles,double maxheight); 705 static bool segments_crossing(const point &p,const point &r,const point &q,const point &s,point &crossing); 706 static bool point2segment_projection(const point &p,const point &q,const point &r,point &proj); 707 void force_directed_placement(layout &x,double K,double R=DBL_MAX,double tol=0.01,bool ac=true); 708 static bool get_node_position(const attrib &attr,point &p); 709 void coarsening_mis(const ivector &V,graphe &G,sparsemat &P) const; 710 void coarsening_ec(const ipairs &M,graphe &G,sparsemat &P) const; 711 int best_quadrant(const point &p,const layout &x) const; 712 void append_segment(vecteur &drawing, const point &p,const point &q,int color,int width,int style,bool arrow=false) const; 713 void append_node(vecteur &drawing,const point &p,int color,int width,int shape) const; 714 void append_label(vecteur &drawing,const point &p,const gen &label,int quadrant,int color=_BLACK) const; 715 static int face_has_edge(const ivector &face,int i,int j); 716 int first_neighbor_from_subgraph(const vertex &v,int sg) const; 717 void set_nodes_embedded(const ivector &v,bool yes=true); 718 void unembed_all_nodes(); 719 int planar_embedding(ivectors &faces); 720 void set_embedding(const ivectors &faces); 721 void clear_embedding(); 722 int choose_embedding_face(const ivectors &faces,int v); 723 int choose_outer_face(const ivectors &faces); 724 static void make_regular_polygon_layout(layout &x,const ivector &v,double R=1.0,double elongate=0.0); 725 bool edges_crossing(const ipair &e1,const ipair &e2,const layout &x,point &crossing) const; 726 static void build_block_tree(int i,ivectors &blocks); 727 static int common_element(const ivector &v1,const ivector &v2,int offset=0); 728 void embed_children_blocks(int i,ivectors &block_tree,std::vector<ivectors> &blocks_faces); 729 void periphericity(const ivector &outer_face,ivector &p); 730 void tree_height_dfs(int i,int level,int &depth); 731 void make_product_nodes(const graphe &G,graphe &P) const; 732 static void extract_path_from_cycle(const ivector &cycle,int i,int j,ivector &path); 733 static void generate_nk_sets(int n,int k,std::vector<ulong> &v); 734 void strongconnect_dfs(ivectors &components,std::vector<bool> &onstack,int i,int sg); 735 bool degrees_equal(const ivector &v,int deg=0) const; 736 void lca_recursion(int u,const ipairs &p,ivector &lca_recursion,unionfind &ds); 737 void st_numbering_dfs(int i,ivector &preorder); 738 void rdfs(int i,ivector &d,bool rec,int sg,bool skip_embedded); 739 bool is_descendant(int v,int anc) const; 740 static int pred(int i,int n); 741 static int succ(int i,int n); 742 static void arc_path(int i,int j,const ivector &cycle,ivector &path); 743 void fold_face(const ivector &face,bool subdivide,int &label); 744 void find_chords(const ivector &face,ipairs &chords); 745 void augment(const ivectors &faces,int outer_face,bool subdivide=false); 746 int saturation_degree(const vertex &v,std::set<int> &colors) const; 747 int uncolored_degree(const vertex &v) const; 748 bool is_partially_colored() const; 749 void remove_maximal_clique(iset &V) const; 750 bool bipartite_matching_bfs(ivector &dist); 751 bool bipartite_matching_dfs(int u,ivector &dist); 752 static ipair forest_root_info(const ivector &forest,int v); 753 static gen make_colon_label(const ivector &v); 754 void simplify(graphe &G,bool color_temp_vertices=false) const; 755 intpoly tutte_poly_recurse(int vc); 756 static void poly_mult(intpoly &a,const intpoly &b); 757 static void poly_add(intpoly &a,const intpoly &b); 758 static intpoly poly_geom(int var,int k,bool leading_one,bool add_other_var=false); 759 static intpoly poly_one(); 760 static gen intpoly2gen(const intpoly &v,const gen &x,const gen &y); 761 void sharc_order(); 762 static void compute_rutcounts(int n,vecteur &t); 763 void ranrut(int n,ivector &tree,const vecteur &pt); 764 void ranrut_forest(int m,ivectors &trees,const vecteur &alpha,const vecteur &a); 765 void insert_tree(const ivector &tree,int root); 766 static ipair rat2ipair(const gen &r); 767 static gen ipair2rat(const ipair &p); 768 void save_subgraphs(); 769 void restore_subgraphs(); 770 int vertex_pair_connectivity(int v,int w); harmonic_mean_exact(gen a,gen b,gen c)771 static inline gen harmonic_mean_exact(gen a,gen b,gen c) { return 3*a*b*c/(a*b+b*c+a*c); } harmonic_mean(double a,double b,double c)772 static inline double harmonic_mean(double a,double b,double c) { return 3.0*a*b*c/(a*b+b*c+a*c); } 773 void strec(int i,int t,int counter,int np,iset &Q,vecteur ×tamp,vecteur &l); 774 bool hamcycle_recurse(ivector &path,int pos); 775 776 public: 777 graphe(const context *contextptr=context0,bool support_attributes=true); 778 graphe(const graphe &G); 779 graphe(const std::string &name,const context *contextptr=context0); rand_integer(int n)780 inline int rand_integer(int n) const { assert(n>=0); return n==0?0:giac::giac_rand(ctx)%n; } rand_uniform()781 inline double rand_uniform() const { return giac::giac_rand(ctx)/(RAND_MAX+1.0); } rand_normal()782 inline double rand_normal() const { return giac::randNorm(ctx); } 783 ivector rand_permu(int n) const; 784 static bool is_real_number(const gen &g); 785 static gen to_binary(int number,int chars); giac_context()786 inline const context *giac_context() const { return ctx; } 787 static gen make_idnt(const char* name,int index=-1,bool intern=true); 788 void make_default_labels(vecteur &labels,int n,int n0=0,int offset=-1) const; 789 bool labels2iset(const vecteur &labels,iset &s); boole(bool b)790 static gen boole(bool b) { return b?VRAI:FAUX; } 791 static gen word2gen(const std::string &word); 792 static gen str2gen(const std::string &str,bool isstring=false); 793 static std::string genstring2str(const gen &g); 794 static std::string gen2str(const gen &g); 795 static gen plusinf(); 796 void ivectors2vecteur(const ivectors &v,vecteur &res,bool sort_all=false) const; reserve_nodes(int n)797 inline void reserve_nodes(int n) { assert(nodes.empty()); nodes.reserve(n); } 798 bool read_gen(const gen &g); 799 void read_special(const int *special_graph); 800 void read_special(const char **special_graph); 801 void copy(graphe &G) const; 802 inline void copy_nodes(const std::vector<vertex> &V); supports_attributes()803 inline bool supports_attributes() const { return m_supports_attributes; } 804 void clear(); clear_maximal_cliques()805 void clear_maximal_cliques() { maxcliques.clear(); } 806 void find_maximal_cliques(); maximal_cliques()807 const ivectors &maximal_cliques() const { return maxcliques; } 808 int tag2index(const std::string &tag); 809 std::string index2tag(int index) const; 810 int register_user_tag(const std::string &tag); 811 void register_user_tags(const std::vector<std::string> &tags); get_marked_nodes()812 inline const ivector &get_marked_nodes() const { return marked_nodes; } 813 void get_marked_nodes(vecteur &V) const; 814 void get_marked_nodes_in_subgraph(int s,ivector &m) const; copy_marked_nodes(const ivector & mv)815 inline void copy_marked_nodes(const ivector &mv) { marked_nodes=ivector(mv.begin(),mv.end()); } 816 void mark_node(int v); mark_node(const gen & v)817 void mark_node(const gen &v) { mark_node(node_index(v)); } 818 bool unmark_node(int v); unmark_node(const gen & v)819 inline bool unmark_node(const gen &v) { return unmark_node(node_index(v)); } unmark_all_nodes()820 inline void unmark_all_nodes() { marked_nodes.clear(); } sort_marked_nodes()821 inline void sort_marked_nodes() { std::sort(marked_nodes.begin(),marked_nodes.end()); } 822 void set_edge_visited(int i,int j); set_edge_visited(const ipair & e)823 inline void set_edge_visited(const ipair &e) { set_edge_visited(e.first,e.second); } 824 bool is_edge_visited(int i,int j) const; is_edge_visited(const ipair & e)825 inline bool is_edge_visited(const ipair &e) const { return is_edge_visited(e.first,e.second); } unvisit_all_edges()826 inline void unvisit_all_edges() { visited_edges.clear(); } 827 gen to_gen(); 828 int *to_array(int &sz,bool reduce=false) const; 829 bool write_latex(const std::string &filename,const gen &drawing) const; 830 bool write_dot(const std::string &filename) const; 831 bool read_dot(const std::string &filename); is_null()832 inline bool is_null() const { return nodes.empty(); } 833 bool is_empty() const; 834 void weight_matrix(matrice &W) const; 835 gen weight(int i,int j) const; weight(const ipair & edge)836 inline gen weight(const ipair &edge) const { return weight(edge.first,edge.second); } 837 int edge_count(int sg=-1) const; node_count()838 inline int node_count() const { return nodes.size(); } 839 vecteur vertices(int sg=-1) const; 840 void unvisit_all_nodes(int sg=-1); 841 void unset_all_ancestors(int sg=-1); 842 void uncolor_all_nodes(int base_color=0,int sg=-1); set_node_color(int i,int c)843 void set_node_color(int i,int c) { node(i).set_color(c); } 844 void dfs(int root,bool rec=true,bool clr=true,ivector *D=NULL,int sg=-1,bool skip_embedded=false); 845 void bfs(int root,bool rec=true,bool clr=true,ivector *D=NULL,int sg=-1,bool skip_embedded=false); get_discovered_nodes()846 inline const ivector &get_discovered_nodes() const { return disc_nodes; } 847 bool is_connected(int sg=-1); 848 bool is_biconnected(int sg=-1); 849 bool is_triconnected(int sg=-1); 850 bool is_cycle(ipairs &E,int sg=-1); 851 void adjacent_nodes(int i,ivector &adj,bool include_temp_edges=true) const; 852 void get_edges_as_pairs(ipairs &E,int sg=-1) const; 853 vecteur edges(bool include_weights,int sg=-1) const; 854 ivector edge_multiplicities() const; 855 int sum_of_edge_multiplicities() const; 856 int add_node(); 857 int add_node(const gen &v,const attrib &attr=attrib()); 858 void add_nodes(const vecteur &v); 859 void add_nodes(int n); 860 void add_unlabeled_nodes(int n); 861 void remove_isolated_nodes(const iset &I,graphe &G); 862 void isolate_nodes(const iset &V); node(int i)863 inline const vertex &node(int i) const { return nodes[i]; } node_label(int i)864 inline const gen node_label(int i) const { assert(i>=0 && i<node_count()); return nodes[i].label(); } 865 vecteur get_node_labels(const ivector &v) const; 866 int node_index(const gen &v) const; 867 int edge_index(const ipair &e) const; 868 int largest_integer_label() const; 869 void set_subgraph(const ivector &v,int s); 870 void set_subgraph(const ipairs &e,int s); 871 void get_subgraph(int sg,ivector &v) const; 872 int subgraph_size(int sg) const; 873 int first_vertex_from_subgraph(int sg) const; 874 void merge_subgraphs(int s,int t); 875 void unset_subgraphs(int default_sg=-1); 876 int max_subgraph_index() const; graph_attributes()877 inline const attrib &graph_attributes() const { return attributes; } 878 const attrib &node_attributes(int i) const; 879 const attrib &edge_attributes(int i,int j) const; 880 attrib &edge_attributes(int i,int j); edge_attributes(const ipair & e)881 inline const attrib &edge_attributes(const ipair &e) const { return edge_attributes(e.first,e.second); } edge_attributes(const ipair & e)882 inline attrib &edge_attributes(const ipair &e) { return edge_attributes(e.first,e.second); } 883 void attrib2vecteurs(const attrib &attr,vecteur &tags,vecteur &values) const; 884 void add_edge(int i,int j,const gen &w=gen(1)); 885 void add_edge(int i,int j,const attrib &attr); add_edge(const ipair & edge)886 inline void add_edge(const ipair &edge) { add_edge(edge.first,edge.second); } add_edge(const ipair & edge,const attrib & attr)887 inline void add_edge(const ipair &edge,const attrib &attr) { add_edge(edge.first,edge.second,attr); } 888 ipair add_edge(const gen &v,const gen &w,const gen &weight=gen(1)); 889 ipair add_edge(const gen &v,const gen &w,const attrib &attr); 890 void add_temporary_edge(int i,int j); 891 bool is_temporary_edge(int i,int j) const; 892 void remove_temporary_edges(); 893 bool remove_edge(int i,int j); remove_edge(const ipair & p)894 inline bool remove_edge(const ipair &p) { return remove_edge(p.first,p.second); } 895 bool has_edge(int i,int j,int sg=-1) const; 896 inline bool has_edge(const ipair &p,int sg=-1) const { return has_edge(p.first,p.second,sg); } 897 ipair make_edge(const vecteur &v) const; 898 bool edges2ipairs(const vecteur &E,ipairs &ev,bool ¬found) const; 899 vecteur ipairs2edges(const ipairs &E) const; 900 static void ipairs2edgeset(const ipairs &E,edgeset &Eset); 901 bool nodes_are_adjacent(int i,int j) const; 902 int in_degree(int index,int sg=-1) const; 903 int out_degree(int index,int sg=-1) const; 904 int degree(int index,int sg=-1) const; 905 int maximum_degree() const; 906 int minimum_degree() const; 907 int average_degree() const; 908 vecteur degree_sequence(int sg=-1) const; 909 void sort_by_degrees(); 910 void adjacency_matrix(matrice &m) const; 911 void adjacency_sparse_matrix(sparsemat &sm) const; 912 void laplacian_matrix(matrice &m,bool normalize=false) const; 913 void incidence_matrix(matrice &m) const; set_graph_attribute(int key,const gen & val)914 inline void set_graph_attribute(int key,const gen &val) { attributes[key]=val; } set_graph_attributes(const attrib & attr)915 inline void set_graph_attributes(const attrib &attr) { copy_attributes(attr,attributes); } 916 void set_node_attribute(int index,int key,const gen &val); 917 void set_edge_attribute(int i,int j,int key,const gen &val); 918 bool get_graph_attribute(int key,gen &val) const; 919 bool get_node_attribute(int i,int key,gen &val) const; 920 bool get_edge_attribute(int i,int j,int key,gen &val) const; 921 void discard_graph_attribute(int key); 922 void discard_node_attribute(int i,int key); 923 void discard_edge_attribute(int i,int j,int key); set_name(const std::string & str)924 inline void set_name(const std::string &str) { set_graph_attribute(_GT_ATTRIB_NAME,str2gen(str,true)); } name()925 inline std::string name() const { gen s; if (get_graph_attribute(_GT_ATTRIB_NAME,s)) return genstring2str(s); else return ""; } 926 bool is_directed() const; 927 bool is_weighted() const; set_directed(bool yes)928 inline void set_directed(bool yes) { set_graph_attribute(_GT_ATTRIB_DIRECTED,boole(yes)); } set_weighted(bool yes)929 inline void set_weighted(bool yes) { set_graph_attribute(_GT_ATTRIB_WEIGHTED,boole(yes)); } 930 void make_weighted(const matrice &m); make_directed()931 void make_directed() { set_directed(true); } 932 void make_unweighted(); 933 void randomize_edge_weights(double a,double b,bool integral_weights=false); 934 int is_regular(int d) const; 935 bool is_strongly_regular(ipair &sig); 936 bool is_equal(const graphe &G) const; 937 void underlying(graphe &G) const; 938 void complement(graphe &G) const; 939 bool isomorphic_copy(graphe &G,const ivector &sigma,bool strip_attributes=false); 940 bool relabel_nodes(const vecteur &labels); 941 void induce_subgraph(const ivector &vi,graphe &G) const; 942 void extract_subgraph(const ipairs &E,graphe &G) const; 943 bool is_subgraph(const graphe &G) const; 944 void maximal_independent_set(ivector &ind) const; 945 void find_maximum_matching(ipairs &M); 946 void find_maximal_matching(ipairs &matching) const; 947 bool find_augmenting_path(ivector &ap,std::map<int,int> &matching); 948 bool trail(const vecteur &v); 949 bool demoucron(ivectors &faces,int sg=-1); 950 void create_random_layout(layout &x,int dim); 951 void make_spring_layout(layout &x,int d,double tol=0.001); 952 void make_circular_layout(layout &x,const ivector &hull,double A=0,double tol=0.005,double elongate=0.0); 953 void make_tutte_layout(layout &x,const ivector &outer_face); 954 bool make_planar_layout(layout &x); 955 void make_tree_layout(layout &x,double sep,int apex=0); 956 void make_bipartite_layout(layout &x,const ivector &p1,const ivector &p2); 957 void layout_best_rotation(layout &x); 958 static rectangle layout_bounding_rect(layout &ly,double padding=0); 959 static void pack_rectangles(std::vector<rectangle> &rectangles); 960 static gen point2gen(const point &p,bool vect=false); 961 static bool gen2point(const gen &g,point &p); 962 static point layout_center(const layout &x); 963 static void scale_layout(layout &x,double diam); is_tree()964 inline bool is_tree() { return !is_directed() && edge_count()+1==node_count() && is_connected(); } 965 bool is_forest(); 966 bool is_tournament() const; 967 bool is_planar(); 968 bool is_clique(int sg=-1) const; 969 gen triangle_count(ivectors *dest=NULL,bool ccoeff=false,bool exact=true); 970 int tree_height(int root); 971 void clique_stats(std::map<int,int> &m,int mode=0); 972 int maximum_clique(ivector &clique); 973 void greedy_neighborhood_clique_cover_numbers(ivector &cover_numbers); 974 bool clique_cover(ivectors &cover,int k=0); 975 int maximum_independent_set(ivector &v) const; 976 int girth(bool odd=false,int sg=-1); 977 bool hakimi(const ivector &L); 978 void erdos_renyi(double p); 979 void preferential_attachment(int d,int o); 980 void molloy_reed(const vecteur &p); 981 void make_plane_dual(const ivectors &faces); 982 void make_lcf_graph(const ivector &jumps,int e); 983 void make_lcf_graph(const int *j,int e); 984 void make_sierpinski_graph(int n,int k,bool triangle); 985 void make_shrikhande_graph(); 986 void make_tutte_graph(); 987 void make_complete_graph(); 988 void make_complete_multipartite_graph(const ivector &partition_sizes,layout *x=NULL); 989 void make_petersen_graph(int n,int k,layout *x=NULL); 990 bool make_kneser_graph(int n,int k); 991 void make_path_graph(); 992 void make_cycle_graph(); 993 void make_grid_graph(int m,int n,bool torus=false); 994 void make_web_graph(int n,int m,layout *x=NULL); 995 void make_wheel_graph(int n,layout *x=NULL); 996 void make_antiprism_graph(int n,layout *x=NULL); 997 void make_complete_kary_tree(int k,int d); 998 void make_random_tree(int maxd=0); 999 void make_random_rooted_tree(); 1000 void make_random_free_tree(); 1001 void make_random_planar(double p,int connectivity); 1002 void make_random_sequential(const ivector &d); 1003 void make_random_bipartite(int a,int b,double p); 1004 void make_random_regular(int d,bool connected); 1005 static void translate_layout(layout &x,const point &dx); 1006 void cartesian_product(const graphe &G,graphe &P) const; 1007 void tensor_product(const graphe &G,graphe &P) const; 1008 void connected_components(ivectors &components,int sg=-1,bool skip_embedded=false,int *count=NULL); 1009 int connected_component_count(int sg=-1); 1010 void biconnected_components(ivectors &components,int sg=-1); 1011 void strongly_connected_components(ivectors &components,int sg=-1); 1012 bool has_cut_vertex(int sg=-1,int i=0); 1013 void find_cut_vertices(ivector &articulation_points,int sg=-1); 1014 void find_blocks(std::vector<ipairs> &blocks,int sg=-1); 1015 void find_bridges(ipairs &B,int sg=-1); 1016 void find_ears(ivectors &ears,int sg=-1); 1017 bool find_cycle(ivector &cycle,int sg=-1); 1018 bool find_path(int i,int j,ivector &path,int sg=-1,bool skip_embedded=false); 1019 bool find_eulerian_trail(ivector &path); 1020 int eulerian_trail_start(bool &iscycle) const; 1021 bool fleury(int start,ivector &path); 1022 void hierholzer(ivector &path); 1023 bool is_multigraph() const; 1024 int multiedges(const ipair &e) const; 1025 void set_multiedge(const ipair &e,int k); 1026 bool weights2multiedges(); 1027 void contract_edge(int i,int j,bool adjust_positions=true); 1028 inline void contract_edge(const ipair &e,bool adjust_pos=true) { contract_edge(e.first,e.second,adjust_pos); } 1029 void subdivide_edge(const ipair &e,int n,int &label); 1030 void incident_edges(const ivector &V,edgeset &E); 1031 static bool edges_incident(const ipair &e1,const ipair &e2); 1032 void convex_hull(const layout &x,layout &hull); 1033 void edge_labels_placement(const layout &x); 1034 void draw_edges(vecteur &drawing,const layout &x); 1035 void draw_nodes(vecteur &drawing,const layout &x) const; 1036 void draw_labels(vecteur &drawing,const layout &x) const; 1037 void distance(int i,const ivector &J,ivector &dist,ivectors *shortest_paths=NULL); 1038 void allpairs_distance(matrice &m) const; 1039 void dijkstra(int src,const ivector &dest,vecteur &path_weights,ivectors *cheapest_paths=NULL,int sg=-1); 1040 bool bellman_ford(int src,const ivector &dest,vecteur &path_weights,ivectors *cheapest_paths=NULL); 1041 bool topologic_sort(ivector &ordering); 1042 bool is_arborescence() const; 1043 void reverse(graphe &G) const; 1044 void spanning_tree(int i,graphe &T,int sg=-1); 1045 void minimal_spanning_tree(graphe &T,int sg=-1); 1046 void lowest_common_ancestors(int root,const ipairs &p,ivector &lca_recursion); 1047 int lowest_common_ancestor(int i,int j,int root); 1048 void compute_st_numbering(int s,int t); 1049 vecteur get_st_numbering() const; 1050 void assign_edge_directions_from_st(); 1051 void parametrized_st_orientation(int s,int t,double p); 1052 void greedy_vertex_coloring_biggs(ivector &ordering); 1053 int greedy_vertex_coloring(const ivector &p); 1054 int exact_vertex_coloring(int max_colors=0); 1055 int exact_edge_coloring(ivector &colors,int *numcol=NULL); 1056 void get_node_colors(ivector &colors); 1057 bool is_bipartite(ivector &V1,ivector &V2,int sg=-1); 1058 bool is_vertex_colorable(int k); 1059 void dsatur(); 1060 int color_count() const; 1061 ipair adjacent_color_count(int i) const; 1062 bool adjacent_colors(int i,std::set<int> &colors) const; 1063 ipair chromatic_number_bounds(); 1064 void store_layout(const layout &x); 1065 bool has_stored_layout(layout &x) const; 1066 int bipartite_matching(const ivector &p1,const ivector &p2,ipairs &matching); 1067 void line_graph(graphe &G,ipairs &E) const; 1068 void transitive_closure(graphe &G,bool weighted=false); 1069 int is_isomorphic(const graphe &other,std::map<int,int> &isom) const; 1070 gen aut_generators() const; 1071 bool canonical_labeling(ivector &lab) const; 1072 bool bondy_chvatal_closure(graphe &G,ivector &d); 1073 int hamcond(bool make_closure=true); 1074 bool is_hamiltonian(ivector &hc); 1075 bool hamcycle(ivector &path); 1076 int traveling_salesman(ivector &h,double &cost,bool approximate=false); 1077 bool find_directed_tours(int k,ivectors &hcv,dvector &costs,const ipairs &incl); 1078 bool make_euclidean_distances(); 1079 gen maxflow_edmonds_karp(int s,int t,std::vector<std::map<int,gen> > &flow,const gen &limit=plusinf()); 1080 void minimum_cut(int s,const std::vector<std::map<int,gen> > &flow,ipairs &cut); 1081 gen tutte_polynomial(const gen &x,const gen &y); 1082 void fundamental_cycles(ivectors &cycles,int sg=-1,bool check=true); 1083 void mycielskian(graphe &G) const; 1084 gen local_clustering_coeff(int i) const; 1085 gen clustering_coeff(bool approx,bool exact); 1086 gen transitivity(); 1087 int edge_connectivity(); 1088 int vertex_connectivity(); 1089 void truncate(graphe &dest,const ivectors &faces); 1090 void condensation(graphe &G); 1091 void elementary_cycles(ivectors &cyc,int lo,int hi); 1092 void yen_ksp(int K,int src,int dest,ivectors &paths); 1093 void compute_in_out_degrees(ivector &ind,ivector &outd) const; 1094 static gen colon_label(int i,int j); 1095 static gen colon_label(int i,int j,int k); 1096 static size_t intersect_fast(ivector_iter min1,ivector_iter max1,ivector_iter min2,ivector_iter max2); 1097 static size_t intersect_linear(ivector_iter min1,ivector_iter max1,ivector_iter min2,ivector_iter max2); 1098 static size_t intersect_hybrid(ivector_iter min1,ivector_iter max1,ivector_iter min2,ivector_iter max2); 1099 static bool is_graphic_sequence(const ivector &s_orig); 1100 graphe &operator =(const graphe &other); 1101 }; 1102 1103 #ifndef NO_NAMESPACE_GIAC 1104 } // namespace giac 1105 #endif // ndef NO_NAMESPACE_GIAC 1106 #endif // __GRAPHE_H 1107