[Commit-gnuradio] r3792 - gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++

[jcorgan]

Author: jcorgan
Date: 2006-10-15 16:05:37 -0600 (Sun, 15 Oct 2006)
New Revision: 3792

Modified:
   
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.cc
   
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.h
Log:
Work in progress.

Modified: 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.cc
 2006-10-15 20:31:52 UTC (rev 3791)
+++ 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.cc
 2006-10-15 22:05:37 UTC (rev 3792)
@@ -25,9 +25,7 @@
 #include <gr_io_signature.h>
 #include <gr_buffer.h>
 
-#include <utility>
 #include <algorithm>
-#include <functional>
 
 using namespace std;
 
@@ -174,18 +172,28 @@
        (*block_iter)->set_detail(detail);
     }
     
-    // 'connect_inputs()'
+    // Connect inputs to outputs for each block
     for(block_iter = d_blocks.begin(); block_iter != d_blocks.end(); 
block_iter++) {
+       // Get its detail and edges that feed into it
        gr_block_detail_sptr detail = (*block_iter)->detail();
        gr_edge_vector_t in_edges = calc_input_edges(*block_iter);
+       printf("Block %s(%li) has %i input edges.\n",
+           (*block_iter)->name().c_str(), (*block_iter)->unique_id(), 
in_edges.size());
+
+       // For each edge that feeds into it
        gr_edge_vector_iterator_t edge_iter;
        for(edge_iter = in_edges.begin(); edge_iter != in_edges.end(); 
edge_iter++) {
+           // Set the input buffer on the destination port to the output
+           // buffer on the source port
            int dst_port = edge_iter->second.second;
            int src_port = edge_iter->first.second;
            gr_block_sptr src_block = edge_iter->first.first;
            gr_buffer_sptr src_buffer = src_block->detail()->output(src_port);
-           printf("Setting input buffer on %s(%i).\n", 
-               edge_iter->second.first->name().c_str(), dst_port);
+
+           printf("Setting input buffer on %i:%s(%i).\n", dst_port, 
+               edge_iter->second.first->name().c_str(),
+               edge_iter->second.first->unique_id());
+
            detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, 
(*block_iter)->history()-1));
        }
     }
@@ -336,7 +344,10 @@
     
     while (nodes.size() > 0) {
        graph = calc_reachable_vertices(nodes[0], nodes);
-       printf("graph.size() = %i \n", graph.size());
+
+       // Partition should be at least one block
+       assert(graph.size());
+
        result.push_back(topological_sort(graph));
        printf("n=%i g=%i r=%i\n", nodes.size(), graph.size(), result.size());
        
@@ -349,16 +360,42 @@
     return result;
 }
 
-gr_block_vector_t gr_flow_graph::calc_reachable_vertices(gr_block_sptr block, 
gr_block_vector_t blocks)
+gr_block_vector_t gr_flow_graph::calc_reachable_vertices(gr_block_sptr block, 
gr_block_vector_t &blocks)
 {
     gr_block_vector_t result;
+    gr_vertex_vector_t vertices;
+    
+    // Create working list of vertices
+    gr_block_vector_iterator_t block_iter;
+    for(block_iter = blocks.begin(); block_iter != blocks.end(); block_iter++)
+       vertices.push_back(make_pair(*block_iter, GR_VERTEX_WHITE));
+    
+    // Mark all reachable vertices from 'block'
+    reachable_dfs_visit(block, vertices);
+    
+    // Collect all the blocks from the marked vertices into the result vector
+    gr_vertex_vector_iterator_t vertex_iter;
+    for (vertex_iter = vertices.begin(); vertex_iter != vertices.end(); 
vertex_iter++)
+       if (vertex_iter->second == GR_VERTEX_BLACK)
+           result.push_back(vertex_iter->first);
 
-    // NOP
-    result.push_back(block);
-    
     return result;
 }
 
