# Generic Template Markov Chain

This is a simple real state based markov chain (I'm using real states instead of a markov matrix to enable making an animated version later).

My goal was to make the markov chain as generic and reusable as possible, while practicing using smart pointers.

What general coding style, performance, semantic, or functional improvements could I make?

#pragma once
#include <memory>
#include <list>
#include <vector>
#include <iostream>

template <typename T>
class State;

template <typename T>
struct Transition {
std::shared_ptr<State<T>> nextState;
int rawCount;
float weight;
Transition(std::shared_ptr<State<T>> nextState);
};

template <typename T>
class State {
std::list<Transition<T>> transitions;

public:
T data;
float startWeight;
int rawStartCount;

State(T data);
void calculateTransitionWeights();
std::shared_ptr<State<T>> getNextState(float randomValue);
};

template <typename T>
class MarkovChain {
std::vector<std::shared_ptr<State<T>>> states;
std::shared_ptr<State<T>> currentState;

public:
MarkovChain();
void addData(T data, bool isStartData = false);
void calculateWeights();
void setStartState(float randomValue);

};

template <typename T>
Transition<T>::Transition(std::shared_ptr<State<T>> nextState) {
weight = 0;
rawCount = 0;
this->nextState = nextState;
}

template <typename T>
State<T>::State(T data) {
rawStartCount = 0;
startWeight = 0;
this->data = data;
}

template <typename T>
void State<T>::addTransitionEvent(std::shared_ptr<State<T> > nextState) {
bool tansitionAlreadyExists = false;
for (auto&& transition : transitions) {
if (nextState->data == transition.nextState->data) {
transition.rawCount++;
break;
}
}

transitions.push_back(Transition<T>(nextState));
transitions.back().rawCount++;

}
}

template <typename T>
void State<T>::calculateTransitionWeights() {
int weightCounter = 0;
for(auto&& transition : transitions) {
weightCounter += transition.rawCount;
}
for(auto&& transition : transitions) {
if (!weightCounter) {
std::cout << "No Counter Values!" <<std::endl;
weightCounter = 1;
}
transition.weight = float(transition.rawCount) / float(weightCounter);
}

}

template <typename T>
std::shared_ptr<State<T>> State<T>::getNextState(float randomValue) {
float value = randomValue;
for(auto&& transition : transitions) {
value -= transition.weight;
if (value >= 0.01) {
return transition.nextState;
}
}
return transitions.front().nextState;//This should never get called
std::cout <<"\nError\n";
}

template <typename T>
MarkovChain<T>::MarkovChain() {
currentState = std::shared_ptr<State<T>>(nullptr);
}

template <typename T>
void MarkovChain<T>::addData(T data, bool isStartData) {
if (states.size()==0) {
auto newState = std::make_shared<State<T>>(data);
currentState = newState;
newState->rawStartCount++;
states.push_back(newState);
} else {
bool stateAlreadyExists = false;
std::shared_ptr<State<T>> newState(nullptr);
for (auto&& state: states) {
if (state->data == data) {
newState = state;
break;
}
}
newState = std::make_shared<State<T>>(data);
states.push_back(newState);
}
currentState = newState;
if (isStartData) {
newState->rawStartCount++;
}

}
}

template <typename T>
void MarkovChain<T>::calculateWeights() {
int startWeightCounter = 0;
for (auto&& state: states) {
startWeightCounter += state->rawStartCount;
state->calculateTransitionWeights();
}
for (auto&& state: states) {
state->startWeight = float(state->rawStartCount) / float(startWeightCounter);
}
}

template <typename T>
void MarkovChain<T>::setStartState(float randomValue) {
float value = randomValue;
for (auto&&state :  states) {
value -= state->startWeight;
if (value > 0.01 ) {
currentState = state;
}
}
}

template <typename T>
T MarkovChain<T>::getDataAndAdvance(float randomValue) {
T currentData = currentState->data;
currentState = currentState->getNextState(randomValue);
return currentData;
}


Sample main()

#include <iostream>
#include <array>
#include <cstdlib>
#include <ctime>
#include <string>
#include "MarkovChain.hpp"
#include "MarkovChain.cpp"

