graph theory commands for Giac

[parisse]

Ok, I will update the source tarball on Monday.

[lukamar]

Here's a couple of improvements before you update:
1. I have implemented exact vertex coloring with minimum colors using GLPK's MIP solver (it's a heavy problem), so now it finishes in reasonable time and thus chromatic_number, clique_cover and is_vertex_colorable are much faster. For example, one can find minimal coloring of a sparse graph or of any graph with less than 100 vertices pretty quickly, in a couple of seconds. That required inclusion of glpk.h in graphe.h.
2. There is a new command clique_stats, which gives cardinality of k-cliques for every k (or for chosen k or between bounds m,n). Here is the short help:

Code : Tout sélectionner

# clique_stats
0 G,[k or m..n]
2 Returns the list of numbers of maximal cliques of size s in the graph G for each s. If parameter k is given, the number of k-cliques is returned. If an interval m..n is given, only cliques with size between m and n (inclusive) are counted (m also may be +infinity).
-1 maximum_clique
-2 clique_cover
clique_stats(random_graph(50,0.5))
clique_stats(random_graph(50,0.5),5)
clique_stats(random_graph(50,0.5),3..5)

That's a compensation for the maximal_cliques command which has been removed.

[parisse]

Source tarball should be updated!

[lukamar]

Thanks! However I've found a bug yesterday that prevented the correct coloring to be read from MIP solution, I've managed to fix it just now. If you have time, please update only the graphe.cc file once more (it's an one-line fix). The bug produces confusing situations where the chromatic number is right but the coloring is wrong.

[parisse]

Tarball updated!

[lukamar]

I have a few changes:
1. fixed a bug in _is_planar in my source, face vertices got mixed up,
2. in misc.cc, line 1935: enabled checking for graph even when an identifier is passed as the second argument,
3. in plot.cc, 7154-7157: added purge for identifier "faces" (maybe that wasn't necessary? but it's a temporary identifier anyway).

Changed files misc.cc and plot.cc are attached below.

Also I've added a new command called minimal_vertex_coloring:

Code : Tout sélectionner

# minimal_vertex_coloring
0 G,[sto]
2 Computes minimal vertex coloring for graph G and returns the colors in the order of vertices. If optional parameter "sto" is given, the colors are assigned to vertices and the modified copy of G is returned.
-1 chromatic_number
-2 is_vertex_colorable
minimal_vertex_coloring(graph("petersen"))
draw_graph(minimal_vertex_coloring(graph("petersen"),sto))

[parisse]

Source updated!

[lukamar]

Is it possible to add some configuration to graph drawing as a vector of geometrical objects? I mean, can a specification like hiding axes and orthonormal drawing be included in the vector somehow, to be automatically applied when displaying the drawing?

Related: when applying latex command to the drawing I get the drawing with pstricks, but it also shows the axes of the coordinate system as dashed lines with arrows. Can these be suppressed?

[parisse]

In Xcas, axes=0 in a graphic command will hide axes and gl_ortho=1 will orthonormalize. In giac, you must create the corresponding symbolic objects, like this
symb_equal(change_subtype(gen(GL_AXES),_INT_PLOT),0);
For latex pstricks, a quick look at the source shows that you must run show_axes(0,contextptr); to disable axes printing.

[lukamar]

Thank you for this information, it works and makes the drawings looking much better.
In the last few days I fixed some bugfixes and made few improvements:
1. the minimal vertex coloring algorithm now uses better branch/backtrack techniques, also I fixed the bug which caused the number of colors to be maximized, not minimized.
2. Fixed a bug in draw_graph which was affecting disconnected graphs and producing crashes.
3. The keyword "bipartite" seems to be properly defined (at the top of lexer_tab_int.h), but Xcas does not recognize it (should be set to 149). I don't know how to fix this...
4. The command

Code : Tout sélectionner

graph("harries")

produces a crash in Xcas, but I can't reproduce this in my source. Can you make a backtrack?
5. The command "maximal_matching" was removed as it's not particularly useful. Can you please remove the corresponding entry from aide_cas?
6. I've added three new commands: bipartite_matching, line_graph and transitive_closure. Here's the corresponding short help:

Code : Tout sélectionner

# bipartite_matching
0 G
2 Returns the sequence containing the size of maximum matching of the undirected unweighted bipartite graph G and the list of edges of the matching.
-1 is_bipartite
-2 maximum_matching
bipartite_matching(graph("desargues"))

# line_graph
0 G
2 Returns the line graph of the undirected input graph G.
-1 plane_dual
line_graph(hypercube_graph(3))

# transitive_closure
0 G,[weighted[=true or false]]
2 Returns the [weighted, by default false] transitive closure of the input graph G.
-1 allpairs_distance
-2 is_connected
-3 shortest_path
-4 vertex_distance
transitive_closure(digraph([1,2,3,4,5,6],%{[1,2],[2,3],[2,4],[4,5],[3,5]%}),weighted)

6. The manual was heavily updated (but still not finished), I now use TeXmacs for it because it looks good and it's really easy to add practical examples to the text as it supports insertion of interactive Giac sessions. Also, it's by far the most easy way to write math. Unfortunately, TeXmacs is somewhat buggy, but one can cope with it relatively easy when sticking to the default style packages.

[parisse]

The segfault happens in

Code : Tout sélectionner

void graphe::make_regular_polygon_layout(layout &x,const ivector &v,double R)

If I put a breakpoint in the loop, n is 70 and when k is 69 then i=v[k] is -1 and x is undefined.

[parisse]

bipartite was not working because it was not alpha-sorted.
I had to modify graphe.cc in graphe::dsatur because pos and it are not const iterator, they can not be declared as ivector_iter. Perhaps you should modify the typedef.

[lukamar]

Thanks for the fixes and for locating the segfault, I'll mirror the changes. I prefer to have a typedef for the const_iterator, since I use it most of the time (it could be something like ivector_constiter but ivector_iter is shorter, although may be misleading). My compiler does not complain about such mistakes, I'll include the -pedantic option for the future compiling.

[lukamar]

Bug fixed, along with dozen others.
I also made some improvements to graph drawing. In particular, 3D layouts are now allowed to be disconnected and the special graphs now get predefined layouts.
The manual was updated as well, I've written the secion on random graphs.

[parisse]

Source tarball updated. I will probably make binary builds tomorrow.