/home/serif/byzantine_generals/src/ordertree.cpp

Go to the documentation of this file.

/**
 * @file ordertree.cpp
 * @author Reshen Amin <reshen@zensrc.com>
 *
 * @brief Contains the class declarations for the public class @ref OrderTree,
 * and private classes @ref OrderTree::DFSVotingVisitor and @ref
 * OrderTree::OrderVertexWriter
 *
 * @license Byzantine Generals Problem Coding Sample.<br>
 * Copyright (C) 2010  Reshen Amin.<br>
 * See @ref license_sec for details.<br>
 */

#include "ordertree.h"

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/containers/string.hpp>

#include <log4cpp/Category.hh>
#include <algorithm>
#include <string>

/**
 * @brief  Depth First Search visitor of tree where vertex visitations
 * populate child_majority_marching_orders
 */
class OrderTree::DFSVotingVisitor : public boost::default_dfs_visitor {
    public:
        /**
         * @brief  Constructor
         *
         * @param tree Tree to visit
         */
        explicit DFSVotingVisitor(OrderGraphType *tree): tree_(tree) {}

        /**
         * @brief  From Boost's documentation: "is invoked on a vertex
         * after all of its out edges have been added to the search tree
         * and all of the adjacent vertices have been discovered (but
         * before their out-edges have been examined)."
         *
         * @param u Vertex to visit
         * @param g Graph from which Vertex came
         */
        template < typename Vertex, typename Graph >
            void finish_vertex(Vertex u, const Graph & g) {
                /* majority (children's orders) */

                int attackVotes = 0;
                int retreatVotes = 0;

                OrderVertex* order_vertex = &((*tree_)[u]);

                /* Setup iterators to find vertices (our out edges
                 * point to adjacent vertices). In the context of a
                 * tree, we're finding child nodes. */
                OrderNodeIteratorType vi, vend;
                tie(vi, vend) = adjacent_vertices(u, g);

                if (vi == vend) {
                    /* No out edges - this vertex is a leaf node */

                    const LocalOrder local_order = order_vertex->local_order;

                    const MarchingOrders::type leaf_orders =
                        (*local_order).marching_orders;

                    assert(leaf_orders == MarchingOrders::kAttack ||
                           leaf_orders == MarchingOrders::kRetreat);

                    /* Received order -> child_majority_marching_orders */
                    leaf_orders == MarchingOrders::kAttack ?
                        ++attackVotes :
                        ++retreatVotes;
                } else {
                    /* This vertex has children. Tally their
                     * child_majority_marching_orders. */

                    for (; vi != vend; ++vi) {
                        OrderVertex child_order_vertex = g[*vi];

                        const MarchingOrders::type child_orders =
                            child_order_vertex.child_majority_marching_orders;

                        assert(child_orders == MarchingOrders::kAttack ||
                               child_orders == MarchingOrders::kRetreat);

                        child_orders == MarchingOrders::kAttack ?
                            ++attackVotes :
                            ++retreatVotes;
                    }
                }

                if (attackVotes < retreatVotes) {
                    order_vertex->child_majority_marching_orders =
                        MarchingOrders::kRetreat;
                } else {
                    /* Both when we have more attack votes and when we have a
                     * tie amongst our children, we pick an arbitrary
                     * tie-breaker : attacking.  It isn't important what the tie
                     * breaker behavior is, so long as its consistent amongst
                     * all of the generals. */
                    order_vertex->child_majority_marching_orders =
                        MarchingOrders::kAttack;
                }
            }

    private:
        /**
         * @brief  Reference to the tree being visited
         */
        OrderGraphType *tree_;
};

/**
 * @brief  A type of property writer that writes out vertices.  We use this
 * class to write out our graph in graphviz/dot format with a few customizations
 */
class OrderTree::OrderVertexWriter {
    public:
        /**
         * @brief  Constructor
         *
         * @param g Graph to output
         */
        explicit OrderVertexWriter(const OrderGraphType &g)
            : writer_order_tree(g) {}

        /**
         * @brief  Destructor
         */
        ~OrderVertexWriter() {}

