diff src/graph_helpers.hpp @ 0:add35537fdbb tip

Initial import

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/graph_helpers.hpp	Thu Aug 25 11:05:55 2011 +0100
@@ -0,0 +1,104 @@
+//  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);
+}