The geodetic closure of a graph

[sagetrac-azi]

Hello!

The plan is to ship the algorithm for the minimal geodetic set of a graph but first let me try to sell this simple method for computing the geodetic closure of a (di) graph.

Let me know if there are any bugs/suggestions for this contribution.

CC: @nathanncohen

Component: graph theory

Author: Jernej Azarija, David Coudert

Branch/Commit: 6da082a

Reviewer: Travis Scrimshaw

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

[sagetrac-azi]

Branch: u/azi/geodeticClosure

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b8709f3

trac #17537: Added method to compute the geodetic closure of a (di)graph

[sagetrac-git]

Commit: b8709f3

[sagetrac-git]

Changed commit from b8709f3 to 04f0332

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

04f0332

trac #17537: Added missing description in the header of generic_graph.py

[nathanncohen]

comment:5

Hmmm... Calling "distances_all_pairs" in a function like that is a suicide. You cannot re-compute all distances every time you want to compute a closure. Actually, the information that you need is precisely the one that is stored in convexity_properties.

The "convexity properties" object associates to every pair of vertices u,v the bitset of all z such that z is on a shortest uv path. Thus if you need to find the closure of a set of points, all you have to do is compute the union (with 'or' processor operations) of the bitsets associated to all pairs of vertices.

My point is that the code is already there, but of course the name 'convexity properties' is very ill-chosen in this case. We will probably have to change the terminology... What do you think about all this ?

By the way, is the terminology 'closure' used anywhere ? Because formally it is not a closure function. One of the property of closure functions is that f(f(X)) should be equal to f(x).

Nathann

[sagetrac-azi]

comment:6

Replying to @nathanncohen:

Hmmm... Calling "distances_all_pairs" in a function like that is a suicide. You cannot re-compute all distances every time you want to compute a closure. Actually, the information that you need is precisely the one that is stored in convexity_properties.

That's true, though we can make for an optional argument DP that lets you pass the distance dictionary in case anyone really needs to compute this often.

The "convexity properties" object associates to every pair of vertices u,v the bitset of all z such that z is on a shortest uv path. Thus if you need to find the closure of a set of points, all you have to do is compute the union (with 'or' processor operations) of the bitsets associated to all pairs of vertices.

I see.

My point is that the code is already there, but of course the name 'convexity properties' is very ill-chosen in this case. We will probably have to change the terminology... What do you think about all this ?

Fine to me. As far as my preferences go I'd like convexity properties to be part of the graph/generic graph family and cache this stuff in some other way. Having a module like that for just a few functions seems a bit unnatural to me?

By the way, is the terminology 'closure' used anywhere ? Because formally it is not a closure function. One of the property of closure functions is that f(f(X)) should be equal to f(x).

Yes it appears that this is the standard way to call it. See for example the paper "On pitfalls in computing the geodetic number of a graph" by Hansen and van Omme.

Nathann

[nathanncohen]

comment:7

Yo !

Fine to me. As far as my preferences go I'd like convexity properties to be part of the graph/generic graph family and cache this stuff in some other way. Having a module like that for just a few functions seems a bit unnatural to me?

Yes, it is a bad implementation. I can say it, it's mine. It is ugly. I needed someplace to store this bitset, and I did not know where.

Yes it appears that this is the standard way to call it. See for example the paper "On pitfalls in computing the geodetic number of a graph" by Hansen and van Omme.

Weird O_o

Nathann

[sagetrac-azi]

comment:8

Replying to @nathanncohen:

Yo !

Hiiii

Fine to me. As far as my preferences go I'd like convexity properties to be part of the graph/generic graph family and cache this stuff in some other way. Having a module like that for just a few functions seems a bit unnatural to me?

Yes, it is a bad implementation. I can say it, it's mine. It is ugly. I needed someplace to store this bitset, and I did not know where.

So what do you suggest that we do?

Yes it appears that this is the standard way to call it. See for example the paper "On pitfalls in computing the geodetic number of a graph" by Hansen and van Omme.

Weird O_o

:-)

Nathann

[nathanncohen]

comment:9

So what do you suggest that we do?

We rename convexity_properties to geodetic_properties and you add your geodetic_closure function there ? :-P

It is a bad design, but I still don't know how to implement it otherwise ^^;

Nathann

[nathanncohen]

comment:10

http://en.wikipedia.org/wiki/Closure_%28mathematics%29

They also agree that a closure operator should be idempotent. Cursed wrong terminology. If we have a geodetic_closure function we must remember to add a big warning saying that this operation is NOT a closure, and blame those guys while citing the reference :-P

Nathann

[sagetrac-azi]

comment:11

Replying to @nathanncohen:

So what do you suggest that we do?

We rename convexity_properties to geodetic_properties and you add your geodetic_closure function there ? :-P

Okay. Do you also want to do it your way with the bitfields present there or use the thing I pushed here? In the former case I suppose its much better if you just put it in as you already know the code?

It is a bad design, but I still don't know how to implement it otherwise ^^;

:-P

Nathann

[nathanncohen]

comment:12

Yo !

Okay. Do you also want to do it your way with the bitfields present there or use the thing I pushed here? In the former case I suppose its much better if you just put it in as you already know the code?

Sorry I can't do that now... Juggling with many computers at once and a slideshow to get ready for tomorrow. Can you do it ? Really it is nothing very complicated, and you should find inside some very similar function that computes the hull of a set of vertices. The geodetic is even simpler.

Nathann

[sagetrac-azi]

comment:13

yoo,

Okay hopefully I manage to do it by today.

Good luck with presentation :-)

Jernej

[dcoudert]

Changed commit from 04f0332 to 475e605

[dcoudert]

Changed author from Jernej Azarija to Jernej Azarija, David Coudert

[dcoudert]

Changed branch from u/azi/geodeticClosure to public/graphs/17537_geodetic_closure

[dcoudert]

comment:14

I pushed a new branch with a more efficient implementation (in Cython). In particular, it does not require to compute and store the full distance matrix, and so can be used on quite large graphs. It is so far for undirected graphs only.

---

New commits:

475e605

trac #17537: geodesic closure in Cython

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8bac332

trac #17537: prevent calling this method on digraphs

[sagetrac-git]

Changed commit from 475e605 to 8bac332

[dcoudert]

comment:16

Add not implemented error when calling this method on digraphs.

[slel]

comment:17

Geodesic or geodetic?

[dcoudert]

comment:18

The term used in the field is geodetic https://doi.org/10.1016/0895-7177(93)90259-2. Don't know why...

[tscrim]

comment:19

LGTM.

If you care enough, I believe there is a typo in this comment:

# Copy the graph has a short digraph

[tscrim]

Reviewer: Travis Scrimshaw

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

6eb2a53	trac #17537: merged with 9.5.beta2
6da082a	trac #17537: typo

[sagetrac-git]

Changed commit from 8bac332 to 6da082a

[dcoudert]

comment:21

I fixed the typo. Let me know if I should set the ticket back to needs review.

Thank you for the review.

[tscrim]

comment:22

Trac does it automatically with the push.

[vbraun]

Changed branch from public/graphs/17537_geodetic_closure to 6da082a