view 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