search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.34k stars 452 forks source link

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

Closed dcoudert closed 11 years ago

dcoudert commented 12 years ago

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:

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

dcoudert commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,3 @@
 This patch implements the generators for Queen, King, and Knight graphs.

+These graphs are useful for testing graph coloring algorithms, hamiltonian cycles, etc.
33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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 commented 12 years ago
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?

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.

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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 commented 12 years ago
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.

dcoudert commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,4 @@
-This patch implements the generators for Queen, King, and Knight graphs.
+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.
+
33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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.

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

dcoudert commented 12 years ago
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 !

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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 commented 12 years ago
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.

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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 commented 12 years ago
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.

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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:

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 commented 12 years ago
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?

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago

Reviewer: Sebastian Luther

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
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 commented 12 years ago
comment:15

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

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
comment:16

Tests good, docs good -> positive review

dcoudert commented 12 years ago
comment:17

Many thanks for the help improving this patch.

jdemeyer commented 12 years ago
comment:18

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.

dcoudert commented 12 years ago
comment:19

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 ?

jdemeyer commented 12 years ago
comment:20

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
dcoudert commented 12 years ago
comment:21

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.

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
comment:22

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

dcoudert commented 12 years ago
comment:23

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.

33c50bab-f304-4398-bab0-d28191788497 commented 12 years ago
comment:24

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

dcoudert commented 12 years ago
comment:25

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.

dcoudert commented 12 years ago

Description changed:

--- 
+++ 
@@ -2,3 +2,8 @@

 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](https://github.com/sagemath/sage-prod/files/10656076/trac_13306-queen-king-knight-graphs-v2.patch.gz)
+
dcoudert commented 12 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@

 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(...)`.
+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](https://github.com/sagemath/sage-prod/files/10656076/trac_13306-queen-king-knight-graphs-v2.patch.gz)
dcoudert commented 12 years ago
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 commented 12 years ago
comment:28

Could anyone review this patch ? Thanks.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:29

(cc me)

robertwb commented 11 years ago
comment:30

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

dcoudert commented 11 years ago
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 commented 11 years ago
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 commented 11 years ago
comment:33

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

dcoudert commented 11 years ago

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

dcoudert commented 11 years ago
comment:34

Done.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
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.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago

Description changed:

--- 
+++ 
@@ -6,4 +6,4 @@

 APPLY:
 * [attachment: trac_13306-queen-king-knight-graphs-v2.patch](https://github.com/sagemath/sage-prod/files/10656076/trac_13306-queen-king-knight-graphs-v2.patch.gz)
-
+* [attachment: trac_13306-review.patch](https://github.com/sagemath/sage-prod/files/10656077/trac_13306-review.patch.gz)
dcoudert commented 11 years ago
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.
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago

Attachment: trac_13306-review.patch.gz

dcoudert commented 11 years ago
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.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:40

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

Nathann

dcoudert commented 11 years ago
comment:41

I agree with your changes. Thanks.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:42

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

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago

Changed reviewer from Sebastian Luther to Sebastian Luther, Nathann Cohen

dcoudert commented 11 years ago
comment:43

Thanks!

jdemeyer commented 11 years ago

Merged: sage-5.5.beta0