Reviews needed in Graph Theory !

[Nathann Cohen]

Hello everybody !!

I am writing about two tickets in Graph Theory that really need reviews... They have been standing there for some time (something like 3 months !!!), and I wouldn't mind so much if it was not for the fact that these two tickets contains very fundamental functions that block the implementation of many others ones...


Flow, Matching, Connectivity, and some Hard problems
-----------------------------------------------------------------------------------
URL : http://trac.sagemath.org/sage_trac/ticket/6680

Contents :
Minimum dominating Set
Minimum Independent Dominating Set
Minimum Vertex Cover
Maximum weighted matching
Maximum Flow
Minimum Edge cut
Minimum Vertex Cut
Edge Connectivity
Vertex Connectivity

Vertex Coloring, Edge Coloring
----------------------------------------------------------------------------------
URL : http://trac.sagemath.org/sage_trac/ticket/6679

Contents :
Vertex Coloring
Edge Coloring

All these functions are documented and explained, first because the user could be interested in them, but also to ease reviews.  I also tried to add comments to the code when necessary.

If you have some time to review them, please help the Graph Theory section of Sage :-)

Nathann

[David Joyner]

I'm definitely not a graph-theorist by any stretch. However,
some colleagues at work talked me into lecturing on abelian sandpiles
(David Perkinson's sandpiles page: http://people.reed.edu/~davidp/sand/,
with Sage code:-) in a department seminar, so I am getting very
interest in vertex
colors as they seem very closely related to "chip configurations"
(associating an integer >=0 to a non-sink vertex).

Can your "colored" graphs be plotted in black and white but in
such a way that the "colors" appear as weights besides the labels in the plot?

These look like excellent patches! I think I will have time to try to review
some towards the end of November, when we have a Thanksgiving break.

[Nathann Cohen]

Hello !!!

The two coloring functions are meant to output a number when the user
is just interested in the number of classes, but the most "natural"
behaviour for these functions is to output a partition of the vertices
( of the edges ) such that each class is an independent set. As the
former coloring function included a different output ( see keyword
hex_colors=True ) so that everything is well displayed in the plot
command ( it output a dictionary whose keys are colors and values are
sets of vertices/edges ), I added this output to the functions too.

In your situation, you tell me you would like the functions to input
nothing but to place the id of the classes on each of the vertices ?
To obtain the information you mention, you can use a dictionary for
example :

classes=g.vertex_coloring()
dic={}
for (c,id) in zip(classes,range(len(classes))):
for v in c:
dic[v]=i

This way your dictionary associates to each vertex its color, which
seem to be in your case a better type of output ;-)

By the way, I am kind of studying graph theory, which includes a LOT
of colorings. If you have any theoretical question on this subject I'd
be glad to think about it :-)

Nathann

On Oct 31, 11:55 pm, David Joyner <wdjoy...@gmail.com> wrote: