graph theory commands for Giac

[parisse]

Actually, if I install libnauty2-dev on debian 9, I don't have nauty/nauty.h, I get

Code : Tout sélectionner

ls -l /usr/include/nauty
total 60
-rw-r--r-- 1 root root 10480 août  23  2016 gtools.h
-rw-r--r-- 1 root root  1829 août  23  2016 gutils.h
-rw-r--r-- 1 root root  1669 août  23  2016 naugroup.h
-rw-r--r-- 1 root root  1223 août  23  2016 naurng.h
-rw-r--r-- 1 root root  5663 août  23  2016 nausparse.h
-rw-r--r-- 1 root root  2582 août  23  2016 nautinv.h
-rw-r--r-- 1 root root 14984 août  23  2016 naututil.h
-rw-r--r-- 1 root root  2753 août  23  2016 schreier.h
-rw-r--r-- 1 root root  3080 août  23  2016 traces.h

What's wrong?

[lukamar]

I was wondering too at first, nauty.h resides in include/x86_64-linux-gnu/ for some reason. On my system it somehow appeared afterwards in include/nauty/, I don't know what happened.
If nauty.h is not in include/x86_64-linux-gnu/, try replacing #include "nauty/nauty.h" by #include "nauty/nausparse.h" because it includes nauty.h, wherever that may be.

[lukamar]

Sorry for leaving this mistake in the code, the directory x86_64-linux-gnu was included at one place in my build configuration so my compiler didn't complain. The nauty.h file resides there by design of the package libnauty2-dev. I think the best option is to include nausparse.h instead of nauty.h.

[lukamar]

I have commited the implementation of exact edge coloring, it uses vertex coloring algorithm on the line graph of the input graph. It is reasonably fast due to the tight Vizing bounds for chromatic index [D,D+1].
Here are the new commands:

Code : Tout sélectionner

# minimal_edge_coloring
0 G,[sto]
2 Finds the minimal edge coloring of the input graph G and returns the sequence n,L where n is the class of G (1 for D colors and 2 for D+1 colors) and L is the list of colors of edges of G as returned by the edges command, or a copy of G with colored edges if the option 'sto' is specified.
-1 chromatic_index
-2 minimal_vertex_coloring
-3 edges
minimal_edge_coloring(graph("petersen"))
G:=minimal_edge_coloring(graph("dodecahedron"),sto); draw_graph(G)

# chromatic_index
0 G,[cols]
2 Returns the number of colors in the minimal edge coloring of the input graph G. If an unassigned identifier cols is given, the coloring is stored to it.
-1 minimal_edge_coloring
-2 chromatic_number
chromatic_index(graph("petersen"))
chromatic_index(graph("dodecahedron"),colors)

I haven't replicated your modifications in nautywrapper.c yet, I'll do that after Giac source is synchronized so I can compile my code which links to Giac dynamically.

[parisse]

I will update the source tomorrow. I have kept the header check with nauty/naututil.h.

[parisse]

Source updated!

[lukamar]

Thanks!
There is however one issue with nauty interface. When I run the compilation of Giac, the preprocessor switch

Code : Tout sélectionner

#if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H

evaluates to true in graphe.cc (I updated the switches in graphe::is_isomorphic, graphe::aut_generators and graphe::canonical_labeling), but, during the same compilation, to false in nautywrapper.c. Apparently HAVE_NAUTY_NAUTUTIL_H isn't defined at that time. Everything works fine when the

Code : Tout sélectionner

defined HAVE_NAUTY_NAUTUTIL_H

condition is removed, i.e. when replacing the above preprocessor switch with:

Code : Tout sélectionner

#if HAVE_LIBNAUTY

in nautywrapper.c.
This error causes the commands is_isomorphic and canonical_labeling to exhibit undefined behavior, as they are informed that nauty is available, but just the dummy interface to nauty is compiled.

[parisse]

Indeed. nautywrapper.c should begin with #include "config.h". By the way, I wonder how HAVE_LIBNAUTY is recognized...

[lukamar]

I forgot to erase HAVE_LIBNAUTY from my version of graphe.h which I used until now. So it indeed should not have had been recognized.
I included config.h in nautywrapper.c, now it works!

[lukamar]

Hello Bernard,
I have some updates:
1. there was a bug in Edmonds' blossom algorithm which produced suboptimal results in some cases, which is now fixed. Also, the algorithm is faster.
2. I fixed a bug in isomorphic_copy command and also rewrote the code so that it is much faster now (works in linear time). Previously it was hanging on large graphs (with over 100000 edges).
3. A new command trail2edges was added to facilitate easy conversion from a trail to list of edges, simplifying the extraction of trails with subgraph command.

Code : Tout sélectionner

# trail2edges
0 T
2 Converts a trail T to the list of its edges.
-1 subgraph
-2 trail
trail2edges(trail(1,2,3,4,1,3))
trail2edges([1,2,3,4,1,3])

4. I've implemented a solver for traveling salesman problem and a command for testing hamiltonicity (traveling_salesman and is_hamiltonian, respectively). TSP solver is an amalgam of a brand new technique in generating subtour elimination constraints by the method of hierarchical clustering (published in 2017) and classical methods. It uses branch-and-cut solver from GLPK with the rules by Padberg and Rinaldi and also some powerful heuristical methods (Christofides algorithm and Lin-Kernighan heuristic). It can solve TSP with up to 40-50 cities and find near-optimal solutions for 100-600 cities in less than a minute.

