/home/serif/byzantine_generals/src/ordertree.h

Go to the documentation of this file.

/**
 * @file ordertree.h
 * @author Reshen Amin <reshen@zensrc.com>
 *
 * @brief Contains the class definition for @ref OrderTree
 *
 * @license Byzantine Generals Problem Coding Sample.<br>
 * Copyright (C) 2010  Reshen Amin.<br>
 * See @ref license_sec for details.<br>
 */

#ifndef SRC_ORDERTREE_H_
#define SRC_ORDERTREE_H_

#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

#include <log4cpp/Category.hh>

#include "order.h"

/**
 * @brief  An N-ary Tree of @ref Order "Orders"
 */
class OrderTree {
    public:
        /**
         * @brief  Constructor
         *
         * @param kLogCategoryName Debugging name for logger endpoint
         * @param kSharedMemName Shared memory name (used to find traitor set)
         * @param kTraitorSetName Traitor set, located in shared memory
         */
        OrderTree(const char* kLogCategoryName,
                  const char* kSharedMemName,
                  const char* kTraitorSetName);

        /**
         * @brief  Destructor
         */
        ~OrderTree();

        /**
         * @brief  Serialize the tree to Graphviz DOT file format
         *
         * @param outfile The name of the file to write
         */
        void PrintTree(const char* outfile) const;

        /**
         * @brief  Add an @ref Order to the tree.  The Order's
         * communication_path is used as the insertion key.
         *
         * @param kOrderToAdd Order to add to the tree
         *
         * @return  Depth at which the Order was added
         */
        int Add(const LocalOrder kOrderToAdd);

        /**
         * @brief  The number of nodes present in the tree
         *
         * @return  Node count
         */
        unsigned int NodeCount() const;

        /**
         * @brief  The number of edges present in the tree
         *
         * @return  Edge count
         */
        unsigned int EdgeCount() const;

        /**
         * @brief  Roll up output orders for the nodes in the tree.
         * This function performs a Depth First Search (DFS) on the tree, and
         * for leaf nodes, input orders are copied to output orders.  For
         * non-lef nodes, the output orders are set to the majority of child
         * node output orders.  In this way, parent's output orders
         * reflect what the majority of their children output orders indicated.
         * If a tie occurs during voting, MarchingOrders::kAttack is chosen.
         *
         * @return  The root's output marching order after the output orders
         * have rolled up the tree.  This represents the final decision for this
         * general to attack or retreat.
         */
        MarchingOrders::type FinalizeOrders();

    private:
        /**
         * @brief  Graph vertices' definition
         */
        struct OrderVertex {
            /**
             * @brief  Reference to the locally owned (non-shared) @ref Order
             */
            LocalOrder local_order;

            /**
             * @brief  This field is where the output of the @ref FinalizeOrders
             * is stored, the majority of child vertices @ref local_order
             * "local_orders'" marching orders. If this vertex is a leaf node,
             * the @ref local_order "local_order's" marching orders are copied
             * to this field directly.
             */
            MarchingOrders::type child_majority_marching_orders;

            /**
             * @brief  Used in vertex coloring when generating output, indicates
             * if the path that includes this vertex has passed through a
             * Traitor General's hands.
             */
            bool comm_path_contains_traitor;
        };

        /**
         * @brief  Graph data structure definition.
         * VertexList uses vecS (std::vector) because of the lower per-vertex
         * space overhead; the compromise is that add_vertex has often-decent
         * performance (except in the case of having to reallocate the whole
         * graph).  OutEdgeList uses vecS (std::vector) because it has the
         * lowest amount of space overhead per edge and the often-fastest
         * performance for add_edge(). Directed since we are creating a tree,
         * and the vertex type is provided.
         *
         * For details, see <http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/using_adjacency_list.html#sec:choosing-graph-type>
         */
        typedef boost::adjacency_list<boost::vecS,
                                      boost::vecS,
                                      boost::directedS,
                                      OrderVertex> OrderGraphType;

