[Commit-gnuradio] r6162 - gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime

[jcorgan]

Author: jcorgan
Date: 2007-08-22 09:58:16 -0600 (Wed, 22 Aug 2007)
New Revision: 6162

Added:
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
Modified:
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/Makefile.am
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_block.h
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_types.h
Log:
First pass refactoring new flowgraph code.

gr_flowgraph will contain all the container/topology code.

gr_flat_flowgraph will contain all code that knows about gr_block_detail.

These classes are not used by the rest of the code yet.


Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/Makefile.am
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/Makefile.am
   2007-08-21 19:15:43 UTC (rev 6161)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/Makefile.am
   2007-08-22 15:58:16 UTC (rev 6162)
@@ -31,6 +31,8 @@
 
 libruntime_la_SOURCES =                        \
        gr_basic_block.cc                       \
+       gr_flowgraph.cc                         \
+       gr_flat_flowgraph.cc                    \
        gr_simple_flowgraph.cc                  \
        gr_simple_flowgraph_detail.cc           \
        gr_block.cc                             \
@@ -72,6 +74,8 @@
 
 grinclude_HEADERS =                            \
        gr_basic_block.h                        \
+       gr_flowgraph.h                          \
+       gr_flat_flowgraph.h                     \
        gr_simple_flowgraph.h                   \
        gr_simple_flowgraph_detail.h            \
        gr_block.h                              \

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_block.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_block.h
    2007-08-21 19:15:43 UTC (rev 6161)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_block.h
    2007-08-22 15:58:16 UTC (rev 6162)
@@ -1,6 +1,6 @@
 /* -*- c++ -*- */
 /*
- * Copyright 2004 Free Software Foundation, Inc.
+ * Copyright 2004,2007 Free Software Foundation, Inc.
  * 
  * This file is part of GNU Radio
  * 
@@ -214,4 +214,9 @@
 typedef std::vector<gr_block_sptr> gr_block_vector_t;
 typedef std::vector<gr_block_sptr>::iterator gr_block_viter_t;
 
+inline gr_block_sptr make_gr_block_sptr(gr_basic_block_sptr p)
+{
+  return boost::dynamic_pointer_cast<gr_block, gr_basic_block>(p);
+}
+
 #endif /* INCLUDED_GR_BLOCK_H */

Added: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
                          (rev 0)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
  2007-08-22 15:58:16 UTC (rev 6162)
