Fix is_interval() on graphs

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Unify certificate=True: in every function return a pair where first element is a Boolean.

Also add definition of interval graph and a link to Wikipedia page.

CC: @dcoudert @kevindilks @fchapoton

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: 98782ab

Reviewer: David Coudert

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/fix_is_interval___on_graphs

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: 3c99bb1

[f29946bc-ee7b-48cd-9abc-3445948c551d]

New commits:

3c99bb1

Modify docs etc.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Author: Jori Mäntysalo

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

fcce7d0

Merge branch 'develop' into t/24446/fix_is_interval___on_graphs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c99bb1 to fcce7d0

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:4

Three lines to code, several to docs. Easy to review.

I changed this test:

sage: n = 8
sage: count = [0]*(n+1)
sage: for g in graphs(n, augment='vertices',property= lambda x:x.is_interval()): # not tested -- 50s
....:     count[g.order()] += 1                                                  # not tested -- 50s
sage: count                                                                      # not tested -- 50s
[1, 1, 2, 4, 10, 27, 92, 369, 1807]

I think it is not a good test, even if it is good way to generate interval graphs.

[dcoudert]

comment:6

Some comments

You should

• move See :wikipedia:`Interval_graph` for more information. to the SEEALSO block.

• add link to is_chordal, IntervalGraph, RandomIntervalGraph in see also block

• The Petersen Graph is not chordal, so in can't -> The Petersen Graph is not chordal, so it can't

• Enumerate all small interval graphs:: -> Enumerate all small interval graphs (see :oeis:`A005975`)::

• then remove Compare to A005975 in OEIS.

• I'm not sure of the interest of the line sage: print(d)

you may remove some [ ] in the code, for instance:

• set([]) -> set()
• dict([(v, (beg[v], end[v])) for v in self]) -> {v: (beg[v], end[v]) for v in self}

[dcoudert]

Reviewer: David Coudert

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:7

Replying to @dcoudert:

• move See :wikipedia:`Interval_graph` for more information. to the SEEALSO block.

Of 21 Wikipedia links on the doc page only one, is_self_complementary, has the link in SEEALSO block. So I think this should discussed on sage-devel and to be done in all functions.

I will do other changes.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b658d78

Reviewer's comments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fcce7d0 to b658d78

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:9

What' wrong with my links? References seems to be broken.

(Patch contains a non-related colon in is_immutable() doc.)

[dcoudert]

comment:10

It should be :meth: and not :func:, right?

I'm always having difficulties with links to methods. Here the last 2 don't turn to links in the html doc. Don't know why.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:11

Replying to @dcoudert:

It should be :meth: and not :func:, right?

I tried that too, no help.

Frédéric, what's wrong with my links?

[fchapoton]

comment:12

Sorry, I have no idea either, and I usually don't build the doc.

[dcoudert]

comment:13

This form is working for me !!!

            - :meth:`~sage.graphs.graph_generators.GraphGenerators.IntervalGraph`
            - :meth:`~sage.graphs.graph_generators.GraphGenerators.RandomIntervalGraph`

If you follow the links, you may discover another issue: in the html file .../graphs/graph_generators.html the name of many methods is preceded by static, like static IntervalGraph(intervals, points_ordered=False). Don't remember if it was the case before. May be a side effect of some recent change ? or it's due to the call to staticmethod ?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

98782ab

Links in doc.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b658d78 to 98782ab

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:15

Thanks David!

I mark this as needs_review, because I think that the case for Wikipedia links should be handled for all functions, if at all.

[dcoudert]

comment:16

This looks good to me.

[vbraun]

Changed branch from u/jmantysalo/fix_is_interval___on_graphs to 98782ab