Free suffix trees algorithm software for linux

STX B+ Tree project is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset and multimap and follow their interfaces very closely. By packing multiple value pairs into each node of the tree the B+ tree reduces heap fragmentation and utilizes cache-line effects better than the standard red-black binary tree.
The tree algorithms are based on the implementation in Cormen, Leiserson and Rivests Introduction into Algorithms, Jan Janninks paper and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementations correctness by testing the tree invariants.
The main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments btree.h.
Special interest was put into performing a speed comparison test between the standard red-black tree and the new B+ tree implementation. The speed test results are interesting and show the B+ tree to be significantly faster.
Enhancements:
- This release introduces the demonstration program wxBTreeDemo.
- This program draws illustrations of the B+ trees constructed by the STX B+ Tree template classes.
- It allows the user to select different types of B+ tree instantiations: integer or string keys and different slot numbers.
- The user may insert and erase key/data pairs from the tree and run different search operations.
- The demo program uses the cross-platform wxWidgets toolkit and can be compiled on Linux, Windows, and Mac OS X.

mcl-algorithm is a scalable cluster algorithm for graphs based on stochastic flow.
The flow process employed by the algorithm is mathematically sound and intrinsically tied to cluster structure in graphs, which is revealed as the imprint left by the process.
The threaded implementation has handled graphs of up to one million nodes within hours, and is widely used in the field of protein family analysis. It comes with a wide range of sibling utilities for handling and analyzing graphs, matrices, and clusterings.
The MCL algorithm simulates flow using (alternating) two simple algebraic operations on matrices. Its formulation is simple and elegant. There are no high-level procedural instructions for assembling, joining, or splitting of groups - cluster structure is bootstrapped via a flow process that is inherently affected by any cluster structure present.
The first operation used by MCL is expansion, which coincides with normal matrix multiplication. Expansion models the spreading out of flow, it becoming more homogeneous. The second is inflation, which is mathematically speaking a Hadamard power followed by a diagonal scaling. Inflation models the contraction of flow, it becoming thicker in regions of higher current and thinner in regions of lower current. The MCL process causes flow to spread out within natural clusters and evaporate inbetween different clusters.
- By varying parameters, clusterings on different scales of granularity can be found. The number of clusters can not and need not be specified in advance, but the algorithm can be adapted to different contexts.
- The issue how many clusters? is not dealt with in an arbitrary manner, but rather by strong internal logic. Cluster structure leaves its marks on the flow process simulated by the algorithm, and the flow parameters control the granularity of the cluster imprint.
- The limit of the MCL process (the process simulated by the algorithm) is in general extremely sparse, and the iterands are sparse in a weighted sense. This gives the means to scale the algorithm drastically, leading to a worst-case complexity of order Nk^2, where N is the number of nodes of the input graph, and where k is a threshold for the number of resources allocated per node.
- The rate of convergence of the MCL process, and projection of the iterands afterwards onto the resulting clustering, give hooks for unsupervised parameter adjustment.
- The iterands of the MCL process have structural properties which allow a cluster interpretation, and which generalize the mapping of MCL limits onto clusterings. The mathematics associated with the MCL process shows that there is an intrinsic relationship between the MCL process and cluster structure in graphs. This is very valuable given the many heuristic approaches in cluster analysis.
Enhancements:
- Numerous cleanups in much of the code.
- Improvements in caching intermediate results.

Genetic Algorithm File Fitter (gaffitter) is a command-line software written in C++ that extracts --via Genetic Algorithm-- subsets of an input list of files/directories that best fit the given volume size (target), such as CD, DVD and others. Genetic Algorithm File Fitter is initially designed to run under Linux and POSIX systems, but easily portable to non-POSIX operating environment.
Using GA search, gaffitter improve different combinations of the files on the list so that the lost of space will be minimized. Ideal to be used for backups/records in CD, DVD and others.
Main features:
- Uses a global meta-heuristic (Genetic Algorithm search).
- The command-line interface provides high integration (via pipe) with other tools, i.e. works as a "filter".
- Pretty configurable. gaffitter have many input parameters to control/adjust its behavior (including GA params).
- It is free software! (GPL)
Usage:
gaffitter [options...] < files >
... | gaffitter - [options...] [files]
General options:
-t < n >, --target < n >
target size [default = 700]
--bytes
target, min and max size in bytes
--kb
target, min and max size in kibi bytes (KiB)
--mb
target, min and max size in mebi bytes (MiB) [default]
--gb
target, min and max size in gibi bytes (GiB)
-i < n >, --iter < n >
number of iterations [default = 1]
-v, --verbose
verbose
--min < n >, --min-size < n >
minimum file size [default = none]
--max < n >, --max-size < n >
maximum file size [default = none]
--bs < n >, --block-size < n >
the smallest amount of bytes a file can occupy [default = 1]
--ss, --show-size
print size of each output file
--sb, --show-bytes
print output sizes in bytes too
--su, --show-unselected
print unselected files
--hsel, --hide-selected
Dont print selected files
--hs, --hide-summary
hide summary line containing sum, difference and number of
selected files
-h, --help
this help
Enhancements:
- This release fixes a bug regarding an uninitialized variable and changes the default behavior of GAFFitter, which now extracts the volumes as much as possible (with unlimited iterations).