@@ -0,0 +1,372 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2007 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gr_flat_flowgraph.h>
+#include <gr_block_detail.h>
+#include <gr_io_signature.h>
+#include <gr_buffer.h>
+#include <iostream>
+#include <map>
+
+#define GR_FLAT_FLOWGRAPH_DEBUG 1
+
+gr_flat_flowgraph_sptr
+gr_make_flat_flowgraph()
+{
+  return gr_flat_flowgraph_sptr(new gr_flat_flowgraph());
+}
+
+gr_flat_flowgraph::gr_flat_flowgraph()
+{
+}
+
+gr_flat_flowgraph::~gr_flat_flowgraph()
+{
+}
+
+void
+gr_flat_flowgraph::setup_connections()
+{
+  // Assign block details to blocks
+  for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
+    make_gr_block_sptr(*p)->set_detail(allocate_block_detail(*p));
+
+  // Connect inputs to outputs for each block
+  for(gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
+    connect_block_inputs(*p);
+}
+
+gr_block_detail_sptr
+gr_flat_flowgraph::allocate_block_detail(gr_basic_block_sptr block, 
gr_block_detail_sptr old_detail)
+{
+  int ninputs = calc_used_ports(block, true).size();
+  int noutputs = calc_used_ports(block, false).size();
+  gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs);
+
+  if (GR_FLAT_FLOWGRAPH_DEBUG)
+    std::cout << "Creating block detail for " << block << std::endl;
+
+  // Re-use or allocate output buffers
+  for (int i = 0; i < noutputs; i++) {
+    gr_buffer_sptr buffer;
+
+    if (!old_detail || i >= old_detail->noutputs()) {
+      if (GR_FLAT_FLOWGRAPH_DEBUG)
+       std::cout << "Allocating new buffer for output " << i << std::endl;
+      buffer = allocate_buffer(block, i);
+    }
+    else {
+      if (GR_FLAT_FLOWGRAPH_DEBUG)
+       std::cout << "Reusing old buffer for output " << i << std::endl;
+      buffer = old_detail->output(i);
+    }
+
+    detail->set_output(i, buffer);
+  }
+
+  return detail;
+}
+
+gr_buffer_sptr
+gr_flat_flowgraph::allocate_buffer(gr_basic_block_sptr block, int port)
+{
+  gr_block_sptr grblock = make_gr_block_sptr(block);
+  if (!grblock)
+    throw std::runtime_error("allocate_buffer found non-gr_block");
+  int item_size = block->output_signature()->sizeof_stream_item(port);
+  int nitems = s_fixed_buffer_size/item_size;
+
+  // Make sure there are at least twice the output_multiple no. of items
+  if (nitems < 2*grblock->output_multiple())   // Note: this means 
output_multiple()
+    nitems = 2*grblock->output_multiple();     // can't be changed by block 
dynamically
+
+  // If any downstream blocks are decimators and/or have a large 
output_multiple,
+  // ensure we have a buffer at least twice their decimation 
factor*output_multiple
+  gr_basic_block_vector_t blocks = calc_downstream_blocks(block, port);
+
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    gr_block_sptr dgrblock = make_gr_block_sptr(*p);
+    if (!dgrblock)
+      throw std::runtime_error("allocate_buffer found non-gr_block");
+
+    double decimation = (1.0/dgrblock->relative_rate());
+    int multiple      = dgrblock->output_multiple();
+    int history       = dgrblock->history();
+    nitems = std::max(nitems, 
static_cast<int>(2*(decimation*multiple+history)));
+  }
+
+  return gr_make_buffer(nitems, item_size);
+}
+
+void
+gr_flat_flowgraph::connect_block_inputs(gr_basic_block_sptr block)
+{
+  gr_block_sptr grblock = make_gr_block_sptr(block);
+  if (!grblock)
+    throw std::runtime_error("found non-gr_block");
+  
+  // Get its detail and edges that feed into it
+  gr_block_detail_sptr detail = grblock->detail();
+  gr_edge_vector_t in_edges = calc_upstream_edges(block);
+  
+  // For each edge that feeds into it
+  for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
+    // Set the buffer reader on the destination port to the output
+    // buffer on the source port
+    int dst_port = e->dst().port();
+    int src_port = e->src().port();
+    gr_basic_block_sptr src_block = e->src().block();
+    gr_block_sptr src_grblock = make_gr_block_sptr(src_block);
+    if (!src_grblock)
+      throw std::runtime_error("found non-gr_block");
+    gr_buffer_sptr src_buffer = src_grblock->detail()->output(src_port);
+    
+    if (GR_FLAT_FLOWGRAPH_DEBUG)
+      std::cout << "Setting input " << dst_port << " from edge " << (*e) << 
std::endl;
+
+    detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, 
grblock->history()-1));
+  }
+}
+
+void
+gr_flat_flowgraph::merge_connections(gr_flat_flowgraph_sptr old_ffg)
+{
+  std::map<gr_block_sptr, gr_block_detail_sptr> old_details;
+
+  // Allocate or reuse output buffers
+  for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
+    gr_block_sptr block = make_gr_block_sptr(*p);
+
+    gr_block_detail_sptr old_detail = block->detail();
+    block->set_detail(allocate_block_detail(block, old_detail));
+
+    // Save old detail for use in next step
+    old_details[block] = old_detail;
+  }
+
+  for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
+    gr_block_sptr block = make_gr_block_sptr(*p);
+
+    if (GR_FLAT_FLOWGRAPH_DEBUG)
+      std::cout << "merge: testing " << (*p) << "...";
+    
+    if (old_ffg->has_block_p(*p)) {
+      // Block exists in old flow graph
+      if (GR_FLAT_FLOWGRAPH_DEBUG)
+       std::cout << "used in old flow graph" << std::endl;
+      gr_block_detail_sptr detail = block->detail();
+
+      // Iterate through the inputs and see what needs to be done
+      for (int i = 0; i < detail->ninputs(); i++) {
+       if (GR_FLAT_FLOWGRAPH_DEBUG)
+         std::cout << "Checking input " << i << "...";
+       gr_edge edge = calc_upstream_edge(*p, i);
+
+       // Fish out old buffer reader and see if it matches correct buffer from 
edge list
+       gr_block_sptr src_block = make_gr_block_sptr(edge.src().block());
+       gr_block_detail_sptr src_detail = src_block->detail();
+       gr_buffer_sptr src_buffer = src_detail->output(edge.src().port());
+       gr_buffer_reader_sptr old_reader;
+       gr_block_detail_sptr old_detail = old_details[block];
+       if (old_detail && i < old_detail->ninputs())
+         old_reader = old_detail->input(i);
+       
+       // If there's a match, use it
+       if (old_reader && (src_buffer == old_reader->buffer())) {
+         if (GR_FLAT_FLOWGRAPH_DEBUG)
+           std::cout << "matched" << std::endl;
+         detail->set_input(i, old_reader);
+
+       }
+       else {
+         if (GR_FLAT_FLOWGRAPH_DEBUG)
+           std::cout << "needs a new reader" << std::endl;
+
+         // Create new buffer reader and assign
+         detail->set_input(i, gr_buffer_add_reader(src_buffer, 
block->history()-1));
+       }
+      }
+    }
+    else {
+      // Block is new, it just needs buffer readers at this point
+      if (GR_FLAT_FLOWGRAPH_DEBUG)
+       std::cout << "new block" << std::endl;
+      connect_block_inputs(block);
+    }
+  }  
+}
+
+std::vector<gr_block_vector_t>
+gr_flat_flowgraph::partition()
+{
+  std::vector<gr_block_vector_t> result;
+  gr_basic_block_vector_t blocks = calc_used_blocks();
+  gr_basic_block_vector_t graph;
+
+  while (blocks.size() > 0) {
+    graph = calc_reachable_blocks(blocks[0], blocks);
+    assert(graph.size());
+    result.push_back(topological_sort(graph));
+
+    for (gr_basic_block_viter_t p = graph.begin(); p != graph.end(); p++)
+      blocks.erase(find(blocks.begin(), blocks.end(), *p));
+  }
+
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flat_flowgraph::calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t result;
+
+  // Mark all blocks as unvisited
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+    make_gr_block_sptr(*p)->detail()->set_color(gr_block_detail::WHITE);
+
+  // Recursively mark all reachable blocks
+  reachable_dfs_visit(block, blocks);
+
+  // Collect all the blocks that have been visited
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+    if ((make_gr_block_sptr(*p))->detail()->color() == gr_block_detail::BLACK)
+      result.push_back(*p);
+
+  return result;
+}
+
+// Recursively mark all reachable blocks from given block and block list
+void 
+gr_flat_flowgraph::reachable_dfs_visit(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  // Mark the current one as visited
+  boost::dynamic_pointer_cast<gr_block, 
gr_basic_block>(block)->detail()->set_color(gr_block_detail::BLACK);
+
+  // Recurse into adjacent vertices
+  gr_basic_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
+
+  for (gr_basic_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
+    if (boost::dynamic_pointer_cast<gr_block, 
gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE)
+      reachable_dfs_visit(*p, blocks);
+}
+
+// Return a list of block adjacent to a given block along any edge
+gr_basic_block_vector_t 
+gr_flat_flowgraph::calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t tmp, result;
+  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
+    
+  // Find any blocks that are inputs or outputs
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+
+    if (p->src().block() == block)
+      tmp.push_back(p->dst().block());
+    if (p->dst().block() == block)
+      tmp.push_back(p->src().block());
+  }    
+
+  // Remove duplicates
+  sort(tmp.begin(), tmp.end());
+  unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+gr_block_vector_t
+gr_flat_flowgraph::topological_sort(gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t tmp;
+  gr_block_vector_t result;
+  tmp = sort_sources_first(blocks);
+
+  // Start 'em all white
+  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
+    make_gr_block_sptr(*p)->detail()->set_color(gr_block_detail::WHITE);
+
+  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
+    if (make_gr_block_sptr(*p)->detail()->color() == gr_block_detail::WHITE)
+      topological_dfs_visit(*p, result);
+  }    
+
+  reverse(result.begin(), result.end());
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flat_flowgraph::sort_sources_first(gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t sources, nonsources, result;
+
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    if (source_p(*p))
+      sources.push_back(*p);
+    else
+      nonsources.push_back(*p);
+  }
+
+  for (gr_basic_block_viter_t p = sources.begin(); p != sources.end(); p++)
+    result.push_back(*p);
+
+  for (gr_basic_block_viter_t p = nonsources.begin(); p != nonsources.end(); 
p++)
+    result.push_back(*p);
+
+  return result;
+}
+
+bool
+gr_flat_flowgraph::source_p(gr_basic_block_sptr block)
+{
+  return (calc_upstream_edges(block).size() == 0);
+}
+
+void
+gr_flat_flowgraph::topological_dfs_visit(gr_basic_block_sptr block, 
gr_block_vector_t &output)
+{
+  make_gr_block_sptr(block)->detail()->set_color(gr_block_detail::GREY);
+  gr_basic_block_vector_t blocks(calc_downstream_blocks(block));
+
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    switch (make_gr_block_sptr(*p)->detail()->color()) {
+    case gr_block_detail::WHITE:           
+      topological_dfs_visit(*p, output);
+      break;
+
+    case gr_block_detail::GREY:            
+      throw std::runtime_error("flow graph has loops!");
+
+    case gr_block_detail::BLACK:
+      continue;
+
+    default:
+      throw std::runtime_error("invalid color on block!");
+    }
+  }
+
+  gr_block_sptr result_block = make_gr_block_sptr(block);
+  result_block->detail()->set_color(gr_block_detail::BLACK);
+  output.push_back(result_block);
+}
+

