Generators for chessboard graphs: King, Queen, Knight, Bishop, Rooks

[dcoudert]

This patch implements generators for multi-dimensional chessboard graphs: Queen, King, Knight, Bishop, and Rook graphs. Variations of these graphs can be constructed changing the radius of the ball in which a chess piece can move.

These graphs are useful for testing graph coloring algorithms, hamiltonian cycles, etc.

In addition, this patch creates directory sage/graphs/generators/ to store new generators. The new functions of this patch are located in file sage/graphs/generators/chessboard.py. The functions are then included inside the GraphGenerators class and so accessible like graphs.QueenGraph(...).

APPLY:

• attachment: trac_13306-queen-king-knight-graphs-v2.patch
• attachment: trac_13306-review.patch

Component: graph theory

Keywords: generator

Author: David Coudert

Reviewer: Sebastian Luther, Nathann Cohen

Merged: sage-5.5.beta0

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

[sagetrac-sluther]

comment:2

Two comments:

1. What about supporting d-dimensional chess boards?
   i.e. G = graphs.QueenGraph(2, 2, 2)
   or G = graphs.QueenGraph(5,6,7,8,9)

2. Your input checks require n to be of type Integer. This excludes python ints and other things considered an integer. What about: "if n not in ZZ:"?

[dcoudert]

comment:3

Replying to @sagetrac-sluther:

Two comments:

1. What about supporting d-dimensional chess boards?
   i.e. G = graphs.QueenGraph(2, 2, 2)
   or G = graphs.QueenGraph(5,6,7,8,9)

Why not, but what would be the definition of valid movements?

• It is obvious for rook's (clique on each dimension).
• For a knight, it will still be +1 in one dimension and +2 in another dimension. So it should be ok
• For a king it is already more difficult to define legal and illegal movements.
• Same for the queen: what is legal and illegal?

2. Your input checks require n to be of type Integer. This excludes python ints and other things considered an integer. What about: "if n not in ZZ:"?

Yes, that's much better.

Thanks,
D.

[sagetrac-sluther]

comment:4

I'd think in directions. There are two types. The first type is defined by the nearest neighbours in the d-dimensional lattice, i.e. those points that change one coordinate by one.
The second type is defined by the second nearest heighbours, i.e. those points that change the coordinate in two different dimensions by one each.

The allowed directions then are:

King: 1 + 2

Rook: 1

Bishop: 2

Queen: 1 + 2

Your definition for the knight makes sense.

[dcoudert]

comment:5

I found a nice and generic way to implement all the chessboard graphs. I'm using a hidden function that takes many parameters and allows to add edges to all vertices along one dimension and/or on the diagonals of any pairs of dimensions and/or knight-like movements in any pairs of dimensions. The function also allows to control the radius of the visibility ball (could be useful).

Hope you'll like it.

[sagetrac-sluther]

comment:6

Excellent idea to organize it that way!

Some coding comments though.

try: 
 	8297	            if isinstance(dim_list,dict): 
 	8298	                dim = [dim_list[a] for a in dim_list] 
 	8299	            else: 
 	8300	                dim = [a for a in dim_list] 
 	8301	            nb_dim = len(dim) 
 	8302	        except: 
 	8303	            raise ValueError('The first parameter must be an iterable object.') 

1. if dim is a dict the keys aren't ordered. This means dim = {1: 2, 2: 3} might end up as dim = [3, 2] instead of [2,3]. Suggestion: dim = [dim_list[a] for a in sorted(dim_list)]

2. "dim = [a for a in dim_list]" can be replaced with "dim = list(dim_list)"

3. Never use except statements without an exception type to be catched. The reason is that this also catches things like SystemExit, which is raised by CTRL+C. Suggestion: "except TypeError:"

dimstr = '' 
 	8307	        for a in dim: 
 	8308	            if not a in ZZ or a < 1: 
 	8309	                raise ValueError('The dimensions must be positive integers larger than 1.') 
 	8310	            if dimstr == '': 
 	8311	                dimstr = '('+str(a) 
 	8312	            else: 
 	8313	                dimstr += ','+str(a) 
 	8314	        dimstr += ')' 

4. This could be split into:

if any(a not in ZZ or a < 1 for a in dim):
    raise ValueError('The dimensions must be positive integers larger than 1.')
dimstr = '(%s)' % "".join(dim)

5. In the code flowing code, there are checks like "rook_radius < 1 or not rook_radius in ZZ:". These could be reversed, i.e. "not rook_radius in ZZ or rook_radius < 1". The reason is that the comparison might raise an exception if it doesn't make sense.

        8331	        v = [0 for a in dim]
 	8332	        V = [v] 

 	8332	        V = [ [0]*nb_dim ] 

7. In the code below, there are some instances of "u = [x for x in v]". These should be replaced by "u = v[:]".

8343	        combin = combinations([i for i in xrange(nb_dim)],2) 

