dag.cpp

Go to the documentation of this file.

/*
 * dag.cpp
 *
 * Copyright (C) 2007  Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Directed acyclic graph
 */

// includes --------------------------------------------------------------------
#include "dag.h"                        // always include our own header first!

#include "perf/perf.h"



namespace graph {


DAG::~DAG(void) throw() { }


typedef std::map<std::string, smart_ptr<SetString> > map_set_t;


////////////////////////////////////////////////////////////////////////////////
//
//      static helper methods
//
////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////////////////
//
//      DagImpl - class that implements the DAG interface
//
////////////////////////////////////////////////////////////////////////////////

class DagImpl : public DAG {
public:
        ~DagImpl(void) throw() { }

        // public class methods ------------------------------------------------
        void initialize(void) throw() { }

        // graph::DAG class interface methods ----------------------------------
        void addNode(IN const char * node);
        void addEdge(IN const char * from_node,
                                IN const char * to_node);
        void getOrderedNodeList(OUT VecString& leaf_to_root) const;

private:
        // private helper methods ----------------------------------------------
        SetString * getSet(IN const char * node);

        // private data members ------------------------------------------------
        map_set_t               m_map;
        SetString               m_allNodes;     // everything we've seen
};



void
DagImpl::addNode
(
IN const char * node
)
{
        ASSERT(node, "null");

        m_allNodes.insert(node);
}



void
DagImpl::addEdge
(
IN const char * from_node,
IN const char * to_node
)
{
        ASSERT(from_node, "null from_node in DAG::addEdge()");
        ASSERT(to_node, "null to_node in DAG::addEdge()");

        // we'll keep a record that the from_node references the to_node
        SetString * set = this->getSet(from_node);
        ASSERT(set, "getSet() should always return non-null");

        set->insert(to_node);

        // and add both to our master set
        this->addNode(from_node);
        this->addNode(to_node);
}



void
DagImpl::getOrderedNodeList
(
OUT VecString& leaf_to_root
)
const
{
        perf::Timer timer("DAG::getOrderedNodeList");

        // initialize
        leaf_to_root.clear();

        // first, populate visited set with all leaf nodes
        SetString visited;
        SetString remaining;
        for (SetString::const_iterator i = m_allNodes.begin();
             i != m_allNodes.end(); ++i) {
                // DPRINTF("  checking node '%s'", i->c_str());
                if (m_map.end() == m_map.find(*i)) {
                        visited.insert(*i);
                        leaf_to_root.push_back(*i);
                } else {
                        remaining.insert(*i);
                }
        }
        ASSERT(visited.size() > 0, "No leaf nodes?  Cyclical dependency");

        // short-circuit (all leaf nodes)
        if (0 == remaining.size())
                return;

        // now keep walking until all nodes have been processed
        for (long depth = 1; true; ++depth) {
                // DPRINTF("Depth = %ld", depth);

                // find all nodes that have this depth.  That means all of
                //   their children must already be in the visited set
                VecString nuke;
                for (SetString::const_iterator i = remaining.begin();
                     i != remaining.end(); ++i) {
                        if (visited.end() != visited.find(*i)) {
                                continue;       // already in the visited set
                        }

                        // okay how about everything it depends on?
                        map_set_t::const_iterator j = m_map.find(*i);
                        ASSERT(m_map.end() != j,
                            "not a leaf, must have set! '%s'", i->c_str());
                        const SetString * set = j->second;
                        ASSERT(set, "null set in map?");

                        bool all_children_visited = true;
                        for (SetString::const_iterator k = set->begin();
                             k != set->end(); ++k) {
                                if (visited.end() == visited.find(*k)) {
                                        all_children_visited = false;
                                        break;
                                }
                        }

                        if (!all_children_visited)
                                continue;       // skip this one

                        // okay, this node matches this depth
                        visited.insert(*i);
                        nuke.push_back(*i);
                        leaf_to_root.push_back(*i);
                }
                ASSERT(nuke.size() > 0, "cyclical dependency?");

                // nuke everything we pulled out at this depth
                for (VecString::iterator i = nuke.begin(); i != nuke.end(); ++i)
                {
                        remaining.erase(remaining.find(*i));
                }

                if (0 == remaining.size())
                        break;          // all done!
        }
}



SetString *
DagImpl::getSet
(
IN const char * node
)
{
        ASSERT(node, "null node in getSet()");

        map_set_t::iterator i = m_map.find(node);
        if (m_map.end() == i) {
                smart_ptr<SetString> set = new SetString;
                ASSERT(set, "out of memory");
                m_map[node] = set;
                return set;
        } else {
                return i->second;
        }
}



////////////////////////////////////////////////////////////////////////////////
//
//      public API
//
////////////////////////////////////////////////////////////////////////////////

smart_ptr<DAG>
DAG::create
(
void
)
{
        smart_ptr<DagImpl> local = new DagImpl;
        ASSERT(local, "out of memory");

        local->initialize();

        return local;
}



};      // graph namespace