[Commit-gnuradio] r4097 - gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime

[jcorgan]

Author: jcorgan
Date: 2006-12-15 23:24:06 -0700 (Fri, 15 Dec 2006)
New Revision: 4097

Modified:
   
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
   
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
Log:
Implemented topological sort.

Modified: 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
        2006-12-15 18:23:50 UTC (rev 4096)
+++ 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
        2006-12-16 06:24:06 UTC (rev 4097)
@@ -32,7 +32,7 @@
 #include <iostream>
 #include <stdexcept>
 
-#define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 0
+#define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 1
 
 gr_edge_sptr
 gr_make_edge(const std::string &src_name, int src_port,
@@ -79,6 +79,17 @@
         return gr_block_sptr();
 }
 
+std::string
+gr_simple_flowgraph_detail::lookup_name(gr_block_sptr block)
+{
+    for (gr_component_miter_t p = d_components.begin(); p != 
d_components.end(); p++) {
+        if (p->second == block)
+            return p->first;
+    }
+
+    return std::string(""); // Not found
+}
+
 void
 gr_simple_flowgraph_detail::define_component(const std::string &name, 
gr_block_sptr block)
 {
@@ -345,6 +356,22 @@
     return result;
 }
 
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_downstream_blocks(const std::string &name)
+{
+    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)
+            tmp.push_back(lookup_block((*p)->dst_name()));
+
+    // Remove duplicates
+    sort(tmp.begin(), tmp.end());
+    unique_copy(tmp.begin(), tmp.end(), inserter);
+    return result;
+}
+
 gr_edge_vector_t
 gr_simple_flowgraph_detail::calc_upstream_edges(const std::string &name)
 {
@@ -458,14 +485,101 @@
     return result;
 }
 
+void
+gr_simple_flowgraph_detail::dump_block_vector(gr_block_vector_t blocks)
+{
+    for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+        std::cout << (*p) << std::endl;
+    }
+}
+
 gr_block_vector_t
 gr_simple_flowgraph_detail::topological_sort(gr_block_vector_t &blocks)
 {
-    gr_block_vector_t result;
+    gr_block_vector_t result, tmp;
+    std::cout << "Before source sort: " << std::endl;
+    dump_block_vector(blocks);
+    std::cout << std::endl;
 
-    // NOP for now
-    result = blocks;
+    tmp = sort_sources_first(blocks);
 
+    std::cout << "After source sort: " << std::endl;
+    dump_block_vector(tmp);
+    std::cout << std::endl;
+
+    // Start 'em all white
+    for (gr_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
+        (*p)->detail()->set_color(gr_block_detail::WHITE);
+
+    for (gr_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
+        if ((*p)->detail()->color() == gr_block_detail::WHITE)
+            topological_dfs_visit(*p, result);
+    }    
+
+    reverse(result.begin(), result.end());
+
+    std::cout << "After dfs: " << std::endl;
+    dump_block_vector(result);
+    std::cout << std::endl;
+
     return result;
 }
 
+bool
+gr_simple_flowgraph_detail::source_p(gr_block_sptr block)
+{
+    return (calc_upstream_edges(lookup_name(block)).size() == 0);
+}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::sort_sources_first(gr_block_vector_t &blocks)
+{
+    gr_block_vector_t sources, nonsources, result;
+
+    for (gr_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_block_viter_t p = sources.begin(); p != sources.end(); p++)
+        result.push_back(*p);
+
+    for (gr_block_viter_t p = nonsources.begin(); p != nonsources.end(); p++)
+        result.push_back(*p);
+
+    return result;
+}
+
+void
+gr_simple_flowgraph_detail::topological_dfs_visit(gr_block_sptr block, 
gr_block_vector_t &output)
+{
+    block->detail()->set_color(gr_block_detail::GREY);
+
+    gr_block_vector_t ds_blocks = calc_downstream_blocks(lookup_name(block));
+    std::cout << "Downstream blocks of " << block << ":" << std::endl;
+    dump_block_vector(ds_blocks);
+
+    gr_block_vector_t blocks(ds_blocks);
+    for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+        switch ((*p)->detail()->color()) {
+            case gr_block_detail::WHITE:            // (u, v) is a tree edge
+                topological_dfs_visit(*p, output);
+                break;
+
+            case gr_block_detail::GREY:             // (u, v) is a back edge - 
not a DAG
+                throw std::runtime_error("flow graph has loops!");
+
+            case gr_block_detail::BLACK:
+                continue;
+
+            default:
+                throw std::runtime_error("invalid color on block!");
+        }
+
+    }
+
+    block->detail()->set_color(gr_block_detail::BLACK);
+    output.push_back(block);
+}

Modified: 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
 2006-12-15 18:23:50 UTC (rev 4096)
+++ 
gnuradio/branches/developers/jcorgan/sfg/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
 2006-12-16 06:24:06 UTC (rev 4097)
@@ -75,6 +75,7 @@
 private:
     friend class gr_simple_flowgraph;
     friend class gr_runtime_impl;
+    friend class topo_block_cmp;
     
     gr_simple_flowgraph_detail();
 
@@ -87,6 +88,8 @@
     void connect(const std::string &src, int src_port, 
                  const std::string &dst, int dst_port);
     gr_block_sptr lookup_block(const std::string &name);
+    std::string lookup_name(const gr_block_sptr block);
+
     void check_valid_port(gr_io_signature_sptr sig, int port);
     void check_dst_not_used(const std::string &name, int port);
     void check_type_match(gr_block_sptr src_block, int src_port,
@@ -99,6 +102,7 @@
     void setup_connections();
     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_block_vector_t calc_downstream_blocks(const std::string &name);
     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();
@@ -106,6 +110,10 @@
     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);
+    bool source_p(gr_block_sptr block);
+    gr_block_vector_t sort_sources_first(gr_block_vector_t &blocks);
+    void topological_dfs_visit(gr_block_sptr block, gr_block_vector_t &output);
+    void dump_block_vector(gr_block_vector_t blocks);
         
 public:
     ~gr_simple_flowgraph_detail();