AlgorithmBox

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

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.

simple-cls

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

node-tralic

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

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

lucene.js

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

libgeocached

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

Source Code

https://github.com/dennycd/libgeocached

gcd-netlib

A C++ networking library built on top of Apple's grand central dispatch (libdispatch) and low-level TCP socket API

  • internal serial dispatch queue for IO processing
  • listener and delegate callback using blocks
  • non-blocking socket I/O

The library is cross-platform with build system available for Mac OS, Linux, Node.js and iOS.

Usage

const char* hostname = "localhost";  
const char* servname = "8888";

libgcdnet::NetworkAgent server(NetworkAgent::SERVER, NULL);  
server.listen(NULL, servname);

libgcdnet::NetworkAgent client(NetworkAgent::CLIENT,NULL);  
client.connect(hostname, servname);

Source Code

https://github.com/dennycd/gcd-netlib

rna-dv

RNA-DV provides an interactive GUI toolkit for visualizing and designing RNA secondary structures. It allows users to interact directly with the RNA 2-d planar structure and modify it by altering primary sequence content and connect/disconnect nucleotide bonds. It integrates thermodynamic energy calculations including

  • efn2
  • HotKnots
  • Major
  • RNAeval

It also recognizes a number of secondary structure formats including CT, RNAML and dot bracket (dp). For details, please look at the following papers

  • Herbert H. Tsang and Denny C. Dai, “RNA-DV: an interactive tool for editing and visualizing RNA secondary structures”. BCB ’12 Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine. 2012 (link)

A user manual is here GUIManual. There is also a screencast demo

RNA-DV

Source Code

https://github.com/dennycd/rna-dv

dnode-objc

An Objective-C native implementation of dnode asynchronous RPC protocol for iOS and OSX. It uses the following library

Usage

Start by subclassing DNode and define your local dnode interface in a header file.

#import "DNode.h"

@interface TestClient : DNode
-(void)foo; //the method your would like to call on remote
@end

To expose your local dnode interface to the remote, use C++ macro DEFINE_CLIENT_METHOD(local_name). For example

//the direct call from remote dnode
DEFINE_CLIENT_METHOD(hello) {  
    NSLog(@"hello from server: %@ ", args); 
}

To explicitly declare a method on remote and receive callback, use DEFINE_SERVER_METHOD_WITH_CALLBACK(remote_name)

//the callback from a previous local-to-remote call
DEFINE_SERVER_METHOD_WITH_CALLBACK(echo) {  
    NSLog(@"callback from server %@", args);
}

To invoke a method on remote, use CALL_SERVER_METHOD(remote_name, arg) whose remote_name must match the name defined in DEFINE_SERVER_METHOD_WITH_CALLBACK. For example

-(void)foo
{
    id arg = @[@"hello from client"];
    CALL_SERVER_METHOD(echo, arg);
}

To create a dnode instance and connect to a remote

TestClient* client = [[TestClient alloc] init];  
[client connectToHost:@"192.168.1.100" Port:8000 Callback:^(BOOL success, NSNumber* err){
        NSLog(@"connected %d with err %@", success, err);
    }];

Set up a delegate object to get notified on connection status

[client addListener:self CallbackQueue:dispatch_get_main_queue()];

A number of delegate callbacks are

-(void)connectSuccess; //connected to remote
-(void)connectFailed:(NSNumber*)code; 
-(void)disconnected; 
-(void)remoteReady; //remote interface ready

For details please look into the test directory for OSX and iOS demo projects.

Todo List

  • local listening server that receives remote connection
  • callback to remote from a previous remote-to-local invocation
  • more unit testing and examples

Source Code

https://github.com/dennycd/dnode-objc

iSanGuo

Much of the game specs are in Chinese language so this page is just a brief outline of what the game is about. For details please check out the GDD.

In Tales of the Three Kingdom (WiKi), historical events occur chronologically but also spatially distributed across a variety of geo-locations in China, such as Cities, Mountains, Rivers, and Ancient Relics. The game maps the story to real geographical places and put players in it by allowing them to trigger those events via location check-in.

In iSanGuo, player assume the role of an out-of-power lord and need to work his way up to establish a new kingdom. While travelling in China, player can explore historical relics, check in to a city and find out its SanGuo history, or discover some of the famous hero character NPCs during the three kingdom war.



The game’s social system is Foursquare-alike, allowing players to compete for a city ruler and will rank players against each other based on their in-game activity. Player will receive quest which requires them to complete certain tasks that are usually location relevant.