8343	        combin = combinations(range(nb_dim),2) 

I hope I don't discourage you with my nitpicking. Most the comments concern only style and efficiency, the only show stopper is 3).

[dcoudert]

comment:7

Thanks for the propositions. I have incorporated all of them but the following which causes a type error

sage: dim = [2,3,4,5]
sage: dimstr = '(%s)' % "".join(dim)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/dcoudert/<ipython console> in <module>()

TypeError: sequence item 0: expected string, int found

Instead, I use the following code which is in fact easier:

dimstr = str(tuple(dim)) 

This is much better now !

[sagetrac-sluther]

comment:8

1. There are white space issues, see patchbot output.

2. I would have expected the following:

G = graphs.QueenGraph( [3,3,3], radius=1 );
len(G.neighbors((1,1,1))) == 26

but the result is 18. This is because the second nearest neighbors in the third dimension are missing.

[dcoudert]

comment:9

Replying to @sagetrac-sluther:

1. There are white space issues, see patchbot output.

Removed. Why isn't it automatic :(

2. I would have expected the following:

G = graphs.QueenGraph( [3,3,3], radius=1 );
len(G.neighbors((1,1,1))) == 26

but the result is 18. This is because the second nearest neighbors in the third dimension are missing.

I disagree. The correct result is 18.

• 26 is not multiple of 3. so you could have expected 24
• Although we have 8 neighbors per pairs of dimensions, the sum is not 24 but 18 since you must remove redundancy.
  • in x,y you have 8 neighbors
  • in x,z you also have 8 neighbors, but 2 of them were found with x,y => 6 more
  • in y,z you have 8 neighbors, but 2 were already in x,y and 2 in x,z => 4 more
  • 8+6+4 = 18

[sagetrac-sluther]

comment:10

Replying to @dcoudert:

Replying to @sagetrac-sluther:

2. I would have expected the following:

G = graphs.QueenGraph( [3,3,3], radius=1 );
len(G.neighbors((1,1,1))) == 26

but the result is 18. This is because the second nearest neighbors in the third dimension are missing.

I disagree. The correct result is 18.

• 26 is not multiple of 3. so you could have expected 24
• Although we have 8 neighbors per pairs of dimensions, the sum is not 24 but 18 since you must remove redundancy.
  • in x,y you have 8 neighbors
  • in x,z you also have 8 neighbors, but 2 of them were found with x,y => 6 more
  • in y,z you have 8 neighbors, but 2 were already in x,y and 2 in x,z => 4 more
  • 8+6+4 = 18

26 = 3**3-1

In general I would expect 3**d -1 directions. They are defined by the 3^d points in {-1,0,1}^d. Only the central point doesn't define a direction.

[dcoudert]

comment:11