Added: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
                           (rev 0)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
   2007-08-22 15:58:16 UTC (rev 6162)
@@ -0,0 +1,78 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006,2007 Free Software Foundation, Inc.
+ * 
+ * This file is part of GNU Radio
+ * 
+ * GNU Radio 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, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio 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 GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifndef INCLUDED_GR_FLAT_FLOWGRAPH_H
+#define INCLUDED_GR_FLAT_FLOWGRAPH_H
+
+#include <gr_flowgraph.h>
+#include <gr_block.h>
+
+// 32Kbyte buffer size between blocks
+#define GR_FIXED_BUFFER_SIZE (32*(1L<<10))
+
+// Create a shared pointer to a heap allocated gr_flat_flowgraph
+// (types defined in gr_runtime_types.h)
+gr_flat_flowgraph_sptr gr_make_flat_flowgraph();
+
+/*!
+ *\brief Class specializing gr_flat_flowgraph that has all nodes
+ * as gr_blocks, with no hierarchy
+ *
+ */
+class gr_flat_flowgraph : public gr_flowgraph
+{
+public:
+  friend gr_flat_flowgraph_sptr gr_make_flat_flowgraph();
+
+  // Destruct an arbitrary gr_flat_flowgraph
+  ~gr_flat_flowgraph();
+
+  // Wire gr_blocks together in new flat_flowgraph
+  void setup_connections();
+
+  // Merge applicable connections from existing flat flowgraph
+  void merge_connections(gr_flat_flowgraph_sptr sfg);
+
+  // Return vector of vectors of disjointly connected blocks, topologically
+  // sorted.
+  std::vector<gr_block_vector_t> partition();
+
+private:
+  gr_flat_flowgraph();
+
+  static const unsigned int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE;
+  gr_block_detail_sptr allocate_block_detail(gr_basic_block_sptr block, 
+                                            gr_block_detail_sptr 
old_detail=gr_block_detail_sptr());
+  gr_buffer_sptr allocate_buffer(gr_basic_block_sptr block, int port);
+  void connect_block_inputs(gr_basic_block_sptr block);
+
+  // FIXME: these should be in gr_flowgraph but use gr_block_detail so must be 
here
+  gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
+  void reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t 
&blocks);
+  gr_basic_block_vector_t calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
+  gr_block_vector_t topological_sort(gr_basic_block_vector_t &blocks);
+  gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks);
+  bool source_p(gr_basic_block_sptr block);
+  void topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t 
&output);
+};
+
+#endif /* INCLUDED_GR_FLAT_FLOWGRAPH_H */

