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:

Status badges

Change History (47)

comment:1 Changed 6 years ago by mcognetta

  • 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 mcognetta

  • Summary changed from CubeConnectedGraph generator to CubeConnectedCycle generator

comment:3 Changed 6 years ago by 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.

Last edited 6 years ago by mcognetta (previous) (diff)

comment:4 Changed 6 years ago by mcognetta

  • Branch set to u/mcognetta/cubeconnectedgraph_generator

comment:5 follow-up: Changed 6 years ago by dcoudert

  • 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:

8a012f6Added a generator for CubeConnectedCycles to families.py

comment:6 in reply to: ↑ 5 Changed 6 years ago by 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:

8a012f6Added 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 git

  • Commit changed from 8a012f6ccc58e17a641ac8364c1f47f2907358cb to d201b449b4db7fe9dec44e8065e7b0b9fb6437db

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

d201b44updated 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 mcognetta

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

comment:10 Changed 6 years ago by 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?

comment:11 Changed 6 years ago by 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 %.

comment:12 Changed 6 years ago by 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 %?

comment:13 Changed 6 years ago by git

  • Commit changed from d201b449b4db7fe9dec44e8065e7b0b9fb6437db to 298b15c9b9f1cb807293d23762b895f8a6989aa1

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

298b15cchanged the pow() operation to use the python ** operator

comment:14 Changed 6 years ago by 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` ::

comment:15 Changed 6 years ago by git

  • Commit changed from 298b15c9b9f1cb807293d23762b895f8a6989aa1 to d43cbdac3074b3969ec27df6c7fccddadd890db2

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

d43cbdaUpdated docs

comment:16 Changed 6 years ago by dcoudert

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 mcognetta

comment:18 Changed 6 years ago by 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)]

comment:19 Changed 6 years ago by dcoudert

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

comment:21 Changed 6 years ago by 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 ;)

comment:22 Changed 6 years ago by dcoudert

any update?

comment:23 Changed 5 years ago by dcoudert

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

comment:25 Changed 5 years ago by git

  • Commit changed from d43cbdac3074b3969ec27df6c7fccddadd890db2 to 40155f76e74af7beb55bd4e5058dd8c2c552b5e2

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

8579fdaupdated docs to fix several typos and added special cases for d=1,2
99cfe7fupdated the documentation for cube connected cycles
40155f7changed order to dimension in docstring

comment:26 Changed 5 years ago by mcognetta

  • 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 dcoudert

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

comment:29 follow-up: Changed 2 years ago by dcoudert

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 gh-vipul79321

  • 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 git

  • Commit set to e84a304f5d6eb7277f573f04dae0ccd2aaece933

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

96efb1dmethod updated
e84a304updated according to comment 27

comment:32 in reply to: ↑ 29 Changed 2 years ago by gh-vipul79321

  • 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: Changed 2 years ago by dcoudert

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

  • Commit changed from e84a304f5d6eb7277f573f04dae0ccd2aaece933 to 52f845182ac6b5c8b957e299118b078e797ac059

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

52f8451updated according comment 34

comment:36 follow-up: Changed 2 years ago by 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.

comment:37 Changed 2 years ago by git

  • Commit changed from 52f845182ac6b5c8b957e299118b078e797ac059 to 8a438b92616aabde60b4decb74dce6ca3748250b

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

8a438b9updated for d = 2

comment:38 in reply to: ↑ 36 Changed 2 years ago by gh-vipul79321

Replying to dcoudert:

Hopefully I updated it to PEP8 style. If not, please point out where I am missing it.

comment:39 Changed 2 years ago by 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))])
    

comment:40 Changed 2 years ago by dcoudert

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

comment:41 Changed 2 years ago by git

  • Commit changed from 8a438b92616aabde60b4decb74dce6ca3748250b to 85f81c6819c61f7985b4d641f823eb95a6d60f4c

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

85f81c6updated to comment 39

comment:42 Changed 2 years ago by gh-vipul79321

  • Authors set to Vipul Gupta

comment:43 follow-up: Changed 2 years ago by dcoudert

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 git

  • Commit changed from 85f81c6819c61f7985b4d641f823eb95a6d60f4c to f89d491d3fe7f2757d109a42c1611cdea00c0eec

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

f89d491Patchbot issues fixed

comment:45 in reply to: ↑ 43 Changed 2 years ago by 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

Last edited 2 years ago by gh-vipul79321 (previous) (diff)

comment:46 Changed 2 years ago by dcoudert

  • Description modified (diff)
  • Status changed from needs_review to positive_review

LGTM.

comment:47 Changed 2 years ago by vbraun

  • Branch changed from u/gh-vipul79321/ticket21423 to f89d491d3fe7f2757d109a42c1611cdea00c0eec
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.