        /**
         * @brief  Another underlying graph related type, this one provides an
         * identifier for vertices.
         */
        typedef boost::graph_traits<OrderGraphType>::vertex_descriptor
            OrderNodeIDType;

        /**
         * @brief  Another underlying graph related type, this one provides an
         * iterator for traversing the graph.
         */
        typedef boost::graph_traits<OrderGraphType>::adjacency_iterator
            OrderNodeIteratorType;

        /**
         * @brief  Recursive function that adds the provided order to the tree
         * in the proper position.  The function walks down the tree using
         * the LocalOrder's embedded communication_path to know which path to
         * traverse.
         *
         * @param kParentNodeID Keeps track of the current vertex's parent in
         * the tree
         * @param kOrderToAdd Order to add to the tree, since we're passing by
         * reference the stack overhead is minimal.
         * @param traitor_in_path Once we find a traitor general in the path, we
         * can toggle this to TRUE such that we don't have to continue checking
         * since all children along that path are suspect.  Otherwise, no
         * traitors have been found, so this remains FALSE.
         *
         * @return  The depth at which the kOrderToAdd was inserted.
         */
        int Add(const OrderNodeIDType kParentNodeID,
                const LocalOrder kOrderToAdd,
                bool traitor_in_path);

        /**
         * @brief  Check if left_order's entire communication_path is a prefix
         * of right_order's communication_path.  If it is, return TRUE, FALSE
         * otherwise.
         *
         * @param left_order Order to check entire communication_path
         * @param right_order Order to check prefix
         *
         * @return   TRUE if prefix matches, FALSE otherwise
         */
        bool PrefixMatches(const LocalOrder left_order,
                           const LocalOrder right_order) const;

        /**
         * @brief  Check the @ref traitor_set_ for the provided argument
         *
         * @param kGeneralID General's Unique ID to search @ref traitor_set_ for
         *
         * @return   TRUE if found, FALSE otherwise
         */
        bool TraitorSetContains(const unsigned int kGeneralID) const;

        /**
         * @brief  Add a @ref OrderVertex "vertex" to the tree.  If the
         * parent_node_id is valid, then a directed edge is added between the
         * parent and the newly created vertex. The vertex is populated with the
         * other provided arugments.
         *
         * @param parent_node_id Parent node identifier to add as source of
         * edge, if valid.  Otherwise, an edge is not created between the newly
         * created vertex and any other vertex.
         * @param kChildOrder Place this value in the newly created vertex's
         * local_order field
         * @param kMarchingOrders Place this value in the newly created vertex's
         * child_majority_marching_orders field
         * @param kCommPathContainsTraitor  Place this value in the newly
         * created vertex's comm_path_contains_traitor field
         *
         * @return   Newly created vertex's unique identifier
         */
        OrderNodeIDType AddVertex(const OrderNodeIDType parent_node_id,
                                  const LocalOrder kChildOrder,
                                  const MarchingOrders::type kMarchingOrders,
                                  const bool kCommPathContainsTraitor);

        /**
         * @brief  Debug logger reference
         */
        log4cpp::Category& log_;

        /**
         * @brief  Reference to the underlying tree
         */
        OrderGraphType* order_tree_;

        /**
         * @brief  Root node's unique identifier
         */
        OrderNodeIDType root_node_id_;

        /**
         * @brief  Reference to shared memory's traitor set
         */
        SharedMemoryUIntSet* traitor_set_;

        /* Forward declare a few nested classes. We define them in the cpp file
         * to avoid including the nested class's definition in this enclosing
         * class, which make sense in this context since the definition is only
         * relevant to our implementation */

        /**
         * @brief  Traverse the tree and write out each vertex to a DOT output
         * file
         */
        class OrderVertexWriter;

        /**
         * @brief  Depth First Search visitor of tree where vertex visitations
         * populate child_majority_marching_orders
         */
        class DFSVotingVisitor;
};

#endif  // SRC_ORDERTREE_H_

---