Code : Tout sélectionner

# traveling_salesman
0 G,[M],[opts]
2 Returns a Hamiltonian cycle in undirected unweighted graph G or solves traveling salesman problem if G is weighted (matrix M can be used for edge weights), returning a sequence containing the minimal cost and the corresponding Hamiltonian cycle.
-1 is_hamiltonian
traveling_salesman(hypercube_graph(5))
M:=randmatrix(4,4,99); traveling_salesman(graph("tetrahedron"),M)
G:=set_vertex_positions(complete_graph(42),[randvector(2,1000)$(k=1..42)]); traveling_salesman(G,vertex_distance)
G:=set_vertex_positions(complete_graph(120),[randvector(2,1000)$(k=1..120)]); c,T:=traveling_salesman(G,vertex_distance,approx)

Code : Tout sélectionner

# is_hamiltonian
0 G,[hc]
2 Returns true if G is a Hamiltonian graph (and stores the Hamiltonian circuit in hc if unassigned identifier is given), else returns false.
-1 traveling_salesman
is_hamiltonian(graph("petersen"))
is_hamiltonian(hypercube_graph(5),C)

5. The manual is corrected and updated. It now documents about 150 commands. I've added some hyperlinks for easier navigation and the command index.

@jocaps: Thank you for considering using nauty from Xcas in your work. I've tested, fixed and documented the commands and they're now ready to go. You'll find them in sections 4.2.9 and 4.2.10 of the manual.

Edit: added more examples to the short help for traveling_salesman and trail2edges commands.

[lukamar]

A couple of updates more:
1. support for networks (commands: is_network, random_network_graph, maxflow)
2. improved highlight_subgraph command, now it supports overwriting edge weights with those in the subgraph which is useful when highlighting optimal flows
3. added is_cut_set command

Here's the short help for the new commands:

Code : Tout sélectionner

# is_network
0 G,[s,t]
2 Returns true if the graph G is a network with the source s and sink t, else returns false. If s,t are not given, the output is a sequence of two sets of vertices: sources and sinks.
-1 random_network
-2 maxflow
is_network(digraph(trail(1,2,3,4,5,6,4,7)))
is_network(digraph(trail(1,2,3,4,5,6,4,7)),1,7)
is_network(digraph(trail(1,2,3,4,5,6,4,1)))

Code : Tout sélectionner

# random_network
0 a,b,[p],[opts]
2 Returns a random network graph with b grid frames of size a*a in which every edge appears with the probability p (by default 0.5).
-1 is_network
-2 maxflow
random_network(3,3)
random_network(3,3,acyclic)
random_network(3,4,0.75)

Code : Tout sélectionner

# maxflow
0 G,s,t,[M]
2 Returns the optimal value for the max flow problem for network G with the source s and sink t (an optimal flow is written to M as a matrix).
-1 is_network
-2 random_network
maxflow(digraph(%{[[1,2],2],[[2,3],4],[[3,4],3],[[1,5],3],[[5,2],1],[[5,4],2]%}),1,4)

Code : Tout sélectionner

# is_cut_set
0 G,E
2 Returns true if removing the edges in E from the graph G increases the number of connected components of G, else returns false.
-1 connected_components
-2 delete_edge
is_cut_set(graph(trail(1,2,3,4,5,6,4,1,3)),[[1,4],[3,4]])

Also, the following changes are required to support new option "acyclic":
1. Add the following line below line 595 (at the end of the maple_conversion enum) in dispatch.h:

Code : Tout sélectionner

    _GT_ACYCLIC = 150, // acyclic

2. Add the line

Code : Tout sélectionner

    {"acyclic", 0, _GT_ACYCLIC, _INT_MAPLECONVERSION, T_TYPE_ID},

after the line 71 in lexer_tab_int.h.
Short help for the option:

Code : Tout sélectionner

# acyclic
0 Opt
2 Option for the random_network_graph command.
-1 random_network_graph

Edit: changed random_network_graph to random_network

[parisse]

Hi!
Thanks for the updates!
I got compilation errors after updating, in graphe.cc:
* INT_MAX undefined, replaced by RAND_MAX
* std::log2(...) does not exist (older C++), replaced by std::log(...)/M_LN2
* std::round(...) does not exist, replaced by std::floor(...+.5) (also in graphtheory.cc)
* there is a warning about name lookup of i:

Code : Tout sélectionner

graphe.cc:9606: warning: name lookup of ‘i’ changed
graphe.cc:9578: warning:   matches this ‘i’ under ISO standard rules
graphe.cc:9586: warning:   matches this ‘i’ under old rules

You should have a look there, because a definition of i in a loop shadows a previous definition of i.

[lukamar]

Thank you, I fixed graphe.cc and graphtheory.cc. There was indeed shadowing of variables in graphe::tsp::straighten, but my compiler did not complain about it...

[lukamar]

I changed random_network_graph to random_network, it is more consistent. I edited the post with short help for network commands accordingly.

[lukamar]

Recent changes:
- I added vertex color detection to the is_isomorphic, canonical_labeling and graph_automorphism commands, now only vertices wth the same color can be mapped to each other. This makes the inclusion of nauty complete. It is also necessary for computing Tutte polynomials, which will be implemented soon.
- I fixed couple of bugs: in draw_graph (with bipartite option) and in has_edge and has_arc commands.
- All the implemented commands are documented. I also added syntax blocks to the manual for easier usage of the commands.