Indexed Priority Queue in C++
Basics
Priority queues are a useful data structure e.g. when you repeatedly need to access the largest or smallest element of a set of values but want more efficiency than keeping an array ordered. The C++ standard library contains std::priority_queue, which works well for basic use cases. It offers insertion of elements as well as access and removal of the minimum (or maximum). It does not, however, offer a method for changing the priority of a value, which is needed for some applications (like Dijkstra’s algorithm to find shortest paths in graphs). Often such a method is called decreaseKey or changeKey. This post offers an implementation using a binary heap which supports this operation in O(log(n)) time.
Efficient Union-Find in C++ – or: Disjoint-set forests with Path Compression and Ranks
tl;dr: https://github.com/nspo/graphs-cpp/blob/master/general/include/DisjointSets.h
Basics
Disjoint-set data structures are useful in cases where you have a (possibly very large) number of elements and want to repeatedly execute two operations: marking two elements as connected, and checking whether two elements are connected. A query of the latter kind does not necessarily mean that the two elements p and q were explicitly connected to each other by the caller – it is possible, e.g., that p was first connected to the element r, and only much later in time q was also connected to r.
The disjoint sets in the data structure are commonly represented by trees, where each node in the tree contains a link to its parent, the parent in turn contains a link to the parent’s parent, and so on. The node at the root of the tree contains contains a link to itself, i.e. it is its own parent. All nodes of a tree are in the same set. It can be easily checked whether two elements are in the same set by evaluating whether they have the same root. The set of trees is called the disjoint-set forest. While this approach is common and can be implemented efficiently, the C++ standard library does not contain an implementation – this post tries to offer one.
Let us assume the data structure is used for N elements, each having an index between 0 and N-1. The links to the parent nodes of all elements can then easily be saved in an array of length N. If parent[p] == q, then q is the parent of p. Whenever two sets containing the elements p and q should be merged, this can be achieved by attaching the root of one element to the root of the other.
NMPC with CasADi and Python – Part 3: State-space equations of a 2-DOF robot with SymPy or MATLAB
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, we will look at determining the system equations of a robot with two degrees of freedom in stace-space form. These state-space equations can be used for simulation and for developing a nonlinear model predictive controller. For some transformation tasks, Python with SymPy will be utilized and an alternative using the MATLAB Symbolic Math Toolbox will be shown.
During the following, we are considering a robot with two links, two masses at the end of the links, and motors applying torque as control input at the joints. A diagram of the robot is shown below.
NMPC with CasADi and Python – Part 2: Simulation of an uncontrolled system
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, we will try to simulate an uncontrolled system with a forward Euler and a 4th order Runge-Kutta integration method. The latter can be the base for future closed-loop simulations.
NMPC with CasADi and Python – Part 1: ODE and steady state
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, a file describing the system equations and a script to determine a steady-state setpoint will be developed. This older post contains similar code for CasADi inside MATLAB.
Linearize nonlinear state space equation in MATLAB at steady state setpoint
This post shows one way to linearize a nonlinear state equation 
function dx = ode(t, x, u)
% example ODE
dx1 = tan(x(4)) * x(2) + 2*u(2) - 1;
dx2 = x(1) - sin(x(2));
dx3 = 13 * x(4) + u(1) + 1;
dx4 = 2*x(1);
dx = [dx1; dx2; dx3; dx4];
end
Calculate Levenshtein distance in MATLAB (words or characters) with Wagner–Fischer algorithm
This is a MATLAB implementation of the Wagner–Fischer algorithm.
Convert dSPACE ControlDesk measurements to MATLAB/Simulink timeseries (updated)
- With this updated MATLAB script, multiple dSPACE ControlDesk measurements can be imported with a single execution
- The result is saved as a tscollection (collection of timeseries) and all signals are saved with their corresponding name
- Access imported data with Simulink ‘From Workspace’ block and, e.g., dsp_tscs{1}.my_signal
Fix for Latex4CorelDraw with CorelDraw 2017
I was not able to make the official build of Latex4CorelDraw work with CorelDraw 2017 (and Windows 10). The ‘Latex’ Docker window was always empty. The solution was to recompile it with Visual Studio 2017 Community.
Convert dSPACE ControlDesk measurement to MATLAB timeseries that can be used in Simulink
- dSPACE ControlDesk can export measurements to mdf4 files or mat files
- mat file exports can be converted to timeseries with this MATLAB script
- The timeseries can then be imported into Simulink with the ‘From Workspace’ blog
- Multiple signals can be imported at once
Example output:
>> import_dspace_mat_to_simulink_ts --Imported dSPACE mat file C:\Users\Nicolai\Nextcloud\foo.mat into workspace variable dsp_ts --Time: 0.000000 s to 42.399572 s, 423980 steps --2 variables are in dsp_ts: 'In1' 'In1_1'