OrderTree Class Reference

#include <ordertree.h>

Classes
class	DFSVotingVisitor
	Depth First Search visitor of tree where vertex visitations populate child_majority_marching_orders. More...
struct	OrderVertex
	Graph vertices' definition. More...
class	OrderVertexWriter
	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. More...
Public Member Functions
	OrderTree (const char kLogCategoryName, const char kSharedMemName, const char *kTraitorSetName)
	Constructor.
	~OrderTree ()
	Destructor.
void	PrintTree (const char *outfile) const
	Serialize the tree to Graphviz DOT file format.
int	Add (const LocalOrder kOrderToAdd)
	Add an Order to the tree. The Order's communication_path is used as the insertion key.
unsigned int	NodeCount () const
	The number of nodes present in the tree.
unsigned int	EdgeCount () const
	The number of edges present in the tree.
MarchingOrders::type	FinalizeOrders ()
	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.
Private Types
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, OrderVertex >	OrderGraphType
	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.
typedef boost::graph_traits < OrderGraphType > ::vertex_descriptor	OrderNodeIDType
	Another underlying graph related type, this one provides an identifier for vertices.
typedef boost::graph_traits < OrderGraphType > ::adjacency_iterator	OrderNodeIteratorType
	Another underlying graph related type, this one provides an iterator for traversing the graph.
Private Member Functions
int	Add (const OrderNodeIDType kParentNodeID, const LocalOrder kOrderToAdd, bool traitor_in_path)
	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.
bool	PrefixMatches (const LocalOrder left_order, const LocalOrder right_order) const
	Check if left_order's entire communication_path is a prefix of right_order's communication_path. If it is, return TRUE, FALSE otherwise.
bool	TraitorSetContains (const unsigned int kGeneralID) const
	Check the traitor_set_ for the provided argument.
OrderNodeIDType	AddVertex (const OrderNodeIDType parent_node_id, const LocalOrder kChildOrder, const MarchingOrders::type kMarchingOrders, const bool kCommPathContainsTraitor)
	Add a 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.
Private Attributes
log4cpp::Category &	log_
	Debug logger reference.
OrderGraphType *	order_tree_
	Reference to the underlying tree.
OrderNodeIDType	root_node_id_
	Root node's unique identifier.
SharedMemoryUIntSet *	traitor_set_
	Reference to shared memory's traitor set.

Detailed Description

An N-ary Tree of Orders.

Definition at line 26 of file ordertree.h.

Member Typedef Documentation

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, OrderVertex> OrderTree::OrderGraphType [private]

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>

Definition at line 132 of file ordertree.h.

typedef boost::graph_traits<OrderGraphType>::vertex_descriptor OrderTree::OrderNodeIDType [private]

Another underlying graph related type, this one provides an identifier for vertices.

Definition at line 139 of file ordertree.h.

typedef boost::graph_traits<OrderGraphType>::adjacency_iterator OrderTree::OrderNodeIteratorType [private]

Another underlying graph related type, this one provides an iterator for traversing the graph.

Definition at line 146 of file ordertree.h.

Constructor & Destructor Documentation

OrderTree::OrderTree	(	const char *	kLogCategoryName,
		const char *	kSharedMemName,
		const char *	kTraitorSetName
	)

Constructor.

Parameters:

	kLogCategoryName	Debugging name for logger endpoint
	kSharedMemName	Shared memory name (used to find traitor set)
	kTraitorSetName	Traitor set, located in shared memory

Definition at line 187 of file ordertree.cpp.

OrderTree::~OrderTree ( )

Destructor.

Definition at line 206 of file ordertree.cpp.

Member Function Documentation

int OrderTree::Add	(	const OrderNodeIDType	kParentNodeID,
		const LocalOrder	kOrderToAdd,
		bool	traitor_in_path
	)			`[private]`

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.

Parameters:

	kParentNodeID	Keeps track of the current vertex's parent in the tree
	kOrderToAdd	Order to add to the tree, since we're passing by reference the stack overhead is minimal.
	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.

Returns:: The depth at which the kOrderToAdd was inserted.

Definition at line 345 of file ordertree.cpp.

Here is the call graph for this function:

int OrderTree::Add ( const LocalOrder kOrderToAdd )

Add an Order to the tree. The Order's communication_path is used as the insertion key.

Parameters:

kOrderToAdd

Order to add to the tree

Returns:: Depth at which the Order was added

Definition at line 272 of file ordertree.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

OrderTree::OrderNodeIDType OrderTree::AddVertex	(	const OrderNodeIDType	parent_node_id,
		const LocalOrder	kChildOrder,
		const MarchingOrders::type	kMarchingOrders,
		const bool	kCommPathContainsTraitor
	)			`[private]`

Add a 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.

Parameters:

	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.
	kChildOrder	Place this value in the newly created vertex's local_order field
	kMarchingOrders	Place this value in the newly created vertex's child_majority_marching_orders field
	kCommPathContainsTraitor	Place this value in the newly created vertex's comm_path_contains_traitor field

Returns:: Newly created vertex's unique identifier

Definition at line 243 of file ordertree.cpp.

Here is the caller graph for this function:

unsigned int OrderTree::EdgeCount ( ) const

The number of edges present in the tree.

Returns:: Edge count

Definition at line 235 of file ordertree.cpp.

MarchingOrders::type OrderTree::FinalizeOrders ( )

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.

Returns:: 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.

Definition at line 213 of file ordertree.cpp.

Here is the caller graph for this function:

unsigned int OrderTree::NodeCount ( ) const

The number of nodes present in the tree.

Returns:: Node count

Definition at line 239 of file ordertree.cpp.

Here is the caller graph for this function:

bool OrderTree::PrefixMatches	(	const LocalOrder	left_order,
		const LocalOrder	right_order
	)			const `[private]`

Check if left_order's entire communication_path is a prefix of right_order's communication_path. If it is, return TRUE, FALSE otherwise.

Parameters:

	left_order	Order to check entire communication_path
	right_order	Order to check prefix

Returns:: TRUE if prefix matches, FALSE otherwise

Definition at line 323 of file ordertree.cpp.

Here is the caller graph for this function:

void OrderTree::PrintTree ( const char * outfile ) const

Serialize the tree to Graphviz DOT file format.

Parameters:

outfile

The name of the file to write

Definition at line 228 of file ordertree.cpp.

Here is the caller graph for this function:

bool OrderTree::TraitorSetContains ( const unsigned int kGeneralID ) const [private]

Check the traitor_set_ for the provided argument.

Parameters:

kGeneralID

General's Unique ID to search traitor_set_ for

Returns:: TRUE if found, FALSE otherwise

Definition at line 309 of file ordertree.cpp.

Here is the caller graph for this function:

Member Data Documentation

log4cpp::Category& OrderTree::log_ [private]

Debug logger reference.

Definition at line 217 of file ordertree.h.

OrderGraphType* OrderTree::order_tree_ [private]

Reference to the underlying tree.

Definition at line 222 of file ordertree.h.

OrderNodeIDType OrderTree::root_node_id_ [private]

Root node's unique identifier.

Definition at line 227 of file ordertree.h.

SharedMemoryUIntSet* OrderTree::traitor_set_ [private]

Reference to shared memory's traitor set.

Definition at line 232 of file ordertree.h.

The documentation for this class was generated from the following files:

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

OrderTree Class Reference

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation