ian@0: //  Copyright 2011, Ian Hobson.
ian@0: //
ian@0: //  This file is part of gpsynth.
ian@0: //
ian@0: //  gpsynth is free software: you can redistribute it and/or modify
ian@0: //  it under the terms of the GNU General Public License as published by
ian@0: //  the Free Software Foundation, either version 3 of the License, or
ian@0: //  (at your option) any later version.
ian@0: //
ian@0: //  gpsynth is distributed in the hope that it will be useful,
ian@0: //  but WITHOUT ANY WARRANTY; without even the implied warranty of
ian@0: //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
ian@0: //  GNU General Public License for more details.
ian@0: //
ian@0: //  You should have received a copy of the GNU General Public License
ian@0: //  along with gpsynth in the file COPYING. 
ian@0: //  If not, see http://www.gnu.org/licenses/.
ian@0: 
ian@0: // Some helper functions for boost.graph
ian@0: 
ian@0: #pragma once
ian@0: 
ian@0: #include "boost/graph/adjacency_list.hpp"
ian@0: #include "boost/tuple/tuple.hpp"
ian@0: 
ian@0: // removes the tree starting at the specified edge from the graph
ian@0: template<typename GRAPH>
ian@0: void RemoveSubTree(typename boost::graph_traits<GRAPH>::edge_descriptor edge,
ian@0:                    GRAPH& graph) {
ian@0:   typename boost::graph_traits<GRAPH>::vertex_descriptor source;
ian@0:   typename boost::graph_traits<GRAPH>::vertex_descriptor target;
ian@0:   source = boost::source(edge, graph);
ian@0:   target = boost::target(edge, graph);
ian@0:   // avoid iteration as removing edges invalidates iterators
ian@0:   while (boost::in_degree(source, graph) > 0) {
ian@0:     RemoveSubTree(*(boost::in_edges(source, graph).first), graph);
ian@0:   }
ian@0:   boost::remove_edge(source, target, graph);
ian@0:   boost::remove_vertex(source, graph);
ian@0: }
ian@0: 
ian@0: // removes the tree starting at the specified vertex from the graph
ian@0: template<typename T>
ian@0: void RemoveSubTree(typename boost::graph_traits<T>::vertex_descriptor vertex,
ian@0:                    T& graph) {
ian@0:   // avoid iteration as removing edges invalidates iterators
ian@0:   while (boost::in_degree(vertex, graph) > 0) {
ian@0:     RemoveSubTree(*(boost::in_edges(vertex, graph).first), graph);
ian@0:   }
ian@0:   boost::remove_vertex(vertex, graph);
ian@0: }
ian@0: 
ian@0: // inserts the subtree identified by source in to target_graph
ian@0: // returns the root vertex of the inserted subtree
ian@0: template<typename GRAPH>
ian@0: typename boost::graph_traits<GRAPH>::vertex_descriptor
ian@0: InsertSubTree(typename boost::graph_traits<GRAPH>::vertex_descriptor source,
ian@0:               const GRAPH& source_graph,
ian@0:               GRAPH& target_graph) {
ian@0:   typedef typename boost::graph_traits<GRAPH>::vertex_descriptor Vertex;
ian@0:   typedef typename boost::graph_traits<GRAPH>::in_edge_iterator InEdge;
ian@0:   Vertex new_vertex = boost::add_vertex(source_graph[source], target_graph);
ian@0:   InEdge in_edge;
ian@0:   InEdge in_edges_end;
ian@0:   boost::tie(in_edge, in_edges_end) = boost::in_edges(source, source_graph);
ian@0:   while (in_edge != in_edges_end) {
ian@0:     Vertex input = InsertSubTree(boost::source(*in_edge, source_graph),
ian@0:                                  source_graph,
ian@0:                                  target_graph);
ian@0:     boost::add_edge(input, new_vertex, source_graph[*in_edge], target_graph);
ian@0:     ++in_edge;
ian@0:   }
ian@0:   return new_vertex;
ian@0: }
ian@0: 
ian@0: // SwapSubTrees - swaps the subtrees starting at node_1 and node_2
ian@0: // writing to graphs passed in as targets
ian@0: template<typename GRAPH>
ian@0: void SwapSubTrees(typename boost::graph_traits<GRAPH>::vertex_descriptor node_1,
ian@0:                   typename boost::graph_traits<GRAPH>::vertex_descriptor node_2,
ian@0:                   const GRAPH& source_1, const GRAPH& source_2,
ian@0:                   GRAPH& target_1, GRAPH& target_2) {
ian@0: 
ian@0:   typedef typename boost::graph_traits<GRAPH>::vertex_descriptor Vertex;
ian@0:   typedef typename boost::graph_traits<GRAPH>::edge_descriptor Edge;
ian@0:   // copy sources to targets
ian@0:   target_1 = source_1;
ian@0:   target_2 = source_2;
ian@0:   // get connecting output edges
ian@0:   Edge edge_1 = *(boost::out_edges(node_1, source_1).first);
ian@0:   Edge edge_2 = *(boost::out_edges(node_2, source_2).first);
ian@0:   // get connecting nodes on other end of outputs
ian@0:   Vertex target_node_1 = boost::target(edge_1, source_1);
ian@0:   Vertex target_node_2 = boost::target(edge_2, source_2);
ian@0:   // delete subtrees
ian@0:   RemoveSubTree(edge_1, target_1);
ian@0:   RemoveSubTree(edge_2, target_2);
ian@0:   // insert copies of subtrees in opposing target graphs
ian@0:   Vertex new_node_1 = InsertSubTree(node_2, source_2, target_1);
ian@0:   Vertex new_node_2 = InsertSubTree(node_1, source_1, target_2);
ian@0:   // connect the new subtrees using the same edge properties as old connection
ian@0:   boost::add_edge(new_node_1, target_node_1, source_1[edge_1], target_1);
ian@0:   boost::add_edge(new_node_2, target_node_2, source_2[edge_2], target_2);
ian@0: }