annotate src/graph_helpers.hpp @ 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/.

// Some helper functions for boost.graph

#pragma once

#include "boost/graph/adjacency_list.hpp"
#include "boost/tuple/tuple.hpp"

// removes the tree starting at the specified edge from the graph
template<typename GRAPH>
void RemoveSubTree(typename boost::graph_traits<GRAPH>::edge_descriptor edge,
                   GRAPH& graph) {
  typename boost::graph_traits<GRAPH>::vertex_descriptor source;
  typename boost::graph_traits<GRAPH>::vertex_descriptor target;
  source = boost::source(edge, graph);
  target = boost::target(edge, graph);
  // avoid iteration as removing edges invalidates iterators
  while (boost::in_degree(source, graph) > 0) {
    RemoveSubTree(*(boost::in_edges(source, graph).first), graph);
  }
  boost::remove_edge(source, target, graph);
  boost::remove_vertex(source, graph);
}

// removes the tree starting at the specified vertex from the graph
template<typename T>
void RemoveSubTree(typename boost::graph_traits<T>::vertex_descriptor vertex,
                   T& graph) {
  // avoid iteration as removing edges invalidates iterators
  while (boost::in_degree(vertex, graph) > 0) {
    RemoveSubTree(*(boost::in_edges(vertex, graph).first), graph);
  }
  boost::remove_vertex(vertex, graph);
}

// inserts the subtree identified by source in to target_graph
// returns the root vertex of the inserted subtree
template<typename GRAPH>
typename boost::graph_traits<GRAPH>::vertex_descriptor
InsertSubTree(typename boost::graph_traits<GRAPH>::vertex_descriptor source,
              const GRAPH& source_graph,
              GRAPH& target_graph) {
  typedef typename boost::graph_traits<GRAPH>::vertex_descriptor Vertex;
  typedef typename boost::graph_traits<GRAPH>::in_edge_iterator InEdge;
  Vertex new_vertex = boost::add_vertex(source_graph[source], target_graph);
  InEdge in_edge;
  InEdge in_edges_end;
  boost::tie(in_edge, in_edges_end) = boost::in_edges(source, source_graph);
  while (in_edge != in_edges_end) {
    Vertex input = InsertSubTree(boost::source(*in_edge, source_graph),
                                 source_graph,
                                 target_graph);
    boost::add_edge(input, new_vertex, source_graph[*in_edge], target_graph);
    ++in_edge;
  }
  return new_vertex;
}

// SwapSubTrees - swaps the subtrees starting at node_1 and node_2
// writing to graphs passed in as targets
template<typename GRAPH>
void SwapSubTrees(typename boost::graph_traits<GRAPH>::vertex_descriptor node_1,
                  typename boost::graph_traits<GRAPH>::vertex_descriptor node_2,
                  const GRAPH& source_1, const GRAPH& source_2,
                  GRAPH& target_1, GRAPH& target_2) {

  typedef typename boost::graph_traits<GRAPH>::vertex_descriptor Vertex;
  typedef typename boost::graph_traits<GRAPH>::edge_descriptor Edge;
  // copy sources to targets
  target_1 = source_1;
  target_2 = source_2;
  // get connecting output edges
  Edge edge_1 = *(boost::out_edges(node_1, source_1).first);
  Edge edge_2 = *(boost::out_edges(node_2, source_2).first);
  // get connecting nodes on other end of outputs
  Vertex target_node_1 = boost::target(edge_1, source_1);
  Vertex target_node_2 = boost::target(edge_2, source_2);
  // delete subtrees
  RemoveSubTree(edge_1, target_1);
  RemoveSubTree(edge_2, target_2);
  // insert copies of subtrees in opposing target graphs
  Vertex new_node_1 = InsertSubTree(node_2, source_2, target_1);
  Vertex new_node_2 = InsertSubTree(node_1, source_1, target_2);
  // connect the new subtrees using the same edge properties as old connection
  boost::add_edge(new_node_1, target_node_1, source_1[edge_1], target_1);
  boost::add_edge(new_node_2, target_node_2, source_2[edge_2], target_2);
}