Free algorithm demo software for linux

Algorithm::Permute is a Perl module with handy and fast permutation with object oriented interface.

SYNOPSIS

use Algorithm::Permute;

my $p = new Algorithm::Permute([a..d]);
while (@res = $p->next) {
print join(", ", @res), "n";
}

my @array = (1..9);
Algorithm::Permute::permute { print "@arrayn" } @array;

This handy module makes performing permutation in Perl easy and fast, although perhaps its algorithm is not the fastest on the earth. Currently it only supports permutation n of n objects.

No exported functions. This version is not backward compatible with the previous one, version 0.01. The old interface is no longer supported.

METHODS

new [@list]

Returns a permutor object for the given items.

next

Returns a list of the items in the next permutation. The order of the resulting permutation is the same as of the previous version of Algorithm::Permute.

peek

Returns the list of items which will be returned by next(), but doesnt advance the sequence. Could be useful if you wished to skip over just a few unwanted permutations.

reset

Resets the iterator to the start. May be used at any time, whether the entire set has been produced or not. Has no useful return value.

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.

Algorithm::Loops is a Perl module with looping constructs: NestedLoops, MapCar*, Filter, and NextPermute*.

SYNOPSYS

use Algorithm::Loops qw(
Filter
MapCar MapCarU MapCarE MapCarMin
NextPermute NextPermuteNum
NestedLoops
);

