Generalized Sierpinski graphs generator

[dcoudert]

See https://ask.sagemath.org/question/62417/generalized-sierpinski-graph-construction/

CC: @sagetrac-tmonteil @fchapoton

Component: graph theory

Author: David Coudert

Branch/Commit: 11c69b7

Reviewer: Thierry Monteil, Frédéric Chapoton

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

[dcoudert]

New commits:

4d4f224

trac #33854: generalized Sierpinski graphs

[dcoudert]

Branch: public/graphs/33854_sierpinski

[dcoudert]

Commit: 4d4f224

[dcoudert]

comment:2

To get the Sierpinski graph S(n, k), it suffices to call GeneralizedSierpinskiGraph with a clique of order n.

[prajnanaswaroopa]

comment:4

The source code as given on the GitHub page, gives the error object of type 'int' has no len().

[dcoudert]

comment:5

Which parameters have you used ? It's impossible for me to guess from your message.

Have you read and followed the description of the method ?

[prajnanaswaroopa]

comment:6

I used the parameters H=graphs.CompleteGraph(4), kk=2. I tried to modify the code to make it somehow work by changing next(H.vertex_iterator()) to H.order() and the lineJ = H.relabel(perm={u: (i,) + u for u in H}, inplace=False) to J = H.relabel(perm={u: (i,u) for u in H}, inplace=False). But the graph output is not as expected. On only changing next(H.vertex_iterator to H.order(), the error is can only concatenate tuple, not 'int' to tuple.

[dcoudert]

comment:7

Can you clarify what you expect ?

The code in this ticket strictly follows the definition given in the paper by Gravier, Kovse and Parreau, and we can get all the examples given in the papers about generalized Sierpinski graphs. For your parameters, we get:

sage: G = GeneralizedSierpinskiGraph(graphs.CompleteGraph(4), 2)
sage: print(G.vertices())
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3)]
sage: print(G.edges(labels=False))
[((0, 0), (0, 1)), ((0, 0), (0, 2)), ((0, 0), (0, 3)), ((0, 1), (0, 2)), ((0, 1), (0, 3)), ((0, 1), (1, 0)), ((0, 2), (0, 3)), ((0, 2), (2, 0)), ((0, 3), (3, 0)), ((1, 0), (1, 1)), ((1, 0), (1, 2)), ((1, 0), (1, 3)), ((1, 1), (1, 2)), ((1, 1), (1, 3)), ((1, 2), (1, 3)), ((1, 2), (2, 1)), ((1, 3), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (2, 2)), ((2, 0), (2, 3)), ((2, 1), (2, 2)), ((2, 1), (2, 3)), ((2, 2), (2, 3)), ((2, 3), (3, 2)), ((3, 0), (3, 1)), ((3, 0), (3, 2)), ((3, 0), (3, 3)), ((3, 1), (3, 2)), ((3, 1), (3, 3)), ((3, 2), (3, 3))]

If you want another construction, please give its formal definition.

[prajnanaswaroopa]

comment:8

Where are you able to run the function? I mean, do you use the Sage compiler, or, you use some other kernel to run the command GeneralizedSierpinskiGraph(,). Or, did you write the full source code and then run the function?

[dcoudert]

comment:9

I copy/paste the method in a sagemath console, but you can also use a Jupyter notebook running sagemath kernel.

[prajnanaswaroopa]

comment:10

Thanks! I copied the whole source code from Git Hub page, and it worked well. Hope this get pushed to Sage repository soon.

[dcoudert]

comment:11

feel free to help reviewing this ticket.

[sagetrac-tmonteil]

comment:12

This is only a tiny contribution to the review, since i did not check the code. Here are some typos:

• "Sierpiński" : the accent is over the n, not the s
• "pervertex"

Also, the motivation for such a construction seems to be geometrical. So, if the vertices of a graph have planar positions, then so should its generalized Sierpiński image. For example, with the house graph of the poster:

