| Commit message (Collapse) | Author | Age |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Having stated the principle in the previous commit, I should apply it
consistently. A source file linked into the Puzzles library of common
support code should not also define a main() under ifdef.
This commit only goes as far as the _library_ support modules. It
would be a much bigger job to do the same for all the actual _puzzles_
that have test main()s or standalone-solver main()s. And it's not
necessary, because modifying one of those source files only triggers a
rebuild of _one_ puzzle, not absolutely everything. (Not to mention
that it's quite likely the puzzle and the test main() will need to be
modified in conjunction anyway.)
As in the previous commit, this has required exposing a few internal
API functions as global, and maybe editing them a bit. In particular,
the one-shot internal function that divvy_rectangle() loops on until
it succeeds is now exposed as divvy_rectangle_attempt(), which means
the test program doesn't have to condition a failure counter into the
real function.
I've thrown away penrose-vector-test completely, because that didn't
look like a test program with any ongoing use at all - it was surely
vestigial, while James was getting the vector representation up and
running in the first place.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
I noticed commit db3b531e2cab765a00475054d2e9046c9d0437d3 in the history
where Simon added a bunch of "static" qualifiers. That suggested that
consistently marking internal functions "static" is desirable, so I
tried a build using GCC's -Wmissing-declarations, which requires prior
declaration (presumed to be in a header file) of all global functions.
This commit makes the GTK build clean under GCC's
-Wmissing-declarations. I've also adding "static" to a few obviously
internal objects, but GCC doesn't complain about those so I certainly
haven't got them all.
|
| |
|
|
|
|
|
| |
This is mostly so that the function is used at all, but I've also
removed another memory leak from --autotest mode to make it apparently
leak-free. The testing from standard input mode has more leaks than I
want to fix.
|
| |
|
|
|
|
|
|
|
|
| |
This is the main bulk of this boolification work, but although it's
making the largest actual change, it should also be the least
disruptive to anyone interacting with this code base downstream of me,
because it doesn't modify any interface between modules: all the
inter-module APIs were updated one by one in the previous commits.
This just cleans up the code within each individual source file to use
bool in place of int where I think that makes things clearer.
|
| |
|
|
|
|
| |
This commit removes the old #defines of TRUE and FALSE from puzzles.h,
and does a mechanical search-and-replace throughout the code to
replace them with the C99 standard lowercase spellings.
|
|
|
This is a dedicated algorithm for finding a maximal matching in a
bipartite graph.
Previously I've been solving that problem in this code base using
maxflow.c, modelling the graph matching problem as a restricted case
of the optimal network flow problem and then using a full-strength
algorithm for the latter. That's overkill, and also algorithmically
wasteful - the H-K algorithm is asymptotically better, because it can
find multiple augmenting paths in each pass (hence getting the maximum
benefit out of each expensive breadth-first search), as a consequence
of not having to worry about lower- or higher-value augmenting paths
in this restricted problem.
So I expect this algorithm to be faster, at least in principle or in
large cases, when it takes over the jobs currently being done by
maxflow. But that's not the only benefit. Another is that the data
representation is better suited to the problems actually being solved,
which should simplify all the call sites; a third is that I've
incorporated randomisation of the generated matching into the H-K
module itself, which will further save effort at each call site
because they will no longer have to worry about permuting the
algorithm's input - they just have to pass it a random_state and it
will take care of that internally.
This commit only introduces the new matching.c and builds a test
utility for it. I haven't yet migrated any clients of maxflow.
|
