Hi Nathann, Why isn't are multigraphs (labelled graphs, graphs with loops etc) implemented as a separate class(es) which inherit from a stripped down version of graphs? This way graphs would not incur any speed penalty because of all of these extra checks that are needed for these more "exotic" graphs?
Andrew On Tuesday, 17 December 2013 11:22:12 UTC+1, 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.
