Sparse bitsets in C++
Sparsity when referring to systems indicates that they are loosely coupled. Thus, a sparse matrix is a matrix in which most of its elements are zero, a sparse graph has very few adjacent vertices (its adjacency matrix is also sparse) etc. Opposite to sparsity is density, and dense systems are those that are strongly coupled.
In a recent post we proposed BITSCAN a recent C++ library to manipulate bit strings. A comparative survey with other state of the art implementations (such as bitset (STL), or dynamic_biset(BOOST)) may be found here. This post brifely describes how BITSCAN operates with sparse bitsets.
How did biicode begin?
…certainly not in a parking lot, but Pablo San Segundo and I were pretty close to the one at the University the very first time Diego explained biicode to us.
I consider myself lucky for being part of biicode’s birth. The day we decided its name, or those endless meetings with a chalkboard full of diagrams, the first “battle logo” as we named our first “company mascot”.
In addition, I really enjoy my work as a university professor and engineer. Thanks to the university I have had the opportunity to devote myself to something that fascinated me since I was a child: robotics. But you cannot master robotics without solid programming skills, so I’ve been programming since I started hacking the fascinating Commodore 64, with its “peek” and “poke”, and his incredible voice synthesizer accessible through a simple command: “say”.
Hacking the Commodore 64 was classy.
ZMQ or ZeroMQ is one of the coolest open source libraries out there. It fills a real necessity in a new, brilliant way. It is very active, has bindings to many languages… that’s why it is so popular.
I was a professor in university, teaching C/C++, software engineering, distributed systems (plain old sockets, SOAP, web…), and I really enjoyed keeping my classes up to date and teaching last trends and technologies. If I was still a teacher, I would definitely teach some sessions using ZeroMQ.
As Nacho Lasheras points out in his blog Orcs and Fireballs
Once you’ve grasped the basics of coding (variables, execution flow, conditions, loops, functions, etc.) you can start learning how to develop “easy” games. It’s important to go step by step. Do not try to rush and start programming in C++, OpenGL and Android at the same time because it can be overwhelming.
Watchduino is an open source Arduino Smart Watch that combines inexpensive electronic parts with complex Arduino (C++) code. It’s fully hackable from hardware to software. You can build your own one, it’s useful and reprogrammable.
This is the first chapter of our story, a story in which we embarked on a journey to create biicode. We hope this gives you a hint of the pains and gains of creating a start-up from scratch. This is our story.
Why I quit a tenure track position as professor
I’m Diego Rodriguez-Losada, the first promoter of biicode and one of its founders. Right before embracing this adventure, I had a comfortable position as a professor in Universidad Politecnica de Madrid.
Professor Jose Daniel García (UC3M) explains its main features:
This week ISO/IEC JTC1 has reported that DIS 14882, the revision to the C++ Standard, has been APPROVED with 0 negative votes. What does this mean in practice? Well, it is just another step towards the publication of the new version of the C++ standard that will eventually get the official name of ISO/IEC 14882:2014 (C++14 for friends).
The ISO C++ committee aka WG21. Not standard people at all!
Today, by the hand of Pablo San Segundo, we present graph and ugraph, two simple, easy-to-use, C++ wrappers for unweighted graphs encoded as bit strings.
One of the most interesting and versatile applications of bit strings is to encode simple unweighted graphs dynamic in the number of edges (i.e. there is an efficient way to add/remove edges but not so for the vertices). Graphs encoded as bit strings have recently attracted the attention of researchers in relation to well known NP-hard problems such as vertex coloring or clique. The main reason is that efficient algorithms that exploit bit-parallelism at CPU level have been found for such problems.
This is is a small explanation about BITSCAN, the C++ library exclusively developed by Pablo San Segundo.
BITSCAN is dedicated to the efficient processing of bit strings. In programming, a bit string is a data structure that stores collections of 1s and 0s. It gets interesting when those 1s and 0s refer to a Boolean property of a group, so that each element of this group is identified by a bit of that chain.
Time to move your pawns forward
A good example of this is the game of chess. In a chessboard each position is formed by six different types of pieces with two possible colours. A string of 64 bits can encode the position of all pieces of the same type and color on the board (e.g. “white pawns”) by referring each bit to a square with the semantics of a value to 1 (TRUE) if the square is occupied by a piece of the chosen type and 0 (FASLE) otherwise. Continue reading