The geodetic closure of a graph

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

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

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

Branch: u/azi/geodeticClosure

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Commit: b8709f3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from b8709f3 to 04f0332

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 9 years ago

comment:13

yoo,

Okay hopefully I manage to do it by today.

Good luck with presentation :-)

Jernej

dcoudert commented 3 years ago

Changed commit from 04f0332 to 475e605

dcoudert commented 3 years ago

Changed author from Jernej Azarija to Jernej Azarija, David Coudert

dcoudert commented 3 years ago

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

dcoudert commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

8bac332 trac #17537: prevent calling this method on digraphs

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 475e605 to 8bac332

dcoudert commented 3 years ago

comment:16

Add not implemented error when calling this method on digraphs.

slel commented 3 years ago

comment:17

Geodesic or geodetic?

dcoudert commented 3 years ago

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 commented 3 years ago

comment:19

LGTM.

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

# Copy the graph has a short digraph

tscrim commented 3 years ago

Reviewer: Travis Scrimshaw

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 8bac332 to 6da082a

dcoudert commented 3 years ago

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 commented 3 years ago

comment:22

Trac does it automatically with the push.

vbraun commented 3 years ago

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

sagemath / sage

The geodetic closure of a graph #17537