On a high-level scope, the game consists a network of city nodes interconnecting with roads and sub-divided into geographical regions. This represents a collective influence of different players in game. Assuming the role of a city ruler will spread that player’s influence across the city region and therefore changing the influence boundary against other players.

There exists an artificial economic model in each city that governs what benefits a city ruler will receive and how other player’s activity can collectively affect it. In general, this produces a micro system that allows players to play either co-operatively or competitively in the game.



Background

I started working on the game in 2012, following my previous adventure (Btwxt Games) on location-based game (WhereWars!). Though not a graphic or game designer myself, I find that potential still exist in location-based game and that much need to be done to realize the goal. I worked collaboratively with friends and various teams in China on the game. So watch this space :-)

AskMath

The Pitch

What is it ?
The objective is to enable searchable math and help people find math content on the web more easily and accurately.

What problem it is trying to solve ?
Students learn math by examples via observing how a math formula or equation is used in a variety of places. Through this, they gain perspective and deeper understanding of the knowledge. However it is difficult for them to collect these information outside the scope of textbooks: existing search engines mostly provide text-based search which makes expressing math-related query difficult.

On the other hand, academic researchers develop their knowledge and base their work on existing literatures. Academic publications contain a lot of structured math content that is valuable but difficult to index and search for. There also exist inter-dependencies among these knowledge that are up to now could only be identified with a reader’s experience and memory.

On a broader scope, the world-wide web is growing exponentially, while in the mean time, the quality of existing search engine is continuously degrading. The inherent issue is the noise being introduced by indexing mass amount of uncategorized, hard-to-filter content from heterogeneous sources. However, the reality is that people are using them as their essential learning tool on a daily basis. We believe that this is not the most effective and efficient way of self-education and knowledge discovery.

The above problems are essentially the same: the lack of a search tool to help people express structured content such as math, and the lack of ways to index, organize and present these knowledge with good quality.

How
Askmath will provide a WYSIWYG web app that allows user to enter math formulas in their natural written form. On the backend, the search involves applying heuristic algorithms to convert a presentational form of the math (e.g. MathML) to its unambiguous semantic counterparts, and then search against an indexed database of mathematic corpus to identify the relevant ones that are semantically similar to user’s query.

Why
AskMath started as a side project and I had been working with my undergrad (GDUT) friends in GuangZhou, China since 2008. The motivation is simple: we looked at the online education market in China and thought there is a gap in between what students demand to learn outside classrooms and the lack of a quality tool to do so. Especially for science and engineering study where mathematical content are the central elements, it is not easy for people to collect, organize and search for the information using existing search engines. Having had 2+ years of experiences working in a start-up (Btwxt Games) and some 5 years of academic research practice in the field of empirical algorithm design, I decided to give it a try and see what it would become.

The Architecture



  • Index DB: inverse indexing database of mathematical corpus that conforms to Apache Lucene index format
  • Redis DB: contains original raw document content that can be retrieved via unique document ID
  • Lucene Indexer: A heterogeneous parser that consumes existing mathematic content (latex source file, pdf, html, etc.) and convert into lucene index DB.
  • Search Server: Search engine core that parses user query and retrieves semantically similar content from the Index DB.
  • Web Server: serving WYSIWYG web app to the user.

Prototype Demo

http://askmath.dennycd.me
I implemented a barebone prove-of-concept prototype to demonstrate the idea. It allows you to enter simple math formulas and query against a sample database of latex documents. A few implementation details of the front-end are:

  • html layout using Bootstrap
  • math rendering with MathJax math editor is a modification on MathJax that enables interactive editing on part of the math formulas. Keyboards are enabled (direction arrows) for easier navigation within the formula.
  • socket.io and DNode are being used for client app communication with the search server.

The search server and indexer are implemented in Node.js with two native C++ module extension

  • clucene for content indexing and query that conforms to apache lucene format
  • tralics library for parsing latex source to xml expressJS, dnode and socket.io are used for communication with the front-end web app.

RoadMap

There are a lot needs to be done.

  • Scoring Function: that takes two math formulas and calculates a similarity value in between them. This would be implemented as an addon to the apache lucene’s scoring framework and ultimately drives the math indexing and search query.
  • Java-based Search Server: the clucene project is outdated and hasn’t been kept in sync with the official Apache Lucene Core. To integrate with the java-based lucene core while maintaining a high-performance web service platform, Netty.io would be a good choice.
  • Content Parsing and Aggregation: including existing online repository of academic publications, as well as mathmml content on the web.