public class Range : IStructuralEquatable, IStructuralComparable, IComparable {
    public int Start { get; set; }
    public int End { get; private set; }
 
    public int Size {
      get { return End - Start; }
    }
 
    public Range(int start, int end) {
      if (Start > End) throw new ArgumentException("Start cannot be greater than End.");
      Start = start;
      End = end;
    }
 
    public int CompareTo(object obj) {
      return ((IComparable)this).CompareTo(obj);
    }
 
    public int CompareTo(object other, IComparer comparer) {
      return ((IStructuralComparable)this).CompareTo(other, comparer);
    }
 
    public override bool Equals(object obj) {
      return ((IStructuralEquatable)this).Equals(obj, EqualityComparer<object>.Default);
    }
 
    public bool Equals(object other, IEqualityComparer comparer) {
      if (other == null) return false;
      var otherRange = other as SlidingWindowRange;
      if (otherRange == null) return false;
      return comparer.Equals(Start, otherRange.Start) && comparer.Equals(End, otherRange.End);
    }
 
    int IComparable.CompareTo(Object obj) {
      return ((IStructuralComparable)this).CompareTo(obj, Comparer<object>.Default);
    }
 
    int IStructuralComparable.CompareTo(Object other, IComparer comparer) {
      if (other == null) return 1;
 
      var otherRange = other as SlidingWindowRange;
 
      if (otherRange == null) {
        throw new ArgumentException("Incorrect type of other object.");
      }
 
      int c = comparer.Compare(Start, otherRange.Start);
      return c == 0 ? comparer.Compare(End, otherRange.End) : c;
    }
 
    public override int GetHashCode() {
      return ((IStructuralEquatable)this).GetHashCode(EqualityComparer<object>.Default);
    }
 
    int IStructuralEquatable.GetHashCode(IEqualityComparer comparer) {
      return Range.CombineHashCodes(comparer.GetHashCode(Start), comparer.GetHashCode(End));
    }
 
    public int GetHashCode(IEqualityComparer comparer) {
      return ((IStructuralEquatable)this).GetHashCode(comparer);
    }
 
    internal static int CombineHashCodes(int h1, int h2) {
      return (((h1 << 5) + h1) ^ h2);
    }
 
    public override string ToString() {
      StringBuilder sb = new StringBuilder();
      return (this).ToString(sb);
    }
 
    string ToString(StringBuilder sb) {
      sb.Append("(");
      sb.Append(Start);
      sb.Append(" - ");
      sb.Append(End);
      sb.Append(")");
      return sb.ToString();
    }
  }

We use symbolic expression trees in HeuristicLab in our genetic programming implementation.

I implemented the layout algorithm described in the paper of Buchheim, Jünger and Leipert, Drawing rooted trees in linear time.

The implementation is very straightforward, with the only difference that I used a dictionary to map the symbolic expression trees nodes to the node structures used by the layout algorithm.

The resulting layout:

