Graphs in Sage : labels on edges and vertices
Nathann Cohen
I have been working with graphs in Sage for some time now, and I have
a few remarks about how labels are defined in Graphs ( I may be wrong
as I do not think I know ALL about graphs in Sage, so please tell me
when I'm wrong ) :
- Vertices do not have any kind label. They just have names.
- Edges have labels of the form (u,v,label)
Well. Most of the time, I do not care about labels in graphs, and I do
not like the fact that I have to write :
for (u,v,l) in g.edges():
To iterate over the edges, always ignoring the last variable 'l'. It
is weird to see an information appear where is never has to be used.
You think this is just a unimportant remark, which is faaaaaaar from
being one of the worst problems sage has ? I agree :-)
The thing is that this label on the edges is the only way I know to
deal with weighted graphs. And that I do not have the slightest idea
of how to deal with graphs whose weights are associated to vertices
instead of edges ( algorithms such as cliquer, or all the Linear
Programming related graphs, deal with Weighted cliques, or Weighted
cover, etc, etc ), and I see no clean way to implement functions
dealing with vertex-weighted graphs.
Actually, my question is the following : would it be a problem to have
classes like Vertex, or Edge which would encode these data in a
Graph ? It would also solve another problem : an edge (a,b) is
sometimes returned as (b,a), and one has to check whether the two are
equal.
It would also let us define a numbering on the vertices totally
independent from the labels... Many graphs algorithms are easy to
implement when the vertices have names from [0,1,...,n-1], and the
current "solution" when one has to build a function on an unknown
graph is to first build a copy of that graph which would be correctly
labeled, apply the algorithm and then return an answer according to
the original graph's labels.
Well, I just sent this message to gather thoughts about these things
and begin to think about how to fix it. I only have my own experience,
for the moment, so I need your help to devise a not-too-bad answer to
all that :-)
Thankkkkkks !!!
Nathann
Copying a graph just to ensure it is correctly labeled is not an
elegant way to code for me ^^;
Jason Grout
> Hello everybody !!!
>
> I have been working with graphs in Sage for some time now, and I have
> a few remarks about how labels are defined in Graphs ( I may be wrong
> as I do not think I know ALL about graphs in Sage, so please tell me
> when I'm wrong ) :
>
> - Vertices do not have any kind label. They just have names.
> - Edges have labels of the form (u,v,label)
>
> Well. Most of the time, I do not care about labels in graphs, and I do
> not like the fact that I have to write :
> for (u,v,l) in g.edges():
>
> To iterate over the edges, always ignoring the last variable 'l'. It
> is weird to see an information appear where is never has to be used.
>
> You think this is just a unimportant remark, which is faaaaaaar from
> being one of the worst problems sage has ? I agree :-)
That has bothered me every time I use g.edges, since
g.edges(labels=False) looks clunky, and I don't think I've ever needed
the weights.
>
> The thing is that this label on the edges is the only way I know to
> deal with weighted graphs. And that I do not have the slightest idea
> of how to deal with graphs whose weights are associated to vertices
> instead of edges ( algorithms such as cliquer, or all the Linear
> Programming related graphs, deal with Weighted cliques, or Weighted
> cover, etc, etc ), and I see no clean way to implement functions
> dealing with vertex-weighted graphs.
>
> Actually, my question is the following : would it be a problem to have
> classes like Vertex, or Edge which would encode these data in a
> Graph ? It would also solve another problem : an edge (a,b) is
> sometimes returned as (b,a), and one has to check whether the two are
> equal.
I have really liked having vertices and edges just be generic hashable
objects and tuples, respectively. It strips one layer of complexity
away from using graphs.
>
> It would also let us define a numbering on the vertices totally
> independent from the labels... Many graphs algorithms are easy to
> implement when the vertices have names from [0,1,...,n-1], and the
> current "solution" when one has to build a function on an unknown
> graph is to first build a copy of that graph which would be correctly
> labeled, apply the algorithm and then return an answer according to
> the original graph's labels.
Well, usually you just store a mapping between [0..n-1] to the labels,
then apply the reverse map to the output list of integers. You
hopefully shouldn't need to construct a graph.
>
> Well, I just sent this message to gather thoughts about these things
> and begin to think about how to fix it. I only have my own experience,
> for the moment, so I need your help to devise a not-too-bad answer to
> all that :-)
I would *strongly* recommend looking at the API for networkx 1.0.
They've just dealt with this issue of weights and other metadata, and at
least on the surface, they have a nice, consistent way of dealing with it.
See http://networkx.lanl.gov/reference/api_1.0.html for a short description.
Now, this is a new API for them; I was going to wait a few months to see
if they had any problems with it before proposing we look at redesigning
our graph classes.
Our model is roughly based after Networkx 0.36. Networkx also made some
huge simplifications in the move to 0.99, so that documentation also
might give some big hints on places where it makes sense to simplify or
consolidate or change things. See
http://networkx.lanl.gov/reference/api_0.99.html
>
> Thankkkkkks !!!
>
> Nathann
>
> Copying a graph just to ensure it is correctly labeled is not an
> elegant way to code for me ^^;
I'm not sure how your proposal fixes things. Say I have a graph that is
labeled [0, 1, 2, 3, 4, 5]. I then delete vertices 2 and 3. Now I have
a graph [0, 1, 4, 5], and I still have to do the vertex mapping to get
to a graph [0, 1, 2, 3] before applying an algorithm. Am I not
understanding something?
Thanks,
Jason