AlgorithmBox is an algorithm development toolkit for solving discrete optimization problems. It provides a framework for implementing metaheuristic algorithms in javascript and an empirical experiment library for testing the algorithm against a number of standard optimization problems. It can be installed as a Node.js module via

npm install algorithmbox  

How to Use

With algorithmbox, you can write a few lines of javascript code to implement a local search algorithm and run it against problems such as TSP and SAT. AlgorithmBox defined a number of basic stochastic local search algorithms including

• Simulated Annealing https://en.wikipedia.org/wiki/Simulated_annealing
• Tabu Search https://en.wikipedia.org/wiki/Tabu_search
• Hill Climbing / Iterative Improvement https://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Iterative_Improvement/Hill_Climbing

It also provides spec for the following optimization problems

• Travelling Sales Problem (TSP)
• Satisfiability Problem (SAT)

To implement a hill climbing algorithm for solving TSP, do the following

//base algorithm definition of hill climbing
var IIA = require('algorithmbox').IIA;  
var defineClass = require('algorithmbox').defineClass;

//extend the framework-provided IIA definition
var MyIIA = defineClass({  
    name : "MyIIA",
    extend : IIA, 
    methods : {

        //given a candidate solution, return a set of neighborhood
        //solutions that can be reached by 1-point mutation
        'neighbors' : function neighbors(candidate) {

        }
    }
});

To load a TSP problem instance from a file such as tsplib, do

var TSP = require('algorithmbox').TSP;

//load tsp instance from file
var raw = fs.readFileSync('tsplib/bayg29.xml');

//parse data and create a TSP instance 
var instance = new TSP(TSP.parseData(raw));  

Now run the algorithm against the problem instance

//create a IIA algorithm with predefined terminate condition
var algs = new MyIIA(instance, {  
    'terminate_ls_steps' : 1000  //stop if maximum search steps reached
});

//run the algorithm and monitor progress
algs.run(function(step){  
    console.log("step %d. best found solution: [%s]", step, algs.best_sol);
    if(algs.lo_trap)
        console.log("trapped");  //algorithm trapped in local optima
});        

Experiment and Analysis

AlgorithmBox provides a simple framework for experimenting with different problem instances and algorithm parameter configurations . To define an experiment

var Experiment = require('algorithmbox').Experiment;

var config = {  
    //test against TSP problem class
    "tsp": { 
        //run each algorithm against each TSP instance loaded from a file
        "instances" : ["bayg29.xml", "br17.xml"],   

        "algorithms": {
            //setting for a user-defined Simulated Annealing algorithm 
            "tsp_sa": [ 
                {
                    "boltzmanconst": 0.05,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.005,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.001,
                    "coolingscheme": "geometric"
                }, 
            ]
            //settings for a user-defined hill climbing algorithm
            "tsp_iia": []
        },

        //total number of independent runs (with random restart)
        "runs": 100,

        //terminate condition for each run
        "max_ls_steps" : 5000
    }
};

To run the experiment and output the raw data result to a folder:

var session = new Experiment(config, "default.box");  
session.run();  

To analyze the experimental result, use the Analyzer to load the experiment raw data

var Analyzer = require('algorithm').Analyzer;

//load runtime quality distribution result for a specific algorithm runed against a specific problem instance
var rqds = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 30});  
var rqds2 = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 10});  
var rsd = analyzer.get_runtime_solvability('sat', "uf20-01.cnf", "gsat_iia", {}, 85);  
rsd = analyzer.get_runtime_solvability('tsp', "bayg29.xml", "tsp_iia", {}, 1800);

AlgorithmBox provides the following experimental analysis matrix

• Runtime Quality Distribution showing how solution quality changes over local search steps
• Runtime Solvability Distribution showing the probability of reaching a solution quality over local search steps
• Problem Solution Quality shows the average solution of the algorithm across mutlitple problem instances over a number of indepedent runs

For further details, please look into the test case examples.

Visualization and Ploting

A sample visualization is provided (test/test_visualization.js) that demonstrate how to use Socket.IO and D3 to visualize the runtime quality distribution of a typical experiment. In the test folder, do

nodeunit test_visualization.js  

In the browser, open

localhost:8888  

and you would obtain the runtime quality distribution showing how solution quality (Y Axis for minimization problem) improves over runtime (X axis as local search steps)

Source Code and RoadMap

https://github.com/dennycd/algorithmbox
AlgorithmBox is still a new concept under developement. Contributors are welcomed.

a simple class system for node.js that adds a number of object-oriented features to the basic javascript language, including

• convinient class definition with inheritance
• abstract class a.k.a. interface support
• runtime introspection with dynamic type checking

The design goal is to provide a clean and easily understandable class system while minimizing overhead and avoid poluting the javascript built-in objects. It is inspired and built upon the defineClass from JavaScript The Definitive Guide.

Usage

Install the package "simple-cls"

npm install simple-cls  

To define a class, do the following

var cls = require('simple-cls')

var MyClass = cls.defineClass({  
    //optional class name 
    name : "MyClass",
    //optional super class, default is Object
    extend : BaseClass,
    //constructor code
    construct : function(msg){
        this.msg = msg;
    }, 
    //instance methods
    methods: {  
        foo: function() {
            console.log("foo");
        }
    },
    //instance variables
    variables: {
        bar : 1,
        msg : null
    },
    // class level variables or methods
    statics : {

    }
});

To instantiate an object and start using it

var obj = new MyClass("hello");  
obj.foo();  
console.log(obj.bar);  