The code:

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
  public class Node {
    public Node Thread;
    public Node Ancestor;

    public float Mod; // position modifier
    public float Prelim;
    public float Change;
    public float Shift;
    public int Number;

    public float X;
    public float Y;

    public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;

    public bool IsLeaf {
      get { return SymbolicExpressionTreeNode.SubtreeCount == 0; }
    }
  }

  public class TreeLayout {
    private float distance = 5;
    public float Distance {
      get { return distance; }
      set { distance = value; }
    }

    private ISymbolicExpressionTree symbolicExpressionTree;
    public ISymbolicExpressionTree SymbolicExpressionTree {
      get { return symbolicExpressionTree; }
      set {
        symbolicExpressionTree = value;
        nodes.Clear();
        var treeNodes = SymbolicExpressionTree.IterateNodesBreadth().ToList();
        foreach (var treeNode in treeNodes) {
          var node = new Node { SymbolicExpressionTreeNode = treeNode };
          node.Ancestor = node;
          nodes.Add(treeNode, node);
        }
        // assign a number to each node, representing its position among its siblings (parent.IndexOfSubtree)
        foreach (var treeNode in treeNodes.Where(x => x.SubtreeCount > 0)) {
          for (int i = 0; i != treeNode.SubtreeCount; ++i) {
            nodes[treeNode.GetSubtree(i)].Number = i;
          }
        }
        var r = nodes[symbolicExpressionTree.Root];
        FirstWalk(r);
        SecondWalk(r, -r.Prelim);
        NormalizeCoordinates();
      }
    }

    /// <summary>
    /// Returns a map of coordinates for each node in the symbolic expression tree.
    /// </summary>
    /// <returns></returns>
    public Dictionary<ISymbolicExpressionTreeNode, PointF> GetNodeCoordinates() {
      var dict = new Dictionary<ISymbolicExpressionTreeNode, PointF>();
      if (nodes == null || nodes.Count == 0) return dict;
      foreach (var node in nodes.Values) {
        dict.Add(node.SymbolicExpressionTreeNode, new PointF { X = node.X, Y = node.Y });
      }
      return dict;
    }

    /// <summary>
    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
    /// </summary>
    /// <returns></returns>
    public RectangleF Bounds() {
      float xmin, xmax, ymin, ymax; xmin = xmax = ymin = ymax = 0;
      var list = nodes.Values.ToList();
      for (int i = 0; i != list.Count; ++i) {
        float x = list[i].X, y = list[i].Y;
        if (xmin > x) xmin = x;
        if (xmax < x) xmax = x;
        if (ymin > y) ymin = y;
        if (ymax < y) ymax = y;
      }
      return new RectangleF(xmin, ymin, xmax + distance, ymax + distance);
    }

    /// <summary>
    /// Returns a string containing all the coordinates (useful for debugging).
    /// </summary>
    /// <returns></returns>
    public string DumpCoordinates() {
      if (nodes == null || nodes.Count == 0) return string.Empty;
      return nodes.Values.Aggregate("", (current, node) => current + (node.X + " " + node.Y + Environment.NewLine));
    }

    private readonly Dictionary<ISymbolicExpressionTreeNode, Node> nodes;

    public TreeLayout() {
      nodes = new Dictionary<ISymbolicExpressionTreeNode, Node>();
    }

    /// <summary>
    /// Transform node coordinates so that all coordinates are positive and start from 0.
    /// </summary>
    private void NormalizeCoordinates() {
      var list = nodes.Values.ToList();
      float xmin = 0, ymin = 0;
      for (int i = 0; i != list.Count; ++i) {
        if (xmin > list[i].X) xmin = list[i].X;
        if (ymin > list[i].Y) ymin = list[i].Y;
      }
      for (int i = 0; i != list.Count; ++i) {
        list[i].X -= xmin;
        list[i].Y -= ymin;
      }
    }

    private void FirstWalk(Node v) {
      Node w;
      if (v.IsLeaf) {
        w = LeftSibling(v);
        if (w != null) {
          v.Prelim = w.Prelim + distance;
        }
      } else {
        var symbExprNode = v.SymbolicExpressionTreeNode;
        var defaultAncestor = nodes[symbExprNode.GetSubtree(0)]; // let defaultAncestor be the leftmost child of v
        for (int i = 0; i != symbExprNode.SubtreeCount; ++i) {
          var s = symbExprNode.GetSubtree(i);
          w = nodes[s];
          FirstWalk(w);
          Apportion(w, ref defaultAncestor);
        }
        ExecuteShifts(v);
        int c = symbExprNode.SubtreeCount;
        var leftmost = nodes[symbExprNode.GetSubtree(0)];
        var rightmost = nodes[symbExprNode.GetSubtree(c - 1)];
        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
        w = LeftSibling(v);
        if (w != null) {
          v.Prelim = w.Prelim + distance;
          v.Mod = v.Prelim - midPoint;
        } else {
          v.Prelim = midPoint;
        }
      }
    }

    private void SecondWalk(Node v, float m) {
      v.X = v.Prelim + m;
      v.Y = symbolicExpressionTree.Root.GetBranchLevel(v.SymbolicExpressionTreeNode) * distance;
      var symbExprNode = v.SymbolicExpressionTreeNode;
      foreach (var s in symbExprNode.Subtrees) {
        SecondWalk(nodes[s], m + v.Mod);
      }
    }

    private void Apportion(Node v, ref Node defaultAncestor) {
      var w = LeftSibling(v);
      if (w == null) return;
      Node vip = v;
      Node vop = v;
      Node vim = w;
      Node vom = LeftmostSibling(vip);

      float sip = vip.Mod;
      float sop = vop.Mod;
      float sim = vim.Mod;
      float som = vom.Mod;

      while (NextRight(vim) != null && NextLeft(vip) != null) {
        vim = NextRight(vim);
        vip = NextLeft(vip);
        vom = NextLeft(vom);
        vop = NextRight(vop);
        vop.Ancestor = v;
        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + distance;
        if (shift > 0) {
          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
          MoveSubtree(ancestor, v, shift);
          sip += shift;
          sop += shift;
        }
        sim += vim.Mod;
        sip += vip.Mod;
        som += vom.Mod;
        sop += vop.Mod;
      }
      if (NextRight(vim) != null && NextRight(vop) == null) {
        vop.Thread = NextRight(vim);
        vop.Mod += (sim - sop);
      }
      if (NextLeft(vip) != null && NextLeft(vom) == null) {
        vom.Thread = NextLeft(vip);
        vom.Mod += (sip - som);
        defaultAncestor = v;
      }
    }

    private void MoveSubtree(Node wm, Node wp, float shift) {
      int subtrees = wp.Number - wm.Number;
      wp.Change -= shift / subtrees;
      wp.Shift += shift;
      wm.Change += shift / subtrees;
      wp.Prelim += shift;
      wp.Mod += shift;
    }

    private void ExecuteShifts(Node v) {
      if (v.IsLeaf) return;
      float shift = 0;
      float change = 0;
      for (int i = v.SymbolicExpressionTreeNode.SubtreeCount - 1; i >= 0; --i) {
        var subtree = v.SymbolicExpressionTreeNode.GetSubtree(i);
        var w = nodes[subtree];
        w.Prelim += shift;
        w.Mod += shift;
        change += w.Change;
        shift += (w.Shift + change);
      }
    }

    #region Helper functions
    private Node Ancestor(Node vi, Node v) {
      var ancestor = vi.Ancestor;
      return ancestor.SymbolicExpressionTreeNode.Parent == v.SymbolicExpressionTreeNode.Parent ? ancestor : null;
    }

    private Node NextLeft(Node v) {
      int c = v.SymbolicExpressionTreeNode.SubtreeCount;
      return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(0)]; // return leftmost child
    }

    private Node NextRight(Node v) {
      int c = v.SymbolicExpressionTreeNode.SubtreeCount;
      return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(c - 1)]; // return rightmost child
    }

    private Node LeftSibling(Node n) {
      var parent = n.SymbolicExpressionTreeNode.Parent;
      if (parent == null) return null;
      int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);
      if (i == 0) return null;
      return nodes[parent.GetSubtree(i - 1)];
    }

    private Node LeftmostSibling(Node n) {
      var parent = n.SymbolicExpressionTreeNode.Parent;
      if (parent == null) return null;
      int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);
      if (i == 0) return null;
      return nodes[parent.GetSubtree(0)];
    }
    #endregion
  }
}