C Algorithms Library is a collection of commonly used Computer Science algorithms.
The focus is on code that is well documented and tested, portable, and reusable.
The C Programming Language has a much smaller standard library compared to other more modern programming languages such as Java or Python.
In particular, it lacks implementations of many common data structures and algorithms. This is a collection of such algorithms to attempt to alleviate this problem.
The source code is released under the Modified BSD license, and as such can be freely modified and reused in any project, either proprietary or free. It is written in 100% ANSI standard C.
Each algorithm is written to be independent from the other implementations, allowing particular algorithms to be included in projects as needed.
Data structures
Collections
ArrayList : Automatically resizing array.
Doubly linked list : A set of values stored in a list with links that point in both directions.
Singly linked list : A set of values stored in a list with links that point in one direction.
Queue : Double ended queue which can be used as a FIFO or a stack.
Set : Unordered set of values.
Mappings
Hash table : Collection of values which can be addressed using a key.
Trie : Fast mapping using strings as keys.
Binary search trees
AVL tree : Balanced binary search tree with O(log n) worst case performance.
Utility functions
All of the above data structures operate on void pointers. It is sometimes necessary to compare values (when sorting a list, for example) or generate a hash key (in a hash table or set). This is done by providing a pointer to a function which provides this functionality. The following functions provide this functionality for some common data types.
- Integer comparison and hash functions.
- String comparison and hash functions.
- Generic (void) pointer comparison and hash functions.

Algorithm::Diff is a Perl module to compute `intelligent differences between two files / lists.

SYNOPSIS

require Algorithm::Diff;

# This example produces traditional diff output:

my $diff = Algorithm::Diff->new( @seq1, @seq2 );

$diff->Base( 1 ); # Return line numbers, not indices
while( $diff->Next() ) {
next if $diff->Same();
my $sep = ;
if( ! $diff->Items(2) ) {
printf "%d,%dd%dn",
$diff->Get(qw( Min1 Max1 Max2 ));
} elsif( ! $diff->Items(1) ) {
printf "%da%d,%dn",
$diff->Get(qw( Max1 Min2 Max2 ));
} else {
$sep = "---n";
printf "%d,%dc%d,%dn",
$diff->Get(qw( Min1 Max1 Min2 Max2 ));
}
print "< $_" for $diff->Items(1);
print $sep;
print "> $_" for $diff->Items(2);
}


# Alternate interfaces:

use Algorithm::Diff qw(
LCS LCS_length LCSidx
diff sdiff compact_diff
traverse_sequences traverse_balanced );

@lcs = LCS( @seq1, @seq2 );
$lcsref = LCS( @seq1, @seq2 );
$count = LCS_length( @seq1, @seq2 );

( $seq1idxref, $seq2idxref ) = LCSidx( @seq1, @seq2 );


# Complicated interfaces:

@diffs = diff( @seq1, @seq2 );

@sdiffs = sdiff( @seq1, @seq2 );

@cdiffs = compact_diff( @seq1, @seq2 );

traverse_sequences(
@seq1,
@seq2,
{ MATCH => &callback1,
DISCARD_A => &callback2,
DISCARD_B => &callback3,
},
&key_generator,
@extra_args,
);

traverse_balanced(
@seq1,
@seq2,
{ MATCH => &callback1,
DISCARD_A => &callback2,
DISCARD_B => &callback3,
CHANGE => &callback4,
},
&key_generator,
@extra_args,
);