sort-networks.git
7 years agosn-tex: Fix indentation (remove tabs). master
Florian Forster [Fri, 19 Aug 2011 15:34:04 +0000 (17:34 +0200)]
sn-tex: Fix indentation (remove tabs).

7 years agosn-tex: Added flip option (-f) to sn-tex
Moritz Muehlenthaler [Fri, 19 Aug 2011 08:08:14 +0000 (10:08 +0200)]
sn-tex: Added flip option (-f) to sn-tex

Signed-off-by: Florian Forster <octo@verplant.org>
7 years agoBump version to 1.1.0; Update ChangeLog. v1.1.0
Florian Forster [Mon, 6 Jun 2011 20:13:39 +0000 (22:13 +0200)]
Bump version to 1.1.0; Update ChangeLog.

7 years agosrc/sn-merge.c: Removed unused function.
Florian Forster [Mon, 6 Jun 2011 13:19:19 +0000 (15:19 +0200)]
src/sn-merge.c: Removed unused function.

7 years agosrc/sn-apply.c: Remove unused include.
Florian Forster [Mon, 6 Jun 2011 13:19:06 +0000 (15:19 +0200)]
src/sn-apply.c: Remove unused include.

7 years agosrc/sn_random.[ch]: Be more random.
Florian Forster [Mon, 6 Jun 2011 13:04:58 +0000 (15:04 +0200)]
src/sn_random.[ch]: Be more random.

A couple of experiments actually ran into limitations due to the limit
of the PRNG.

8 years agosrc/sn_network.c: Fix the Pairwise Sorting network for arbitrary n.
Florian Forster [Tue, 22 Feb 2011 08:03:59 +0000 (09:03 +0100)]
src/sn_network.c: Fix the Pairwise Sorting network for arbitrary n.

Powers of two worked fine before. With this change the function generates
valid sorting networks for arbitrary number of lines.

For arbitrary n, PS(n) is not as efficient nor as fast as OES(n).

8 years agosn-transpositionsort: New tool.
Florian Forster [Tue, 22 Feb 2011 07:01:40 +0000 (08:01 +0100)]
sn-transpositionsort: New tool.

8 years agosrc/sn_network.c: sn_network_network_add(): Renumber stages.
Florian Forster [Sun, 20 Feb 2011 13:42:53 +0000 (14:42 +0100)]
src/sn_network.c: sn_network_network_add(): Renumber stages.

8 years agosn-markov: Implement the "-b" option.
Florian Forster [Sun, 20 Feb 2011 13:42:35 +0000 (14:42 +0100)]
sn-markov: Implement the "-b" option.

When given, uses the bitonic merge.

8 years agosn-markov: Implement counting of comparators.
Florian Forster [Fri, 4 Feb 2011 13:08:24 +0000 (14:08 +0100)]
sn-markov: Implement counting of comparators.

8 years agosn-evolution: Add the "-m" option.
Florian Forster [Tue, 1 Feb 2011 07:43:10 +0000 (08:43 +0100)]
sn-evolution: Add the "-m" option.

8 years agosn-evolution: Disable mutation.
Florian Forster [Tue, 1 Feb 2011 06:31:24 +0000 (07:31 +0100)]
sn-evolution: Disable mutation.

8 years agosn-evolution-cut: Implement the "-n" and "-r" options.
Florian Forster [Tue, 1 Feb 2011 06:30:43 +0000 (07:30 +0100)]
sn-evolution-cut: Implement the "-n" and "-r" options.

8 years agosn-count-markov: Flush STDOUT for more immediate output when using tee.
Florian Forster [Tue, 1 Feb 2011 06:30:08 +0000 (07:30 +0100)]
sn-count-markov: Flush STDOUT for more immediate output when using tee.

8 years agosrc/sn_{network,stage}.[ch]: Implement sn_{network,stage}_show_fh.
Florian Forster [Mon, 24 Jan 2011 07:28:35 +0000 (08:28 +0100)]
src/sn_{network,stage}.[ch]: Implement sn_{network,stage}_show_fh.

