Opened 16 months ago

Closed 11 months ago

Last modified 11 months ago

#30728 closed enhancement (fixed)

Drawing generalizations of generalized Petersen graphs

Reported by: gh-NinaKl Owned by: gh-NinaKl
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: gh-vipul79321 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 16 months ago by gh-NinaKl

  • Branch set to u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs

comment:2 Changed 16 months ago by gh-NinaKl

  • Authors set to Nina Klobas
  • Commit set to 7f3ef45d91838eccdc0e97a524800df92b7afb79
  • Component changed from PLEASE CHANGE to graph theory
  • Type changed from PLEASE CHANGE to enhancement

New commits:

7f3ef45Added nice drawings for 4 graph families

comment:3 Changed 16 months ago by gh-NinaKl

  • Owner changed from (none) to gh-NinaKl

comment:4 Changed 16 months ago by gh-NinaKl

  • Status changed from new to needs_review

comment:5 Changed 16 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_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 16 months ago by git

  • Commit changed from 7f3ef45d91838eccdc0e97a524800df92b7afb79 to d5b51a0369da31db3078e5b5352eda52f1f581c9

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

d5b51a0Better structure of code

comment:7 Changed 16 months ago by gh-NinaKl

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

comment:8 Changed 16 months ago by dcoudert

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 16 months ago by gh-vipul79321

  • Cc gh-vipul79321 added

comment:10 Changed 15 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:11 Changed 13 months ago by dcoudert

  • Branch changed from u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs to public/graphs/30728_drawings
  • Commit changed from d5b51a0369da31db3078e5b5352eda52f1f581c9 to a2948cdcda637ba5a43646d53ba99afcb032fe44
  • Status changed from needs_work to needs_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 13 months ago by git

  • Commit changed from a2948cdcda637ba5a43646d53ba99afcb032fe44 to 0d739ba082b679d266731e50e3709dbef5b1ee10

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

0d739batrac #30728: fix block issue

comment:13 Changed 13 months ago by dcoudert

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

comment:14 Changed 12 months ago by dcoudert

  • Status changed from needs_review to positive_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 11 months ago by vbraun

  • Branch changed from public/graphs/30728_drawings to 0d739ba082b679d266731e50e3709dbef5b1ee10
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:16 Changed 11 months ago by slelievre

  • Commit 0d739ba082b679d266731e50e3709dbef5b1ee10 deleted

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.