CubeConnectedCycle generator

[mcognetta]

Adds Cube Connected Cycle generator as described in ​https://en.wikipedia.org/wiki/Cube-connected_cycles and ​http://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html

[mcognetta]

I have a patch for this done but I am getting the following error when I try to push it:

    STDERR: Host key verification failed.
    STDERR: fatal: Could not read from remote repository.
    STDERR: 
    STDERR: Please make sure you have the correct access rights
    STDERR: and the repository exists.

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.

[dcoudert]

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

[mcognetta]

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) 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

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 ^?

[git]

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.

[mcognetta]

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.

[dcoudert]

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) with sage: len(g)==d*2**d and the expected result to True.
• 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.

[mcognetta]

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?

[dcoudert]

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 %.

[mcognetta]

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 %?

[git]

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

​298b15c

changed the pow() operation to use the python ** operator

[dcoudert]

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) with sage: len(g)==d*2**d and the expected result to True.
• All vertices have degree `3` when `d > 1` :: -> All vertices have degree `3` when `d > 2` ::

[git]

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

​d43cbda

Updated docs

[dcoudert]

you forgot the last item

• All vertices have degree `3` when `d > 1` :: -> All vertices have degree `3` when `d > 2` ::

[mcognetta]

It seems to be correct as is. See ​http://mathworld.wolfram.com/Cube-ConnectedCycle.html

[dcoudert]

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)]

[dcoudert]

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.

[mcognetta]

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.

[dcoudert]

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 ;)

[dcoudert]

any update?

[dcoudert]

just a ping to know if you are willing to finalize this ticket.

[mcognetta]

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

[git]

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

​8579fda	updated docs to fix several typos and added special cases for d=1,2
​99cfe7f	updated the documentation for cube connected cycles
​40155f7	changed order to dimension in docstring

[mcognetta]

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.

[dcoudert]

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 !

[gh-vipul79321]

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?

[dcoudert]

I think it's better to follow the wolfram definition of CCC here ​http://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html.

[git]

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

​96efb1d	method updated
​e84a304	updated according to comment 27

[gh-vipul79321]

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))]

[dcoudert]

which one follows best the definition given here ​https://en.wikipedia.org/wiki/Cube-connected_cycles ?

[gh-vipul79321]

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 in​http://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).

[git]

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

​52f8451

updated according comment 34

[dcoudert]

• Please follow the PEP8 coding style ​https://www.python.org/dev/peps/pep-0008/
• Use for x, y in G: instead of for 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.

[git]

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

​8a438b9

updated for d = 2

[gh-vipul79321]

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.

[dcoudert]

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))])
  

[dcoudert]

and don't forget to add your name in the authors field.

[git]

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

​85f81c6

updated to comment 39

[dcoudert]

Can you check the error reported by the patchbot ?

Have you check if the documentation builds and displays well ?

[git]

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

​f89d491

Patchbot issues fixed

[gh-vipul79321]

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

[dcoudert]

LGTM.