8 years agosrc/sn_{network,stage}.[ch]: Implement sn_{network,stage}_compare.
Florian Forster [Mon, 24 Jan 2011 07:27:53 +0000 (08:27 +0100)]
src/sn_{network,stage}.[ch]: Implement sn_{network,stage}_compare.

8 years agosn-count-markov: Print current network when receiving SIGHUP.
Florian Forster [Mon, 24 Jan 2011 07:12:04 +0000 (08:12 +0100)]
sn-count-markov: Print current network when receiving SIGHUP.

8 years agosn-count-markov: Add tool to determine the circle length of random walks.
Florian Forster [Mon, 24 Jan 2011 06:42:08 +0000 (07:42 +0100)]
sn-count-markov: Add tool to determine the circle length of random walks.

8 years agosrc/sn_hashtable.[ch]: Implement sn_hashtable_check_collision().
Florian Forster [Mon, 17 Jan 2011 13:30:33 +0000 (14:30 +0100)]
src/sn_hashtable.[ch]: Implement sn_hashtable_check_collision().

8 years agosn-count-cuts: Implement the "-1" (exit after collision) option.
Florian Forster [Mon, 17 Jan 2011 13:30:00 +0000 (14:30 +0100)]
sn-count-cuts: Implement the "-1" (exit after collision) option.

8 years agosrc/sn_hashtable.c: Use a 40-bit hashtable.
Florian Forster [Mon, 17 Jan 2011 09:54:55 +0000 (10:54 +0100)]
src/sn_hashtable.c: Use a 40-bit hashtable.

8 years agosn-count-cuts: Tool to count the number of networks reachable through cuts.
Florian Forster [Mon, 17 Jan 2011 09:50:21 +0000 (10:50 +0100)]
sn-count-cuts: Tool to count the number of networks reachable through cuts.

8 years agosn_network_get_hashval(): Return a 64bit integer value.
Florian Forster [Thu, 13 Jan 2011 13:27:45 +0000 (14:27 +0100)]
sn_network_get_hashval(): Return a 64bit integer value.

8 years agosrc/sn_hashtable.[ch]: Add module for counting sort networks.
Florian Forster [Thu, 13 Jan 2011 11:57:16 +0000 (12:57 +0100)]
src/sn_hashtable.[ch]: Add module for counting sort networks.

8 years agosrc/sn_{network,stage}.[ch]: Implement sn_network_unify().
Florian Forster [Thu, 13 Jan 2011 11:56:30 +0000 (12:56 +0100)]
src/sn_{network,stage}.[ch]: Implement sn_network_unify().

8 years agosrc/sn_{network,stage,comparator}.[ch]: Implement sn_network_get_hashval() and friends.
Florian Forster [Thu, 13 Jan 2011 10:03:14 +0000 (11:03 +0100)]
src/sn_{network,stage,comparator}.[ch]: Implement sn_network_get_hashval() and friends.

8 years agosn-tex-cut: Add tool to visualize cut sequences.
Florian Forster [Mon, 10 Jan 2011 09:46:43 +0000 (10:46 +0100)]
sn-tex-cut: Add tool to visualize cut sequences.

8 years agoChangeLog: Update for version 1.0.0. v1.0.0
Florian Forster [Tue, 21 Dec 2010 11:14:49 +0000 (12:14 +0100)]
ChangeLog: Update for version 1.0.0.

8 years agosrc/sn-merge.c: Bitonic merge works with all numbers, now, not only powers of two.
Florian Forster [Tue, 21 Dec 2010 11:05:22 +0000 (12:05 +0100)]
src/sn-merge.c: Bitonic merge works with all numbers, now, not only powers of two.

8 years agoREADME: Updated.
Florian Forster [Tue, 21 Dec 2010 10:53:11 +0000 (11:53 +0100)]
README: Updated.

8 years agosrc/sn_network.c: Fix a memory leak in sn_network_create_odd_even_mergesort().
Florian Forster [Tue, 21 Dec 2010 10:38:31 +0000 (11:38 +0100)]
src/sn_network.c: Fix a memory leak in sn_network_create_odd_even_mergesort().

