Graftal

[Kyon]

I recently read a few articles on graftals, and then felt the urge to program again (since a very long time). I made a little application that will accept a set of rules (constants don't need to be defined) and will apply those rules to a string.

I've currently got this:

// Graftal
#include <iostream>
#include <string>
#include <list>

using namespace std;

struct CRule // Basically just a structure with an input and an output string, no real functionality
{   public:
        std::string a;
        std::string b;
        CRule():a(""),b("") {}
        CRule(std::string A, std::string B):a(A),b(B) {}
        CRule(const CRule& r):a(r.a), b(r.b) {}};

struct CRuleSet // This contains all rules and functionality
{   private:
        std::list<CRule> rs; // The rules
        unsigned apply(std::string& s, unsigned i); // Private member function that applies the needed rule to position i in string s

    public:
        CRuleSet() {}
        void add(CRule r) {rs.push_back(r);} // Add a rule
        void applyrules(std::string& s);};

unsigned CRuleSet::apply(std::string& s, unsigned i)
{   for(std::list<CRule>::iterator it = rs.begin(); it!=rs.end();it++)
    {   if (it->a == s.substr(i, it->a.size())) // if there is a match
        {   s.erase(i,it->a.size()); // remove the checked for string
            s.insert(i,it->b); // add the needed string
            return it->b.size();}} // Move on with the amount of characters that are outputted (to prevent from appending that which is just added)
    return 1;} // Move on 1

void CRuleSet::applyrules(std::string& s)
{
    unsigned x=0;
    while(x<s.size()) x+=apply(s,x); // Apply the appropriate rule and increment x so that the just appended part doesn't get appended more than once per iteration
}

int main()
{
    CRuleSet set;
    set.add(CRule("0","1[0]0"));
    set.add(CRule("1","11"));

    std::string x("0");
    for(unsigned u=0;u<=10;u++)
    {   cout << u << " " << x << endl;
        set.applyrules(x);}
    return 0;
}

And I was thinking on how I would go about adding probabilistic rules and context sensitive rules. Context sensitive will probably be the easiest to do, as I just need to add two strings and check for them. But how would I go around doing proper* probabilistic rules?

* Proper, as in, they will in the following example always apply either one of the rules, instead of doing a "dice roll" every time a rule is applied.
0 (0.5) → 1[0]0
0 (0.5) → 0

Thanks in advance,



Kyon

[hamsterman]

I'd suggest changing your CRule to

struct CRule{
   string a;
   vector<string> b;
   string choose_random_b();
}

and replacing it->b in s.insert(i,it->b); // add the needed string with it->choose_random_b().
It's fairly easy to implement choose_random_b() and assign each element it's own probability. (Randomize a double R = [0; 1]. Then for each string in b, if it's probability P is higher than R, you've got your choice, else do R -= P and go to the next element.)
You'll want to modify the constructor into something more comfortable though.. (I suggest overloading operator << (CRule&, string) )
Should I explain any of the above?

[Kyon]

That seems like a neat way to get around the problem.. You're a genius. :P

[Kyon]

Woo, thanks to you, I finished my Graftal header file. :3

For anyone interested, here it is:

/*
** Name:          Graftal.h
** Functionality: Adds CRule and CRuleSet classes to simulate regular, stochastic and context sensitive graftal grammars.
** Made by:       T. "Kyon" Westendorp
** Example:

CRuleSet graftal;
graftal.add(CRule("1","1","1")>>"1[0]1" // If there is a 1 in between a 1 and a 1, there is a 50% chance it will change into 1[0]1
                              >>"1");   // If there is a 1 in between a 1 and a 1, there is a 50% chance of not changing
graftal.add(CRule("1")>>"11");  // Change 1 into 11
graftal.add(CRule("0")>>"1[0]0" // 50% chance of changing 0 into 1[0]0
                      >>"0");   // 50% chance of not changing

std::string x = "0"; // Apply the rules to this axiom

for(unsigned u=0;u<=10;u++) // Evaluate the outcome for the first 10 steps (first printing the axiom)
{
    cout << u << " " << x << endl;
    graftal.applyrules(x);
}

*/

#ifndef GRAFTAL_H_INCLUDED
#define GRAFTAL_H_INCLUDED

#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>

struct CRule
{   public:
        std::string a;
        std::vector<std::string> b;
        std::string front;
        std::string back;
        CRule():a(""),front(""),back("") {}
        CRule(std::string A,std::string f="",std::string b=""):a(A),front(f),back(b) {}
        CRule(const CRule& r):a(r.a),b(r.b),front(r.front),back(r.back) {}
        CRule& operator>>(std::string s);
        inline void randomize();};

struct CRuleSet
{   private:
        std::list<CRule> rs;
        unsigned apply(std::string&,unsigned);
    public:
        inline void add(CRule);
        void applyrules(std::string&);};

CRule& CRule::operator>>(std::string s) {b.push_back(s); return *this;}

void CRule::randomize() {random_shuffle(b.begin(), b.end());}

void CRuleSet::add(CRule r) {rs.push_back(r);}

void CRuleSet::applyrules(std::string& s) {unsigned x=0;while(x<s.size()) x+=apply(s,x);}

unsigned CRuleSet::apply(std::string& s, unsigned i)
{   for(std::list<CRule>::iterator it = rs.begin(); it!=rs.end();it++)
    {   if ((it->front==""||(i>=it->front.size()&&it->front==s.substr(i-it->front.size(),it->front.size())))&&it->a==s.substr(i,it->a.size())&&(it->back==""||(i<=s.size()-it->back.size()&&it->back==s.substr(i+it->a.size(),it->back.size()))))
        {   it->randomize();
            s.erase(i,it->a.size());
            s.insert(i,it->b[0]);
            return it->b[0].size();}}
    return 1;}


#endif // GRAFTAL_H_INCLUDED