Opened 8 years ago
Closed 8 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 )
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)
Change History (47)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
comment:3 in reply to: ↑ 2 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
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 8 years ago by
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: ↓ 9 Changed 8 years ago by
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: ↓ 10 Changed 8 years ago by
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))) == 26but 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 8 years ago by
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))) == 26but 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.
comment:11 follow-up: ↓ 12 Changed 8 years ago by
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 the3^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 8 years ago by
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 the3^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 8 years ago by
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 8 years ago by
- 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 8 years ago by
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 8 years ago by
- Status changed from needs_review to positive_review
Tests good, docs good -> positive review
comment:17 Changed 8 years ago by
Many thanks for the help improving this patch.
comment:18 Changed 8 years ago by
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: ↓ 20 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
Did you add an __init__.py
to sage/graphs/generators?
comment:23 Changed 8 years ago by
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 8 years ago by
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
comment:25 Changed 8 years ago by
- 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 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:27 Changed 8 years ago by
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 8 years ago by
Could anyone review this patch ? Thanks.
comment:29 Changed 8 years ago by
(cc me)
comment:30 follow-up: ↓ 31 Changed 8 years ago by
Do we really need to import sage.graphs.generators.chessboard at startup?
comment:31 in reply to: ↑ 30 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
Mostly looks good, but I would remove the double underscores around ChessboardGraphGenerator
Changed 8 years ago by
comment:34 Changed 8 years ago by
Done.
comment:35 follow-up: ↓ 37 Changed 8 years ago by
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 8 years ago by
- Description modified (diff)
comment:37 in reply to: ↑ 35 ; follow-up: ↓ 38 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
comment:39 Changed 8 years ago by
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 8 years ago by
Well.. Then "if you agree with those changes", let's get this ticket in :-)
Nathann
comment:41 Changed 8 years ago by
I agree with your changes. Thanks.
comment:42 Changed 8 years ago by
- 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 8 years ago by
Thanks!
comment:44 Changed 8 years ago by
- Milestone changed from sage-5.4 to sage-5.5
comment:45 Changed 8 years ago by
- Merged in set to sage-5.5.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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:"?