8 years agoImplement the bitonic sort in src/sn_network.c.
Florian Forster [Tue, 21 Dec 2010 10:35:12 +0000 (11:35 +0100)]
Implement the bitonic sort in src/sn_network.c.

The new implementation can handle input numbers which are not a power of
two. Also sn-bitonicmerge has been added which works analogously to
sn-oddevenmerge.

8 years agoRename "sn-pairwise" to "sn-pairwisesort".
Florian Forster [Tue, 21 Dec 2010 08:35:56 +0000 (09:35 +0100)]
Rename "sn-pairwise" to "sn-pairwisesort".

8 years agoRename "sn-batcher" to "sn-bitonicsort".
Florian Forster [Tue, 21 Dec 2010 08:33:52 +0000 (09:33 +0100)]
Rename "sn-batcher" to "sn-bitonicsort".

8 years agoREADME: Add research applications.
Florian Forster [Tue, 21 Dec 2010 08:27:52 +0000 (09:27 +0100)]
README: Add research applications.

8 years agosrc/sn_{comparator,network,random,stage}.[ch]: Change license to LGPLv2.1+.
Florian Forster [Mon, 20 Dec 2010 22:29:15 +0000 (23:29 +0100)]
src/sn_{comparator,network,random,stage}.[ch]: Change license to LGPLv2.1+.

8 years agosrc/sn_network.[ch]: Implement sn_network_network_add().
Florian Forster [Mon, 20 Dec 2010 22:11:09 +0000 (23:11 +0100)]
src/sn_network.[ch]: Implement sn_network_network_add().

8 years agosrc/sn-tex.c: Close comment (typo).
Florian Forster [Mon, 20 Dec 2010 10:30:56 +0000 (11:30 +0100)]
src/sn-tex.c: Close comment (typo).

8 years agosrc/sn-tex.c: Make it possible to specify the absolute width of the graphic.
Florian Forster [Mon, 20 Dec 2010 09:55:50 +0000 (10:55 +0100)]
src/sn-tex.c: Make it possible to specify the absolute width of the graphic.

8 years agosrc/sn-svg.c: Fix XML namespace declaration.
Florian Forster [Mon, 20 Dec 2010 09:02:45 +0000 (10:02 +0100)]
src/sn-svg.c: Fix XML namespace declaration.

8 years agoMerge remote branch 'origin/master'
Florian Forster [Mon, 20 Dec 2010 08:41:04 +0000 (09:41 +0100)]
Merge remote branch 'origin/master'

Conflicts:
src/sn-svg.c

8 years agosrc/sn-svg.c: Add the -e (embed) option.
Florian Forster [Mon, 20 Dec 2010 08:37:33 +0000 (09:37 +0100)]
src/sn-svg.c: Add the -e (embed) option.

8 years agosrc/sn-oddevenmerge.c: Only output a merging network.
Florian Forster [Mon, 20 Dec 2010 08:35:59 +0000 (09:35 +0100)]
src/sn-oddevenmerge.c: Only output a merging network.

See sn-oddevensort for a generator for the odd-even _sorting_ network.

8 years agosrc/sn_comparator.[ch]: Add a user data member.
Florian Forster [Mon, 20 Dec 2010 08:34:55 +0000 (09:34 +0100)]
src/sn_comparator.[ch]: Add a user data member.

8 years agosrc/sn-evolution-cut: Use the new cut interface.
Florian Forster [Mon, 20 Dec 2010 08:33:34 +0000 (09:33 +0100)]
src/sn-evolution-cut: Use the new cut interface.

8 years agoconfigure.ac: Remove libltdl, since it's not used.
Florian Forster [Sat, 18 Dec 2010 23:31:52 +0000 (00:31 +0100)]
configure.ac: Remove libltdl, since it's not used.

8 years agosrc/sn-svg.c: Print the SVG's height and width and a viewBox.
Florian Forster [Sat, 18 Dec 2010 11:22:37 +0000 (12:22 +0100)]
src/sn-svg.c: Print the SVG's height and width and a viewBox.

8 years agosrc/sn-markov.c: Add missing include.
Florian Forster [Sat, 18 Dec 2010 11:20:13 +0000 (12:20 +0100)]
src/sn-markov.c: Add missing include.

