dag.cpp

Go to the documentation of this file.
00001 /*
00002  * dag.cpp
00003  *
00004  * Copyright (C) 2007  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  *
00031  * Directed acyclic graph
00032  */
00033 
00034 // includes --------------------------------------------------------------------
00035 #include "dag.h"                        // always include our own header first!
00036 
00037 #include "perf/perf.h"
00038 
00039 
00040 
00041 namespace graph {
00042 
00043 
00044 DAG::~DAG(void) throw() { }
00045 
00046 
00047 typedef std::map<std::string, smart_ptr<SetString> > map_set_t;
00048 
00049 
00050 ////////////////////////////////////////////////////////////////////////////////
00051 //
00052 //      static helper methods
00053 //
00054 ////////////////////////////////////////////////////////////////////////////////
00055 
00056 
00057 ////////////////////////////////////////////////////////////////////////////////
00058 //
00059 //      DagImpl - class that implements the DAG interface
00060 //
00061 ////////////////////////////////////////////////////////////////////////////////
00062 
00063 class DagImpl : public DAG {
00064 public:
00065         ~DagImpl(void) throw() { }
00066 
00067         // public class methods ------------------------------------------------
00068         void initialize(void) throw() { }
00069 
00070         // graph::DAG class interface methods ----------------------------------
00071         void addNode(IN const char * node);
00072         void addEdge(IN const char * from_node,
00073                                 IN const char * to_node);
00074         void getOrderedNodeList(OUT VecString& leaf_to_root) const;
00075 
00076 private:
00077         // private helper methods ----------------------------------------------
00078         SetString * getSet(IN const char * node);
00079 
00080         // private data members ------------------------------------------------
00081         map_set_t               m_map;
00082         SetString               m_allNodes;     // everything we've seen
00083 };
00084 
00085 
00086 
00087 void
00088 DagImpl::addNode
00089 (
00090 IN const char * node
00091 )
00092 {
00093         ASSERT(node, "null");
00094 
00095         m_allNodes.insert(node);
00096 }
00097 
00098 
00099 
00100 void
00101 DagImpl::addEdge
00102 (
00103 IN const char * from_node,
00104 IN const char * to_node
00105 )
00106 {
00107         ASSERT(from_node, "null from_node in DAG::addEdge()");
00108         ASSERT(to_node, "null to_node in DAG::addEdge()");
00109 
00110         // we'll keep a record that the from_node references the to_node
00111         SetString * set = this->getSet(from_node);
00112         ASSERT(set, "getSet() should always return non-null");
00113 
00114         set->insert(to_node);
00115 
00116         // and add both to our master set
00117         this->addNode(from_node);
00118         this->addNode(to_node);
00119 }
00120 
00121 
00122 
00123 void
00124 DagImpl::getOrderedNodeList
00125 (
00126 OUT VecString& leaf_to_root
00127 )
00128 const
00129 {
00130         perf::Timer timer("DAG::getOrderedNodeList");
00131 
00132         // initialize
00133         leaf_to_root.clear();
00134 
00135         // first, populate visited set with all leaf nodes
00136         SetString visited;
00137         SetString remaining;
00138         for (SetString::const_iterator i = m_allNodes.begin();
00139              i != m_allNodes.end(); ++i) {
00140                 // DPRINTF("  checking node '%s'", i->c_str());
00141                 if (m_map.end() == m_map.find(*i)) {
00142                         visited.insert(*i);
00143                         leaf_to_root.push_back(*i);
00144                 } else {
00145                         remaining.insert(*i);
00146                 }
00147         }
00148         ASSERT(visited.size() > 0, "No leaf nodes?  Cyclical dependency");
00149 
00150         // short-circuit (all leaf nodes)
00151         if (0 == remaining.size())
00152                 return;
00153 
00154         // now keep walking until all nodes have been processed
00155         for (long depth = 1; true; ++depth) {
00156                 // DPRINTF("Depth = %ld", depth);
00157 
00158                 // find all nodes that have this depth.  That means all of
00159                 //   their children must already be in the visited set
00160                 VecString nuke;
00161                 for (SetString::const_iterator i = remaining.begin();
00162                      i != remaining.end(); ++i) {
00163                         if (visited.end() != visited.find(*i)) {
00164                                 continue;       // already in the visited set
00165                         }
00166 
00167                         // okay how about everything it depends on?
00168                         map_set_t::const_iterator j = m_map.find(*i);
00169                         ASSERT(m_map.end() != j,
00170                             "not a leaf, must have set! '%s'", i->c_str());
00171                         const SetString * set = j->second;
00172                         ASSERT(set, "null set in map?");
00173 
00174                         bool all_children_visited = true;
00175                         for (SetString::const_iterator k = set->begin();
00176                              k != set->end(); ++k) {
00177                                 if (visited.end() == visited.find(*k)) {
00178                                         all_children_visited = false;
00179                                         break;
00180                                 }
00181                         }
00182 
00183                         if (!all_children_visited)
00184                                 continue;       // skip this one
00185 
00186                         // okay, this node matches this depth
00187                         visited.insert(*i);
00188                         nuke.push_back(*i);
00189                         leaf_to_root.push_back(*i);
00190                 }
00191                 ASSERT(nuke.size() > 0, "cyclical dependency?");
00192 
00193                 // nuke everything we pulled out at this depth
00194                 for (VecString::iterator i = nuke.begin(); i != nuke.end(); ++i)
00195                 {
00196                         remaining.erase(remaining.find(*i));
00197                 }
00198 
00199                 if (0 == remaining.size())
00200                         break;          // all done!
00201         }
00202 }
00203 
00204 
00205 
00206 SetString *
00207 DagImpl::getSet
00208 (
00209 IN const char * node
00210 )
00211 {
00212         ASSERT(node, "null node in getSet()");
00213 
00214         map_set_t::iterator i = m_map.find(node);
00215         if (m_map.end() == i) {
00216                 smart_ptr<SetString> set = new SetString;
00217                 ASSERT(set, "out of memory");
00218                 m_map[node] = set;
00219                 return set;
00220         } else {
00221                 return i->second;
00222         }
00223 }
00224 
00225 
00226 
00227 ////////////////////////////////////////////////////////////////////////////////
00228 //
00229 //      public API
00230 //
00231 ////////////////////////////////////////////////////////////////////////////////
00232 
00233 smart_ptr<DAG>
00234 DAG::create
00235 (
00236 void
00237 )
00238 {
00239         smart_ptr<DagImpl> local = new DagImpl;
00240         ASSERT(local, "out of memory");
00241 
00242         local->initialize();
00243 
00244         return local;
00245 }
00246 
00247 
00248 
00249 };      // graph namespace
00250