[Commit-gnuradio] r4038 - gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime

[jcorgan]

Author: jcorgan
Date: 2006-11-28 12:10:33 -0700 (Tue, 28 Nov 2006)
New Revision: 4038

Modified:
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
   
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
Log:
Work in progress.  Able to flatten and partition graph.

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
  2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
  2006-11-28 19:10:33 UTC (rev 4038)
@@ -38,7 +38,8 @@
 gr_block_detail::gr_block_detail (unsigned int ninputs, unsigned int noutputs)
   : d_ninputs (ninputs), d_noutputs (noutputs),
     d_input (ninputs), d_output (noutputs),
-    d_done (false)
+    d_done (false),
+    d_color (gr_block_detail::WHITE)
 {
   s_ncurrently_allocated++;
 }

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
   2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
   2006-11-28 19:10:33 UTC (rev 4038)
@@ -1,19 +1,19 @@
 /* -*- c++ -*- */
 /*
  * Copyright 2004 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 2, 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 detail.
- * 
+ *
  * 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,
@@ -75,18 +75,26 @@
 
   void produce_each (int how_many_items);
 
+  /*!
+   * \brief Allow the flowgraph to set for sorting and partitioning
+   */
+  enum vcolor { WHITE, GREY, BLACK };
+  void set_color(vcolor color) { d_color = color; }
+  vcolor color() const { return d_color; }
+
   // 
----------------------------------------------------------------------------
 
  private:
-  unsigned int                     d_ninputs;
-  unsigned int                     d_noutputs;
+  unsigned int                       d_ninputs;
+  unsigned int                       d_noutputs;
   std::vector<gr_buffer_reader_sptr> d_input;
-  std::vector<gr_buffer_sptr>      d_output;
-  bool                             d_done;
-    
+  std::vector<gr_buffer_sptr>       d_output;
+  bool                               d_done;
+  vcolor                             d_color;
+
   gr_block_detail (unsigned int ninputs, unsigned int noutputs);
 
-  friend gr_block_detail_sptr 
+  friend gr_block_detail_sptr
   gr_make_block_detail (unsigned int ninputs, unsigned int noutputs);
 };
 

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
  2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
  2006-11-28 19:10:33 UTC (rev 4038)
@@ -36,7 +36,8 @@
 gr_runtime_impl::gr_runtime_impl(gr_hier_block2_sptr top_block) :
 d_running(false),
 d_top_block(top_block),
-d_sfg(gr_make_simple_flowgraph())
+d_sfg(gr_make_simple_flowgraph()),
+d_graphs()
 {
 }
   
@@ -55,9 +56,15 @@
     else
         d_running = true;
 
+    d_sfg->d_detail->reset();
     d_top_block->d_detail->flatten(d_sfg);
     d_sfg->d_detail->validate();
     d_sfg->d_detail->setup_connections();
+
+    d_graphs = d_sfg->d_detail->partition();
+    if (GR_RUNTIME_IMPL_DEBUG)
+        std::cout << "Flow graph has " << d_graphs.size() 
+                  << " sub-graphs." << std::endl;
 }
 
 void 

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
   2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
   2006-11-28 19:10:33 UTC (rev 4038)
@@ -24,6 +24,7 @@
 #define INCLUDED_GR_RUNTIME_IMPL_H
 
 #include <gr_runtime_types.h>