        /**
         * @brief  Functor for writing out each vertex's properties to DOT
         * format
         *
         * @param out Stream to write to
         * @param u Vertex to serialize
         */
        template <class Vertex>
            void operator() (std::ostream &out, Vertex u) {
                namespace bi = boost::interprocess;

                const OrderVertex* order_vertex = &(writer_order_tree[u]);

                const LocalOrder local_order = order_vertex->local_order;

                const MarchingOrders::type marching_orders =
                    (*local_order).marching_orders;

                const bi::string kCommunicationPath =
                    (*local_order).CommunicationPathToString();

                const bi::string kMarchingOrder =
                    Order::MarchingOrderTypeToString(marching_orders);

                const bi::string kChildMarchingOrder =
                    Order::MarchingOrderTypeToString(
                            order_vertex->child_majority_marching_orders);

                const bool kTraitorInPath =
                    order_vertex->comm_path_contains_traitor;

                /* Nodes get colored based a traitor being present in the
                 * communication path.  Pink indicates a traitor was present,
                 * so the order is suspect. */
                const bi::string fillcolor =
                    kTraitorInPath ? "pink" : "white";

                out << "[label=\"" << kCommunicationPath << "\\n"
                    << "Rx: " << kMarchingOrder << "\\n"
                    << "Vote: " << kChildMarchingOrder << "\" "
                    << "fillcolor=\"" << fillcolor << "\" "
                    << "style=filled"
                    << "]";
            }


    private:
        /**
         * @brief  Reference to graph we're writing
         */
        const OrderGraphType &writer_order_tree;
};

OrderTree::OrderTree(const char* kLogCategoryName,
                     const char* kSharedMemName,
                     const char* kTraitorSetName)
    : log_(log4cpp::Category::getInstance(kLogCategoryName)) {
    namespace bi = boost::interprocess;

    root_node_id_ = boost::graph_traits<OrderGraphType>::null_vertex();

    /* Create our received order tree (empty grpah object with zero
     * vertices and zero edges */
    order_tree_ = new OrderGraphType();
    assert(order_tree_ != NULL);

    bi::managed_shared_memory segment(bi::open_only, kSharedMemName);

    traitor_set_ = segment.find<SharedMemoryUIntSet>(kTraitorSetName).first;
    assert(traitor_set_ != NULL);
}

OrderTree::~OrderTree() {
    if (order_tree_ != NULL) {
        delete order_tree_;
        order_tree_ = NULL;
    }
}

MarchingOrders::type OrderTree::FinalizeOrders() {
    assert(root_node_id_ != boost::graph_traits<OrderGraphType>::null_vertex());

    /* Roll up (vote on) orders */
    DFSVotingVisitor vis(order_tree_);
    depth_first_search(*order_tree_, visitor(vis));

    /* Safety check to ensure that the initial order I was given was what
     * ended up rolling up the tree */
    const OrderVertex* root_order_vertex = &((*order_tree_)[root_node_id_]);
    const LocalOrder root_local_order = root_order_vertex->local_order;

    return root_order_vertex->child_majority_marching_orders;
}

void OrderTree::PrintTree(const char* outfile) const {
    log_.infoStream() << "Writing " << std::string(outfile);

    std::ofstream ofs(outfile);
    write_graphviz(ofs, *order_tree_, OrderVertexWriter(*order_tree_));
}

unsigned int OrderTree::EdgeCount() const {
    return num_edges(*order_tree_);
}

unsigned int OrderTree::NodeCount() const {
    return num_vertices(*order_tree_);
}

OrderTree::OrderNodeIDType OrderTree::AddVertex(
        const OrderNodeIDType parent_node_id,
        const LocalOrder kChildOrder,
        const MarchingOrders::type kMarchingOrders,
        const bool kCommPathContainsTraitor) {
    /* Safety check: valid tree  */
    assert(order_tree_ != NULL);

    /* Create new vertex in the underlying graph */
    const OrderNodeIDType child_node_id = add_vertex(*order_tree_);
    assert(child_node_id != boost::graph_traits<OrderGraphType>::null_vertex());

    /* Translate vertex identifier to vertex object */
    OrderVertex* child_vertex = &((*order_tree_)[child_node_id]);

    /* Populate the vertex object */
    child_vertex->local_order = kChildOrder;
    child_vertex->child_majority_marching_orders = kMarchingOrders;
    child_vertex->comm_path_contains_traitor = kCommPathContainsTraitor;

    if (parent_node_id != boost::graph_traits<OrderGraphType>::null_vertex()) {
        /* We're adding a child to an existing parent */
        add_edge(parent_node_id, child_node_id, *order_tree_);
    }
    /* else: We're adding a child without a parent (root node) */

    return child_node_id;
}