We said before (#comment:4) that the Queen could move either in 1 dimension or in 2 dimensions, and adding an edge from (1,1,1) to (2,2,2) means moving in the 3 dimensions. That's why 8 points are not reachable from (1,1,1).

In general I would expect 3**d -1 directions. They are defined by the 3^d points in {-1,0,1}^d. Only the central point doesn't define a direction.

I don't understand.

[sagetrac-sluther]

comment:12

Replying to @dcoudert:

We said before (#comment:4) that the Queen could move either in 1 dimension or in 2 > dimensions, and adding an edge from (1,1,1) to (2,2,2) means moving in the 3 dimensions. That's why 8 points are not reachable from (1,1,1).

You're right that's what I said, but not what I meant. Sorry.

In general I would expect 3**d -1 directions. They are defined by the 3^d points in {-1,0,1}^d. Only the central point doesn't define a direction.

I don't understand.

A point in the d-dimensional lattice has d integer coordinates, say x_i (i=1..d).
All points with x_i restricted to the set {-1,0,1} (for all i), lie in a hypercube.

This hypercube:

• is centered at the origin

• has all edges parralel to the coordinate axes

• has only edges of lenght 2

• contains exactly 3^d lattice points

Now define a valid direction as the vector from the origin (0,0,...,0) to any other of the 3^d-1 points.

And here is the fun question: Which definition makes more sense?

I'd propse the following: If you don't feel like putting more work into this, we'll leave it as is. If you're willing to work on it: What about adding a parameter, say 'higher_diagonals' that switches between the two definitions?

[dcoudert]

comment:13

I prefer to let the patch as it is for now.

If one needs it, we can latter add this "super-queen" definition. Also, your alternative definition should also be used for bishops and it would make bishops much more powerful than rooks (only able to move along one dimension at a time). And what about knights?

[sagetrac-sluther]

Reviewer: Sebastian Luther

[sagetrac-sluther]

comment:14

The n\equiv 1,5 \pmod(6) in the QueenGraph doc string looks strange, both on the command line and in the html doc.

Once this is fixed, I'll give it a positive review.

[dcoudert]

comment:15

I changed it to n\equiv 1,5 \bmod{6} and the output is now correct: n\equiv 1,5 (mod 6).

[sagetrac-sluther]

comment:16

Tests good, docs good -> positive review

[dcoudert]

comment:27

Addition of line # This file is not empty ! in file __init__.py as Nathann told me we should not have empty files.

[dcoudert]

comment:28

Could anyone review this patch ?
Thanks.

[nathanncohen]

comment:29

(cc me)

[robertwb]

comment:30

Do we really need to import sage.graphs.generators.chessboard at startup?

[dcoudert]

comment:31

Replying to @robertwb:

Do we really need to import sage.graphs.generators.chessboard at startup?

I don't know.

Following Jeroen's suggestion, I have created a new directory to store graph generators instead of continuously increasing the size of sage.graphs.graph_generators.py. Later, we could split the graph_generators file and create smaller files, easier to read, faster to test, etc. in the generators directory.

Now, the question is how to make these functions accessible from graphs (e.g., graphs.QueenGraph()) without importing the file at startup. Is there a way to import them the first time they are used? or any other interesting trick I'm not aware of?

[robertwb]

comment:32

You could try using lazy import. However, ignore that for now, as I think all of graph_generators should be lazily imported. #13562

[robertwb]

comment:33

Mostly looks good, but I would remove the double underscores around __ChessboardGraphGenerator__

[dcoudert]

Attachment: trac_13306-queen-king-knight-graphs-v2.patch.gz

[dcoudert]

comment:34

Done.

[nathanncohen]

comment:35

Helloooooooooooooooooooooooooooooo !!

Well, that patch was muuuuuuch cleaner than I feared, given its size :-)

Here is a list of comments, and a small innocent reviewer's patch.

• Default values : rook = True, bishop = True, knight = False : that's weird. Why not set them all to True or all to False ?
• dim_list : it takes any iterable as an input, and you say that it takes sets or even dicts ! That's asking for trouble because the order in which the elements are listed in sets and dicts is platform-dependent, but then you specifically SORT the elements by key value when the inout is a dict, and take the VALUES into account. That's not what it is expected. A dict is an iterable, but list(my_dict) lists its keys, not values ! It would make more sense to remove the part of the code that deals with dict (why especially dicts, by the way ? One can make custom iterables !), and just use your dim = list(dim_list) which is perfect as it is.
• I replaced "at least" or "least" by ">=". This way you know whether ">=" or ">" is intended, which is never clear with "at least" :-P
• Replaced a block of code by itertools.product
• Added many "`" for tuples that could appear in LaTeX instead.

Nathann

[dcoudert]

comment:37

I'm unable to install the review patch. Have you make it using the file I have uploaded this morning in which I have removed double underscores ?

• Default values : rook = True, bishop = True, knight = False : that's weird. Why not set them all to True or all to False ?

That way the default behavior is QueenGraph, which is the most common chessboard graph. But all default parameters are OK for me.

• dim_list : it takes any iterable as an input, and you say that it takes sets or even dicts ! That's asking for trouble because the order in which the elements are listed in sets and dicts is platform-dependent, but then you specifically SORT the elements by key value when the inout is a dict, and take the VALUES into account. That's not what it is expected. A dict is an iterable, but list(my_dict) lists its keys, not values ! It would make more sense to remove the part of the code that deals with dict (why especially dicts, by the way ? One can make custom iterables !), and just use your dim = list(dim_list) which is perfect as it is.

That's right. Can you insert this in the review patch?

• I replaced "at least" or "least" by ">=". This way you know whether ">=" or ">" is intended, which is never clear with "at least" :-P
• Replaced a block of code by itertools.product

I didn't know that command. Very nice.

• Added many "`" for tuples that could appear in LaTeX instead.

[nathanncohen]

comment:38

I'm unable to install the review patch. Have you make it using the file I have uploaded this morning in which I have removed double underscores ?

O_o
I thought I did. And none of the patch I had applied before changed chessboard.py. Well, I saw the errors when applying the patches and rebased it. Weird, but done.

That way the default behavior is QueenGraph, which is the most common chessboard graph. But all default parameters are OK for me.

Just set them all to True

That's right. Can you insert this in the review patch?

Done.

Patch updated !

Nathann

[nathanncohen]

Attachment: trac_13306-review.patch.gz

[dcoudert]

comment:39

Now it's working and the doc is nicer. Thanks.
I didn't know the product function and the way you use it is really nice.

[nathanncohen]

comment:40

Well.. Then "if you agree with those changes", let's get this ticket in :-)

Nathann

[dcoudert]

comment:41

I agree with your changes. Thanks.

[nathanncohen]

comment:42

Arf. I thought you would change the ticket's status :-)

Nathann

[nathanncohen]

Changed reviewer from Sebastian Luther to Sebastian Luther, Nathann Cohen

[dcoudert]

comment:43

Thanks!

[jdemeyer]

Merged: sage-5.5.beta0