8 years agosrc/sn-cut.c: Use the new cut-interface to do all the cuts at once.
Florian Forster [Fri, 17 Dec 2010 21:36:24 +0000 (22:36 +0100)]
src/sn-cut.c: Use the new cut-interface to do all the cuts at once.

This greatly simplifies line numbering when doing multiple cuts.

8 years agosrc/sn_network.[ch]: Implement sn_network_cut().
Florian Forster [Fri, 17 Dec 2010 21:34:39 +0000 (22:34 +0100)]
src/sn_network.[ch]: Implement sn_network_cut().

Using this function it is possible to do multiple cuts at once.

8 years agosrc/sn_stage.c: Add missing variable.
Florian Forster [Fri, 17 Dec 2010 21:04:55 +0000 (22:04 +0100)]
src/sn_stage.c: Add missing variable.

8 years agosn-pairwise: Implement the pairwise sorting network.
Florian Forster [Fri, 17 Dec 2010 13:31:54 +0000 (14:31 +0100)]
sn-pairwise: Implement the pairwise sorting network.

8 years agosrc/sn-markov.c: Add the "-n" command line option.
Florian Forster [Fri, 17 Dec 2010 12:03:36 +0000 (13:03 +0100)]
src/sn-markov.c: Add the "-n" command line option.

Specifying the maximum number of iterations to perform.

8 years agosn-oddevensort: Copy of "sn-oddevenmerge".
Florian Forster [Tue, 14 Dec 2010 15:28:09 +0000 (16:28 +0100)]
sn-oddevensort: Copy of "sn-oddevenmerge".

8 years agosn-markov: Add Markov-chain version of sn-evolution.
Florian Forster [Mon, 13 Dec 2010 08:17:38 +0000 (09:17 +0100)]
sn-markov: Add Markov-chain version of sn-evolution.

8 years agosn-bb, sn-bb-merge: Add branch and bound algorithms for searching for sort and merge...
Florian Forster [Thu, 25 Nov 2010 14:50:45 +0000 (15:50 +0100)]
sn-bb, sn-bb-merge: Add branch and bound algorithms for searching for sort and merge networks.

8 years agoRequest X/Open 7 rather than declaring strdup ourselves.
Florian Forster [Mon, 22 Nov 2010 09:18:45 +0000 (10:18 +0100)]
Request X/Open 7 rather than declaring strdup ourselves.

8 years agosn-evolution-merge: Add programm.
Florian Forster [Mon, 22 Nov 2010 09:15:16 +0000 (10:15 +0100)]
sn-evolution-merge: Add programm.

8 years agoAdd 32 and 64 line networks found by evolution-cut.
Florian Forster [Tue, 22 Jun 2010 08:05:37 +0000 (10:05 +0200)]
Add 32 and 64 line networks found by evolution-cut.

8 years agodata/32-ec-1277190372.sn: 32-input SN found with evolution-cut.
Florian Forster [Tue, 22 Jun 2010 07:08:08 +0000 (09:08 +0200)]
data/32-ec-1277190372.sn: 32-input SN found with evolution-cut.

8 years agosn-svg: Add new tool to display sort network as SVG.
Florian Forster [Thu, 27 May 2010 07:53:51 +0000 (09:53 +0200)]
sn-svg: Add new tool to display sort network as SVG.

8 years agosrc/sn_comparator.h: Add Doxygen documentation.
Florian Forster [Wed, 19 May 2010 15:59:17 +0000 (17:59 +0200)]
src/sn_comparator.h: Add Doxygen documentation.

8 years agoMerge remote branch 'origin/master'
Florian Forster [Wed, 19 May 2010 14:49:40 +0000 (16:49 +0200)]
Merge remote branch 'origin/master'

8 years agosrc/sn_network.h: Print "NULL" in a monospace font.
Florian Forster [Wed, 19 May 2010 14:49:13 +0000 (16:49 +0200)]
src/sn_network.h: Print "NULL" in a monospace font.

