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 &timestamp,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 &notfound) 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