• a generic templated genetic algorithm
• a neural network, trained with backpropagation (better training with rprop is on the way)
• some useful classes for calculating statistics (mean, variance, covariance, pearson’s R2), generating random numbers and dealing with datasets.

This code is far from complete and will likely have bugs and I will keep working on it when I have time. For now, it is available at github: https://github.com/bburlacu/meta

Usage example
The genetic algorithm optimizer ga_optimizer needs to be provided with the problem-specific operators for creating, evaluating and modifying chromosomes/individuals.

template <class Evaluator, class Creator, class CrossoverOp, class MutationOp>
class ga_optimizer;

Each of these operators can be defined by deriving the op_base base class:

template<typename ReturnType, typename... Args>
class op_base {
public:
    virtual ReturnType operator()(Args... args) = 0;
    rnd *r;
};

where each derived class should take or return pointers to ga_individual or to the derived type:

class ga_individual {
public:
	ga_individual() = default;
	ga_individual(const ga_individual&) = default;
	ga_individual(ga_individual&&) = default;
	ga_individual& operator=(const ga_individual&) = default;
	ga_individual& operator=(ga_individual&&) = default;

    virtual ~ga_individual() = default;
    virtual ga_individual* clone() = 0;
    double fitness = 0;
};

The usage is very easy to figure out if you have a look at the complete source code. There is an example of using the ga optimizer with real-valued vector chromosomes for optimizing the weights of a neural network.

Today I wanted to implement a save_to_image function for a project I was working on this week, and I thought about using GIL. So after reading the docs I figured out how it works and it’s remarkably simple.

If we have the raw image data (or can produce it in some way), in the form of three channel vectors:

unsigned char r[width*height]; // red
unsigned char g[width*height]; // green
unsigned char b[width*height]; // blue

Then we can write it to a png file, for example, like this:

#include <boost/gil/extension/io/png_io.hpp>
boost::gil::rgb8c_planar_view_t view = boost::gil::planar_rgb_view(width, height, r, g, b, width);
boost::gil::png_write_view("gil.png", view);

Also, if your image data also contains an alpha channel, then it’s just:

unsigned char a[width*height]; // red

#include <boost/gil/extension/io/png_io.hpp>
boost::gil::rgba8c_planar_view_t view = boost::gil::planar_rgba_view(width, height, r, g, b, a, width);
boost::gil::png_write_view("gil.png", view);