Added: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
                               (rev 0)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
       2007-08-22 15:58:16 UTC (rev 6162)
@@ -0,0 +1,282 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2007 Free Software Foundation, Inc.
+ * 
+ * This file is part of GNU Radio
+ * 
+ * GNU Radio 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, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio 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 GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gr_flowgraph.h>
+#include <gr_io_signature.h>
+#include <stdexcept>
+#include <iostream>
+
+#define GR_FLOWGRAPH_DEBUG 1
+
+gr_flowgraph_sptr gr_make_flowgraph()
+{
+  return gr_flowgraph_sptr(new gr_flowgraph());
+}
+
+gr_flowgraph::gr_flowgraph()
+{
+}
+  
+gr_flowgraph::~gr_flowgraph()
+{
+}
+
+void
+gr_flowgraph::connect(const gr_endpoint &src, const gr_endpoint &dst)
+{
+  check_valid_port(src.block()->output_signature(), src.port());
+  check_valid_port(dst.block()->input_signature(), dst.port());
+  check_dst_not_used(dst);
+  check_type_match(src, dst);
+
+  // All ist klar, Herr Kommisar
+  d_edges.push_back(gr_edge(src,dst));
+}
+
+void
+gr_flowgraph::disconnect(const gr_endpoint &src, const gr_endpoint &dst)
+{
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+    if (src == p->src() && dst == p->dst()) {
+      d_edges.erase(p);
+      return;
+    }
+  }
+
+  throw std::invalid_argument("edge to disconnect not found");
+}
+
+void
+gr_flowgraph::validate()
+{
+  d_blocks = calc_used_blocks();
+
+  for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
+    std::vector<int> used_ports;
+    int ninputs, noutputs;
+
+    if (GR_FLOWGRAPH_DEBUG)
+      std::cout << "Validating block: " << (*p) << std::endl;
+
+    used_ports = calc_used_ports(*p, true); // inputs
+    ninputs = used_ports.size();
+    check_contiguity(*p, used_ports, true); // inputs
+
+    used_ports = calc_used_ports(*p, false); // outputs
+    noutputs = used_ports.size();
+    check_contiguity(*p, used_ports, false); // outputs
+
+    if (!((*p)->check_topology(ninputs, noutputs)))
+      throw std::runtime_error("check topology failed");
+  }
+}
+
+void
+gr_flowgraph::clear()
+{
+  // Boost shared pointers will deallocate as needed
+  d_blocks.clear();
+  d_edges.clear();
+}
+
+void
+gr_flowgraph::check_valid_port(gr_io_signature_sptr sig, int port)
+{
+  if (port < 0)
+    throw std::invalid_argument("negative port number");
+  if (sig->max_streams() >= 0 && port >= sig->max_streams())
+    throw std::invalid_argument("port number exceeds max");
+}
+
+void
+gr_flowgraph::check_dst_not_used(const gr_endpoint &dst)
+{
+  // An destination is in use if it is already on the edge list
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
+    if (p->dst() == dst)
+      throw std::invalid_argument("dst already in use");
+}
+
+void
+gr_flowgraph::check_type_match(const gr_endpoint &src, const gr_endpoint &dst)
+{
+  int src_size = 
src.block()->output_signature()->sizeof_stream_item(src.port());
+  int dst_size = 
dst.block()->input_signature()->sizeof_stream_item(dst.port());
+
+  if (src_size != dst_size)
+    throw std::invalid_argument("itemsize mismatch between src and dst");
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::calc_used_blocks()
+{
+  gr_basic_block_vector_t tmp, result;
+  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
+
+  // Collect all blocks in the edge list
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+    tmp.push_back(p->src().block());
+    tmp.push_back(p->dst().block());
+  }
+
+  // Return vector of unique blocks
+  sort(tmp.begin(), tmp.end());
+  unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+std::vector<int>
+gr_flowgraph::calc_used_ports(gr_basic_block_sptr block, bool check_inputs)
+{
+  std::vector<int> tmp, result;
+  std::insert_iterator<std::vector<int> > inserter(result, result.begin());
+
+  // Collect all seen ports 
+  gr_edge_vector_t edges = calc_connections(block, check_inputs);
+  for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
+    if (check_inputs == true)
+      tmp.push_back(p->dst().port());
+    else
+      tmp.push_back(p->src().port());
+  }
+
+  // Return vector of unique values
+  std::sort(tmp.begin(), tmp.end());
+  std::unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+gr_edge_vector_t
+gr_flowgraph::calc_connections(gr_basic_block_sptr block, bool check_inputs)
+{
+  gr_edge_vector_t result;
+
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+    if (check_inputs) {
+      if (p->dst().block() == block)
+       result.push_back(*p);
+    }
+    else {
+      if (p->src().block() == block)
+       result.push_back(*p);
+    }
+  }
+
+  return result; // assumes no duplicates
+}
+
+void
+gr_flowgraph::check_contiguity(gr_basic_block_sptr block,
+                              const std::vector<int> &used_ports,
+                              bool check_inputs)
+{
+  gr_io_signature_sptr sig =
+    check_inputs ? block->input_signature() : block->output_signature();
+
+  int nports = used_ports.size();
+  int min_ports = sig->min_streams();
+
+  if (nports == 0) {
+    if (min_ports == 0)
+      return;
+    else
+      throw std::runtime_error("insufficient ports");
+  }
+
+  if (used_ports[nports-1]+1 != nports) {
+    for (int i = 0; i < nports; i++)
+      if (used_ports[i] != i)
+       throw std::runtime_error("missing input assignment");
+  }
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::calc_downstream_blocks(gr_basic_block_sptr block, int port)
+{
+  gr_basic_block_vector_t tmp, result;
+  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
+
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
+    if (p->src() == gr_endpoint(block, port))
+      tmp.push_back(p->dst().block());
+
+  // Remove duplicates
+  sort(tmp.begin(), tmp.end());
+  unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::calc_downstream_blocks(gr_basic_block_sptr block)
+{
+  gr_basic_block_vector_t tmp, result;
+  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
+
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
+    if (p->src().block() == block)
+      tmp.push_back(p->dst().block());
+
+  // Remove duplicates
+  sort(tmp.begin(), tmp.end());
+  unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+gr_edge_vector_t
+gr_flowgraph::calc_upstream_edges(gr_basic_block_sptr block)
+{
+  gr_edge_vector_t result;
+
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
+    if (p->dst().block() == block)
+      result.push_back(*p);
+
+  return result; // Assume no duplicates
+}
+
+bool
+gr_flowgraph::has_block_p(gr_basic_block_sptr block)
+{
+  gr_basic_block_viter_t result;
+  result = std::find(d_blocks.begin(), d_blocks.end(), block);
+  return (result != d_blocks.end());
+}
+
+gr_edge
+gr_flowgraph::calc_upstream_edge(gr_basic_block_sptr block, int port)
+{
+  gr_edge result;
+
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+    if (p->dst() == gr_endpoint(block, port)) {
+      result = (*p);
+      break;
+    }
+  }
+
+  return result;
+}
+

Added: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
                                (rev 0)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
        2007-08-22 15:58:16 UTC (rev 6162)
@@ -0,0 +1,174 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006,2007 Free Software Foundation, Inc.
+ * 
+ * This file is part of GNU Radio
+ * 
+ * GNU Radio 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, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio 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 GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifndef INCLUDED_GR_FLOWGRAPH_H
+#define INCLUDED_GR_FLOWGRAPH_H
+
+#include <gr_basic_block.h>
+#include <iostream>
+
+/*!
+ *\brief Class representing a specific input or output graph endpoint
+ *
+ */
+class gr_endpoint
+{
+private:
+  gr_basic_block_sptr d_basic_block;
+  int d_port;
+
+public:
+  gr_endpoint() : d_basic_block(), d_port(0) { }
+  gr_endpoint(gr_basic_block_sptr block, int port) { d_basic_block = block; 
d_port = port; }
+  gr_basic_block_sptr block() const { return d_basic_block; }
+  int port() const { return d_port; }
+
+  bool operator==(const gr_endpoint &other) const;
+};    
+
+inline bool gr_endpoint::operator==(const gr_endpoint &other) const
+{
+  return (d_basic_block == other.d_basic_block && 
+         d_port == other.d_port);
+}
+
+// Hold vectors of gr_endpoint objects
+typedef std::vector<gr_endpoint> gr_endpoint_vector_t;
+typedef std::vector<gr_endpoint>::iterator gr_endpoint_viter_t;
+
+/*!
+ *\brief Class representing a connection between to graph endpoints
+ *
+ */
+class gr_edge
+{
+public:
+  gr_edge() : d_src(), d_dst() { };
+  gr_edge(const gr_endpoint &src, const gr_endpoint &dst) : d_src(src), 
d_dst(dst) { }
+  ~gr_edge();
+
+  const gr_endpoint &src() const { return d_src; }
+  const gr_endpoint &dst() const { return d_dst; }
+
+private:
+  gr_endpoint d_src;
+  gr_endpoint d_dst;
+};
+
+// Hold vectors of gr_edge objects
+typedef std::vector<gr_edge> gr_edge_vector_t;
+typedef std::vector<gr_edge>::iterator gr_edge_viter_t;
+
+
+// Create a shared pointer to a heap allocated flowgraph
+// (types defined in gr_runtime_types.h)
+gr_flowgraph_sptr gr_make_flowgraph();
+
+/*!
+ *\brief Class representing a directed, acyclic graph of basic blocks
+ *
+ */
+class gr_flowgraph
+{
+public:
+  friend gr_flowgraph_sptr gr_make_flowgraph();
+
+  // Destruct an arbitrary flowgraph
+  ~gr_flowgraph();
+
+  // Connect two endpoints
+  void connect(const gr_endpoint &src, const gr_endpoint &dst);
+
+  // Disconnect two endpoints
+  void disconnect(const gr_endpoint &src, const gr_endpoint &dst);
+
+  // Connect an output port to an input port (convenience)
+  void connect(gr_basic_block_sptr src_block, int src_port,
+              gr_basic_block_sptr dst_block, int dst_port);
+
+  // Disconnect an input port from an output port (convenience)
+  void disconnect(gr_basic_block_sptr src_block, int src_port,
+                 gr_basic_block_sptr dst_block, int dst_port);
+
+  // Validate connectivity, raise exception if invalid
+  void validate();
+
+  // Clear existing flowgraph
+  void clear();
+
+  // Return vector of connected blocks
+  gr_basic_block_vector_t calc_used_blocks();
+
+protected:
+  gr_flowgraph();
+
+  gr_basic_block_vector_t d_blocks;
+  gr_edge_vector_t d_edges;
+
+  std::vector<int> calc_used_ports(gr_basic_block_sptr block, bool 
check_inputs); 
+  gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block, 
int port);
+  gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block);
+  gr_edge_vector_t calc_upstream_edges(gr_basic_block_sptr block);
+  bool has_block_p(gr_basic_block_sptr block);
+  gr_edge calc_upstream_edge(gr_basic_block_sptr block, int port);
+
+private:
+
+  void check_valid_port(gr_io_signature_sptr sig, int port);
+  void check_dst_not_used(const gr_endpoint &dst);
+  void check_type_match(const gr_endpoint &src, const gr_endpoint &dst);
+  gr_edge_vector_t calc_connections(gr_basic_block_sptr block, bool 
check_inputs); // false=use outputs
+  void check_contiguity(gr_basic_block_sptr block, const std::vector<int> 
&used_ports, bool check_inputs);
+};
+
+// Convenience functions
+inline
+void gr_flowgraph::connect(gr_basic_block_sptr src_block, int src_port,
+                     gr_basic_block_sptr dst_block, int dst_port)
+{
+  connect(gr_endpoint(src_block, src_port),
+         gr_endpoint(dst_block, dst_port));
+}
+
+inline
+void gr_flowgraph::disconnect(gr_basic_block_sptr src_block, int src_port,
+                        gr_basic_block_sptr dst_block, int dst_port)
+{
+  disconnect(gr_endpoint(src_block, src_port),
+            gr_endpoint(dst_block, dst_port));
+}
+
+inline std::ostream&
+operator <<(std::ostream &os, const gr_endpoint endp)
+{
+  os << endp.block() << ":" << endp.port();
+  return os;
+}
+
+inline std::ostream&
+operator <<(std::ostream &os, const gr_edge edge)
+{
+  os << edge.src() << "->" << edge.dst();
+  return os;
+}
+
+#endif /* INCLUDED_GR_FLOWGRAPH_H */

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_types.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_types.h
    2007-08-21 19:15:43 UTC (rev 6161)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_types.h
    2007-08-22 15:58:16 UTC (rev 6162)
