Opened 6 years ago

Closed 6 years ago

#17532 closed PLEASE CHANGE (worksforme)

Convexity properties on graphs works incorrectly

Reported by: azi Owned by: azi
Priority: trivial Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: ncohen Merged in:
Authors: Reviewers:
Report Upstream: Completely fixed; Fix reported upstream Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Hello!

It appears that the convexity properties module gives incorrect results. The hull (geodetic) number of the Petersen graph is 4 while Sage says it is 3.

sage: G.convexity_properties().hull_number(value_only=false)
[4, 7, 8]
sage: G.convexity_properties().hull([4,7,8])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

I have implemented a corrected version of the hull number algorithm that I believe to be faster as well. I'd suggest we make these two function part of the graph class instead of having a separate convexity module.

What do you guys think?

Change History (12)

comment:1 Changed 6 years ago by ncohen

Hello !

I don't get it: I look at Petersen's graph, I look at vertices 4,7,8, and to me their convex hull is the whole graph. If you want to convince me that the answer is not correct, you have to tell me which vertex among the 10 is not in the convex hull of 4,7,8.

Actually, here is how it works for me:

4,7,8 are in the convex hull of 4,7,8

3 is the only neighbor of 4,8, so it is inside 2 is the only neighbor of 7,3, so it is inside 5 is the only neighbor of 7,8, so it is inside 9 is the only neighbor of 4,7, so it is inside 6 is the only neighbor of 7,9, so it is inside 1 is the only neighbor of 2,6, so it is inside 0 is the only neighbor of 4,1, so it is inside

As a conclusion, the hull number of Petersen's graph cannot be 4 :-P

Nathann

comment:2 follow-up: Changed 6 years ago by azi

I have verified the result in 4ways

  1. By implementing a different algorithm and getting 4 as an answer
  2. By drawing the solution given by sage and seeing that it does not give the whole graph
  3. Arguing as follows. In the Petersen graph any pair of vertices is connected by a UNIQUE shortest path and has diameter 2. Hence 3 vertices give you a hull of size at most 3+ (3 \choose 2)*1 = 9
  4. By checking this paper http://ajc.maths.uq.edu.au/pdf/26/ajc_v26_p011.pdf where it says that the Petersen graph has hull number 4.

Best,

Jernej

comment:3 in reply to: ↑ 2 Changed 6 years ago by ncohen

  1. By implementing a different algorithm and getting 4 as an answer
  2. By drawing the solution given by sage and seeing that it does not give the whole graph
  3. Arguing as follows. In the Petersen graph any pair of vertices is connected by a UNIQUE shortest path and has diameter 2. Hence 3 vertices give you a hull of size at most 3+ (3 \choose 2)*1 = 9
  4. By checking this paper http://ajc.maths.uq.edu.au/pdf/26/ajc_v26_p011.pdf where it says that the Petersen graph has hull number 4.

The paper you cite talks about the geodetic number, not the hull number. The computation that you do in 3 is only correct for the geodetic number. Thus I tend to think that the same reason explains 1 and 2 as well.

Nathann

comment:4 follow-up: Changed 6 years ago by azi

Ooooh, but what is the thing with the cited paper about the geodetic number? Isnt that the same thing?

comment:5 in reply to: ↑ 4 Changed 6 years ago by ncohen

Ooooh, but what is the thing with the cited paper about the geodetic number? Isnt that the same thing?

No, as you can see the hull number of Petersen's graph is 3, while is geodetic number is 4 :-P

More seriously, in one case you take a set S, and add to it all points that are on a shortest uv-path, where u,v\in S.

In the second case, after having added those vertices you repeat the procedure again with the extended set S, then again, then again, then again, until you don't add anything new.

This second (larger) set is the convex hull of your initial set of points.

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:6 follow-up: Changed 6 years ago by azi

Ooooh. So the convex hull of S is *not* the set of all vertices that lie on a shortest path between any u,v in S?

comment:7 in reply to: ↑ 6 Changed 6 years ago by ncohen

Ooooh. So the convex hull of S is *not* the set of all vertices that lie on a shortest path between any u,v in S?

Indeed, it is strictly larger than that in some cases. It is an iterated procedure.

Nathann

comment:8 Changed 6 years ago by azi

Ohhh I got confused by the cited paper then I thought its the same notion.

Closing this as fixed!

comment:9 Changed 6 years ago by azi

  • Owner changed from (none) to azi
  • Priority changed from critical to trivial
  • Report Upstream changed from N/A to Completely fixed; Fix reported upstream
  • Type changed from defect to PLEASE CHANGE

comment:10 Changed 6 years ago by ncohen

  • Milestone changed from sage-6.5 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

The way to 'close' a ticket is to set its milestone to wontfix and to change its status to positive_review. THeeeeeen the release manager will close it.

Good evening,

Nathann

comment:11 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:12 Changed 6 years ago by vbraun

  • Resolution set to worksforme
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.