+#include <gr_block.h>
 
 class gr_runtime_impl
 {
@@ -31,10 +32,11 @@
     gr_runtime_impl(gr_hier_block2_sptr top_block);
     friend class gr_runtime;
     
-    bool                     d_running;
-    gr_hier_block2_sptr      d_top_block;
-    gr_simple_flowgraph_sptr d_sfg;
-    
+    bool                           d_running;
+    gr_hier_block2_sptr            d_top_block;
+    gr_simple_flowgraph_sptr       d_sfg;
+    std::vector<gr_block_vector_t> d_graphs;
+        
     void start();
     void stop();
     void wait();

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
       2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
       2006-11-28 19:10:33 UTC (rev 4038)
@@ -1,19 +1,19 @@
 /* -*- c++ -*- */
 /*
  * Copyright 2006 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 2, 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,
@@ -34,8 +34,8 @@
 
 #define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 1
 
-gr_edge_sptr 
-gr_make_edge(const std::string &src_name, int src_port, 
+gr_edge_sptr
+gr_make_edge(const std::string &src_name, int src_port,
             const std::string &dst_name, int dst_port)
 {
     return gr_edge_sptr(new gr_edge(src_name, src_port, dst_name, dst_port));
@@ -46,7 +46,7 @@
     d_dst(dst_name, dst_port)
 {
 }
-                
+
 gr_edge::~gr_edge()
 {
 }
@@ -56,11 +56,19 @@
 d_edges()
 {
 }
-  
+
 gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail()
 {
 }
 
+void
+gr_simple_flowgraph_detail::reset()
+{
+    // Boost shared pointers will deallocate as needed
+    d_edges.clear();
+    d_components.clear();
+}
+
 gr_block_sptr
 gr_simple_flowgraph_detail::lookup_block(const std::string &name)
 {
@@ -93,7 +101,7 @@
     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
        std::cout << "Connecting " << src_name << ":" << src_port << "->"
               << dst_name << ":" << dst_port << std::endl;
-                         
+
     if (!src_block)
         throw std::invalid_argument("unknown src name");
     if (!dst_block)
@@ -103,7 +111,7 @@
     check_valid_port(dst_block->input_signature(), dst_port);
     check_dst_not_used(dst_name, dst_port);
     check_type_match(src_block, src_port, dst_block, dst_port);
-    
+
     d_edges.push_back(gr_make_edge(src_name, src_port, dst_name, dst_port));
 }
 
@@ -153,7 +161,7 @@
        used_ports = calc_used_ports(p->first, false); // outputs
        noutputs = used_ports.size();
        check_contiguity(p->second, used_ports, false); // outputs
-       
+
        if (!(p->second->check_topology(ninputs, noutputs)))
            throw std::runtime_error("check topology failed");
     }
@@ -168,7 +176,7 @@
 
     std::vector<int> tmp, result;
     std::insert_iterator<std::vector<int> > inserter(result, result.begin());
-    
+
     gr_edge_vector_t edges = calc_connections(name, check_inputs);
 
     for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
@@ -177,14 +185,14 @@
         else
             tmp.push_back((*p)->src_port());
     }
-    
+
     // remove duplicates
     std::sort(tmp.begin(), tmp.end());
     std::unique_copy(tmp.begin(), tmp.end(), inserter);
 
     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
         std::cout << result.size() << std::endl;
-    
+
     return result;
 }
 
@@ -216,12 +224,12 @@
         std::cout << "Checking " << (check_inputs ? "input " : "output ")
                   << "contiguity...";
 
-    gr_io_signature_sptr sig = 
+    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) {
             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
@@ -230,9 +238,9 @@
         }
         else {
             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
-                std::cout << "needs " << min_ports << ", only has " 
+                std::cout << "needs " << min_ports << ", only has "
                           << nports << std::endl;
-           
+
             throw std::runtime_error("insufficient ports");
         }
     }
@@ -277,7 +285,7 @@
         // Get its detail and edges that feed into it
         gr_block_detail_sptr detail = p->second->detail();
         gr_edge_vector_t in_edges = calc_upstream_edges(p->first);
-                       
+
         // For each edge that feeds into it
         for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
             // Set the input buffer on the destination port to the output
@@ -290,7 +298,7 @@
             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
                 std::cout << "Setting input on " << (*e)->dst_name()
                           << ":" << dst_port << std::endl;
-                            
+
             detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, 
p->second->history()-1));
         }
     }
@@ -302,7 +310,7 @@
     gr_block_sptr block = lookup_block(name);
     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*block->output_multiple())   // Note: this means 
output_multiple()
         nitems = 2*block->output_multiple();   // can't be changed by block 
dynamically
@@ -316,11 +324,11 @@
         int history    = (*p)->history();
         nitems = std::max(nitems, 2*(decimation*multiple+history));
     }
-                                           
+
     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
         std::cout << "Allocating buffer for port " << port << " with "
                   << nitems << " items of size " << item_size << std::endl;
-        
+
     return gr_make_buffer(nitems, item_size);
 }
 
@@ -329,11 +337,11 @@
 {
     gr_block_vector_t tmp, result;
     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
-               
+
     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
         if ((*p)->src_name() == name && (*p)->src_port() == port)
             tmp.push_back(lookup_block((*p)->dst_name()));
-                                   
+
     // Remove duplicates
     sort(tmp.begin(), tmp.end());
     unique_copy(tmp.begin(), tmp.end(), inserter);
@@ -344,10 +352,122 @@
 gr_simple_flowgraph_detail::calc_upstream_edges(const std::string &name)
 {
     gr_edge_vector_t result;
-               
+
     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
         if ((*p)->dst_name() == name)
             result.push_back(*p);
 
     return result; // Assume no duplicates
 }
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_used_blocks()
+{
+    std::vector<std::string> tmp, tmp_unique;
+    std::insert_iterator<std::vector<std::string> > inserter(tmp_unique, 
tmp_unique.begin());
+    gr_block_vector_t result;
+
+    for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+        tmp.push_back((*p)->src_name());
+        tmp.push_back((*p)->dst_name());
+    }
+
+    sort(tmp.begin(), tmp.end());
+    unique_copy(tmp.begin(), tmp.end(), inserter);
+
+    for (std::vector<std::string>::iterator p = tmp_unique.begin();
+         p != tmp_unique.end(); p++)
+        result.push_back(lookup_block(*p));
+
+    if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
+        std::cout << "Flowgraph uses " << result.size()
+                  << " distinct blocks." << std::endl;
+
+    return result;
+}
+
+std::vector<gr_block_vector_t>
+gr_simple_flowgraph_detail::partition()
+{
+    std::vector<gr_block_vector_t> result;
+    gr_block_vector_t blocks = calc_used_blocks();
+    gr_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_block_viter_t p = graph.begin(); p != graph.end(); p++)
+            blocks.erase(find(blocks.begin(), blocks.end(), *p));
+    }
+
+    return result;
+}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_reachable_blocks(gr_block_sptr block, 
gr_block_vector_t &blocks)
+{
+    gr_block_vector_t result;
+
+    // Mark all blocks as unvisited
+    for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+        (*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_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+        if ((*p)->detail()->color() == gr_block_detail::BLACK)
+            result.push_back(*p);
+
+    return result;
+}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::topological_sort(gr_block_vector_t blocks)
+{
+    gr_block_vector_t result;
+
+    // NOP for now
+    result = blocks;
+
+    return result;
+}
+
+// Recursively mark all reachable blocks from given block and block list
+void 
+gr_simple_flowgraph_detail::reachable_dfs_visit(gr_block_sptr block, 
gr_block_vector_t &blocks)
+{
+    // Mark the current one as visited
+    block->detail()->set_color(gr_block_detail::BLACK);
+
+    // Recurse into adjacent vertices
+    gr_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
+
+    for (gr_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
+        if ((*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_block_vector_t 
+gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_block_sptr block, 
gr_block_vector_t &blocks)
+{
+    gr_block_vector_t tmp, result;
+    std::insert_iterator<gr_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 (lookup_block((*p)->src_name()) == block)
+            tmp.push_back(lookup_block((*p)->dst_name()));
+        if (lookup_block((*p)->dst_name()) == block)
+            tmp.push_back(lookup_block((*p)->src_name()));
+    }    
+
+    // Remove duplicates
+    sort(tmp.begin(), tmp.end());
+    unique_copy(tmp.begin(), tmp.end(), inserter);
+    return result;
+}

Modified: 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
        2006-11-28 06:23:20 UTC (rev 4037)
+++ 
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
        2006-11-28 19:10:33 UTC (rev 4038)
@@ -82,6 +82,7 @@
     gr_edge_vector_t   d_edges;
     static const unsigned int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE;
     
+    void reset();
     void define_component(const std::string &name, gr_block_sptr block);    
     void connect(const std::string &src, int src_port, 
                  const std::string &dst, int dst_port);
@@ -99,7 +100,13 @@
     gr_buffer_sptr allocate_buffer(const std::string &name, int port);
     gr_block_vector_t calc_downstream_blocks(const std::string &name, int 
port);
     gr_edge_vector_t calc_upstream_edges(const std::string &name);
-    
+    gr_block_vector_t calc_used_blocks();
+    std::vector<gr_block_vector_t> partition();
+    gr_block_vector_t calc_reachable_blocks(gr_block_sptr block, 
gr_block_vector_t &blocks);
+    gr_block_vector_t topological_sort(gr_block_vector_t blocks);
+    void reachable_dfs_visit(gr_block_sptr block, gr_block_vector_t &blocks);
+    gr_block_vector_t calc_adjacent_blocks(gr_block_sptr block, 
gr_block_vector_t &blocks);
+        
 public:
     ~gr_simple_flowgraph_detail();
 };