int OrderTree::Add(const LocalOrder kOrderToAdd) {
    /* Safety check: valid tree  */
    assert(order_tree_ != NULL);

    if (NodeCount() > 0) {
        /* Adding a child (Non-root) case */

        /* Safety checks: valid communication path and root node */
        assert((*kOrderToAdd).communication_path.size() > 1);
        assert(root_node_id_ !=
               boost::graph_traits<OrderGraphType>::null_vertex());

        return Add(root_node_id_,
                   kOrderToAdd,
                   ((*order_tree_)[root_node_id_]).comm_path_contains_traitor);
    }

    /* Adding a root to the tree */

    /* Safety check: valid communication path */
    assert((*kOrderToAdd).communication_path.size() == 1);

    const unsigned int kLastGeneral = (*kOrderToAdd).communication_path.back();
    bool comm_path_contains_traitor = TraitorSetContains(kLastGeneral);

    /* Safety check: we haven't already created a root node */
    assert(root_node_id_ == boost::graph_traits<OrderGraphType>::null_vertex());

    root_node_id_ =
        AddVertex(boost::graph_traits<OrderGraphType>::null_vertex(),
                  kOrderToAdd,
                  MarchingOrders::kInvalid,
                  comm_path_contains_traitor);

    return 0;
}

bool OrderTree::TraitorSetContains(const unsigned int kGeneralID) const {
    bool contains_traitor = false;

    /* Safety check traitor set */
    assert(traitor_set_ != NULL);

    /* Search underlying traitor_set_ for the provided General */
    if (traitor_set_->find(kGeneralID) != traitor_set_->end()) {
        contains_traitor = true;
    }

    return contains_traitor;
}

bool OrderTree::PrefixMatches(const LocalOrder left_order,
                              const LocalOrder right_order) const {
    /* Check if left_order's communication_path is a prefix of
     * right_order's communication_path.  To accomplish this, we use STL's
     * equal algorithm:
     *
     * "equal returns true if and only if for every iterator i in [first1,
     *  last1), *i == *(first2 + (i - first1))"
     */

    SharedMemoryUIntList::const_iterator first1 =
        (*left_order).communication_path.begin();

    SharedMemoryUIntList::const_iterator last1  =
        (*left_order).communication_path.end();

    SharedMemoryUIntList::const_iterator first2 =
        (*right_order).communication_path.begin();

    return equal(first1, last1, first2);
}

int OrderTree::Add(const OrderNodeIDType kParentNodeID,
                   const LocalOrder kOrderToAdd,
                   bool traitor_in_path) {
    const LocalOrder kParentOrder = (*order_tree_)[kParentNodeID].local_order;

    if (PrefixMatches(kParentOrder, kOrderToAdd) == true &&
            ((*kOrderToAdd).communication_path.size() - 1) ==
            ((*kParentOrder).communication_path.size())) {
        /* Found kOrderToAdd's parent (current kParentNodeID), adding
         * kOrderToAdd as child */

        if (traitor_in_path == false) {
            /* If we haven't already been told there is a traitor in this path,
             * check the next general in the communication_path */
            const unsigned int kLastGeneral =
                (*kOrderToAdd).communication_path.back();
            traitor_in_path = TraitorSetContains(kLastGeneral);
        }

        AddVertex(kParentNodeID,
                  kOrderToAdd,
                  MarchingOrders::kInvalid,
                  traitor_in_path);

        /* Base case, depth of 1 */
        return 1;
    } else {
        /* Search each of kParentNodeID's childrens' communication_paths to see
         * if any of them are prefixes of kOrderToAdd's communication_path.  If
         * so, we need to traverse down that path of the tree */

        /* adjacent_vertices returns an iterator-range providing access to the
         * vertices adjacent to vertex u in graph g. For example, if u -> v is
         * an edge in the graph, then v will be in this iterator-range. */

        OrderNodeIteratorType vi, vend;

        for (tie(vi, vend) = adjacent_vertices(kParentNodeID, *order_tree_);
                vi != vend;
                ++vi) {
            const LocalOrder child_node_order = (*order_tree_)[*vi].local_order;

            if (PrefixMatches(child_node_order, kOrderToAdd) == true) {
                /* Found a matching prefix in this child, this is the path we
                 * need to take */

                if (traitor_in_path == false) {
                    /* If we haven't already been told there is a traitor in
                     * this path, check the next general in the
                     * communication_path */
                    const unsigned int kLastGeneral =
                        (*child_node_order).communication_path.back();
                    traitor_in_path = TraitorSetContains(kLastGeneral);
                }

                /* Recurisve step, add 1 to depth and traverse down this path */
                return Add(*vi, kOrderToAdd, traitor_in_path) + 1;
            }
        }
    }

    /* We should only reach this point if by some coding error, we've attempted
     * to add a child to the tree and couldn't find the proper place for it.  We
     * try to provide as much debugging information as possible, then bail
     * out. */

    log_.errorStream()
        << "Unable to find where to insert: '"
        << (*kOrderToAdd).CommunicationPathToString()
        << "' creating error.dot.";
    PrintTree("error.dot");
    assert(false);

    /* We never reach here */
    return -1;
}

---