View Class Reference

#include <View.hpp>

Inheritance diagram for View:

[legend]Collaboration diagram for View:

[legend]

---

Detailed Description

The View class represents a cross section through the hierarchy.

The view is a cross section through the hierarchy. This means, that there cannot be a node and one of its ancestors or descendants in the view at the same time.

Edges in the view

There is an edge between two view nodes if there is an edge between one of the descendants (in the underlying graph) of the hierarchy node corresponding to the first node, and one of the descendants (in the underlying graph) of the hierarchy node corresponding to the second node.

Internals

This implementation does not take into account how many edges exist between descendant nodes, or of any of the properties of the edges between descendant nodes, because it is currently not known what requirements exist here.

There is no pre-computed data improving the speed of expand or collapse operations. For this project, the ad hoc generation of the edges was considered to be superior as the most general approach. Methods improving expand or collapse speed often have drawbacks when it comes to the ability to alter the hierarchy or base graph, which was not desired for a first implementation. Later specialized view implementation can be implemented realizing these methods.

Currently, maps are used instead of hash maps for the mapping of hierarchy nodes to view nodes and vice versa. The reasoning behind this is that in a view, there are probably not so many nodes because of viewing limitations, thus the overhead of a hash_map will make access slower in most cases.

Public Member Functions
	View ()
	Empty constructor.
	View (Hierarchy *h, int init_mode=INIT_TOP, PropertyFacility *p=NULL)
	Constructor.
	View (const View &v)
	Copy Constructor.
virtual	~View ()
	Cleanup.
virtual void	node_id (Node n, NodeID id)
	Set the ID of a node and invoke an update message.
virtual void	edge_id (Edge e, EdgeID id)
	Set the ID of an edge and invoke an update message.
void	update (Subject *sub, long msg, Item item)
	Base graph / hierarchy update.
void	expand (Node node)
	Expand a node.
void	collapse (Node node)
	Collapse a node.
Node	hierarchy_node (const Node node) const
	Returns the hierarchy node corresponding to the given view node.
Node	view_node (const Node node) const
	Returns the view node corresponding to the given hierarchy node.
Hierarchy *	get_hierarchy () const
	Returns the underlying hierarchy.
void	set_hierarchy (Hierarchy *h, int init_mode=INIT_TOP)
	Set the underlying hierarchy.
Static Public Attributes
static const int	INIT_TOP = 1
	Used to init view to top view.
static const int	INIT_BOTTOM = 2
	Used to init view to bottom (completely expanded).
Private Member Functions
void	init (Hierarchy *h, PropertyFacility *p, int init_mode)
	Initialize View to "top view".
void	get_graph_childs (Node parent, std::vector< Node > *nlist, bool do_ignore_node, Node ignore_node, bool do_ignore_edge, Edge ignore_edge)
	Do a BFS down the hierarchy to get the bottom nodes of a parent.
void	add_node_edges (Node node, bool do_ignore_node, Node ignore_node, bool do_ignore_edge, Edge ignore_edge)
	Determine and add all edges of a view node, ignoring the given hierarchy node and edge if do_ignore_(node|edge) is set (thus can be used before they are actually deleted).
void	new_node_update (Subject *sub, Node node)
	Base graph / hierarchy new node update.
void	del_node_update (Subject *sub, Node node)
	Base graph / hierarchy del node update.
void	new_edge_update (Subject *sub, Edge edge)
	Base graph / hierarchy new edge update.
void	del_edge_update (Subject *sub, Edge edge)
	Base graph / hierarchy del edge update.
Private Attributes
std::map< Node, Node > *	hierarchynodes
	Maps view nodes to hierarchy nodes.
std::map< Node, Node > *	viewnodes
	Maps hierarchy nodes to view nodes.
Hierarchy *	hierarchy
	The underlying graph.
bool	own_hierarchy
	Documenting if the hierarchy was created (and should be deleted) by the View.

---

Constructor & Destructor Documentation

View (   )

Empty constructor. This will create e new Hierarchy as a base of this view, which will be deleted automatically when the view is deleted.

View (  Hierarchy *  h, int  init_mode = INIT_TOP, PropertyFacility *  p = NULL )

Constructor. Parameters: h  The underlying hierarchy p  The property facility (if NULL, uses the PropertyFacility of the hierarchy) init_mode  The initialization mode of the view (top, bottom, ...)

View (  const View &  v  )

Copy Constructor. This never creates an own hierarchy. It will always be a view on the hierarchy of the cloned view. Parameters: v  The view to copy

~View (   )  [virtual]

Cleanup.

---

Member Function Documentation

void add_node_edges (  Node  node, bool  do_ignore_node, Node  ignore_node, bool  do_ignore_edge, Edge  ignore_edge )  [private]

Determine and add all edges of a view node, ignoring the given hierarchy node and edge if do_ignore_(node|edge) is set (thus can be used before they are actually deleted). This is done as follows: Get corresponding hierarchy node: O( log(#view_nodes) ) BFS in the hierarchy for leaves via get_graph_childs(): O( #hierarchy_nodes ) Get adjacent edges of the leaves: O( #base_graph_edges * log(#base_graph_nodes) ) For each distinct adjacent node, get the ancestor in the hierarchy that is currently in the view (and thus has to be adjacent to the given view node): O( #base_graph_nodes * hierarchy_height * log(#view_nodes) ) Add each distinct source and target of the view node to the view: O( #view_nodes ) Summarized complexity: O( #hierarchy_nodes + #base_graph_edges * log(#base_graph_nodes) + #base_graph_nodes * hierarchy_height * log(#view_nodes) ) Note that the log factors results from the use of std::map. Parameters: node  The node whose edges are to be determined do_ignore_node  If true, ignore_node contains a valid node ignore_node  If do_ignore_node is true, this node will be skipped in the BFS do_ignore_edge  If true, ignore_edge contains a valid edge ignore_edge  If do_ignore_edge is true, this edge will be skipped in the BFS

void collapse (  Node  node  )

Collapse a node. This will first look for the parent node of the given node. Then, all the children of the parent node are taken out of the view, and the parent node is put into the view. Complexity (without recursion of step 1): O( #view_edges * log(#view_nodes) + #view_nodes * log(#view_nodes) ) If we only look at the changes in the view which have to be done (which cannot be omitted), we can constrain the complexity further. Let #dve be the number of edges which we have delete in the view, and #dne the number of nodes that have to be deleted. Then the complexity can be summarized as follows: Complexity (without recursion of step 1): O( #dve * lov(#view_nodes) + #dne * log(#dne) ) (The log factors in these complexities result from the use of std::set) Internals The following steps are done when collapsing a node: 1) To be able to collapse a node, all children of it's parent have to be in the view. Thus, the first step is to recursively collapse all children which are currently not in the view. 2) For each child of the parent of the node to collapse, all incoming and outgoing edges are considered and all adjacent nodes are inserted into an incoming-edges-set and an outgoing-edges-set. 3) The children are deleted and the new edges are created using the two previously created sets.

void del_edge_update (  Subject *  sub, Edge  edge )  [private]

Base graph / hierarchy del edge update. If an edge in the hierarchy is deleted, and an ancestor of the edge's source is in view, it's edges have to be recalculated, and the target of the hierarchy's deleted edge has to be added to the view. Complexity: O( hierarchy_height * log(#view_nodes) + #view_edges + O(View::add_node_edges()) ) If an edge of the base graph is deleted, which might be the reason that an edge between two view nodes exist, a check has to be done if there is another base graph edge that induces the edge in the view. Complexity: O( hierarchy_height * log(#view_nodes) + O(View::get_graph_childs()) + (#graph_nodes + #graph_edges) * log(#graph_nodes) ) Parameters: sub  The subject sending the message edge  The updated edge

void del_node_update (  Subject *  sub, Node  node )  [private]

Base graph / hierarchy del node update. If a hierarchy node was deleted, and the node was in the view, it is expanded. If it can't be expanded, it is deleted. (Complexity: See expand() operation). If a hierarchy node was deleted which was not in the view, but an ancestor of it was, then the edges of the ancestor in the view have to be deleted and recalculated (add_node_edges()). Also, as the childs of the deleted node are now without parent, they have to be added to the view. Complexity: O( hierarchy_height * log(#view_nodes) + #view_edges + O(add_node_edges()) + log(#view_nodes) * #children(node) ) Updates from the base graph are not used, because an update from the Hierarchy will follow. Parameters: sub  The subject sending the message node  The updated node

void edge_id (  Edge  e, EdgeID  id )  [virtual]

Set the ID of an edge and invoke an update message. See ConstGraph::edge_id(e, id) Parameters: e  The edge id  The new id Reimplemented from ConstGraph.

void expand (  Node  node  )

Expand a node. This will take the given node out of the view and put all it's children (in the hierarchy) into the view. Complexity: O( #base_graph_edges * log(#base_graph_nodes) + #base_graph_nodes * hierarchy_height * log(#view_nodes) ) Internals (The log factors result from the usage of std::set's) // PSEUDOCODE foreach outgoing edge e of old view node in the hierarchy view->add( e->target() ) endforeach delete(old view node) foreach new view node n // Find all nodes in the graph for which n is an ancestor by going down // in the hierarchy // Worst case complexity: O( #base_graph_nodes ) graphnodes = hierarchy->bfs_downwards( n ) // Find all adjacent base graph nodes to all those descendants and store // them in a map // Worst case complexity: O( #base_graph_edges * log(#base_graph_nodes) ) new_leaves = graph->get_adjacent_nodes( graphnodes ) // Of the base graph nodes found in the previous step, find all ancestors // which are in the view // Worst case complexity: O( #base_graph_nodes * hierarchy_height * log(#view_nodes) ) adjacent_nodes = hierarchy->find_predecessors_in_view( new_leaves ) // Create edges for all found adjacent nodes // Worst case complexity: O( #view_nodes ) view->create_edges( n, adjacent_nodes ) endforeach

void get_graph_childs (  Node  parent, std::vector< Node > *  nlist, bool  do_ignore_node, Node  ignore_node, bool  do_ignore_edge, Edge  ignore_edge )  [private]

Do a BFS down the hierarchy to get the bottom nodes of a parent. Worst case complexity (Hierarchy::graph_node() is assumed to be constant time): O( #hierarchy_nodes ) Parameters: parent  Parent node (hierarchy node) nlist  Node list, will contain the resulting graph nodes (unordered) do_ignore_node  If true, ignore_node contains a valid node ignore_node  If do_ignore_node is true, this node will be skipped in the BFS do_ignore_edge  If true, ignore_edge contains a valid edge ignore_edge  If do_ignore_edge is true, this edge will be skipped in the BFS

Hierarchy * get_hierarchy (   )  const

Returns the underlying hierarchy.

Node hierarchy_node (  const Node  node  )  const

Returns the hierarchy node corresponding to the given view node. Complexity (std::map): O( log(#view_nodes) ) Returns: Returns the node in the hierarchy for the given view node

void init (  Hierarchy *  h, PropertyFacility *  p, int  init_mode )  [private]

Initialize View to "top view". Currently, two initialization modes are supported: View::INIT_TOP : The new View consists of the top node(s) of the hierarchy View::INIT_BOTTOM : The new View consists of the base graph nodes Parameters: h  The underlying hierarchy p  The property facility (if NULL, uses the PropertyFacility of the hierarchy) init_mode  The initialization mode of the view (top, bottom, ...)

void new_edge_update (  Subject *  sub, Edge  edge )  [private]

Base graph / hierarchy new edge update. If a new edge was added to the hierarchy, and some predecessor of the new edge's source is in the view, and some ancestor(s) of the target of the new edge (or the target itself) are in the view too, the view-neighborhood of the target's ancestor(s) has to be moved to the predecessor in the view and the target's ancestor(s) have to be removed from the view. Complexity: O( #hierarchy_nodes * log(#view_nodes) + hierarchy_height * #view_edges * log(#view_nodes) ) If a new edge was added to the base graph, a check is done if there is already an edge between the ancestor nodes in the view. If not, it is added. Complexity: O( hierarchy_height + #view_edges ) Parameters: sub  The subject sending the message edge  The updated edge

void new_node_update (  Subject *  sub, Node  node )  [private]

Base graph / hierarchy new node update. If a new node was added to the hierarchy, a new node is inserted in the view via priv_new_node, and viewnodes and hierarchynodes maps are updated. Complexity: O( O(ConstGraph::priv_new_node) + log(#view_nodes) ) If a new node was added to the graph, nothing is done, because it will be added to the hierarchy and we will get the update from there. Parameters: sub  The subject sending the message node  The updated node

void node_id (  Node  n, NodeID  id )  [virtual]

Set the ID of a node and invoke an update message. See ConstGraph::node_id(n, id) Parameters: n  The node id  The new id Reimplemented from ConstGraph.

void set_hierarchy (  Hierarchy *  h, int  init_mode = INIT_TOP )

Set the underlying hierarchy. This sets the Hierarchy on which the View is built. Before it does this, it unregisteres itself as an observer from the previous underlying Hierarchy (which is deleted if it was created by the View), and deletes all it's nodes and edges. A fresh View is then built on the new underlying Hierarchy. Parameters: h  The hierarchy to use now as the underlying hierarchy init_mode  The initialization mode of the view (top, bottom, ...)

void update (  Subject *  sub, long  msg, Item  item )  [virtual]

Base graph / hierarchy update. Parameters: sub  The subject sending the message msg  The message item  The item of the message Implements Observer.

Node view_node (  const Node  node  )  const

Returns the view node corresponding to the given hierarchy node. Complexity (std::map): O( log(#view_nodes) ) Returns: Returns the node in the view for the given hierarchy node

---

Field Documentation

Hierarchy* hierarchy [private]

The underlying graph.

std::map<Node, Node>* hierarchynodes [private]

Maps view nodes to hierarchy nodes.

const int INIT_BOTTOM = 2 [static]

Used to init view to bottom (completely expanded).

const int INIT_TOP = 1 [static]

Used to init view to top view.

bool own_hierarchy [private]

Documenting if the hierarchy was created (and should be deleted) by the View.

std::map<Node, Node>* viewnodes [private]

Maps hierarchy nodes to view nodes.

---