Distance matrix

[sagetrac-azi]

Hello!

We have the adjacency_matrix and kirchhoff_matrix methods for graphs. I am very much missing a method for the distance_matrix since in the current project I am working with requires us to study some algebraic proprieties of the distance matrix.

It is obviously trivial to implement independently but I am tired of writing distance_matrix(G) all the time.

So before adding a patch implementing that I am wondering if you other guys agree with that and if perhaps I have overlooked that functionality.

Apply:

• attachment: trac_14056_distancem.patch
• attachment: trac_14056_distancem.2.patch
• attachment: trac_14056-rev.patch

CC: @rbeezer @nathanncohen @dcoudert @Stefan

Component: graph theory

Author: Jernej Azarija

Reviewer: Nathann Cohen

Merged: sage-5.10.beta5

Issue created by migration from https://trac.sagemath.org/ticket/14056

[dcoudert]

comment:1

So far you can get the distances as a dict of dict but not as a matrix.

I think it could be useful.

[rbeezer]

comment:2

I also think this would be useful. The dict of dicts is a bit cumbersome to work with sometimes.

Plus, it would be nice to have

• the 0-1 matrix for vertex pairs at distance i apart (the adjacency matrix of the distance graphs, which are implemented)

• the actual set (list) of vertices at distance i from a given vertex v

You might give some thought to the name, I tend to think of "distance matrix" as the 0-1 matrix just above and not the matrix of distances, even though that is a perfectly rational choice. matrix_of_distances?

[sagetrac-azi]

comment:3

Thanks for the feedback guys!

As far as the name goes, I would like to have distance_matrix for the distance matrix since this is usually what it is referred to in graph theory (http://en.wikipedia.org/wiki/Distance_matrix)

As for the (0,1)-matrix of vertices at distance i, this sounds like a generalization of the adjacency_matrix and I would suggest it is implemented by introducing an additional parameter to adjacency_matrix. Like

def adjacency_matrix(self, pairs_at_dist=1):

What you guys think?

[nathanncohen]

comment:4

Hello !

Well, I think that it is a matrix only if all vertices are numbered from 0 to n-1, which is not the case in Sage. The reason why distance_all_pairs returns a dict of dict is precisely because vertices are not necessarily integers.

If you prefer to have a matrix instead, and because I am always scared of the number of functions we have in graph, I would prefer (whatever you want the future name to be.. By the way distance_matrix is nice indeed) that distance_all_pairs disappear, and become an optional result of distance_matrix.

Like distance_matrix(as_dictionary = True) ? What do you think of it ?
The point is that distance_all_pairs really is distance_matrix. Vertices just aren't integers.

I had a lot of wine, and a lot of good duck, and a lot of good cheese. I may make more sense tomorrow. Anyway, have fun ! :-)

Nathann

[dcoudert]

comment:5

I agree with distance_matrix returning a matrix and this function could have an argument to return a binary matrix for pairs at distances i.

I disagree with adjacency_matrix returning the binary matrix, and I don't like the proposition of Nathann of a function called distance_matrix able to return a dictionary.

But Nathann is right that the distance_matrix works only for graphs with vertices labeled from 0 to n-1. A solution is to return the map vertex->int as well.

[sagetrac-azi]

comment:6

Hello!

Nathann I don't think its polite to mention your dinner without offering it to us as well!!! At least for the cheese :)))

As for the comments!

The distance matrix is an algebraic object and is not "affected" by the ordering of the vertices. In the same manner as the adjacency_matrix does not return a vertex -> int map.

If you still think it makes to return a map then we could add (analogously to the automorphism_group function) an option "translation=True" in order to return such a map as well. We'd need to add this to the adjacency_matrix() as well for the sake of consistency.

As for the pair at distances k. The adjacency matrix of a graph is defined as the (0,1) matrix such that an entry (i,j) has a 1 if and only if the vertices v_i,v_j are at distance 1. Hence to me it makes pretty much sense to add an option here to generalize this to the case when v_i,v_j are at distance k.

Why don't you agree dcoudert?

Thanks for the comments and have a nice day!

[dcoudert]

comment:7

This is a good idea to return map only if an optional argument is set to True.

For the matrix of vertices at distance k, I don't know which is the best terminology/method. This is also related to the transitive closure of the graph. I let you choose.

You could also have a method returning all such matrices at once to avoid recomputing all the distances.

David.

[nathanncohen]

comment:8

Helloooooooooo !!!

Nathann I don't think its polite to mention your dinner without offering it to us as well!!! At least for the cheese :)))

