comparison src/sc_grammar.cpp @ 0:add35537fdbb tip

Initial import

+//  Copyright 2011, Ian Hobson.
+//
+//  This file is part of gpsynth.
+//
+//  gpsynth 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.
+//
+//  gpsynth 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 gpsynth in the file COPYING. 
+//  If not, see http://www.gnu.org/licenses/.
+
+#include "sc_grammar.hpp"
+
+#include "boost_ex.hpp"
+#include "graph_helpers.hpp"
+#include "logger.hpp"
+#include "statistics.hpp"
+#include "std_ex.hpp"
+
+#include "json/json.h"
+
+#include "boost/graph/random.hpp"
+#include "boost/graph/topological_sort.hpp"
+
+#include <iostream>
+#include <iterator>
+#include <fstream>
+#include <set>
+#include <sstream>
+
+const int g_maximum_mixer_channels = 3;
+
+const double g_probability_command_node_command = 0.85;
+const double g_probability_command_node_special = 0.15;
+
+const double g_probability_mod_node_command = 0.25;
+const double g_probability_mod_node_special = 0.15;
+const double g_probability_mod_node_constant = 0.4;
+
+const double g_probability_argument_affected = 1.0;
+
+const double g_probability_input_mutation = 1.0;
+const double g_probability_connection_mutation = 1.0;
+
+const double g_minimum_connection_weight = 0.001;
+
+namespace {
+  
+  double MapCoefficientToRange(double c, const stdx::Range<double>& range) {
+    return range.minimum_ + (range.Size() * c);
+  }
+  
+  // Returns argument connection weight and offset, scaled to argument input
+  void GenerateWeightAndOffset(const sc::Argument& argument,
+                               sg::CommandRate rate,
+                               sg::Connection* connection) {
+    const stdx::Range<double>& scale_range = (rate == sg::kControlRate) 
+                                             ? argument.range_control_
+                                             : argument.range_;
+    if (argument.fixed_range_) {
+      connection->weight_ = scale_range.Size();
+      connection->offset_ = scale_range.Minimum();
+    } else if (argument.name_ == "in") {
+      // input connections don't have an offset
+      double weight = stdx::RandomCoefficient();
+      if (rate == sg::kAudioRate) {
+        // square audio weightings
+        connection->weight_ = weight * weight;
+      }
+    } else {
+      // generate random weight and offset
+      double weight;
+      do {
+        weight = stdx::RandomCoefficient();
+      } while (weight < g_minimum_connection_weight);
+      double offset = stdx::RandomRange(0.0, 1.0 - weight);
+      switch (argument.scaling_mode_) {
+        case sc::Argument::kScalingLinear:
+          connection->weight_ = MapCoefficientToRange(weight, scale_range);
+          connection->offset_ = MapCoefficientToRange(offset, scale_range);
+          break;
+
+        case sc::Argument::kScalingLog:
+          connection->weight_ = MapCoefficientToRange(weight * weight * weight,
+                                                      scale_range);
+          connection->offset_ = MapCoefficientToRange(offset * offset * offset,
+                                                      scale_range);
+          break;
+
+        case sc::Argument::kConstant:
+          throw std::runtime_error("ApplyRandomWeightAndOffset - preset argument provided");
+      }
+    }
+  }
+
+sc::Argument ParseArgument(const Json::Value& json) {
+  sc::Argument arg;
+  arg.name_ = json.get("name", "").asString();
+  if (json.isMember("constant")) {
+    arg.scaling_mode_ = sc::Argument::kConstant;
+    arg.constant_value_ = json["constant"].asDouble();
+    return arg;
+  }
+  if (json.isMember("range")) {
+    const Json::Value range = json["range"];
+    arg.range_.SetMinimum(range[0].asDouble());
+    arg.range_.SetMaximum(range[1].asDouble());
+  }
+  if (json.isMember("range_control")) {
+    const Json::Value range = json["range_control"];
+    arg.range_control_.SetMinimum(range[0].asDouble());
+    arg.range_control_.SetMaximum(range[1].asDouble());
+  } else {
+    arg.range_control_ = arg.range_;
+  }
+  if (json.isMember("fixed_range")) {
+    arg.fixed_range_ = json["fixed_range"].asBool();
+  }
+  std::string scaling = json.get("scaling", "linear").asString();
+  if (scaling == "linear") {
+    arg.scaling_mode_ = sc::Argument::kScalingLinear;
+  } else if (scaling == "log") {
+    arg.scaling_mode_ = sc::Argument::kScalingLog;
+  }
+  return arg;
+}
+
+sc::Command ParseCommand(const Json::Value& json,
+                         const std::map<std::string, sc::Argument>& types,
+                         sc::Command::CommandMode command_mode) {
+  if (json.type() == Json::stringValue) {
+    return sc::Command(json.asString(), command_mode);
+  }
+  // name
+  std::string name = json["name"].asString();
+  // output type
+  sc::Command::OutputType output_type = sc::Command::kAll;
+  if (json.isMember("output")) {
+    std::string output = json["output"].asString();
+    if (output == "control") {
+      output_type = sc::Command::kControl;
+    } else if (output == "audio") {
+      output_type = sc::Command::kAudio;
+    }
+  }
+  // arguments
+  std::vector<sc::Argument> args;
+  // [in] argument for modifiers
+  if (command_mode == sc::Command::kModifier) {
+    args.push_back(sc::Argument("in"));
+  }
+  Json::Value json_args = json["args"];
+  Json::ValueType arg_type = json_args.type();
+  if (arg_type == Json::stringValue) {
+    // single argument as string
+    args.push_back(sc::Argument(json_args.asString()));
+  } else if (arg_type == Json::objectValue) {
+    // single argument object
+    if (json_args.isMember("type")) {
+      args.push_back(stdx::GetFromMap(types, json_args["type"].asString()));
+      args.back().name_ = json_args["name"].asString();
+    } else {
+      args.push_back(ParseArgument(json_args));
+    }      
+  } else {
+    // array of arguments
+    for (int i = 0; i < json_args.size(); i++) {
+      Json::Value arg = json_args[i];
+      if (arg.type() == Json::stringValue) {
+        args.push_back(sc::Argument(arg.asString()));
+      } else {
+        if (arg.isMember("type")) {
+          args.push_back(stdx::GetFromMap(types, arg["type"].asString()));
+          args.back().name_ = arg["name"].asString();
+        } else {
+          args.push_back(ParseArgument(arg));
+        }
+      }
+    }
+  }
+  // success
+  return sc::Command(name, command_mode, output_type, args);
+}
+
+
+sc::Command ParseSource(const Json::Value& json,
+                        const std::map<std::string, sc::Argument>& types) {
+  return ParseCommand(json, types, sc::Command::kSource);
+}
+
+sc::Command ParseModifier(const Json::Value& json,
+                          const std::map<std::string, sc::Argument>& types) {
+  return ParseCommand(json, types, sc::Command::kModifier);
+}
+
+void MutateValue(double* value, bool* mutation_occurred,
+                 double range_min = 0.0, double range_max = 1.0) {
+  // add gaussian noise to values, low variance 
+  static bx::GaussianGenerator generator = bx::MakeGaussianGenerator(0, 0.125);
+  double new_value = stdx::Clamp(*value + generator(), range_min, range_max);
+  if (*value != new_value) {
+    *value = new_value;
+    *mutation_occurred = true;
+  }
+}
+  
+} // namespace
+
+
+
+namespace sc {
+  
+Grammar::Grammar(const std::string& json_data)
+: max_depth_(3)
+{ 
+  ParseJSON(json_data); 
+}
+
+void Grammar::ParseJSON(const std::string& json_data) {
+  commands_.clear();
+  Json::Reader reader;
+  Json::Value root;
+  if (!reader.parse(json_data, root)) {
+    std::stringstream message;
+    message << "Grammar::Parse: Failed to parse data\n"
+            << reader.getFormattedErrorMessages();
+    throw std::runtime_error(message.str());
+  }
+  try {
+    // argument types
+    // stores predefined argument types while parsing grammar
+    std::map<std::string, Argument> argument_types;
+    const Json::Value& args = root["arg-types"];
+    for (int i = 0; i < args.size(); i++) {
+      const Json::Value& arg = args[i];
+      argument_types[arg["type"].asString()] = ParseArgument(arg);
+    }
+    // sound sources
+    const Json::Value& sources = root["sources"];
+    for (int i = 0; i < sources.size(); i++) {
+      commands_.push_back(ParseSource(sources[i], argument_types)); 
+    }
+    // modifiers
+    const Json::Value& modifiers = root["modifiers"];
+    for (int i = 0; i < modifiers.size(); i++) {
+      commands_.push_back(ParseModifier(modifiers[i], argument_types));
+    }
+  } catch (const std::exception& e) {
+    std::stringstream message;
+    message << "Grammar::Parse: " << e.what();
+    throw std::runtime_error(message.str());
+  }
+}
+  
+int Grammar::RandomCommand(sg::CommandRate rate,
+                           int tree_depth,
+                           bool must_be_modifier /* = false */) const {
+  Command::OutputType output;
+  Command::CommandMode mode;
+  CommandID command = -1;
+  CommandID number_of_commands = commands_.size();
+  // if we're at or one away from maximum depth then the command needs to 
+  // be a source, headroom of 1 for some parameter control
+  bool must_be_source = (tree_depth >= (max_depth_ - 1));
+  do {
+    command = stdx::Random(number_of_commands);
+    output = commands_[command].Output();
+    if (rate == sg::kAudioRate) {
+      do {
+        command = stdx::Random(number_of_commands);
+        output = commands_[command].Output();
+      } while (!(output == Command::kAll || output == Command::kAudio));
+    } else {
+      do {
+        command = stdx::Random(number_of_commands);
+        output = commands_[command].Output();
+      } while (!(output == Command::kAll || output == Command::kControl));
+    }
+    mode = commands_[command].Mode();
+  } while ((must_be_source && (mode != Command::kSource))
+           || (must_be_modifier && (mode != Command::kModifier)));
+  return static_cast<int>(command);
+}
+  
+sg::Vertex Grammar::CreateCommand(sg::Graph &graph,
+                                  sg::CommandRate rate,
+                                  int depth,
+                                  bool must_be_modifier /* = false */,
+                                  bool make_modifier_input /* = true */) const {
+  // select a random command for the node
+  int command_id = RandomCommand(rate, depth, must_be_modifier);
+  // create the node and add it to the graph
+  sg::Node command_info(command_id, sg::kCommand, rate);
+  sg::Vertex vertex = boost::add_vertex(command_info, graph);
+  // a modifier command has to have further nodes added to its main input
+  const Command& command = commands_[command_id];
+  for (int i = 0; i < command.Arguments().size(); i++) {
+    const Argument& argument = command.GetArgument(i);
+    if (argument.name_ == "in") {
+      if (make_modifier_input) {
+        // modifier input must be given a command tree
+        sg::Vertex tree = RandomTree(graph, rate, kTreeMode_Command, depth + 1);
+        sg::Connection connection(i);
+        GenerateWeightAndOffset(argument, rate, &connection);
+        boost::add_edge(tree, vertex, connection, graph);
+      }
+    } else if (argument.scaling_mode_ == sc::Argument::kConstant) {
+      // don't attach inputs to predefined arguments
+      continue;
+    } else if (stdx::Chance(g_probability_argument_affected)) {
+      // randomly create input for command arguments
+      sg::Vertex tree = RandomTree(graph,
+                                   sg::kControlRate,
+                                   kTreeMode_Mod,
+                                   depth + 1);
+      sg::Connection connection(i);
+      GenerateWeightAndOffset(argument, rate, &connection);
+      boost::add_edge(tree, vertex, connection, graph);  
+    }
+  }
+  return vertex;
+}
+  
+sg::Vertex Grammar::RandomTree(sg::Graph &graph,
+                               sg::CommandRate rate,
+                               TreeMode tree_mode,
+                               int depth) const {
+  enum NodeType {
+    kCommand,
+    kSpecial,
+    kConstant,
+    kParameter
+  };
+  static stats::ProbabilitySelector node_type_selector;
+  if (!node_type_selector.Initialized()) {
+    std::vector<double> probabilities(3);
+    probabilities[kCommand] = g_probability_mod_node_command;
+    probabilities[kSpecial] = g_probability_mod_node_special;
+    probabilities[kConstant] = g_probability_mod_node_constant;
+    node_type_selector.SetProbabilities(probabilities);
+  }
+  // establish the type of node to create
+  int node_type;
+  if (depth >= max_depth_) {
+    if (tree_mode == kTreeMode_Command) {
+      // if we're at maximum depth in command mode then create a command
+      node_type = kCommand;
+    } else {
+      // in mod mode at maximum depth pick either a constant or parameter
+      if (stdx::Chance(g_probability_mod_node_constant)) {
+        node_type = kConstant;
+      } else {
+        node_type = kParameter;
+      }
+    }
+  } else {
+    if (tree_mode == kTreeMode_Command) {
+      if (stdx::Chance(g_probability_command_node_command)) {
+        node_type = kCommand;
+      } else {
+        node_type = kSpecial;
+      }
+    } else {
+      // mod mode below max depth, any node type is ok
+      node_type = static_cast<NodeType>(node_type_selector());
+    }   
+  }
+  if (node_type == kCommand) {
+    return CreateCommand(graph, rate, depth);
+  } else if (node_type == kSpecial) {
+    int command = stdx::Random(Command::kNumberOfSpecialCommands);
+    return SpecialCommand(command, graph, rate, tree_mode, depth + 1);   
+  } else if (node_type == kConstant) {
+    return boost::add_vertex(sg::Node(stdx::RandomCoefficient()), graph);
+  } else if (node_type == kParameter) {
+    return boost::add_vertex(sg::Node(RandomParameter(graph), sg::kParameter),
+                             graph);
+  }
+  throw std::runtime_error("Grammar::RandomTree - unknown node type"); 
+}
+
+int Grammar::RandomParameter(sg::Graph& graph) const {
+  // as a simple rule, randomly pick an existing parameter, or if chosen 
+  // parameter is greater than # of parameters, then add a new one
+  std::vector<double>& parameters = graph[boost::graph_bundle].parameters_;
+  int number_of_parameters = static_cast<int>(parameters.size());
+  // parameter ids start at 1
+  int parameter = stdx::RandomRangeInt(1, number_of_parameters + 1);
+  // bump parameter count if we've got a new parameter
+  if (parameter > number_of_parameters) {
+    // store a random value for the new parameter
+    parameters.push_back(stdx::RandomCoefficient());
+  }
+  return parameter;
+}
+
+void Grammar::AddTreeToSpecialCommand(sg::Vertex command_node,
+                                      sg::Graph& graph,
+                                      int input_id,
+                                      TreeMode tree_mode,
+                                      sg::CommandRate command_rate,
+                                      bool* constant_added,
+                                      std::set<int>* parameters,
+                                      int depth) const {
+  bool success = false;
+  while (!success) {
+    sg::Vertex tree;
+    // first channel or audio command should enforce a command source
+    if (input_id == 0) {
+      tree = RandomTree(graph, command_rate, kTreeMode_Command, depth + 1);
+    } else {
+      tree = RandomTree(graph, command_rate, tree_mode, depth + 1);
+    }
+    sg::NodeType tree_type = graph[tree].type_;
+    if (tree_type == sg::kConstant) {
+      // we only need one constant per mixer
+      if (*constant_added) {
+        RemoveSubTree(tree, graph);
+        continue;
+      }
+      *constant_added = true;
+    } else if (tree_type == sg::kParameter) {
+      // we don't want duplicated parameters for special command inputs
+      if (parameters->find(graph[tree].id_) != parameters->end()) {
+        RemoveSubTree(tree, graph);
+        continue;
+      }
+      // store the parameter id
+      parameters->insert(graph[tree].id_);
+    }
+    // apply weighting
+    double weight = stdx::RandomCoefficient();
+    if (command_rate == sg::kAudioRate) {
+      // scale audio to curve
+      weight *= weight;
+    }
+    // make the connection to the generated tree
+    boost::add_edge(tree, command_node, sg::Connection(weight), graph);
+    success = true;
+  }
+}
+  
+sg::Vertex Grammar::SpecialCommand(int command_id,
+                                   sg::Graph& graph,
+                                   sg::CommandRate command_rate,
+                                   TreeMode tree_mode,
+                                   int depth /* = 0 */,
+                                   int minimum_channels /* = 2 */) const {
+  // create the special command node
+  sg::Node command_info(command_id, sg::kSpecial, command_rate);
+  sg::Vertex mixer = boost::add_vertex(command_info, graph);
+  // pick a random number of channels to create for this command
+  int channels = stdx::RandomRangeInt(minimum_channels,
+                                      g_maximum_mixer_channels);
+  bool constant_added = false;
+  std::set<int> parameters;
+  // add a tree for each channel
+  for (int i = 0; i < channels; i++) {
+    AddTreeToSpecialCommand(mixer,
+                            graph,
+                            i,
+                            tree_mode,
+                            command_rate,
+                            &constant_added,
+                            &parameters,
+                            depth);
+  }
+  return mixer;
+}
+
+void Grammar::RandomGraph(sg::Graph& graph) const {
+  graph.clear();
+  // root output node
+  SpecialCommand(sc::Command::kMixer, graph, sg::kAudioRate, kTreeMode_Command);
+}
+  
+void Grammar::PickCrossoverNodes(const sg::Graph& parent_1, 
+                                 const sg::Graph& parent_2,
+                                 sg::Vertex* crossover_node_1,
+                                 sg::Vertex* crossover_node_2) const {
+  sg::Vertex source_node_1;
+  sg::Vertex source_node_2;
+  bool nodes_found = false;
+  do {
+    // pick random edges and their nodes
+    source_node_1 = boost::random_vertex(parent_1, bx::RandomEngine());
+    source_node_2 = boost::random_vertex(parent_2, bx::RandomEngine());
+    // avoid the root output node
+    if ((source_node_1 == 0) || (source_node_2 == 0)) {
+      continue;
+    }
+    // check it's ok to swap these nodes
+    const sg::Node& info_1 = parent_1[source_node_1];
+    const sg::Node& info_2 = parent_2[source_node_2];
+    // command rates need to match
+    if (info_1.rate_ != info_2.rate_) {
+      continue;
+    }
+    // we don't want to swap two constants
+    if (info_1.type_ == sg::kConstant && info_2.type_ == sg::kConstant) {
+      continue;
+    }
+    // we don't want to swap parameter inputs with same parameter id
+    if ((info_1.type_ == sg::kParameter)
+        && (info_2.type_ == sg::kParameter)
+        && (info_1.id_ == info_2.id_)) {
+      continue;
+    }
+    // check that we're not replacing a control modifer's input with non-command
+    sg::Edge connection_1 = *(boost::out_edges(source_node_1, parent_1).first);
+    sg::Edge connection_2 = *(boost::out_edges(source_node_2, parent_2).first);
+    sg::Vertex target_node_1 = boost::target(connection_1, parent_1);
+    sg::Vertex target_node_2 = boost::target(connection_2, parent_2);
+    const sg::Node& info_target_1 = parent_1[target_node_1];
+    const sg::Node& info_target_2 = parent_2[target_node_2];
+    if ((info_target_1.type_ == sg::kCommand)
+        || (info_target_1.type_ == sg::kSpecial)) {
+      const sc::Command& target_command_1 = commands_[info_target_1.id_];
+      const std::vector<Argument>& arguments_1 = target_command_1.Arguments();
+      const sg::Connection& info_connection_1 = parent_1[connection_1];
+      if (arguments_1[info_connection_1.input_].name_ == "in") {
+        // target input is a modifier's 'in' argument, only allow commands to
+        // be swapped in
+        if (!(info_2.type_ == sg::kCommand || info_2.type_ == sg::kSpecial)) {
+          continue;
+        }
+      }
+    }
+    if ((info_target_2.type_ == sg::kCommand)
+        || (info_target_2.type_ == sg::kSpecial)) {
+      const sc::Command& target_command_2 = commands_[info_target_2.id_];
+      const std::vector<Argument>& arguments_2 = target_command_2.Arguments();
+      const sg::Connection& info_connection_2 = parent_1[connection_2];
+      if (arguments_2[info_connection_2.input_].name_ == "in") {
+        // target input is a modifier's 'in' argument, only allow commands to
+        // be swapped in
+        if (!(info_1.type_ == sg::kCommand || info_1.type_ == sg::kSpecial)) {
+          continue;
+        }
+      }
+    }
+    nodes_found = true;
+  } while (!nodes_found);
+  *crossover_node_1 = source_node_1;
+  *crossover_node_2 = source_node_2;
+}
+  
+bool Grammar::MutationReplaceSubTree(sg::Graph& graph) const {
+  // sanity check
+  if (boost::num_vertices(graph) <= 1) {
+    throw std::runtime_error("sc::Grammar::MutationReplaceSubTree - graph has too few nodes");
+  }
+  // pick node to replace
+  sg::Vertex node_to_replace;
+  do {
+    node_to_replace = boost::random_vertex(graph, bx::RandomEngine());
+  } while (node_to_replace == 0);
+  sg::CommandRate new_tree_rate = graph[node_to_replace].rate_;
+  sg::Edge connection = *(boost::out_edges(node_to_replace, graph).first);
+  sg::Vertex connection_target = boost::target(connection, graph);
+  // store the connection info contained in the connection edge
+  sg::Connection connection_info = graph[connection];
+  const sg::Node& target_info = graph[connection_target];
+  // determine new tree mode
+  TreeMode new_tree_mode = kTreeMode_Mod;
+  if (new_tree_rate == sg::kAudioRate) {
+    // audio rate nodes always require command tree replacements
+    new_tree_mode = kTreeMode_Command;
+  } else if (target_info.type_ == sg::kCommand) {
+    // if the connection target is a modifier 
+    // and the connection input is 0 then a command tree is needed
+    if (commands_[target_info.id_].Mode() == Command::kModifier) {
+      if (connection_info.input_ == 0) {
+        new_tree_mode = kTreeMode_Command;
+      }
+    }
+  } else if (target_info.type_ == sg::kSpecial) {
+    // first input to special commands is a command tree
+    if (connection_info.input_ == 0) {
+      new_tree_mode = kTreeMode_Command;
+    }
+  }
+  // remove the sub tree
+  RemoveSubTree(connection, graph);
+  // generate new tree
+  sg::Vertex new_tree = RandomTree(graph, new_tree_rate, new_tree_mode, 0);
+  // connect tree to graph
+  boost::add_edge(new_tree, connection_target, connection_info, graph);
+  return true;
+}
+  
+  
+  
+bool Grammar::MutationAddSubTree(sg::Graph& graph) const {
+  // sanity check
+  if (graph[0].type_ != sg::kSpecial) {
+    throw std::runtime_error("sc::Grammar::MutationAddSubTree - missing root mixer node");
+  }
+  bool mutation_occurred = false;
+  while (!mutation_occurred) {
+    // pick a command or special node to add a tree input to
+    sg::Vertex node;
+    sg::NodeType node_type;
+    do {
+      node = boost::random_vertex(graph, bx::RandomEngine());
+      node_type = graph[node].type_;
+    } while (!(node_type == sg::kCommand || node_type == sg::kSpecial));
+    if (node_type == sg::kCommand) {
+      int node_id = graph[node].id_;
+      const std::vector<Argument>& arguments = commands_[node_id].Arguments();
+      std::size_t number_of_arguments = arguments.size();
+      sg::InEdgeIterator edge;
+      sg::InEdgeIterator edge_end;
+      std::vector<bool> used_arguments(arguments.size(), false);
+      for (boost::tie(edge, edge_end) = boost::in_edges(node, graph);
+           edge != edge_end;
+           ++edge) {
+        used_arguments[graph[*edge].input_] = true;
+      }
+      // check that there is an unused argument available for this command
+      bool argument_available = false;
+      for (std::size_t i = 0; i < number_of_arguments; i++) {
+        if (used_arguments[i] == false) {
+          // we don't want to attach a tree to a preset argument
+          if (arguments[i].scaling_mode_ != Argument::kConstant) {
+            argument_available = true;
+            break;
+          }
+        }
+      }
+      if (argument_available) {
+        // find a random argument to insert a tree into
+        std::size_t argument;
+        do {
+          argument = stdx::Random(arguments.size());
+        } while (used_arguments[argument] == true
+                 || arguments[argument].scaling_mode_ == Argument::kConstant);
+        // add a tree and connect to the unused argument
+        sg::Vertex tree = RandomTree(graph,
+                                     sg::kControlRate,
+                                     kTreeMode_Mod,
+                                     0);
+        sg::Connection connection(static_cast<int>(argument));
+        GenerateWeightAndOffset(arguments[argument],
+                                sg::kControlRate,
+                                &connection);
+        boost::add_edge(tree, node, connection, graph);
+        mutation_occurred = true;
+      }
+    } else if (node_type == sg::kSpecial) {
+      int node_inputs = static_cast<int>(boost::in_degree(node, graph));
+      // we need to check the special command's inputs to avoid adding redundant
+      // constants or parameters
+      bool constant_added = false;
+      std::set<int> parameters;
+      sg::InEdgeIterator edge;
+      sg::InEdgeIterator edge_end;
+      for (boost::tie(edge, edge_end) = boost::in_edges(node, graph);
+           edge != edge_end;
+           ++edge) {
+        const sg::Node& source = graph[boost::source(*edge, graph)];
+        if (source.type_ == sg::kConstant) {
+          constant_added = true;
+        }
+        if (source.type_ == sg::kParameter) {
+          parameters.insert(source.id_);
+        }
+      }
+      // select tree mode based on command rate
+      TreeMode tree_mode;
+      if (graph[node].rate_ == sg::kAudioRate) {
+        tree_mode = kTreeMode_Command;
+      } else {
+        tree_mode = kTreeMode_Mod;
+      }
+      // add the tree
+      AddTreeToSpecialCommand(node,
+                              graph,
+                              node_inputs,
+                              tree_mode,
+                              graph[node].rate_,
+                              &constant_added,
+                              &parameters,
+                              0);
+      mutation_occurred = true;
+    }  
+  }
+  return true;
+}
+
+bool Grammar::MutationModifyInputs(sg::Graph& graph) const {
+  // sanity check
+  if (graph[boost::graph_bundle].parameters_.size() == 0) {
+    sg::VertexIterator vertex;
+    sg::VertexIterator vertex_end;
+    bool constant_found = false;
+    for (boost::tie(vertex, vertex_end) = boost::vertices(graph);
+         vertex != vertex_end;
+         ++vertex) {
+      sg::Node& node = graph[*vertex];
+      if (node.type_ == sg::kConstant) {
+        constant_found = true;
+        break;
+      }
+    }
+    if (!constant_found) {
+      // no parameters, no constants, nothing to do..
+      return false;
+    }
+  }
+  // make a random generator with a narrow guassian distribution 
+  bx::GaussianGenerator gaussian = bx::MakeGaussianGenerator(0, 0.125);
+  bool mutation_occurred = false;
+  while (!mutation_occurred) {
+    // mutate parameters
+    foreach (double& parameter, graph[boost::graph_bundle].parameters_) {
+      if (stdx::Chance(g_probability_input_mutation)) {
+        MutateValue(&parameter, &mutation_occurred);
+      }
+    }
+    // mutate constants
+    sg::VertexIterator vertex;
+    sg::VertexIterator vertex_end;
+    for (boost::tie(vertex, vertex_end) = boost::vertices(graph);
+         vertex != vertex_end;
+         ++vertex) {
+      sg::Node& node = graph[*vertex];
+      if (node.type_ == sg::kConstant) {
+        // constant value
+        if (stdx::Chance(g_probability_input_mutation)) {
+          MutateValue(&node.constant_value_, &mutation_occurred);
+        }
+      }
+    }
+  }
+  return true;
+}
+
+bool Grammar::MutationModifyConnections(sg::Graph& graph) const {
+  // sanity check
+  if (boost::num_edges(graph) < 1) {
+    throw std::runtime_error("sc::Grammar::MutationModifyConnections - graph has no connections");
+  }
+  bx::GaussianGenerator gaussian = bx::MakeGaussianGenerator(0, 0.125);
+  bool mutation_occurred = false;
+  while (!mutation_occurred) {
+    sg::EdgeIterator edge;
+    sg::EdgeIterator edge_end;
+    for (boost::tie(edge, edge_end) = boost::edges(graph);
+         edge != edge_end;
+         ++edge) {
+      if (stdx::Chance(g_probability_connection_mutation)) {
+        sg::Connection& connection = graph[*edge];
+        const sg::Node& target = graph[boost::target(*edge, graph)];
+        const sc::Argument& argument = GetCommandArgument(target.id_,
+                                                          connection.input_);
+        if (!argument.fixed_range_) {
+          // mutate weight
+          MutateValue(&connection.weight_,
+                      &mutation_occurred,
+                      g_minimum_connection_weight);
+          // special command inputs and modifier command input arguments 
+          // have offsets set to zero
+          if ((target.type_ != sg::kSpecial) && (argument.name_ != "in")) {
+            MutateValue(&connection.offset_, &mutation_occurred,
+                        0.0, 1.0 - connection.weight_);
+          }
+        }
+      }
+    }    
+  }
+  return true;
+}
+  
+const std::vector<sc::Argument>& Grammar::CommandArguments(int command) const {
+  return commands_[command].Arguments();
+}
+
+bool Grammar::MutationReplaceCommand(sg::Graph& graph) const {
+  // sanity check
+  if (boost::num_vertices(graph) <= 1) {
+    throw std::runtime_error("sc::Grammar::MutationReplaceCommand - graph has too few nodes");
+  }
+  sg::Vertex node_to_replace;
+  sg::Node* node_info;
+  // find command to replace
+  do {
+    node_to_replace = boost::random_vertex(graph, bx::RandomEngine());
+    node_info = &graph[node_to_replace];
+  } while (node_info->type_ != sg::kCommand);
+  int old_id = node_info->id_;
+  // generate new command id
+  int new_id;
+  int number_of_commands = static_cast<int>(commands_.size());
+  do {
+    // new command must match old output and mode
+    new_id = stdx::Random(number_of_commands);
+  } while (new_id != old_id
+           && commands_[new_id].Output() != commands_[old_id].Output()
+           && commands_[new_id].Mode() != commands_[old_id].Mode());
+  // new command info
+  const std::vector<sc::Argument>& arguments = CommandArguments(new_id);
+  std::size_t number_of_arguments = commands_[new_id].Arguments().size();
+  // remove invalid parameters
+  // removing an in edge invalidates the iterators, so we need to restart the
+  // search each time an edge is removed
+  sg::InEdgeIterator edge;
+  sg::InEdgeIterator edge_end;
+  bool do_it_again;
+  do {
+    do_it_again = false;
+    for (boost::tie(edge, edge_end) = boost::in_edges(node_to_replace, graph);
+         edge != edge_end;
+         ++edge) {
+      int input = graph[*edge].input_;
+      // remove input tree if it's for an extraneous parameter
+      // or if the argument is a constant
+      if (input >= number_of_arguments
+          || arguments[input].scaling_mode_ == sc::Argument::kConstant) {
+        RemoveSubTree(*edge, graph);
+        do_it_again = true;
+        // break out of for loop
+        break;
+      }
+    }
+  } while (do_it_again);
+  // now invalid parameters have been removed, validate the rest
+  for (boost::tie(edge, edge_end) = boost::in_edges(node_to_replace, graph);
+       edge != edge_end;
+       ++edge) {
+    // if the new argument is fixed range then correct the connection weight
+    int input = graph[*edge].input_;
+    if (arguments[input].fixed_range_) {
+      GenerateWeightAndOffset(arguments[input],
+                              node_info->rate_, 
+                              &graph[*edge]);
+    }
+  }
+  // apply new command id
+  node_info->id_ = new_id;
+  return true;
+}
+  
+int Grammar::GetCommandInputID(int command) const {
+  const std::vector<sc::Argument>& arguments = commands_[command].Arguments();
+  for (std::size_t i = 0, size = arguments.size(); i < size; i++) {
+    if (arguments[i].name_ == "in") {
+      return static_cast<int>(i);
+    }
+  }
+  return -1;
+}
+  
+const Argument& Grammar::GetCommandArgument(int command_id,
+                                            int argument_id) const {
+  return commands_[command_id].Arguments()[argument_id];
+}
+
+bool Grammar::MutationInsertCommand(sg::Graph& graph) const {
+  // sanity check
+  if (boost::num_vertices(graph) == 0) {
+    throw std::runtime_error("sc::Grammar::MutationInsertCommand - graph is empty");
+  }
+  // pick a random edge as insertion point
+  sg::Edge edge_to_replace;
+  sg::Vertex source_command;
+  sg::NodeType source_type;
+  do {
+    edge_to_replace = boost::random_edge(graph, bx::RandomEngine());
+    source_command = boost::source(edge_to_replace, graph);
+    source_type = graph[source_command].type_;
+  } while (source_type != sg::kCommand);
+  // store target connection info
+  sg::Vertex target_command = boost::target(edge_to_replace, graph);
+  sg::Connection target_connection = graph[edge_to_replace];
+  // make the new command
+  const sg::Node& source_node = graph[source_command];
+  sg::CommandRate rate = source_node.rate_;
+  sg::Vertex new_command = CreateCommand(graph, rate, 0, true, false);
+  // remove the existing connection
+  boost::remove_edge(source_command, target_command, graph);
+  // connect the new command to the source
+  sg::Connection source_connection(GetCommandInputID(graph[new_command].id_));
+  // generate weighting for new connection
+  double weight = stdx::RandomCoefficient();
+  if (rate == sg::kAudioRate) {
+    weight *= weight;
+  }
+  source_connection.weight_ = weight;
+  boost::add_edge(source_command, new_command, source_connection, graph);
+  // connect new command to the target, use old connection weighting
+  boost::add_edge(new_command, target_command, target_connection, graph);
+  // success!
+  return true;
+}
+
+} // sc namespace