Concept

in simple-cls, the class system is built upon a chain of triple objects, namely the Prototype, Constructor and Class. As the diagram shows, instantiating a new js object will establish a relationship from the bottom up, starting at the object instance. Using javascript's built-in function we can obtain the prototype of that object.

assert.ok(Object.getPrototypeOf(obj) === MyClass.prototype);)  

The prototype object itself is an object instance of the superclass of MyClass. If no superclass is given, it is defaulted to Object. MyClass is an alias of the Constructor function for obj

assert.ok(obj.constructor === MyClass)  

The Class object contains runtime information about the obj class and can be obtained via __class on the constructor or .getClass() methods

assert.ok(obj.constructor.__class === obj.getClass())  

To check if a js object is an instance of a class, or an instance of a subclass of some super classes

test.ok(obj.getClass().isKindOfClass('MyClass'));  
test.ok(obj.getClass().isKindOfClass('BaseClass'));  
test.ok(obj.getClass().isKindOfClass(MyClass.__class));  
test.ok(obj.getClass().isKindOfClass(BaseClass.__class));  

To look at all the methods callable from the obj, including methods defined on the super class

console.log(obj.getClass().getMethods());  

For details, please look at the unit test examples.

Source Code

https://github.com/dennycd/node-cls

A node.js module for converting latex source to javascript json. It is a wrapper based on the following c library

• TRALICS http://www-sop.inria.fr/marelle/tralics/

To install the package in npm

npm install tralics  

To analyze a latex file

var tralic = require('tralics');  
var util = require('util');

tralic.analyze("hello.tex", function(doc){  
    console.log("DOC " + util.inspect(doc));
});

Source Code

https://github.com/dennycd/node-tralic

A Javascript Port of Apache Lucene Core. Lucene.js is a javascript implementation of the popular apache lucene search engine core. you can use it as

• a server-side javascript module running on Node.js
• a js library run directly in the client-side browser

Library features including

• framework API conforming to the latest apache lucene core spec
• pure javascript-based implementation with optional C++ node.js module addon
• integrated networking module
• indexing DB with efficient and scalable data structure format

Source code

https://github.com/dennycd/lucene.js

A fast in-memory geospatial index and query library in C++. The library supports the following

• indexing of arbitray object types with geolocation tag via C++ template
• efficient geohash-based spatial partitioning and search tree implementation for geospatial query
• optional persistency support for NoSQL library including Redis and MongoDB (in-progress)
• cross-platform availability incluing MacOSX, iOS, GNU Linux, Node.js and Windows

Usage

To create a new geocache matrix, do

#include <matrix.hpp>

libgeocached::Matrix<DataObject> matrix; //DataObject can be any type  

To add an object into the matrix and associate it with an id and location tag:

//data insertion
ObjectID id1 = ObjectIDNew();  
DataObject obj("dummy");  
GCLocation location =  GCLocationMake(23.23234, -123.34324);  
matrix.insert(id1, obj, location);  

To query for all objects within a circular geographical area

#include <vector>
...
//define a circle area with center lat/lng and 1000 meter radius
GCCircle circle = GCCircleMake(GCLocationMake(23.23234, -123.34324), 1000);  
std::vector<DataObject> objs;

//circular query
matrix.objs_in_circle(circle, objs);

for(DataObject& obj : objs)  
    cout << obj << endl;

Internal Implementation

libgeocached uses an efficient search tree implementation called GCTree for hierarchical partitioning of geographical space and object indexing. Each tree node represents a rectangular geo cell with bounding latitude (north,south) and longitude (west,east) edges. It uses a binary representation of the geohash values for both lat and lng. For example, a 15bit precision binary geohash

latitude:  0b101000010000101  
longitude: 0b001010000100101

represents a rectangle bounding box of the following edge values

lat_south:    23.2305908203125  
lat_north:    23.236083984375  
lng_west:    -123.343505859375  
lng_east:    -123.33251953125  

Each internal tree node has a branching degree of 4, with each child representing adding an additional lowest bit to its latitude and longitude values

lat lng  
0   0    south half along latitude, west half along longitude  
0   1    south half along latitude, east half along longitude  
1   0    north half along latitude, west half along longitude  
1   1    north half along latitude, east half along longitude  

By going down 1 tree level, the geo cell is partitioned into four sub regions by halfing at the centre line along both latitude and longitude directions. Internal node at tree level k represents a geo rectangle having k bit precision (assuming 0 bit at root node). The leaf node of the tree has the highest bit precision and therefore corresponding to the smallest geo rectangle. Reference to the objects are stored at the leaf nodes.

Runtime Complexity

For a fixed maximum bit representation, the height of the GCTree is bounded by the number of bits K. Therefore inserting an object into the tree is bounded by O(K) . Deletion via geolocaiton tag also requires finding the leaf node containing the object which is O(K).

A spatial query on the gctree resembles that of a R-tree operation by first locating the minimum bounding rectangle cell encompassing the query region, and then recursively traverse down the sub regions and collect all objects fall within the query area.

Performance

More performance evaluation matrix to come for the next milestone release

Version

Current: 0.0.1

Build and Install

platform specific build scripts and projects are available under build folders

References

• Geographiclib http://geographiclib.sourceforge.net/
• libgeohash https://github.com/lyokato/libgeohash
• libspatialindex http://libspatialindex.github.io/
• RTree http://superliminal.com/sources/sources.htm#C%20&%20C++%20Code

Source Code

https://github.com/dennycd/libgeocached