Sorry about that. I'll be looking for a home in the next months, and you will be welcome there to eat cheese and drink wine to compensate :-)

The distance matrix is an algebraic object and is not "affected" by the ordering of the vertices. In the same manner as the adjacency_matrix does not return a vertex -> int map.

O_o

Well .... How would you get the distance between two vertices of your graph given the adjacency matrix unless you know how they are associated to each other ? ^^;

If you still think it makes to return a map then we could add (analogously to the automorphism_group function) an option "translation=True" in order to return such a map as well. We'd need to add this to the adjacency_matrix() as well for the sake of consistency.

Yep. Less easy to use than what we have right now, but then we uselessly store n times each label. I almost think that what we need is a "LabeledMatrix" class :-D

As for the pair at distances k. The adjacency matrix of a graph is defined as the (0,1) matrix such that an entry (i,j) has a 1 if and only if the vertices v_i,v_j are at distance 1. Hence to me it makes pretty much sense to add an option here to generalize this to the case when v_i,v_j are at distance k.

I think that he would like to have something like pairs_at_distance[i] = [(u,v) for u in g for v in g if g.distance(u,v) == i]. The information is contained in the distance matrix, but not in the same order : it's hard to get the list of allentries equal to i.

My opinion on that is that it is "personal code". Stuff that you need yourself but isn't really relevant for Sage...

Have fuuuuuuuuuuuuuuuuuuuuuuunn !!

Nathann

[sagetrac-azi]

comment:9

Hm..

LabeledMatrix class appears exactly as what we need - that would be nice!