@@ -37,16 +37,20 @@
 class gr_buffer;
 class gr_buffer_reader;
 class gr_simple_flowgraph;
+class gr_flat_flowgraph;
+class gr_flowgraph;
 class gr_runtime;
 
 typedef boost::shared_ptr<gr_basic_block>       gr_basic_block_sptr;
 typedef boost::shared_ptr<gr_block>             gr_block_sptr;
-typedef boost::shared_ptr<gr_block_detail>         gr_block_detail_sptr;
-typedef boost::shared_ptr<gr_hier_block2>          gr_hier_block2_sptr;
+typedef boost::shared_ptr<gr_block_detail>     gr_block_detail_sptr;
+typedef boost::shared_ptr<gr_hier_block2>      gr_hier_block2_sptr;
 typedef boost::shared_ptr<gr_io_signature>      gr_io_signature_sptr;
-typedef boost::shared_ptr<gr_buffer>               gr_buffer_sptr;
-typedef boost::shared_ptr<gr_buffer_reader>        gr_buffer_reader_sptr;
-typedef boost::shared_ptr<gr_runtime>              gr_runtime_sptr;
+typedef boost::shared_ptr<gr_buffer>           gr_buffer_sptr;
+typedef boost::shared_ptr<gr_buffer_reader>    gr_buffer_reader_sptr;
+typedef boost::shared_ptr<gr_runtime>          gr_runtime_sptr;
 typedef boost::shared_ptr<gr_simple_flowgraph>  gr_simple_flowgraph_sptr;
+typedef boost::shared_ptr<gr_flowgraph>         gr_flowgraph_sptr;
+typedef boost::shared_ptr<gr_flat_flowgraph>    gr_flat_flowgraph_sptr;
 
 #endif /* INCLUDED_GR_RUNTIME_TYPES_H */