graphs.HouseGraph().plot()

but

graphs.GeneralizedSierpinskiGraph(graphs.HouseGraph(),2).plot()

[sagetrac-tmonteil]

Reviewer: Thierry Monteil

[sagetrac-tmonteil]

comment:13

Also, if you add crosslinks to SierpinskiGasketGraph and HanoiTowerGraph, perhaps should there also be links to GeneralizedSierpinskiGraph from those constructions.

[sagetrac-git]

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

70e0c21	trac #33854: merged with 9.7.beta1
30623b4	trac #33854: typo and crosslinks

[sagetrac-git]

Changed commit from 4d4f224 to 30623b4

[dcoudert]

comment:15

• "Sierpiński" : the accent is over the n, not the s

I'm unable to locate the typo

I agree that it would be nice to provide the nice embedding, but I I don't know how to do that.

[sagetrac-tmonteil]

comment:16

Replying to @dcoudert:

• "Sierpiński" : the accent is over the n, not the s

I'm unable to locate the typo

Oh, it seems that the trac text editor and the gitweb moved the accent, see sagemath/sagetrac-mirror@5fb2a6e...30623b4 (8 occurrences).

I agree that it would be nice to provide the nice embedding, but I I don't know how to do that.

If you have a graph of depth 3, any vertex comes from 3 vertices (i,j,k), one for each depth. You can set the position of that vertex to pos(i) + K*pos(j) + K^2*pos(k) where K > 1 is some stretching factor, that could be set by the user or its default value could be computed as, say, twice the geometrical diameter of the graph.

[sagetrac-git]

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

b9645b2

trac #33854: set positions

[sagetrac-git]

Changed commit from 30623b4 to b9645b2

[dcoudert]

comment:18

I followed your idea. We can get some nice plots.

[sagetrac-tmonteil]

comment:24

I was thinking of a better placement formula, since some pictures are not well rendered, but it will be for a future ticket.

[vbraun]

comment:25

pdf docs don't build

[sagetrac-git]

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

60d010a	trac #33854: Merged with 9.7.beta3
a830e0c	trac #33854: correct accent in index.rst

[sagetrac-git]

Changed commit from a6602f3 to a830e0c

[sagetrac-git]

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

5540573

trac #33854: correct another accent in index.rst

[sagetrac-git]

Changed commit from a830e0c to 5540573

[dcoudert]

comment:28

Now the problem is the accent in Sierpiński in families.py. What's the trick to put it ? the alternative is to remove it.

[dcoudert]

comment:29

@ Frédéric, do you know how to add utf8 symbols to the documentation of a method without breaking the pdf doc ?

[fchapoton]

comment:30

one has to declare characters one by one

see

src/sage_docbuild/conf.py:    \DeclareUnicodeCharacter{0428}{cyrillic Sha}

[dcoudert]

comment:31

I tried to add \DeclareUnicodeCharacter{0144}{Latin small letter n with acute}, but the pdf compilation still failed.

[fchapoton]

comment:32

strange (and probably wrong) use of latex syntax for accents in the master reference file

[fchapoton]

comment:33

The ï of Hanoï is certainly problematic too

[sagetrac-git]

Changed commit from 5540573 to fcac17c

[sagetrac-git]

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

fcac17c

trac #33854: avoid unicode characters

[sagetrac-git]

Changed commit from fcac17c to 11c69b7

[sagetrac-git]

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

11c69b7

trac #33854: remove unicode characters

[dcoudert]

comment:36

I removed the unicode characters.

[fchapoton]

comment:37

are we ok with the accents in

Sandi Klavžar and Uroš Milutinović

?

[dcoudert]

comment:38

I can build the both the html and the pdf docs with the current branch.

May be the issue with the special character in Sierpinski is that I don't have both the right unicode character and its code.

[fchapoton]

comment:39

alors on peut ré-essayer.

[vbraun]

Changed branch from public/graphs/33854_sierpinski to 11c69b7