graph theory commands for Giac

[lukamar]

I added a new command: is_strongly_regular

Code : Tout sélectionner

# is_strongly_regular
0 G,[srg]
2 Returns true iff the graph G is strongly regular and optionally outputs srg=[k,l,m] where k is the vertex degree and l resp. m is the number of common neighbors for adjacent resp. non-adjacent vertices.
-1 is_regular
-2 adjacency_matrix
-3 seidel_spectrum
is_strongly_regular(graph("clebsch"))
is_strongly_regular(graph("shrikhande"),s); s

[parisse]

Updated in my source tree without errors, thanks!

[jocaps]

I just want to congratulate lukamar for such hard work. This is amazing!!

Has one the option to compile giac without Nauty or other graph theory libraries? I think having these options are really what makes giac stands out compared to other CAS. e.g. compiling with/without Pari, Cocoa etc. So one can have a minimalist giac as well as one which has rich features.

I was wondering if there are any thoughts on even integrating GAP. But this is probably a topic for another thread

Jose

[lukamar]

Thanks!!

Yes, Giac can be compiled without nauty and GLPK, which are used in some more difficult tasks. Several commands wouldn't be usable, but the majority is written from scratch so it's Giac native code (I tried to make it as compact and simple as possible for Giac to stay small, 11000 lines of core routines may seem a lot but, for example, only vecteur.cc is about 19000 lines). As about Makefile switches, I'm not so familiar with the details of the compilation process though, so I'll leave Bernard to reply.

[parisse]

It's configure.in that checks for nauty. There is currently no --disable-nauty switch, but it's not hard to add, like for glpk.
Optional linking with other packages (GAP, R, singular, ?) is certainly desirable. I hope someone who knows these packages will be interested...

[lukamar]

Newest changes:
- fixed several minor bugs
- added laplacian_matrix command

Code : Tout sélectionner

# laplacian_matrix
0 G,[normal]
2 Returns the Laplacian matrix L=D-A of an undirected graph G where D resp. A is the degree matrix resp. the adjacency matrix of G.
-1 adjacency_matrix
-2 degree_sequence
-3 number_of_spanning_trees
laplacian_matrix(graph(trail(1,2,3,4,5,2)))
laplacian_matrix(graph(trail(1,2,3,4,5,2)),normal)

- implemented the delete-contract algorithm for computing Tutte polynomials, it uses nauty but also works without it, the related commands are tutte_polynomial, flow_polynomial, chromatic_polynomial and reliability_polynomial

Code : Tout sélectionner

# tutte_polynomial
0 G,[x,y]
2 Returns the Tutte polynomial [or its value at point (x,y)] of an undirected graph G. If G is weighted, all weights must be positive integers and are interpreted as edge multiplicities.
-1 chromatic_polynomial
-2 flow_polynomial
-3 reliability_polynomial
-4 delete_edge
-5 contract_edge
tutte_polynomial(graph("tetrahedron"))
tutte_polynomial(graph("tetrahedron"),1,1)

Code : Tout sélectionner

# flow_polynomial
0 G,[x]
2 Returns the flow polynomial [or its value at point x] of an undirected unweighted graph G.
-1 chromatic_polynomial
-2 reliability_polynomial
-3 tutte_polynomial
flow_polynomial(graph("tetrahedron"))
flow_polynomial(graph("tetrahedron"),5)

Code : Tout sélectionner

# chromatic_polynomial
0 G,[t]
2 Returns the chromatic polynomial [or its value at point t] of an undirected unweighted graph G.
-1 flow_polynomial
-2 reliability_polynomial
-3 tutte_polynomial
chromatic_polynomial(graph("petersen"))
chromatic_polynomial(graph("petersen"),3)

Code : Tout sélectionner

# reliability_polynomial
0 G,[p]
2 Returns the reliability polynomial [or its value at point p] of an undirected graph G. If G is weighted, all weights must be positive integers and are interpreted as edge multiplicities.
-1 chromatic_polynomial
-2 flow_polynomial
-3 tutte_polynomial
reliability_polynomial(graph("petersen"))
reliability_polynomial(graph("petersen"),0.5)

- the manual is corrected and updated, all the new commands are documented

Edit: corrected short help for chromatic_polynomial

[parisse]

I have problems compiling if nauty is not installed, a constructor should be modified in graphe.h:

Code : Tout sélectionner

graphe.h: In constructor ‘giac::graphe::cpol::cpol()’:
graphe.h:446: error: ‘cg’ was not declared in this scope
graphe.h:446: error: ‘col’ was not declared in this scope

[lukamar]

Fixed!
By the way, there was another bug in st-numbering algorithm, I fixed that one also.

[parisse]

Are we ready for a 1.5.0 release on your side?

[lukamar]

Almost ready, there are just couple of things left. Precisely:
- random_network needs improving
- commands (mostly simple ones) that are yet to be implemented:
* mycielski
* edge_connectivity
* vertex_connectivity
* is_two_edge_connected
* two_edge_connected_components
* local_clustering_coefficient
* global_clustering coefficient
It's all pretty straightforward. A week is enough time for me to finish the implementation and to proofread the docs.

[parisse]

Ok, then I will make a 1.4.9* release this week.

[parisse]

Another change I had to make:

Code : Tout sélectionner

diff graphe.cc graphe.cc~
4692d4691
< #ifdef HAVE_LIBGLPK
4695,4697d4693
< #else
<     int ncolors=0;
< #endif

[lukamar]

Indeed, I forgot about that one. I mirrored your fix and added a warning message.

[lukamar]

Hello,
I have finished coding, just to make few corrections in short help and then it's done (I have changed names/syntax of a few commands in the process).
I'll do that later today, so everything will be ready for release of 1.5.0 by tomorrow.

[lukamar]

It's now all ready for releasing 1.5.0 from my side. Some notes:

1. Besides random_network, the random_tree command was rewritten, it now implements algorithms of Herbert Wilf for (theoretical) *exact uniform* generation of random (rooted) trees. It took some effort to detect and correct a minor error in the original Wilf's paper, but it's worth it. Since some insanely large numbers (see https://oeis.org/A000055) need to be computed during this process, it's great that Giac supports unlimited precision integer arithmetic so, theoretically, arbitrarily large trees can be generated. For example, it takes about a minute or two to generate a tree on 10000 nodes uniformly at random. This is vastly superior over naive Maple algorithm which was previously implemented (it is however retained for speed and when generating trees with maximum degree limit) and is potentially usable in research.

2. Random_graph and random_digraph are also rewritten and now properly implement Erdős-Rényi model. They run much faster than before and very large graphs, with millions of edges, can be generated relatively quickly (provided that one has enough RAM...).

3. Maple does not implement average clustering coefficient, but only a global one (i.e. network transitivity). In Giac there is a possibility of computing the former: local and average clustering coeff are unified in clustering_coefficient command. Global clustering coeff has its own command, network_transitivity.

4. Several bugs are fixed, which emerged during testing.

5. The manual is completed and is out of the draft phase.