8 years agosrc/sn_stage.c: Check arguments in some of the methods.
Florian Forster [Wed, 19 May 2010 12:56:32 +0000 (14:56 +0200)]
src/sn_stage.c: Check arguments in some of the methods.

8 years agosrc/sn_stage.h: Completed Doxygen documentation.
Florian Forster [Wed, 19 May 2010 12:56:10 +0000 (14:56 +0200)]
src/sn_stage.h: Completed Doxygen documentation.

8 years agodata/13i-10s-45c-[01].sn: Document the origin in a comment field.
Florian Forster [Mon, 17 May 2010 10:00:38 +0000 (12:00 +0200)]
data/13i-10s-45c-[01].sn: Document the origin in a comment field.

8 years agoAdded two more efficient 14- and 15-input sorting networks.
Florian Forster [Mon, 17 May 2010 09:56:11 +0000 (11:56 +0200)]
Added two more efficient 14- and 15-input sorting networks.

Both created from data/16i-10s-60c-0.sn by sn-evolution-cut.

8 years agodata/15i-56c-10s-0.sn: Add most-efficient 15-input sorting network.
Florian Forster [Mon, 17 May 2010 09:49:08 +0000 (11:49 +0200)]
data/15i-56c-10s-0.sn: Add most-efficient 15-input sorting network.

Found by the sn-evolution-cut algorithm. It is as efficient as the best known
15-input sorting network.

8 years agodata/14i-10s-51c-0.sn: Add most-efficient 14-input sorting network.
Florian Forster [Mon, 17 May 2010 09:46:44 +0000 (11:46 +0200)]
data/14i-10s-51c-0.sn: Add most-efficient 14-input sorting network.

Found by the sn-evolution-cut algorithm. It is as efficient as the best
known 14-input sorting network.

8 years agoAdded 16-input sorting network found by the END algorithm.
Florian Forster [Mon, 17 May 2010 09:42:16 +0000 (11:42 +0200)]
Added 16-input sorting network found by the END algorithm.

8 years agosrc/sn_stage.h: Begin adding Doxygen documentation.
Florian Forster [Mon, 17 May 2010 08:49:12 +0000 (10:49 +0200)]
src/sn_stage.h: Begin adding Doxygen documentation.

8 years agosrc/sn_stage.c: Added some parameter checks.
Florian Forster [Mon, 17 May 2010 08:48:50 +0000 (10:48 +0200)]
src/sn_stage.c: Added some parameter checks.

8 years agosrc/sn_network.h: Add missing documentation.
Florian Forster [Mon, 17 May 2010 08:48:14 +0000 (10:48 +0200)]
src/sn_network.h: Add missing documentation.

8 years agosrc/sn_network.h: All methods are documented now.
Florian Forster [Mon, 17 May 2010 08:07:00 +0000 (10:07 +0200)]
src/sn_network.h: All methods are documented now.

8 years agosrc/sn_stage.c: Fix comparison of signed and unsigned integers.
Florian Forster [Mon, 17 May 2010 07:53:49 +0000 (09:53 +0200)]
src/sn_stage.c: Fix comparison of signed and unsigned integers.

8 years agosrc/sn_{comparator,stage}.h: Add initial Doxygen stuff.
Florian Forster [Mon, 17 May 2010 07:53:27 +0000 (09:53 +0200)]
src/sn_{comparator,stage}.h: Add initial Doxygen stuff.

8 years agosrc/sn_network.[ch]: Rename the bitonic combine method.
Florian Forster [Mon, 17 May 2010 07:53:00 +0000 (09:53 +0200)]
src/sn_network.[ch]: Rename the bitonic combine method.

The sn-merge utility has been improved to accept the "-b" option and
use the bitonic variant if supplied.

8 years agosrc/sn_network.h: Some more Doxygen documentation.
Florian Forster [Mon, 17 May 2010 07:51:13 +0000 (09:51 +0200)]
src/sn_network.h: Some more Doxygen documentation.

8 years agosrc/sn_network.h: Add Doxygen documentation for some functions.
Florian Forster [Mon, 17 May 2010 06:49:43 +0000 (08:49 +0200)]
src/sn_network.h: Add Doxygen documentation for some functions.