As for the "personal code" remark, I am not sure! The notion of the distance matrix is a standard one in graph theory (http://en.wikipedia.org/wiki/Distance_matrix). If we have the adjacency matrix, Kirchhoff matrix and incidence matrix I don't see a reason why we should not have the distance matrix as well.

In addition, Mathematica has a function returning the distance matrix of a graph (http://mathworld.wolfram.com/GraphDistanceMatrix.html) hence I am not really sure it is just a personal thing of me :)

[nathanncohen]

comment:10

LabeledMatrix class appears exactly as what we need - that would be nice!

You mean that it exists in Sage already ? That would be Cooooooooool !! O_o

As for the "personal code" remark, I am not sure!

???

Nonono, my "personal code" thing was about David's pairs_at_distance_i list of lists of pairs. I mean, we need this for some code we work on, but to me that's just our very specific use case, not something that Sage should natively handle.

Nathann

[sagetrac-azi]

comment:11

Hello!

Attached you will find the patch for the distance matrix and some additional documentation for the incidence matrix.

Let me know if there is anything to fix.

Jernej

[nathanncohen]

comment:12

Attachment: trac_14056_distancem.patch.gz

Well, my comment from 3 months ago about distance_all_pairs for a start.

Nathann

[nathanncohen]

comment:13

I also don't get why the method should only work on strongly connected graphs.

Nathann

[sagetrac-azi]

comment:14

Hello!

As far as I see the distances in a weakly connected digraph are not defined for all pair of vertices!

[nathanncohen]

comment:15

What's wrong with setting those entries to infinity ? And what about merging distances all pairs and the distance matrix into the same function ?

Nathann

[sagetrac-azi]

comment:16

Replying to @nathanncohen:

Well, my comment from 3 months ago about distance_all_pairs for a start.

Nathann

What exactly? I am a bit confused since at that time you had some debate about your research code or something and when I asked about that you said it's related to some code of David?

[nathanncohen]

comment:17

(just merging the distance_all_pairs and distance_matrix. Distance matrix would return the distance matrix by default, and if you ask for labels you would get either a Labeled matrix if such a thing exists somewhere, or the current double dictionary ?)

Nathann

[sagetrac-azi]

comment:18

We can do that as well, though I would then still like to have a method distance_matrix() calling distance_all_pairs with the appropriate argument. At least for consistency with adjacency,incidence and Kirchhoff matrix.

As for infinity.. Well I like to think of these matrices as well defined algebraic objects and I am not even sure if a matrix can digest Infinity as its entry...

[nathanncohen]

comment:19

We can do that as well, though I would then still like to have a method distance_matrix() calling distance_all_pairs with the appropriate argument.

What do you mean ? O_o distance_all_pairs has no argument O_o

At least for consistency with adjacency,incidence and Kirchhoff matrix.

I don't understand what you mean here either.

As for infinity.. Well I like to think of these matrices as well defined algebraic objects and I am not even sure if a matrix can digest Infinity as its entry...

Ookok.. I don't like it, but it makes sense.

Nathann

[sagetrac-azi]

comment:20

Replying to @nathanncohen:

We can do that as well, though I would then still like to have a method distance_matrix() calling distance_all_pairs with the appropriate argument.

What do you mean ? O_o distance_all_pairs has no argument O_o

At least for consistency with adjacency,incidence and Kirchhoff matrix.

I don't understand what you mean here either.

What I meant was that If we choose to put this thing under distance_all_pairs and add an argument returning the distance matrix, then I would still like to have a method called distance_matrix() that would call distance_all_pairs asking for the distance matrix. And I would want to have that since I would like to have a method called distance_matrix() as we do for the other mentioned matrices!

That being said I am now starting to doubt it is a good idea to mix this distance matrix with the shortest path algorithm. Especially if we don't have the indexed matrix thing and since (apperently) infinity is not digested by matrices.

What do you think

As for infinity.. Well I like to think of these matrices as well defined algebraic objects and I am not even sure if a matrix can digest Infinity as its entry...

Ookok.. I don't like it, but it makes sense.

Nathann

[nathanncohen]

comment:21

What I meant was that If we choose to put this thing under distance_all_pairs and add an argument returning the distance matrix, then I would still like to have a method called distance_matrix() that would call distance_all_pairs asking for the distance matrix.

Whaaaattttttt ??O_o

"call distance_all_pairs asking for the distance matrix" ? What does that mean ?

What I described above was a function names "distance_matrix" which returns the distance matrix when no optional flags are given, and which returns the current result of "distance_all_pairs" when an optional flag, say labels = True, is added to it.

And distance_all_pairs would be removed from generic_graph.

What about this ?

And I would want to have that since I would like to have a method called distance_matrix() as we do for the other mentioned matrices!

Is that still contradicting what I said above ? I don't understand it either.

That being said I am now starting to doubt it is a good idea to mix this distance matrix with the shortest path algorithm.

Why would we mix "distance matrix" with a shortest path algorithm ? The distance_all_pairs method is written in Cython and actually creates a C array filled with the content of the distance matrix.

Especially if we don't have the indexed matrix thing and since (apperently) infinity is not digested by matrices.

What do you think

Let's make our previous messages clear for a start :-P

Sorry, I have been exchanging a couple of angry messages this morning so I am probably a bit unpleasant to deal with this morning >_<

Nathann

[sagetrac-azi]

comment:22

Replying to @nathanncohen:

What I meant was that If we choose to put this thing under distance_all_pairs and add an argument returning the distance matrix, then I would still like to have a method called distance_matrix() that would call distance_all_pairs asking for the distance matrix.

Whaaaattttttt ??O_o

"call distance_all_pairs asking for the distance matrix" ? What does that mean ?

What I described above was a function names "distance_matrix" which returns the distance matrix when no optional flags are given, and which returns the current result of "distance_all_pairs" when an optional flag, say labels = True, is added to it.

And distance_all_pairs would be removed from generic_graph.

Oookay now I think I do understand you. Somehow I still like it more the way it is structured now (an algorithmically inclined guy would look for the distance_all_pairs method) a math guy for the distance matrix and since we already have the distance_all_pairs method I don't see any good reasons for removing it.

That said, why would you like this specific change?

What about this ?

And I would want to have that since I would like to have a method called distance_matrix() as we do for the other mentioned matrices!

Is that still contradicting what I said above ? I don't understand it either.

That being said I am now starting to doubt it is a good idea to mix this distance matrix with the shortest path algorithm.

Why would we mix "distance matrix" with a shortest path algorithm ? The distance_all_pairs method is written in Cython and actually creates a C array filled with the content of the distance matrix.

Especially if we don't have the indexed matrix thing and since (apperently) infinity is not digested by matrices.

What do you think

Let's make our previous messages clear for a start :-P

Sorry, I have been exchanging a couple of angry messages this morning so I am probably a bit unpleasant to deal with this morning >_<

Hahaha. No worries, I am also quite tense (GSOC is building unnecessary pressure :S). I can hardly imagining you writing unpleasant emails btw :-)

Nathann

[nathanncohen]

comment:23

Oookay now I think I do understand you. Somehow I still like it more the way it is structured now (an algorithmically inclined guy would look for the distance_all_pairs method) a math guy for the distance matrix and since we already have the distance_all_pairs method I don't see any good reasons for removing it.

That said, why would you like this specific change?

Hmmmmmm... Because we already have far too much functions in the Graph classes to have aliases.
But you convinced me anyway. Let's forget it !

Hahaha. No worries, I am also quite tense (GSOC is building unnecessary pressure :S).

Ahahaha. Well, there's nothing to do before the 27th of May, is there ? ;-)

I can hardly imagining you writing unpleasant emails btw :-)

