Edge coloring multigraphs raises exception

[Georgi Guninski]

Edge coloring multigraphs raises exception

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

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?

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]

[Nathann Cohen]

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

[Georgi Guninski]

I don't care much about this.

> --
> 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...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/groups/opt_out.

[Andrew]

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

[Nathann Cohen]

Yooooooooooo !!

> 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?

Ahahah. No idea. Graphs were implemented long before I first installed Sage :-P

Plus... Well, doing this isn't always the right option. I mean, I have no idea what we should do with those awful things, having a different graph class means that you will either

1) Implement some algorithms twice with very minor changes

2) Create a simple graph from a multigraph, THEN call the graph function (and copying graphs is not free, and that's unaffordable fo linear things like distance computations)

3) You write once a function that supports both, and well, you will waste some time on normal graphs too, and have the graph algorithms polluted

It's not an answer to your question, for I really have no idea how we could find a cool way out of this thing. I really HATE multigraphs.

Look, Georgi tried to create the line graph of a multigraph. The line graph is, by the book, a graph whose vertices are the edges of your first graph. That's cool.

But what happens if you have multiple edges ? Now the vertices of your new graph cannot be identified by "pairs of vertices" only, you need more information. Well, you could add an integer to the pairs of vertices to number the labels, but really that is an ugly wy out.

And multigraphs yield infinitely many problems like that. Things that can't be solved cleanly and naturally. Bad work :-/

Nathann

[Georgi Guninski]

if i understand correctly, Nathann is implying that
if one works will multigraphs they shouldn't use sage
for this task.

agree with this and do so.

[Nathann Cohen]

> if i understand correctly, Nathann is implying that
> if one works will multigraphs they shouldn't use sage
> for this task.

Indeed. Or that they should attempt to code what they need, because right now I wouldn't feel confortable myself computing stuff on multigraphs.

> agree with this and do so.

Good luck !

Nathann

[Nathann Cohen]

Helloooooooooooo !!

Here is a more responsible answer : I just created ticket #15572 to raise exceptions when a function is called which isn't supposed to deal with multiple edges and/or loops. I hope I found them all, but in any case now protecting such functions will just take one line. Aaaaaaaaaaaand of course, if a function isn't supported for non-simple graphs even though it would have a meaning to do so, it will have to be implemented eventually :-)

Buuuuut in the meantime, no more wrong answers :-P

http://trac.sagemath.org/ticket/15572

Nathann

[Georgi Guninski]

On Mon, Dec 23, 2013 at 05:17:37AM -0800, Nathann Cohen wrote:
> Helloooooooooooo !!
>
> Here is a more responsible answer : I just created ticket #15572 to raise
> exceptions when a function is called which isn't supposed to deal with
> multiple edges and/or loops. I hope I found them all, but in any case now
> protecting such functions will just take one line. Aaaaaaaaaaaand of
> course, if a function isn't supported for non-simple graphs even though it
> would have a meaning to do so, it will have to be implemented eventually :-)
>
> Buuuuut in the meantime, no more wrong answers :-P
>
> http://trac.sagemath.org/ticket/15572
>
> Nathann
>

lol, thanks.

I liked your answers in this thread :)

Is .eulerian_circuit() expected to work on multigraphs?

[Nathann Cohen]

Yoooooooooo !!

> lol, thanks.
>
> I liked your answers in this thread :)

Cool ! :-D

To be honest, I really believed that they had made you angry ^^;

> Is .eulerian_circuit() expected to work on multigraphs?

Yes I believe so. The implementation of this function is really
elegant and calls "edge_iterator", not the list of neighbors, so it
should be fine :-)

Nathann

[Georgi Guninski]

On Mon, Dec 23, 2013 at 04:31:46PM +0100, Nathann Cohen wrote:
> Yoooooooooo !!
>
> > lol, thanks.
> >
> > I liked your answers in this thread :)
>
> Cool ! :-D
>
> To be honest, I really believed that they had made you angry ^^;
>

No, I wasn't angry at all.

I am pretty sure sage has A LOT OF bugs,
why bother?

Probably a lot of them never will be fixed,
never mind.

[Nathann Cohen]

> I am pretty sure sage has A LOT OF bugs,

Indeed.

> why bother?

Because I use this thing and I need it to give correct answers :-P

> Probably a lot of them never will be fixed,
> never mind.

I am pretty sure that some bugs will never be fixed, but I won't allow a bug to remain in the graph/ or numerical/ folder without doing something about it :-P

Nathann