8 years agosn-evolution-cut: Print details to the found individual.
Florian Forster [Mon, 17 May 2010 06:18:24 +0000 (08:18 +0200)]
sn-evolution-cut: Print details to the found individual.

8 years agoGlobal: collectd → libsortnetwork
Florian Forster [Fri, 14 May 2010 15:59:17 +0000 (17:59 +0200)]
Global: collectd → libsortnetwork

8 years agoAdded the best known networks for 9 and 10 inputs.
Florian Forster [Mon, 10 May 2010 16:18:35 +0000 (18:18 +0200)]
Added the best known networks for 9 and 10 inputs.

8 years agoAdded the best known networks for 13 and 16 inputs.
Florian Forster [Mon, 10 May 2010 14:19:12 +0000 (16:19 +0200)]
Added the best known networks for 13 and 16 inputs.

8 years agoREADME: Document "sn-info".
Florian Forster [Mon, 10 May 2010 14:13:06 +0000 (16:13 +0200)]
README: Document "sn-info".

8 years agosn-info: Add tool for displaying information about a network in human readable form.
Florian Forster [Mon, 10 May 2010 14:12:27 +0000 (16:12 +0200)]
sn-info: Add tool for displaying information about a network in human readable form.

8 years agosn-evolution2: Build this algorithm too when libpopulation is available.
Florian Forster [Mon, 10 May 2010 13:05:05 +0000 (15:05 +0200)]
sn-evolution2: Build this algorithm too when libpopulation is available.

8 years agosn-evolution-cut: Add new evolutionary algorithm for optimizing cuts through networks.
Florian Forster [Mon, 10 May 2010 13:04:38 +0000 (15:04 +0200)]
sn-evolution-cut: Add new evolutionary algorithm for optimizing cuts through networks.

8 years agosn-evolution: Mark appropriate arguments as unused.
Florian Forster [Mon, 10 May 2010 10:23:37 +0000 (12:23 +0200)]
sn-evolution: Mark appropriate arguments as unused.

8 years agosrc/Makefile.am: Build the "sn-evolution" application if libpopulation is available.
Florian Forster [Mon, 10 May 2010 10:23:18 +0000 (12:23 +0200)]
src/Makefile.am: Build the "sn-evolution" application if libpopulation is available.

8 years agoconfigure.ac: Link with "pthread" if no libs are given explicitly.
Florian Forster [Mon, 10 May 2010 10:22:55 +0000 (12:22 +0200)]
configure.ac: Link with "pthread" if no libs are given explicitly.

8 years agosn-cut: Include "config.h".
Florian Forster [Mon, 10 May 2010 10:10:56 +0000 (12:10 +0200)]
sn-cut: Include "config.h".

8 years agoconfigure.ac: Added check for libpopulation.
Florian Forster [Mon, 10 May 2010 10:10:39 +0000 (12:10 +0200)]
configure.ac: Added check for libpopulation.

8 years agosrc/sn_network.c: Fix comparison between signed and unsigned.
Florian Forster [Mon, 10 May 2010 09:36:21 +0000 (11:36 +0200)]
src/sn_network.c: Fix comparison between signed and unsigned.

8 years agosn-apply: Include "config.h".
Florian Forster [Mon, 10 May 2010 09:35:58 +0000 (11:35 +0200)]
sn-apply: Include "config.h".

8 years agosn-normalize: Include "config.h".
Florian Forster [Mon, 10 May 2010 09:30:50 +0000 (11:30 +0200)]
sn-normalize: Include "config.h".

8 years agosn-show: Make it possible to display more than one network at once.
Florian Forster [Mon, 10 May 2010 09:29:11 +0000 (11:29 +0200)]
sn-show: Make it possible to display more than one network at once.

8 years agoconfigure.ac: Define wanted C and POSIX versions.
Florian Forster [Mon, 10 May 2010 09:28:50 +0000 (11:28 +0200)]
configure.ac: Define wanted C and POSIX versions.

8 years agoREADME: Added some information about the utility programs.
Florian Forster [Mon, 10 May 2010 08:58:30 +0000 (10:58 +0200)]
README: Added some information about the utility programs.