I don't care much about this.
On Tue, Dec 17, 2013 at 11:22:12AM +0100, Nathann Cohen wrote: > 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. -- 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.
