Yooooooooooooooooooooooooooo !! > Edge coloring multigraphs raises exception
Ahahaha. That's possible. > sage: > P=graphs.PetersenGraph();ep=P.edges(labels=0);P2=Graph(ep+ep,multiedges=1) > sage: graph_coloring.edge_coloring(P2,value_only=1) > 7 # not sure this is correct It most probably isn't. Really, most of Sage's graph functions are written without multigraphs in mind. I hate those things. Implementing something for multigraphs instead of graphs just makes you add mostly useless code (which, besides, is a pure loss of computational time for normal graphs), and does not add anything interesting to the algorithm. Actually, it's pretty clear from the documentation that edge coloring has not been thought for multigraphs, as one of the parameters is "vizing", and Vizing's theorem does not apply to multigraphs :-P > sage: graph_coloring.edge_coloring(P2,value_only=0) > > RuntimeError: maximum recursion depth exceeded while calling a Python object > > How to get explicit edge coloring of multigraph? Well, I would say "compute their line graph, and the chromatic numbers of those". Which is what you do next : > In addition the line graphs of P and P2 are isomorphic: > > sage: Pl=P.line_graph();P2l=P2.line_graph();Pl.is_isomorphic(P2l) > True > sage: Pl==P2l > True > > sage: P2.degree() > [6, 6, 6, 6, 6, 6, 6, 6, 6, 6] Oh. Right. Same explanation there I guess. Though it looks like the function works if you have different labels on your different edges. Now, for the fix : I personally cannot care less about multigraphs, and I actually don't like the fact that making these functions return meaningful results on normal graps will make all computations slower on normal graphs, wit no value added. Besides, the code will be longer, and unclear because it will be polluted with things which have nothing to do with the smart part of the algorithm itself. I mean, just think of a shortest path algorithm on a multigraph ! I would personally sleep better if I just added a exception to all those functions, saying that "You gave an multigraph as input, and this function has not been checked to work for multigraphs". Which would mean that you wouldn't be able to use any of those functions which multigraphs, which is fair as we expect them to return wrong results. This being said, if you need this feature and if you are willing to help it's a different story. It's pretty hard to have patches reviewed in Sage these days, and unless the patches are reviewed I would just be working to make your own code work, to only see my work being forgotten on our trac server, never merged into Sage. Soooooooo well. What do you think ? :-P As fun as it is to implement graph algorithms in Sage, really multigraphs are nothing but pain and boring bugs. And waste of computational time :-P See youuuuuuu ! Nathann -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
