Opened 7 years ago

Closed 7 years ago

#13306 closed enhancement (fixed)

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

Reported by: dcoudert Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.5
Component: graph theory Keywords: graph, generator
Cc: Merged in: sage-5.5.beta0
Authors: David Coudert Reviewers: Sebastian Luther, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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:

Attachments (2)

trac_13306-queen-king-knight-graphs-v2.patch (22.9 KB) - added by dcoudert 7 years ago.
trac_13306-review.patch (10.5 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 7 years ago by dcoudert

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

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

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:"?

comment:3 in reply to: ↑ 2 Changed 7 years ago by dcoudert

Replying to 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.

comment:4 Changed 7 years ago by sluther

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.

comment:5 Changed 7 years ago by dcoudert

  • Description modified (diff)
  • Summary changed from Generators for Queen, King, and Knight graphs to Generators for chessboard graphs: King, Queen, Knight, Bishop, Rooks

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.

comment:6 Changed 7 years ago by sluther

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

        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[:]".
8)

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

comment:7 Changed 7 years ago by dcoudert

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 !

comment:8 follow-up: Changed 7 years ago by sluther

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.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 7 years ago by dcoudert

Replying to 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

comment:10 in reply to: ↑ 9 Changed 7 years ago by sluther

Replying to dcoudert:

Replying to 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.

Last edited 7 years ago by sluther (previous) (diff)

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

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.

comment:12 in reply to: ↑ 11 Changed 7 years ago by sluther

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?

comment:13 Changed 7 years ago by dcoudert

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?

comment:14 Changed 7 years ago by sluther

  • Reviewers set to Sebastian Luther

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.

comment:15 Changed 7 years ago by dcoudert

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

comment:16 Changed 7 years ago by sluther

  • Status changed from needs_review to positive_review

Tests good, docs good -> positive review

comment:17 Changed 7 years ago by dcoudert

Many thanks for the help improving this patch.

comment:18 Changed 7 years ago by jdemeyer

This patch adds again a considerable amount of code to sage/graphs/graph_generators.py.

At some point, I will have to refuse such patches before that file gets really too big.

comment:19 follow-up: Changed 7 years ago by dcoudert

Then what could be the solution: split the file into several pieces (graph_generators_1.py, graph_generators_2.py, etc...) with a bounded number of lines per file ?

comment:20 in reply to: ↑ 19 Changed 7 years ago by jdemeyer

Replying to dcoudert:

Then what could be the solution: split the file into several pieces (graph_generators_1.py, graph_generators_2.py, etc...) with a bounded number of lines per file ?

Perhaps, although a better solution would be to group "related" graphs together.

For example, put all the code added in this ticket inside a new file

sage/graphs/generators/chessboard.py

comment:21 Changed 7 years ago by dcoudert

I can try to do that, but I don't know how to expose the functions inside the GraphGenerators? class. Should I use something like

import types
import sage.graphs.generators.chessboard 
GraphGenerators.QueenGraph = types.MethodType(sage.graphs.generators.chessboard.QueenGraph, None, Graph) 

I tried but it produces an error: ImportError: No module named generators.chessboard

Any help is more than welcome.

comment:22 Changed 7 years ago by sluther

Did you add an __init__.py to sage/graphs/generators?

comment:23 Changed 7 years ago by dcoudert

I added such a file but it's still not working.

Is the procedure documented somewhere? I haven't find it in the documentation yet.

comment:24 Changed 7 years ago by sluther

See [1] for how to add a new directory. But I'd say you should skip the addition of all.py and the addition to the existing all.py files as you want these things to be visible through the GraphGenerators? class only.

After that add an import like "import sage.graphs.generators.chessboard" to graph_generators.py.

Then:

class GraphGenerators():
   [...]
   QueenGraph = sage.graphs.generators.chessboard.QueenGraph

[1] http://www.sagemath.org/doc/developer/coding_in_python.html#creating-a-new-directory

Last edited 7 years ago by sluther (previous) (diff)

comment:25 Changed 7 years ago by dcoudert

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

OK! it took me some time but know it's working! From my computer, everything is working (build, doc, tests,...). I have not added the new file for docbuild since the documentation of the functions are build with the documentation of graph_generator.py.

I hope this new version will satisfy everyone.

comment:26 Changed 7 years ago by dcoudert

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

comment:27 Changed 7 years ago by dcoudert

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

comment:28 Changed 7 years ago by dcoudert

Could anyone review this patch ? Thanks.

comment:29 Changed 7 years ago by ncohen

(cc me)

comment:30 follow-up: Changed 7 years ago by robertwb

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

comment:31 in reply to: ↑ 30 Changed 7 years ago by dcoudert

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?

comment:32 Changed 7 years ago by robertwb

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

comment:33 Changed 7 years ago by robertwb

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

Changed 7 years ago by dcoudert

comment:34 Changed 7 years ago by dcoudert

Done.

comment:35 follow-up: Changed 7 years ago by ncohen

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

comment:36 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:37 in reply to: ↑ 35 ; follow-up: Changed 7 years ago by dcoudert

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.

comment:38 in reply to: ↑ 37 Changed 7 years ago by ncohen

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

Changed 7 years ago by ncohen

comment:39 Changed 7 years ago by dcoudert

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.

comment:40 Changed 7 years ago by ncohen

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

Nathann

comment:41 Changed 7 years ago by dcoudert

I agree with your changes. Thanks.

comment:42 Changed 7 years ago by ncohen

  • Reviewers changed from Sebastian Luther to Sebastian Luther, Nathann Cohen
  • Status changed from needs_review to positive_review

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

Nathann

comment:43 Changed 7 years ago by dcoudert

Thanks!

comment:44 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5

comment:45 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.5.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.