my @copy= Filter {tr/A-Z.,"()/a-z/d} @list;
my $string= Filter {s/s*$/ /} @lines;

my @transposed= MapCarU {[@_]} @matrix;

my @list= sort getList();
do {
usePermutation( @list );
} while( NextPermute( @list ) );

my $len= @ARGV ? $ARGV[0] : 3;
my @list= NestedLoops(
[ ( [ 1..$len ] ) x $len ],
sub { "@_" },
);

If you want working sample code to try, see below in the section specific to the function(s) you want to try. The above samples only give a feel for how the functions are typically used.

Algorithm::BinPack is a Perl module that can efficiently pack items into bins.

SYNOPSIS

Algorithm::BinPack efficiently packs items into bins. The bins are given a maximum size, and items are packed in with as little empty space as possible. An example use would be backing up files to CD, while minimizing the number of discs required.

my $bp = Algorithm::BinPack->new(binsize => 4);

$bp->add_item(label => "one", size => 1);
$bp->add_item(label => "two", size => 2);
$bp->add_item(label => "three", size => 3);
$bp->add_item(label => "four", size => 4);

for ($bp->pack_bins) {
print "Bin size: ", $_->{size}, "n";
print " Item: ", $_->{label}, "n" for @{ $_->{items} };
}

METHODS

new

Creates a new Algorithm::BinPack object. The maximum bin size is specified as a named argument binsize, and is required. A fudge factor may be specified as a named argument fudge. If a fudge factor is specified, item sizes will be rounded up to a number divisible by the fudge factor. This can help keep items with similar sizes in order by their labels.

my $bp = Algorithm::BinPack->new(binsize => 4);
my $bp = Algorithm::BinPack->new(binsize => 100, fudge => 10);

add_item

Adds an item to be packed into a bin. Required named arguments are label and size, but any others can be specified, and will be saved. An optional bin argument can be used to manually put an item into the specified bin.

$bp->add_item(label => one, size => 1);
$bp->add_item(label => two, size => 2, desc => The second numeral);
$bp->add_item(label => zero, size => 3, bin => 0);
$bp->add_item(qw(label three size 3));
$bp->add_item(qw(label four size 4 random key));

prefill_bin

(Deprecated method) add_item now knows how to handle the bin argument directly, so this method is redundant.

pack_bins

Packs the items into bins. This method tries to leave as little empty space in each bin as possible. It returns a list of hashrefs with the key size containing the total bin size, and items containing an arrayref holding the items in the bin. Each item is in turn a hashref containing the keys label, size, and any others added to the item. If a fudge factor was used, each item will contain a key fudgesize, which is the size this item was fudged to.

for my $bin ($bp->pack_bins) {
print "Bin size: ", $bin->{size}, "n";

for my $item (@{ $bin->{items} }) {
printf " %-6s %-20sn", $_, $item->{$_} for keys %{ $item };
print " ---n";
}
}

Algorithm::SixDegrees is a Perl module that can find a path through linked elements in a set.

SYNOPSIS

use Algorithm::SixDegrees;

my $sd1 = Algorithm::SixDegrees->new();
$sd1->data_source( actors => &starred_in );
$sd1->data_source( movies => &stars_of );
@elems = $sd1->make_link(actors, Tom Cruise, Kevin Bacon);

my $sd2 = Algorithm::SixDegrees->new();
$sd2->forward_data_source( friends => &friends, @args );
$sd2->reverse_data_source( friends => &friend_of, @args );
@elems = $sd2->make_link(friends, Bob, Mark);

Algorithm::SixDegrees is a Perl implementation of a breadth-first search through a set of linked elements in order to find the shortest possible chain linking two specific elements together.

In simpler terms, this module will take a bunch of related items and attempt to find a relationship between two of them. It looks for the shortest (and generally, simplest) relationship it can find.

Algorithm::Huffman is a Perl extension that implements the Huffman algorithm.

SYNOPSIS

use Algorithm::Huffman;

my %char_counting = map {$_ => int rand(100)} (a .. z, A .. Z);
# or better the real counting for your characters
# as the huffman algorithm doesnt work good with random data :-))

my $huff = Algorithm::Huffman->new(%char_counting);
my $encode_hash = $huff->encode_hash;
my $decode_hash = $huff->decode_hash;

my $encode_of_hello = $huff->encode_bitstring("Hello");

print "Look at the encoding bitstring of Hello: $encode_of_hellon";
print "The decoding of $encode_of_hello is ", $huff->decode_bitstring($encode_of_hello), "";

This modules implements the huffman algorithm. The aim is to create a good coding scheme for a given list of different characters (or even strings) and their occurence numbers.

ALGORITHM

Please have a look to a good data compression book for a detailed view. However, the algorithm is like every good algorithm very easy.

Assume we have a heap (keys are the characters/strings; values are their occurencies). In each step of the algorithm, the two rarest characters are looked at. Both get a suffix (one "0", the other "1"). They are joined together and will occur from that time as one "element" in the heap with their summed occurencies. The joining creates a tree growing on while the heap is reducing.
Lets take an example. Given are the characters and occurencies.

a (15) b(7) c(6) d(6) e(5)

In the first step e and d are the rarest characters, so we create this new heap and tree structure:

a(15) de(11) b(7) c(6)

de
/
"0"/ "1"
d e

Next Step:

a(15) bc(13) de(11)

de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Next Step:

a(15) bcde(24)

bcde
/
"0"/ "1"
/
de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Next Step unifies the rest:

Huffman-Table
/
"0"/ "1"
/
/
bcde a
/
"0"/ "1"
/
de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Finally this encoding table would be created:

a 1
b 010
c 011
d 000
e 001

Please note, that there is no rule defining what element in the tree is ordered to left or to right. So its also possible to get e.g. the coding scheme:

a 0
b 100
c 101
d 110
e 111

IDS::Algorithm::MM is a Perl module created to learn or test using a first-order Markov Model (MM).

SYNOPSIS

A usage synopsis would go here. Since it is not here, read on.
In section 4.2 in Kruegel and Vignas paper, they ignored the probability information that the MM provided, and produced a binary result. In effect, they were using the constructed MM as a {N,D}FA.

Someday more will be here.

Ideally, we would be using the algorithm from stolcke94bestfirst. Constructing a DFA rather than a NFA in effect has performed most of the state merging that stolcke93hidden do.

Consider also a java or C/C++ implementaion: http://www.ghmm.org/ http://www.run.montefiore.ulg.ac.be/~francois/software/jahmm/

Useful information: http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html L R Rabiner and B H Juang, `An introduction to HMMs, IEEE ASSP Magazine, 3, 4-16.

printvcg

printvcg(filehandle)

Print in a form usable by VCG for printing the DFA.

If the filehandle is specified, print there; otherwise, print to STDOUT.
This code was stolen from DFA, and does not know about the probabilities.
load(filehandle)

Load a MM from a file; this is the inverse of "print", and the format we expect is that used in $self->print.

test(tokensref, string, instance)

Test the string of tokens and calculate the probability of the string being seen. At each stage, we get a p in [0,1]. The result is the product of these probabilities.
Note that if a transition cannot be made, we return a 0 probability.

add(tokensref, string, instance)

The collection of tokens (in the list referenced by tokensref) is a complete example of a list that should be accepted by the DFA.

string and instance are IDS::Test framework arguments that we ignore because we do not need them.

WE add the transition from the last token to the (ACCEPT) state.

add_transition(from, token)

Add a transition from one state to another when the specified token is received. It is not an error to try to add an existing transition. In that event, this function quietly returns. If no such transition exists, we look for a transition on the token; if so, we add an edge to the destination node for the existing edge. Finally, if there is no other choice, we create a new state and add the edge.

generalize()

Reduce the number of states in the model.

Our building a DFA rather than a NFA has in effect performed most of the state merging that would have occurred.

XXX We should still be doing some checks for additional merge possibilities.
XXX A proof that the DFA is effectively the NFA with merged states would be useful.