Opened 6 years ago
Closed 2 years ago
#21423 closed enhancement (fixed)
CubeConnectedCycle generator
Reported by: | mcognetta | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-9.1 |
Component: | graph theory | Keywords: | graph generators |
Cc: | Merged in: | ||
Authors: | Vipul Gupta | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | f89d491 (Commits, GitHub, GitLab) | Commit: | f89d491d3fe7f2757d109a42c1611cdea00c0eec |
Dependencies: | Stopgaps: |
Description (last modified by )
Adds Cube Connected Cycle generator as described in https://en.wikipedia.org/wiki/Cube-connected_cycles and http://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html
Change History (47)
comment:1 Changed 6 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Keywords graph generators added
- Priority changed from major to minor
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 6 years ago by
- Summary changed from CubeConnectedGraph generator to CubeConnectedCycle generator
comment:3 Changed 6 years ago by
comment:4 Changed 6 years ago by
- Branch set to u/mcognetta/cubeconnectedgraph_generator
comment:5 follow-up: ↓ 6 Changed 6 years ago by
- Commit set to 8a012f6ccc58e17a641ac8364c1f47f2907358cb
Hello,
Thank you for adding this.
Here n
is not the order of the CCC but the dimension. The order of CCC(n) is d*2^d
(You could mention it in the documentation).
I suggest to replace n
with d
to avoid confusion with the order.
Use <
instead of \lt
. As you can see in the documentation displayed in a terminal, \lt
is replaced with lt
, which is not nice. Also, you can avoid using \lfloor...\rfloor
and give directly the value for n
even and n
odd. I don't know what to do with the oplus
. Actually I don't knwo what you mean by x oplus 2^y
.
sage: G = graphs.CubeConnectedCycle? Signature: graphs.CubeConnectedCycle(n) Docstring: Returns the cube-connected cycle of order n. The cube-connected cycle of order n is the n-dimensional hypercube with each of its vertices replaced by a cycle of length n. The construction is as follows: Construct vertex (x,y) for 0 <= x lt 2^n, 0 <= y lt n. For each vertex, (x,y), add an edge between it and (x, (y-1) mod n)), (x,(y+1) mod n), and (x oplus 2^y, y) INPUT: * "n" -- The dimension of the desired hypercube as well as the length of the cycle to be placed at each vertex of the n-dimensional hypercube. n must be a positive integer. EXAMPLES: The diameter of cube-connected cycles for n gt 3 is 2n+ lfloor frac{n}{2} rfloor -2 sage: g = graphs.CubeConnectedCycle(9) sage: g.diameter() 20 All vertices have degree 3 when n gt 1 sage: g = graphs.CubeConnectedCycle(12) sage: all(g.degree(v) == 3 for v in g) True
For the last example, observe that CCC(2) is a cycle of order 8, and so all vertices have degree 2.
The error message could be changed to greater than 0
.
Best, David.
PS: switch the ticket to need review when ready. It is still as new...
New commits:
8a012f6 | Added a generator for CubeConnectedCycles to families.py
|
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Replying to dcoudert:
Hello,
Thank you for adding this.
Here
n
is not the order of the CCC but the dimension. The order of CCC(n) isd*2^d
(You could mention it in the documentation). I suggest to replacen
withd
to avoid confusion with the order.Use
<
instead of\lt
. As you can see in the documentation displayed in a terminal,\lt
is replaced withlt
, which is not nice. Also, you can avoid using\lfloor...\rfloor
and give directly the value forn
even andn
odd. I don't know what to do with theoplus
. Actually I don't knwo what you mean byx oplus 2^y
.sage: G = graphs.CubeConnectedCycle? Signature: graphs.CubeConnectedCycle(n) Docstring: Returns the cube-connected cycle of order n. The cube-connected cycle of order n is the n-dimensional hypercube with each of its vertices replaced by a cycle of length n. The construction is as follows: Construct vertex (x,y) for 0 <= x lt 2^n, 0 <= y lt n. For each vertex, (x,y), add an edge between it and (x, (y-1) mod n)), (x,(y+1) mod n), and (x oplus 2^y, y) INPUT: * "n" -- The dimension of the desired hypercube as well as the length of the cycle to be placed at each vertex of the n-dimensional hypercube. n must be a positive integer. EXAMPLES: The diameter of cube-connected cycles for n gt 3 is 2n+ lfloor frac{n}{2} rfloor -2 sage: g = graphs.CubeConnectedCycle(9) sage: g.diameter() 20 All vertices have degree 3 when n gt 1 sage: g = graphs.CubeConnectedCycle(12) sage: all(g.degree(v) == 3 for v in g) TrueFor the last example, observe that CCC(2) is a cycle of order 8, and so all vertices have degree 2.
The error message could be changed to
greater than 0
.Best, David.
PS: switch the ticket to need review when ready. It is still as new...
New commits:
8a012f6 Added a generator for CubeConnectedCycles to families.py
Hi, thanks for the comments.
I will add the suggested items. \oplus is for the bitwise xor operation. I am not sure the best way to have that in the docs? Maybe just ^
?
comment:7 Changed 6 years ago by
- Commit changed from 8a012f6ccc58e17a641ac8364c1f47f2907358cb to d201b449b4db7fe9dec44e8065e7b0b9fb6437db
Branch pushed to git repo; I updated commit sha1. New commits:
d201b44 | updated some documentation. changed the variable 'n' to 'd' to denote dimension. Also removed some latex symbols and just put their ascii symbol. I kept the xor and floor ones because I don't really know what to do with those.
|
comment:8 Changed 6 years ago by
- Status changed from new to needs_review
I changed the documentation to reflect most of the recommendations but kept the floor and \oplus latex symbols because I don't know what to do with \oplus and floor is present in many other doc strings. I clarified the meaning of \oplus to avoid confusion.
comment:9 Changed 6 years ago by
Some other comments:
order `d2^d`.
->order `d\times 2^d`.
or.
or\cdot
. It will be nicer- in the examples, you could change
sage: len(g)
withsage: len(g)==d*2**d
and the expected result toTrue
. All vertices have degree `3` when `d > 1` ::
->All vertices have degree `3` when `d > 2` ::
You are lucky that the ^
operator is working well here. I have different behavior when using the command line...
sage: G = graphs.CubeConnectedCycle(3) sage: print G.vertices() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2)] sage: def toto(d): ....: G = Graph(name="Cube-Connected Cycle of dimension {}".format(d)) ....: G.add_vertices((x, y) for x in range(pow(2, d)) for y in range(d)) ....: for x, y in G.vertices(): ....: G.add_edge((x, y), (x, (y+1)%d)) ....: G.add_edge((x, y), (x, (y-1)%d)) ....: G.add_edge((x, y), (x^pow(2, y), y)) ....: return G ....: sage: print toto(3).vertices() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (9, 1), (16, 1), (16, 2), (25, 1), (36, 1), (49, 1), (81, 2), (256, 2), (625, 2), (1296, 2), (2401, 2)] sage: G.is_isomorphic(toto(3)) False
I don't know how to prevent such problem.
comment:10 Changed 6 years ago by
I actually had the same problem for a little but it sort of just went away. I tried to use
x.__xor__(y)
but it wouldn't work on either the command line or in loaded modules (can't remember which).
What is the preferred way to do operations such as xor, power, and mod?
comment:11 Changed 6 years ago by
I tried in both command line and module and G.add_edge((x, y), (x.__xor__(pow(2, y)), y))
is working well.
Apparently, ^
is the standard python3 xor https://docs.python.org/3/reference/expressions.html, so you can let it as is.
Exponentiation is done with **
in python3, so it will become the standard, and mod is %
.
comment:12 Changed 6 years ago by
I will leave ^
as is and and change pow to be **
. Is there a case where using the sage pow and mod functions is preferred over using the python operators **
and %
?
comment:13 Changed 6 years ago by
- Commit changed from d201b449b4db7fe9dec44e8065e7b0b9fb6437db to 298b15c9b9f1cb807293d23762b895f8a6989aa1
Branch pushed to git repo; I updated commit sha1. New commits:
298b15c | changed the pow() operation to use the python ** operator
|
comment:14 Changed 6 years ago by
I don't know when is pow
prefered to **
.
You forgot to consider the following comments:
order `d2^d`.
->order `d\times 2^d`.
or.
or\cdot
. It will be nicer- in the examples, you could change
sage: len(g)
withsage: len(g)==d*2**d
and the expected result toTrue
. All vertices have degree `3` when `d > 1` ::
->All vertices have degree `3` when `d > 2` ::
comment:15 Changed 6 years ago by
- Commit changed from 298b15c9b9f1cb807293d23762b895f8a6989aa1 to d43cbdac3074b3969ec27df6c7fccddadd890db2
Branch pushed to git repo; I updated commit sha1. New commits:
d43cbda | Updated docs
|
comment:16 Changed 6 years ago by
you forgot the last item
All vertices have degree `3` when `d > 1` ::
->All vertices have degree `3` when `d > 2` ::
comment:17 Changed 6 years ago by
It seems to be correct as is. See http://mathworld.wolfram.com/Cube-ConnectedCycle.html
comment:18 Changed 6 years ago by
Your construction does not follow the wolfram definition where CCC(1)
has loops and CCC(2)
has multiple (parallel) edges.
sage: graphs.CubeConnectedCycle(1).has_loops() False sage: graphs.CubeConnectedCycle(2).allows_multiple_edges() False
So either you add necessary cases to strictly follow the wolfram definition, or you follow the usual assumption in graph theory that CCC(1)
is an edge and so vertices have degree 1, and CCC(2)
is a cycle of order 8 and so its vertices have degree 2.
If you check the original paper by Preparata and Vuillemin in 1981 http://dl.acm.org/citation.cfm?id=358660, you will see that the definition is slightly different and more general (extra vertices can be added).
If you remind me, I can check on Monday in reference books such as J. de Rumeur, Communication dans les réseaux de processeurs, Masson, 1994
and others.
I realize that there is an error in your code with d=1
due to %1
since 1%1==2%1==0
. Furthermore, the test is not good since all vertices have by definition degree less than 3.
sage: g = graphs.CubeConnectedCycle(1) sage: any(g.degree(v) < 3 for v in g) True sage: g.edges() [] sage: g.vertices() [(0, 0), (1, 0)]
comment:19 Changed 6 years ago by
- Status changed from needs_review to needs_work
In your code, some edges are added twice. A simple method to avoid that is as follows:
if d<1: raise ValueError('d must be greater than 0.') G = Graph(name="Cube-Connected Cycle of dimension {}".format(d)) for x in range(1<<d): G.add_cycle( [(x, y) for y in range(d)] ) for x, y in G.vertices(): G.add_edge((x, y), (x^(1<<y), y)) return G
The 1<<y
are just minor improvements.
comment:20 Changed 6 years ago by
Thanks, I haven't really been able to do anything in Sage for a while (https://groups.google.com/forum/#!topic/sage-devel/jLUq1rqdOC4). I will try to finish it up soon, I feel dumb for having so many small mistakes but it has been prohibitively time consuming to do iterative improvements on anything I was messing with in Sage.
comment:21 Changed 6 years ago by
I also had issues with 7.4-beta4 (#21482), and it took me a lot of compilations to test te patch...
Concerning this ticket, we all make small mistakes. That's why the reviewing process is so important (ok, some times it's really boring).
We are almost done with this ticket. We mostly have to ensure that the definition fits the code and vice-et-versa ;)
comment:22 Changed 6 years ago by
any update?
comment:23 Changed 5 years ago by
- Milestone changed from sage-7.4 to sage-8.1
just a ping to know if you are willing to finalize this ticket.
comment:24 Changed 5 years ago by
Wow I thought this had been closed already. Give me a day or so to get sage set up on my new work station and I'll finish it
comment:25 Changed 5 years ago by
- Commit changed from d43cbdac3074b3969ec27df6c7fccddadd890db2 to 40155f76e74af7beb55bd4e5058dd8c2c552b5e2
comment:26 Changed 5 years ago by
- Status changed from needs_work to needs_review
I've been having a ridiculous amount of trouble getting sage to work/compile/connect to trac correctly. Anyway, I updated the docs and included cases for d=1 and 2 specifically to match the original definition. Hope this is sufficient. Thanks for the help in the past.
comment:27 Changed 5 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
I'm sorry you had difficulties installing/updating sage.
I have several comments. Let's start with the easiest one:
Returns the cube-connected cycle of dimension `d`.
->Return the cube-connected cycle of dimension `d`.
- Instead of
<=
, you can use\leq
. It will be much nicer.
In the examples:
sage: d = 10
this is large. In general we try to have quick tests since there are many many tests in Sagemath.d = 3
could be enough, non?sage: d = 9
. again, 4 is large enough.sage: g = graphs.CubeConnectedCycle(12)
is clearly too large. 3 is enough here.
In the code:
if d<1:
->if d < 1:
ValueError('d must be greater than 0.')
->ValueError('the dimension d must be greater than 0')
without.
at the end. Change the test accordingly.
Now, there is something wrong with the way you handle the case d == 1
and d == 2
. If I use your code, I get:
sage: G = graphs.CubeConnectedCycle(1) sage: G.edges() [((0, 0), (0, 0), None), ((0, 0), (1, 0), None), ((1, 0), (1, 0), None)] sage: G.has_loops() False sage: G.loops() [] sage: G = graphs.CubeConnectedCycle(2) sage: G.edges(labels=0) [((0, 0), (0, 1)), ((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 0), (1, 1)), ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((3, 0), (3, 1)), ((3, 0), (3, 1))] sage: G.has_multiple_edges() False
Could you tell me what you expect CCC(1)
and CCC(2)
to be ?
Also, I'm not able to build the documentation. I got:
OSError: [graphs ] /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.CubeConnectedCycle:33: WARNING: Unexpected indentation.
I suspect it is due to the line The construction is as follows:
. Can you check ?
All these are only minor issues that can easily be fixed. Almost done !
comment:28 Changed 2 years ago by
According to Wikipedia https://en.wikipedia.org/wiki/Cube-connected_cycles#Definition.
In CCC(d), each node (x,y) should have (x,(y+1)mod d) , (x,(y-1)mod d) and (x XOR 2^y, y)
has its neighbor( or adjacent vertices)
CCC(1) can be one of the following:
1).Graph with edges: [((0, 0), (0, 0)), ((0, 0), (0, 1)), ((0, 1), (0, 1))]
if we dont consider a vertex to be its own neighbor unless there is a self loop.
2). A simple Graph with an edge: [((0, 0), (1, 0))]
, If we consider a vertex to be its own neighbor as mentioned in following link http://mathworld.wolfram.com/GraphNeighborhood.html
CCC(2) should be
Simple Graph with edges: [((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((3, 0), (3, 1))]
Code works fine for CCC(d>3).
@docoudert: Can you guide me here?
comment:29 follow-up: ↓ 32 Changed 2 years ago by
I think it's better to follow the wolfram definition of CCC here http://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html.
comment:30 Changed 2 years ago by
- Branch changed from u/mcognetta/cubeconnectedgraph_generator to u/gh-vipul79321/ticket21423
- Commit 40155f76e74af7beb55bd4e5058dd8c2c552b5e2 deleted
- Milestone changed from sage-8.1 to sage-9.1
comment:31 Changed 2 years ago by
- Commit set to e84a304f5d6eb7277f573f04dae0ccd2aaece933
comment:32 in reply to: ↑ 29 Changed 2 years ago by
- Status changed from needs_work to needs_review
Replying to dcoudert:
I think it's better to follow the wolfram definition of CCC here http://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html.
There is still one ambiguity for CCC(2). It can have following edge set according to diagram or definition of CCC(2) in Wolfram :
1) [((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 0), (1, 0)), ((0, 1), (2, 1)), ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 1), (3, 1)), ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((2, 0), (3, 0)), ((3, 0), (3, 1))]
or
2) [((0, 0), (0, 1)), ((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 0), (1, 1)), ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((3, 0), (3, 1)), ((3, 0), (3, 1))]
comment:33 follow-up: ↓ 34 Changed 2 years ago by
which one follows best the definition given here https://en.wikipedia.org/wiki/Cube-connected_cycles ?
comment:34 in reply to: ↑ 33 Changed 2 years ago by
Replying to dcoudert:
which one follows best the definition given here https://en.wikipedia.org/wiki/Cube-connected_cycles ?
Both cases satisfy the condition given.
But sticking to this definition given inhttp://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html The cube-connected cycle graph of order n is the graph obtained by replacing each vertex in a n-dimensional hypercube by a cycle of length n.
Option (2) of comment 32 fits well because each node in hypergraph is replaced by cycle whose x is fixed and that pattern is also followed in all CCC(d>=3).
comment:35 Changed 2 years ago by
- Commit changed from e84a304f5d6eb7277f573f04dae0ccd2aaece933 to 52f845182ac6b5c8b957e299118b078e797ac059
Branch pushed to git repo; I updated commit sha1. New commits:
52f8451 | updated according comment 34
|
comment:36 follow-up: ↓ 38 Changed 2 years ago by
- Please follow the PEP8 coding style https://www.python.org/dev/peps/pep-0008/
- Use
for x, y in G:
instead offor x, y in G.vertices():
- I don't understand how you make the graph for
d == 2
with allowing / disallowing multi edges.
You could directly list the edges of the graph, you know them.
comment:37 Changed 2 years ago by
- Commit changed from 52f845182ac6b5c8b957e299118b078e797ac059 to 8a438b92616aabde60b4decb74dce6ca3748250b
Branch pushed to git repo; I updated commit sha1. New commits:
8a438b9 | updated for d = 2
|
comment:38 in reply to: ↑ 36 Changed 2 years ago by
Replying to dcoudert:
- Please follow the PEP8 coding style https://www.python.org/dev/peps/pep-0008/
Hopefully I updated it to PEP8 style. If not, please point out where I am missing it.
comment:39 Changed 2 years ago by
almost good.
- alignment issue in the ÌNPUT` block
- - ``d`` -- The dimension of the desired hypercube as well as the length - of the cycle to be placed at each vertex of the `d`-dimensional - hypercube. `d` must be a positive integer. + - ``d`` -- integer; the dimension of the desired hypercube as well as the + length of the cycle to be placed at each vertex of the `d`-dimensional + hypercube. `d` must be a positive integer.
- empty line missing
- `2d + \lfloor \frac{d}{2} \rfloor - 2` :: - sage: d = 4 + `2d + \lfloor \frac{d}{2} \rfloor - 2` :: + + sage: d = 4
- nicer presentation
- G.add_edges([((0, 0), (0, 1)), ((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 0), (1, 1)), ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((3, 0), (3, 1)), ((3, 0), (3, 1))]) + G.add_edges([((0, 0), (0, 1)), ((0, 0), (0, 1)), ((0, 0), (1, 0)), + ((0, 1), (2, 1)), ((1, 0), (1, 1)), ((1, 0), (1, 1)), + ((1, 1), (3, 1)), ((2, 0), (2, 1)), ((2, 0), (2, 1)), + ((2, 0), (3, 0)), ((3, 0), (3, 1)), ((3, 0), (3, 1))])
comment:40 Changed 2 years ago by
and don't forget to add your name in the authors field.
comment:41 Changed 2 years ago by
- Commit changed from 8a438b92616aabde60b4decb74dce6ca3748250b to 85f81c6819c61f7985b4d641f823eb95a6d60f4c
Branch pushed to git repo; I updated commit sha1. New commits:
85f81c6 | updated to comment 39
|
comment:42 Changed 2 years ago by
comment:43 follow-up: ↓ 45 Changed 2 years ago by
Can you check the error reported by the patchbot ?
Have you check if the documentation builds and displays well ?
comment:44 Changed 2 years ago by
- Commit changed from 85f81c6819c61f7985b4d641f823eb95a6d60f4c to f89d491d3fe7f2757d109a42c1611cdea00c0eec
Branch pushed to git repo; I updated commit sha1. New commits:
f89d491 | Patchbot issues fixed
|
comment:45 in reply to: ↑ 43 Changed 2 years ago by
Replying to dcoudert:
Can you check the error reported by the patchbot ?
Those issues occured in some other part of the code. I have fixed them
Have you check if the documentation builds and displays well ?
Yes
comment:46 Changed 2 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
LGTM.
comment:47 Changed 2 years ago by
- Branch changed from u/gh-vipul79321/ticket21423 to f89d491d3fe7f2757d109a42c1611cdea00c0eec
- Resolution set to fixed
- Status changed from positive_review to closed
I have a patch for this done but I am getting the following error when I try to push it:
Any advice? I was getting some man-in-the-middle warning before but that is gone now...
edit: fixed it. I had deleted trac.sagemath.org from my known hosts but never readded it.