int main(int argc, const char * argv[]) {

srand (static_cast <unsigned> (time(0)));

MarkovChain<std::string> chain;

for(auto number : numbers) {
}
chain.calculateWeights();
chain.setStartState(static_cast <float> (rand()) / static_cast <float> (RAND_MAX));
for (int i = 0; i<100; i++) {
std::cout << (chain.getDataAndAdvance(static_cast <float> (rand()) / static_cast <float> (RAND_MAX)));
std::cout << " ";
}

std::cout << std::endl;

}


On your general coding style:

First the little things:

template <typename T>
Transition<T>::Transition(std::shared_ptr<State<T>> nextState) {
weight = 0;
rawCount = 0;
this->nextState = nextState;
}

• Use the initializer list of your constructor, that would also elide the necessity of the "this->" see here.
• Later you will always set rawCount to 1 after the construction, so why not here? Your weight would also be better initialized with 1.0f. This would result in:

template <typename T>
Transition<T>::Transition(std::shared_ptr<State<T>> nextState) :
weight(1.0f),
rawCount(1),
nextSate(nextState)
{
/* nothing */
}

• I would suggest to make the "transitions" member a std::vector. All you do is push_back and iterate over it. Since you asked specifically for performance: A vector stores its data in continous memory, a list not neccessraily, thus iterating over a vector will (general) be faster. See this question for detailed comparison.

• If you want to only increment a variable use the prefix operator. For example this newState->rawStartCount++; should be changed to ++(newState->rawStartCount);. The brackets add a little clarity. The reason for that is discussed in many Q/A, for example here. One reason is that the postfix might be less efficient because it needs to store a temporal copy of the value. Another reason is clarity: If you want to increment a value just do it and do nothing extra. Or better: Using the postfix can always lead to someone wondering if you need the old value.

• const-correctness in range-base for-loops. If you do not change the state of the elements make them const. So this

for(auto&& transition : transitions) {
weightCounter += transition.rawCount;
}


should become

for(const auto&& transition : transitions) {
weightCounter += transition.rawCount;
}

• const correctnes in general. I do not see a single const in your code. But there are variables and functions which should be const, for example the numbers in your main function. Always try to make your code as const correct as you can do it.

• use static_cast for number conversions. In your main function you do it but in MarkovChain<T>::calculateWeights() you use float(state->rawStartCount) / float(startWeightCounter);. This should also be a static_cast. One reason is that you can better look it up with search-functions. And again it expresses clearly what you do which is a "static cast". Again more detailed discussion is here.

• Replace std::endl with "\n" when appropriate. std::endl not only inserts a newline it also flushes the stream. This is in most situations not neccessary and can also lead to a huge performance impact.

• Delete not reachable code. In getNextSate(float), the output after the return is useless.

Now a few design related things:

Class State:

• Why do you make some variables public and some private? If you want to use it as a "Storage" which has nothing more to do as to save the data then use a struct, otherwise I would advise to use a class and make every Member private. The purpose is that you have control over the access of the member and thus you can make your class "hard to use wrong" and if you you need permanent access to it from somewhere else maybe the member is misplaced. Example "startWeight" of the Class State is never used in the class itself. Maybe the Class MarkovChain shoukd have a struct which savaes a State and its startWeight.

• "Make it hard to use wrong" : Your program depends on the fact that a user first adds the data, than calls calculateWights() and than iterates. Why not let the addData function update the Weights every time it is called? If you feel bad about the performance maybe you can build a addData function which takes a whole std::vector.

• "A Function should have only one responsibility" : I would break your getDataAndAdvance(float) in one function getData() and one advance(float). This would make the code better to understand and the user could also operate multiple times on the same data before advancing.

And last but not least Bugs:

• The state for the data added last to the chain will not have any transitions, thus getNextState(float) will crash.

• As for your return "will never be called" I would suggest to use assertions. These can be usefull to tell everyone who reads the code what preliminaries you expect. For example in getNextState: assert(randomValue <= 1.0 + 1e-06) will show that you expect the randomValue to be lower than 1.0. I inserted the + 1e-06 cause of problems with comparing floating points. You can insert the same for randomValue >= 0.

I hope this helps a bit.