Don’t forget to link your program with -lpng and, if you run into compile errors, try the following workaround:

/* work around some libpng errors */
#define png_infopp_NULL (png_infopp)NULL
#define int_p_NULL (int*)NULL

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

The solution to this problem is using the following formulas for the iterative generation of new Pythagorean triples:

where:

This can be done easily using recursion:

/* Project Euler - Problems 39 and 75

   39. If p is the perimeter of a right angle triangle, {a, b, c},
       which value, for p ≤ 1000, has the most solutions?

   75. Find the number of different lengths of wire that can form
       a right angle triangle in only one way.

   http://mathworld.wolfram.com/PythagoreanTriple.html */

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef unsigned long ulong;

#define N 1500000

class Problem39
{
public:
    void solve();
private:
    vector<int> p_;
    void r_(ulong a, ulong b, ulong c);
};

void
Problem39::r_(ulong a, ulong b, ulong c)
{
    ulong p = a + b + c;
    if (p > N) return;
    for (ulong i = p-1; i < N; i += p)
    {
        p_[i] += 1;
    }

    r_( a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c );

    r_( a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c );

    r_( -a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c );
}

void
Problem39::solve()
{
    p_ = vector<int>(N, 0);
    r_ (3,4,5);

    ulong c = 0, max = p_[0], p;
    for (int i = 0; i < N; ++i)
    {
        if (max < p_[i])
        {
            max = p_[i];
            p = i+1;
        }
        if (p_[i] == 1)
            c++;
    }
    cout << "p = " << p << " (" << max << " solutions)" << endl;
    cout << "c = " << c << endl;
}

int main(void)
{
    Problem39 p;
    p.solve();
    return 0;
}

Cred că două lucruri: 1) A proceda prin întreguri, nu prin părți; întru câtva organic, nu de la simplu la compus; în nici un caz fals cartezian (fiindcă nici Descartes nu gândea așa), geometric și sistematic. 2) A lăsa întregurile să reiasă din elementul infinitezimal; a gândi deci, până la un punct, intuitiv: văzând — nu făcând, construind.

Pentru ultimul punct, Aristotel — singura dată când mă atrage — are un exemplu sugestiv. Închipuiți-vă o oaste, spune el; o oaste pusă pe fugă în neorânduială. La un moment dat (asta e tot: ”la un moment dat”), un soldat se oprește. În jurul lui se opresc alți patru–cinci. Apoi, în jurul nucleului format de ei se strând și alții, și iată dintr-o dată oastea întreagă întorcând fața către dușman și gata să primească din nou lupta.

Asta înseamnă ”viu”: unul singur, elementul infinitezimal poate să coaguleze restul. Un singur individ vertebrează totul. Nu urci matematic și gradat, de la simplu la compus, ci urci, fără compoziție, de la simplu la întreg. E paradoxul vieții, dar e paradoxul oricărei vieți.

Și mă gândesc la o concluzie ciudată: un adevărat colectivism e mai individualist decât cel care își zice așa. Sau invers: un adevărat individualism ar trebui să fie colectivist. Căci numai acesta din urmă, cel care deține întregul, știe adevăratul preț al părții. În oastea lui Aristotel, soldatul înseamnă ceva, poate ceva. Ce poate el dincolo?

Încă unul din scandalurile vieții, în istorie și dincolo de istorie.

*

Tulburătoare, vorba aceasta a lui Simmel: ”viața ca totalitate de fiecare clipă”. Așa o văd acum; așa este. În fiecare ceas simți că ești un întreg. Ai goluri, firește, dar le cunoști, deci le-ai umplut într-un oarecare fel. Ești o ființă împlinită.

Dar citești o carte: cum puteai trăi până acum fără gândurile ei? Legi o prietenie nouă: cum te puteai crede întreg fără ea? Abia acum simți golul adevărat, golul pe care ar fi trebuit să-l simți. Dar acum ești ”întreg”. Totalitate de fiecare clipă. Trăim alături unii de alții, totalitate lângă totalitate, într-o lume care nu totalizează, dar care se totalizează, parcă, în noi.

*

Singurătatea absolută? O concep câteodată așa: în tren, pe un culoar ticsit, stând pe geamantan. Ești atunci departe nu numai de orice om, mai ales de cei care te împiedică să te miști; dar ești departe și de orice punct fix în spațiu. Ești undeva, între o stație și alta, rupt de ceva, în drup spre altceva, scos din timp, scos din rost, purtat de tren, purtând după tine un alt tren, cu oameni, situații, mărfuri, idei, una peste alta, în vagoane pe care le lași în stații, le pierzi între stații, le uiți în spații, golind lumea, gonind peste lume, singur, mai singur, nicăieri de singur.

