Opened 2 years ago

Closed 21 months ago

Last modified 21 months ago

#30728 closed enhancement (fixed)

Drawing generalizations of generalized Petersen graphs

Reported by: Nina Klobas Owned by: Nina Klobas
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: vipul73921 Merged in:
Authors: Nina Klobas Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 0d739ba (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges


Change History (16)

comment:1 Changed 2 years ago by Nina Klobas

Branch: u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs

comment:2 Changed 2 years ago by Nina Klobas

Authors: Nina Klobas
Commit: 7f3ef45d91838eccdc0e97a524800df92b7afb79
Component: PLEASE CHANGEgraph theory
Type: PLEASE CHANGEenhancement

New commits:

7f3ef45Added nice drawings for 4 graph families

comment:3 Changed 2 years ago by Nina Klobas

Owner: set to Nina Klobas

comment:4 Changed 2 years ago by Nina Klobas

Status: newneeds_review

comment:5 Changed 2 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewneeds_work


Thank you for contributing new graphs with nice embeddings.

Several improvements are needed in your code (which contains errors). I'm putting below a nicer and corrected version of method IGraph. Use it to improve the code of the other methods.

def IGraph(n, j, k):
    Return an I-graph with `2n` nodes.

    The variables `n`, `j`, `k` are integers such that `n > 2` and
    `0 < j, k \leq \lfloor (n - 1) / 2 \rfloor`.
    When `j = 1` the resulting graph is isomorphic to the generalized Petersen
    graph with the same `n` and `k`.


    - ``n`` -- the number of nodes is `2 * n`

    - ``j`` -- integer `0 < j \leq \lfloor (n-1)/2 \rfloor`. Decides how outer
      vertices are connected.

    - ``k`` -- integer `0 < k \leq \lfloor (n-1)/2 \rfloor`. Decides how inner
      vertices are connected.

    PLOTTING: Upon construction, the position dictionary is filled to override
    the spring-layout algorithm. By convention, the I-graphs are displayed as an
    inner and outer cycle pair, with the first n nodes drawn on the outer
    circle.  The first (0) node is drawn at the top of the outer-circle, moving
    counterclockwise after that. The inner circle is drawn with the (n)th node
    at the top, then counterclockwise as well.


    When `j = 1` the resulting graph will be isomorphic to a generalized
    Petersen graph::

        sage: g = graphs.IGraph(7,1,2)
        sage: g2 = GeneralizedPetersenGraph(7,2)
        sage: g.is_isomorphic(g2)
    if n < 3:
        raise ValueError("n must be larger than 2")
    if j < 1 or j > (n - 1) // 2:
        raise ValueError("j must be in 1 <= j <= floor((n - 1) / 2)")
    if k < 1 or k > (n - 1) // 2:
        raise ValueError("k must be in 1 <= k <= floor((n - 1) / 2)")

    G = Graph(2 * n, name="I-graph (n={}, j={}, k={})".format(n, j, k))
    for i in range(n):
        G.add_edge(i, (i + j) % n)
        G.add_edge(i, i + n)
        G.add_edge(i + n, n + (i + k) % n)
    G._circle_embedding(list(range(n)), radius=1, angle=pi/2)
    G._circle_embedding(list(range(n, 2*n)), radius=.5, angle=pi/2)
    return G

Could you also explain what is a IGraph ? For me this name is confusing since there is a graph library called igraph. Is it the most appropriate name ?

comment:6 Changed 2 years ago by git

Commit: 7f3ef45d91838eccdc0e97a524800df92b7afb79d5b51a0369da31db3078e5b5352eda52f1f581c9

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

d5b51a0Better structure of code

comment:7 Changed 2 years ago by Nina Klobas

Regarding the definition of I-graphs one could check page 2 of the following paper.

comment:8 Changed 2 years ago by David Coudert

You should add references to the definitions of these graphs. See e.g., #11736 for examples.

Also add a EXAMPLES: block to all methods.

comment:9 Changed 2 years ago by vipul73921

Cc: vipul73921 added

comment:10 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:11 Changed 2 years ago by David Coudert

Branch: u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphspublic/graphs/30728_drawings
Commit: d5b51a0369da31db3078e5b5352eda52f1f581c9a2948cdcda637ba5a43646d53ba99afcb032fe44
Status: needs_workneeds_review

I have rebased the branch on sage 9.3.beta5 performed several corrections / improvements. In particular, I have added missing references and updated some definitions to fit the original papers.

New commits:

f60310ctrac #30728: merge with 9.3.beta5
a2948cdtrac #30728: review commit

comment:12 Changed 2 years ago by git

Commit: a2948cdcda637ba5a43646d53ba99afcb032fe440d739ba082b679d266731e50e3709dbef5b1ee10

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

0d739batrac #30728: fix block issue

comment:13 Changed 2 years ago by David Coudert

For me this patch is now good to go, but a double check would be appreciated.

comment:14 Changed 22 months ago by David Coudert

Status: needs_reviewpositive_review

I give this ticket a positive review. I did review edit to fix some issues and we have green bot since several weeks.

comment:15 Changed 21 months ago by Volker Braun

Branch: public/graphs/30728_drawings0d739ba082b679d266731e50e3709dbef5b1ee10
Resolution: fixed
Status: positive_reviewclosed

comment:16 Changed 21 months ago by Samuel Lelièvre

Commit: 0d739ba082b679d266731e50e3709dbef5b1ee10

Some "TESTS" blocks have a single colon : instead of double colon ::.

Please fix in follow-up ticket #31461.

Note: See TracTickets for help on using tickets.