graph theory commands for Giac

[lukamar]

I managed to compile Giac/Xcas from the newest source code, it worked without problems (finally!)
But edges are still not visible in graph drawings. Did I mess something up in my code? Segments and vectors are added in lines 5911--5912 of graphe.cc.
I will correct eventual mistakes in aide_cas and post it separately (tomorrow i guess), so you don't have to cut/paste portions of it.

I noticed that when a large graph is created, say with 1000 vertices, Xcas prints "Done" because list representing the graph is too long. I know that's expected behavior, but could it be overriden for graphs? The text to be printed is always sufficiently small to fit into the cell.

[lukamar]

I fixed aide_cas, there were some duplicate entries. Also, I fixed the description for import_graph, it returns "undef" on fail, not 0 or 1 (I tried to correct the french translation too, please check if I did it right). I also added options at the end.

You may continue translating this version, the new entries will be appended as they come.

[lukamar]

Hi Bernard,
I report some more bugfixes:
1. The command set_edge_weight sets the weight correctly but does not return the modified graph, so it's not usable. I fixed that. Can you please change the corresponding entry in aide_cas? The english description should be: Sets weight of the edge e in the weighted graph G to w and returns the modified copy of G. Also, the example for the same command has a typo, it should be:

Code : Tout sélectionner

set_edge_weight(graph(%{[1,2],[2,3]%}),[1,2],5)

2. Fixed a bug in add_arc command, the syntax was not being correctly recognized.
3. Fixed a bug in subdivide_edges command, entering nonexistent edges was leading to a false assertion.
(short help stays the same for both 2. and 3.)
4. The multilevel spring algorithm was too slow but I've found the cause and fixed it, now it performs much better, it is able to layout a graph with 1000 vertices in less than 20 secs.

I've also written a substantial portion of Section 3 of the manual.

Edit: 5. Fixed a bug in set_graph_attribute command, it was skipping the first attribute.

[lukamar]

Could the graph information from is_graphe be printed out in giac console mode as well when a graph is evaluated? That would be necessary for giac sessions in TeXmacs.

[parisse]

I updated, but could not compile without modifications:

Code : Tout sélectionner