Ești undeva, între o stație și alta,
rupt de ceva,
în drup spre altceva,
scos din timp,
scos din rost,
purtat de tren,
purtând după tine un alt tren,
cu oameni, situații, mărfuri, idei,
una peste alta,
în vagoane pe care le lași în stații,
le pierzi între stații,
le uiți în spații,
golind lumea,
gonind peste lume,
singur,
mai singur,
nicăieri de singur.

Puteam să știu că-n zeama ei suava
Albastră-alburie, era otravă ?
M-am îmbătat ? Am murit ?
Lasați-mă să dorm… M-am copilărit.

Cine mai bate, nu sunt acasă,
Cine întreabă, lasă…
Cui mai pot să-i ies în drum
Cu sufletul meu de acum?…

— Tudor Arghezi

    Bunul-simț ne spune că lucrurile pământești nu există decât în mică măsură și că adevărata realitate e doar în vis. Pentru a digera bucuria naturală, ca și pe cea artificială, trebuie mai întâi să ai curajul s-o înghiți; și cei care poate merită bucuria sunt tocmai cei pentru care fericirea, așa cum o concep muritorii, a avut întotdeauna efectul unui vomitiv.
    Spiritelor neghioabe li se va părea neobișnuit, și chiar impertinent, ca o prezentare a voluptăților artificiale să-i fie dedicată unei femei, sursa cea mai obișnuită a voluptăților celor mai naturale. Cu toate acestea este evident că, așa cum lumea naturală pătrunde în cea spirituală, servindu-i drept hrană și concurând astfel la crearea acelui amalgam nedefinit pe care-l numim individualitatea noastră, femeia este ființa care proiectează cea mai mare umbră sau cea mai mare lumină în visele noastre. Femeia este fatalmente sugestivă; ea trăiește o altă viață decât pe a sa proprie; ea trăiește spiritual în nălucirile pe care le bântuie și le fecundează.
    De altfel, are prea puțină importanță dacă această dedicație este înțeleasă sau nu. Pentru mulțumirea autorului ar fi absolut necesar ca o carte, oricare ar fi ea, să fie înțeleasă, excepție făcând doar cel sau cea pentru care a fost scrisă? În sfârșit, ca să spunem totul, este indispensabil să fie scrisă pentru cineva? Cât despre mine, am atât de puțin chef pentru lumea cea vie, încât, asemenea acelor femei sensibile și lipsite de ocupație care își trimit, să zicem, prin poștă confidențele unor prieteni imaginari, aș scrie cu plăcere numai pentru morți.
    Dar nu unei moarte îi dedic această cărticică; ci cuiva care, deși bolnavă, este încă nespus de activă și de vie în mine și care-și întoarce acum toate privirile către Cer, acel loc al tuturor transfigurărilor. Căci ființa omenească se bucură de privilegiul de a putea extrage noi și subtile bucurii chiar și din durere, catastrofă și fatalitate, tot atât de bine ca dintr-un drog de temut.
    Vei vedea în această prezentare un om care se plimbă sumbru și solitar, cufundat în talazul mișcător al mulțimilor, trimițându-și inima și gândul unei Electre îndepărtate care cândva i-a șters fruntea scăldată în sudoare și i-a răcorit buzele arse de febră și vei ghici gratitudinea unui alt Oreste căruia adesea i-ai vegheat coșmarurile și i-ai risipit, cu o mână blândă, ca de mamă, somnul plin de spaime.

— Charles Baudelaire, “Paradisurile Artificiale” ]]> https://blacketernal.wordpress.com/2010/11/25/draga-prietena/feed/ 0 836 blacketernal https://blacketernal.wordpress.com/2010/11/21/one-for-the-shoeshine-man/ https://blacketernal.wordpress.com/2010/11/21/one-for-the-shoeshine-man/#respond Sun, 21 Nov 2010 09:09:18 +0000 http://blacketernal.wordpress.com/?p=817 by Charles Bukowski

flori frumoase
nu întâlnești decât toamna foarte târziu
după ce vânturile răsucite ca otgonul
și-au făcut toate mendrele, au bătut furnicile
și doar albăstrelele de câmp
au rezistat în vaza lor de loess
deschizându-și multiplele lor pleoape
cască niște priviri
pline de uimire
și aceeași nostalgie le unește
pe masa mea
cu pachetul de țigări gol
și cu mine care nu știu de ce
mă tot uit pe fereastră.

— Marin Sorescu