+void gr_flow_graph::reachable_dfs_visit(gr_block_sptr block, 
gr_vertex_vector_t &vertices)
+{
+    printf("Check for reachability of node %s(%li)\n", block->name().c_str(), 
block->unique_id());
+
+    // Find vertex corresponding to block, mark visited
+    gr_vertex_vector_iterator_t vertex_iter;
+    for (vertex_iter = vertices.begin(); vertex_iter != vertices.end(); 
vertex_iter++)
+       if (vertex_iter->first == block)
+           vertex_iter->second = GR_VERTEX_BLACK;
+    
+    // Recurse into adjacent vertices
+    // NOP
+}
+
 gr_block_vector_t gr_flow_graph::topological_sort(gr_block_vector_t blocks)
 {
     gr_block_vector_t result;

Modified: 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.h
  2006-10-15 20:31:52 UTC (rev 3791)
+++ 
gnuradio/branches/developers/jcorgan/cppwrap/gnuradio-examples/c++/gr_flow_graph.h
  2006-10-15 22:05:37 UTC (rev 3792)
@@ -33,17 +33,29 @@
 class gr_scheduler;
 typedef boost::shared_ptr<gr_scheduler> gr_scheduler_sptr;
 
+// Oh, for the love of Python, of which the STL is but the faintest 
approximation,
+// that those poor souls who toil in C++ land might know some glimmer of the
+// beauty and majesty of lists and list comprehensions.  At least one may take 
some 
+// small solace that one is not mired in the dreaded environs of pure C, 
though such 
+// consolation is no recompense for the agony of templates, pairs, and 
iterators!
+
 // Container for list of gr_blocks, and list of lists
 typedef std::vector<gr_block_sptr> gr_block_vector_t;
 typedef std::vector<gr_block_sptr>::iterator gr_block_vector_iterator_t;
 typedef std::vector<gr_block_vector_t> gr_block_vector_vector_t;
 
-// Flow graph endpoints and edges
+// Flow graph endpoints, edges
 typedef std::pair<gr_block_sptr, int> gr_endpoint_t;
 typedef std::pair<gr_endpoint_t, gr_endpoint_t> gr_edge_t;
 typedef std::vector<gr_edge_t> gr_edge_vector_t;
 typedef std::vector<gr_edge_t>::iterator gr_edge_vector_iterator_t;
 
+// Flow graph vertices
+typedef enum { GR_VERTEX_WHITE, GR_VERTEX_GRAY, GR_VERTEX_BLACK } 
gr_vertex_color_t;
+typedef std::pair<gr_block_sptr, gr_vertex_color_t> gr_vertex_t;
+typedef std::vector<gr_vertex_t> gr_vertex_vector_t;
+typedef std::vector<gr_vertex_t>::iterator gr_vertex_vector_iterator_t;
+
 #define GR_FIXED_BUFFER_SIZE 32000
 
 class gr_flow_graph : public boost::enable_shared_from_this<gr_flow_graph>
@@ -67,18 +79,19 @@
     gr_buffer_sptr allocate_buffer(gr_block_sptr block, int port);
     gr_block_vector_t calc_downstream_blocks(gr_endpoint_t src);
     gr_edge_vector_t calc_input_edges(gr_block_sptr block);
-    gr_block_vector_t calc_reachable_vertices(gr_block_sptr block, 
gr_block_vector_t blocks);
+    gr_block_vector_t calc_reachable_vertices(gr_block_sptr block, 
gr_block_vector_t &blocks);
+    void reachable_dfs_visit(gr_block_sptr block, gr_vertex_vector_t 
&vertices);
     gr_block_vector_t topological_sort(gr_block_vector_t blocks);
-    
+
     static const int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE;
     gr_edge_vector_t  d_edges;
     gr_block_vector_t d_blocks;
     gr_scheduler_sptr d_scheduler;
-                            
-    // Topological sort and partition functions here
 
 public:
     ~gr_flow_graph();
+
+    // At least the public interface of the class is sane
     void connect(gr_block_sptr src_block, int src_port,
                 gr_block_sptr dst_block, int dst_port);
     // more connect convenience functions go here