diff graphe.cc graphe.cc~
3503c3503
<         ivector::iterator it,jt;
---
>         ivector_iter it,jt;
3612c3612
<     ivector::iterator it;
---
>     ivector_iter it;
3620c3620
<         for (ivector::iterator jt=U.begin();jt!=U.end();++jt) {
---
>         for (ivector_iter jt=U.begin();jt!=U.end();++jt) {

Otherwise some erase or insert operations do not compile. Note that if you insert in a vector, all iterators may become invalid because the vector may be reallocated, unless you did a reserve before.

[lukamar]

Thanks for fixing and updating the source, I made the same changes in my repository. Also, the newest revision contains significant improvements to the graph drawing algorithms. Several related bugs were fixed along the way.

The problem with displaying edges in graph drawings persists.... they're still invisible after compiling the newest source

Edit: problem solved! Now append_segment contains this code:

Code : Tout sélectionner

vecteur attributs(1,color | width);
    vecteur seg=p.size()==2?
                makevecteur(makecomplex(p[0],p[1]),makecomplex(q[0],q[1]))
            : makevecteur(gen(makevecteur(p[0],p[1],p[2]),_POINT__VECT),gen(makevecteur(q[0],q[1],q[2]),_POINT__VECT));
    drawing.push_back(pnt_attrib(gen(seg,arrow?_VECTOR__VECT:_GROUP__VECT),attributs,ctx));

I've just committed the corrections.

[parisse]

I have updated the source tarball, adding the graph user guide in doc/, with install in /usr/share/giac/doc, and a new item in Xcas Help menu. I have also updated the 1.4.9-65 debian 9 packages (I forgot to modify the 65...).
The graph information should already be displayed in giac console.

[lukamar]

Where do I get the newest debian packages? The directory https://www-fourier.ujf-grenoble.fr/~parisse/giac/ contains the version from May 28.

[parisse]

Indded, should be fixed now.

[lukamar]

Back to the texmacs problem, I think that the graph info is not displayed because texmacs calls latex command, as it displays mathematical output. But latex command does not know about graphs, so it should call is_graphe somewhere. I can try to make a fix, can you point me to the location in the source code where the additional check should be inserted?

[parisse]

The difficult part was to guess where the problem was, how that you solved it, it's easy to fix:

Code : Tout sélectionner

diff tex.cc tex.cc~
39,43d38
< #if defined GIAC_HAS_STO_38 || defined NSPIRE || defined FXCG || defined GIAC_GGB
< inline bool is_graphe(const giac::gen &g,std::string &disp_out,const giac::context *){ return false; }
< #else
< #include "graphtheory.h"
< #endif
1324,1328d1318
<       if (e.subtype==_GRAPH__VECT){
< 	string s;
< 	if (is_graphe(e,s,contextptr))
< 	  return "\\mbox{"+s+'}';
<       }

[lukamar]

That solved the problem indeed, thanks!
I additionally propose to change the first case in the first e.type switch appearing in gen2tex procedure (tex.cc):

Code : Tout sélectionner

switch (e.type){
case _INT_: case _ZINT: case _REAL:
>   if (e.subtype==_INT_BOOLEAN)
>       return "\\mbox{"+e.print(contextptr)+'}';
    return e.print(contextptr);

This way the booleans "true" and "false" are displayed as normal text. Up to now texmacs was showing these words italicized without kerning, probably assuming that every single letter is an identifier.

[lukamar]

New changes in the graphtheory source:
1. graph drawing is improved
2. added heuristics for vertex coloring, improved chromatic number computation and clique cover search
3. new option bipartite is added for draw_graph command, the changed headers are dispatch.h (line 594) and lexer_tab_int.h (line 3), attached below
4. new commands were added, here's the corresponding short help (to be appended to aide_cas):

Code : Tout sélectionner

# bipartite
0 Opt
2 Option for the draw_graph command
-1 draw_graph

# st_ordering
0 G,s,t
2 Returns ST numbering for the biconnected graph G with source s and sink (target) t.
-1 is_biconnected
st_ordering(graph("petersen"),1,2)

# greedy_color
0 G,[p]
2 Returns the list of vertex colors (positive integers) obtained by coloring vertices one at a time [in the order given by permutation p], assigning to each one the smallest available color.
-1 is_vertex_colorable
-2 chromatic_number
greedy_color(graph("petersen"))
greedy_color(graph("petersen"),randperm(10))

# is_bipartite
0 G,[P]
2 Returns true iff the graph G is bipartite [and assign to P the list of partitions represented as lists of vertices].
-1 random_bipartite_graph
-2 draw_graph
is_bipartite(graph("desargues"))
is_bipartite(complete_graph(5))

# plane_dual
0 G or F
2 Returns the plane dual of a biconnected planar graph G or constructed from the list of faces F.
-1 is_planar
plane_dual(hypercube_graph(3))
plane_dual([[1,2,3],[4,1,3],[5,4,3],[1,2,3,5,4,1]])

# is_vertex_colorable
0 G,k,[col]
2 Returns true iff the vertices of graph G can be colored by using at most k colors [use the identifier col to store the colors].
-1 greedy_color
-2 chromatic_number
is_vertex_colorable(graph("petersen"),2)
is_vertex_colorable(graph("petersen"),3,cols)

# set_vertex_positions
0 G,vp
2 Sets the coordinates, given in the list vp, to the vertices of graph G and returns the modified copy of G.
-1 draw_graph
G:=graph([1,2,3,4,5,6],%{[1,2],[1,4],[4,5],[2,5],[2,3],[3,6],[5,6]%}); G:=set_vertex_positions(G,[[0,0],[0.5,0],[1,0],[0,0.5],[0.5,0.5],[1,0.5]])

Edit: added per one more example to greedy_color, is_bipartite and plane_dual commands

[lukamar]

Bernard, I propose that the commands vertices, charpoly and faces contain a check if their argument is a graph. If it is, the input should redirect to graph_vertices, graph_charpoly and is_planar, respectively. For vertices and charpoly the input should be forwarded as is, so it's easy. With faces is a bit different, one should insert something like this to _faces command:

Code : Tout sélectionner

string s;
if (is_graphe(g,s,contextptr)) {
  identificateur f(" faces");
  gen ret=_is_planar(makesequence(g,f),contextptr);
  if (is_one(ret))
    return _eval(f,contextptr);
  return ret;
}

so that the list of faces is returned in case g is a planar biconnected graph.

[lukamar]

Also, can you remove the maximal_cliques entry in aide_cas? I removed this command since it's not very useful and can produce massive results.