Ahahahahahah :-D

Half of the world can't, indeed. The other half can't picture me as doing anything else but waste their time. Usually, those are my colleagues :-P

Have fuuuuuuuuuuuuuuuuuuuuunnn !!

Nathann

[nathanncohen]

comment:24

Ok, nowwwwwwwww the review !

• Would be nice to add in the documentation that this method ignores edge labels
• You can probably save some time by replacing

for i in xrange(n): 
    for j in xrange(i+1,n): 
        d = (dist[V[i]])[V[j]] 

with

for i,Vi in enumerate(V.values()): 
    for j,dj in enumerate(Vi.values()):
        d = dj 

I think that you cannot trust the dictionary for returning its elements in the same ordering on all architectures, but you probably can trust it for always returning its elements in the same ordering on the same machines. Especially when you have several dictionaries containing the very same keys. Would be good to check, though. I'll ask on Sage-devel.

• You do not have to import infinity, nor to test equality. If d>n should be enough.
• Could you add a warning in the docstring saying that we do not expect the ordering in the vertices of the matrix to correspond to anything meaningful ? Unless we do expect it to correspond to something meaningul that I can't guess right now ?
• Could you also add a "SEEALSO" field in this method and in distances_all_pairs so that one points toward the other ?

Thinking about it again, if you replace the loop by what I just said, then you cannot save some time by doing ret[i,j] = ret[j,i] = d anymore. Hmmmm... O_o

Nathann

[nathanncohen]

comment:26

Hellooooooo again !

Ok, then this change in the loops is a wrong idea. If you want your "distance_matrix" to run fast on large instances though [1] you could implement the code of this distance_matrix function directly in the distances_all_pairs.pyx file. This way you would not have to go through a dictionary, and more importantly Sage would not create a dictionary from a matrix only to create a matrix from the dictionary afterwards.

Before the dictionary is created, all the data is contained in a C array that is much easier to transform into a matrix than this dictionary.

Not to mention that it takes MUuuuuuuuuuuuchh less space in memory.

Have fuuuuuuuuuuuuuuuuuuuuuuuunnn !!

Nathann

[1] Really, if you want. Otherwise this patch is fine without it

[sagetrac-azi]

comment:27

Helloo!!

For now I'd prefer to leave this as is because I think there are some other places (backend,khm,khm?) in which a speedup fix is required more than here!

[nathanncohen]

comment:28

For now I'd prefer to leave this as is because I think there are some other places (backend,khm,khm?) in which a speedup fix is required more than here!

No prob !

Nathann

[sagetrac-azi]

comment:29

Should we flag this as done then sir??

[nathanncohen]

comment:30

Should we flag this as done then sir??

Well, unless you tell me why you think that all comments about doc and infinity are irrelevant ?...

Nathann

[sagetrac-azi]

comment:31

They were irrelevant because I completely forgot about them sorry. Will fix that I agree with them!

[sagetrac-azi]

comment:32

Btw, should seealso be added like

.. SEEALSO::

 - :meth:`sage.graphs.generic_graph.distance_all_pairs`

[nathanncohen]

comment:33

Btw, should seealso be added like

.. SEEALSO::

 - :meth:`sage.graphs.generic_graph.distance_all_pairs`

I think that it's ok like that, but you should probably check by building the doc (sage -docbuild reference/graph html only builds the graph doc) because it's tricky sometimes. Note that if you write add an ~ in the link then it will only appear as distance_all_pairs and not as sage.graphs.generic_graph.distance_all_pairs

:meth:`~sage.graphs.generic_graph.distance_all_pairs`

It's up to you !

Nathann

[sagetrac-azi]

comment:34

Attachment: trac_14056_distancem.2.patch.gz

Took me a while to make this last changes since I wanted to make sure the docs are rendered properly. I think that the patch fixes everything you suggested.

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:35

Helloooooooooo !!

There were some trailing whitespaces in your patch, and Sage's dogma says that this is wrong. I also added a warning saying that the ordering of vertices in the matrix may not be the ordering of vertices in g.vertices().

If you agree with this patch, then you can set the ticket to positive_review !

Nathann

[nathanncohen]

Author: Jernej Azarija

[nathanncohen]

comment:36

Attachment: trac_14056-rev.patch.gz

[sagetrac-azi]

comment:38

Hello!

I agree with your modifications. Thank you for the review.

Jernej

[jdemeyer]

Merged: sage-5.10.beta5