I figured it might be useful to collect the updates to different parts of my web existence in a single place, and easier to use livejournal than to roll my own. So here's the first one:

I just updated my Python algorithms library, PADS. Newly added are Sudoku.py, a command-line Sudoku puzzle solver/generator (type "python Sudoku.py -h" at a command line in the PADS directory for more information on how to use it), Repetitivity.py, analysis of paths in graphs that have no two equal consecutive edge labels (see forthcoming paper, used by Sudoku), and StrongConnectivity.py, DFS-based construction of strongly connected components in digraphs. I also added code to BipartiteMatching.py to find edges that can not participate in any perfect matching of a given graph (also used by Sudoku).

I thought the trick for finding unmatchable edges in bipartite graphs was cute; it was new to me, though probably familiar to matching specialists. Find a single perfect matching in the bipartite graph, orient the unmatched edges from one side of the bipartition to the other, and orient the matched edges in the opposite direction. The unmatchable edges are the unmatched ones that have endpoints in different strongly connected components of the resulting digraph.



Comments:

None: Graph library in Python
2005-08-02T21:30:36Z
David: I haven't looked at PADS much, but you might find this interesting if you're not aware of it. Did you know that Boost has a graph library (in C++) with Python bindings? It's experimental, the documentation isn't on the web yet, but will be very shortly. You can see it (and build it) if you download the code from the CVS (see http://www.boost.org/). You have access to all BGL algorithms, listed on http://www.boost.org/libs/graph/doc/table_of_contents.html Herve Br.
11011110:

11011110: Re: Graph library in Python
2005-08-02T23:18:17Z
Hi, Hervé. Didn't know about Boost and Python, I'll have to look into that. PADS is primarily just a collection of algorithms I've needed implementations for at some point or another, so its coverage is not very complete. But some things are much much more straightforward in Python than in C++. For instance the Boost quick tour takes about ten lines of messy code to define a 5-vertex 11-arc graph (the one in their Figure 2):
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    typedef std::pair<int, int> Edge;
    Edge edge_array[] = 
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E), };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
    Graph g(num_vertices);
    for (int i = 0; i < num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);
The same thing can be done in Python as:
    G = {0:[1,2,3,4], 1:[], 2:[0,4], 3:[0,1,4], 4:[0,1]}
I'd be interested to find out whether the Boost Python binding allows the continued use of such simplified definitions. Will send you a copy by email since I'm not sure how regularly you're likely to read here.
None: Re: Graph library in Python
2005-08-03T13:55:14Z
I don't know if I sm doing something wrong, but I have some test examples where Boost is a fair bit slower than raw Python code (not even using PADS). -- Suresh
None: input file for Sudoku.py
2005-09-06T19:00:42Z
David, I am a Python beginner/enthusiast and just recently I found your sudoku script and I am enjoying using it. I wanted to experiment with imput files but I failed: - what is the correct format of an input file? - what is the correct command line form when using an input file? Could you help me please. Thank you Andrzej Kolinski
11011110: Re: input file for Sudoku.py
2005-09-07T01:38:18Z
what is the correct format of an input file? Any text file that lists the cells in order, having a single digit for each given and some other character for the blank cells. By default the blank cells should be given as either a period or a zero, but there is an option to allow any other character to count as a blank cell. Any character other than the digits or the blank cells is ignored. So, the output the program produces is suitable to reuse as input. what is the correct command line form when using an input file? python Sudoku.py <filename or python Sudoku.py -xC <filename to use C as the blank character I suppose, since you found this unclear, I should work on documenting it more thoroughly...
11011110: Re: input file for Sudoku.py
2005-09-07T01:40:10Z
Sorry, my comment got cut off due to my forgetting to mark up the < and > signs appropriately in HTML. Here's the rest of the answer. what is the correct command line form when using an input file? python Sudoku.py <inputfile or python Sudoku.py -xC <inputfile where C is the character you want to use to denote a blank cell. I suppose, since you found this confusing, I should work on documenting it more thoroughly...
None: Re: input file for Sudoku.py
2005-09-07T12:14:37Z
sudoku.py -g option works fine (and I enjoy using your script very much). But python Sudoku.py <sud1.txt -2 -ft > sud2.txt command line where sud1.txt is for example (I tried many other input file formats): ----------------------------------- | 3 . 8 | . . . | 9 . . | | | | | | 7 . 6 | . . 3 | . 2 . | | | | | | . 1 . | . . . | 7 . . | |-----------------------------------| | 9 . . | . 7 . | . 5 . | | | | | | . . 3 | . 6 . | 2 . . | | | | | | . 2 . | . 9 . | . . 1 | |-----------------------------------| | . . 2 | . . . | . 3 . | | | | | | . 4 . | 2 . . | 8 . 6 | | | | | | . . 7 | . . . | 4 . 2 | ----------------------------------- is still giving me the same message: IOError: [Errno 9] Bad file descriptor (I know this error message by heart already) What am I doing wrong? Andrzej Kolinski
11011110: Re: input file for Sudoku.py
2005-09-07T19:55:29Z
This sounds like more a problem with how your python and command line are set up and less with how my code works. That command line should cause python to run in such a way that commands to read input from the standard input stream get their input from the filename. My code doesn't see the <filename part, it just reads from standard input. Does it work to run any other python programs with input redirected? One workaround might be, instead of redirecting input from a file, just run the program without the redirection so that it expects you to type the input, and then copy and paste it into your console window. That's the way I usually run it, actually.
None: Re: input file for Sudoku.py
2005-09-08T13:10:13Z
Does the fact that I am in the windowsXP-land have anything to do with these command line problems?
11011110: Re: input file for Sudoku.py
2005-09-08T18:43:52Z
Probably, but it also means it's going to be hard for me to diagnose them in more detail. I mostly use OS X and occasionally Solaris.
None: Re: input file for Sudoku.py
2005-10-28T11:52:04Z
I returned back to using your excellent program. Mainly because my wife is now after an "evil" level. Could you please just show me how you input data into the command line to solve a puzzle. ex.: c:\dir\sudoku.py -g -ftext > s1.txt (to generate and save) c:\dir\sudoku.py -g -2 -ftext > s1.txt (to generate, solve and save) but c:\dir\sudoku.py -? (to input a puzzle to be solved) Maybe I will then be able to figure out the way on my os (Windows XP) :-). Thank you Andrzej Kolinski
11011110: Re: input file for Sudoku.py
2005-10-28T21:59:12Z
c:\dir\sudoku.py < s1.txt (to solve the puzzle in that file)
11011110:
None: