Hierarchy Class Reference

#include <Hierarchy.hpp>

Inheritance diagram for Hierarchy:

[legend]Collaboration diagram for Hierarchy:

[legend]

---

Detailed Description

The Hierarchy represents a hierarchy on the base graph.

The hierarchy is a tree (or a forest, see Internals), whose leaves correspond to the nodes of the underlying graph.

The edges of the underlying graph, though, are not included in the hierarchy (otherwise, it would not be a valid tree structure any more).

The edges in the Hierarchy class are top-down, that means: the source is the parent and the target is the child. (There was no special reason to do it either way, so the decision for this direction was made more or less randomly.)

The hierarchy is in fact not necessarily a tree, but a forest, there is no requirement of a single top node. We could not think of any reason why we should require this, so we decided that it would be better to leave this to the actual implementation. This means that all structures using the hierarchy should be prepared to work on a forest.

Internals

The hierarchy contains the underlying graph, this means that all leaves correspond to nodes in the underlying graph. Another method was discussed: it would be possible to omit the leaves in the hierarchy and instead provide the parents of view nodes with lists linking to their base graph children. There is a number of reasons why this was not done:

• A hierarchy with leaves one level atop the underlying graph containing lists linking to their children in the underlying graph is much more difficult to maintain.
• It is more consistent with the definition of the hierarchy as a tree on the graph when the leaves are included.
• It is difficult for the View if a view node could represents a node in the Hierarchy or in the base graph.
• There is not much to gain by omitting the leaves except less memory usage.

The hierarchy does not store any information which makes it easier for the view to collapse or expand nodes: It has no knowledge of the Views.

Public Member Functions
	Hierarchy ()
	Empty constructor.
	Hierarchy (ObservableGraph *g, PropertyFacility *p=NULL)
	Constructor.
	Hierarchy (const Hierarchy &h)
	Copy constructor.
virtual	~Hierarchy ()
	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 update.
Node	step (std::vector< Node >::const_iterator children_begin, std::vector< Node >::const_iterator children_end, NodeID id=NodeID(""))
	Add a hierarchical node to the hierarchy.
Node	step (std::vector< Node > *children, NodeID id=NodeID(""))
	Add a hierarchical node to the hierarchy (calls overloaded step()).
void	unstep (Node node)
	Delete a hierarchical node from the graph.
void	connect (Node node, Node parent)
	Connect a (parentless) hierarchical node to a parent (which can't be in the base graph).
void	disconnect (Node node)
	Disconnect a hierarchical node from its parent.
Node	hierarchy_node (const Node node) const
	Returns the hierarchy node corresponding to the given graph node.
Node	graph_node (const Node node) const
	Returns the graph node corresponding to the given hierarchy node.
ObservableGraph *	get_graph () const
	Returns the base graph of the Hierarchy.
void	set_graph (ObservableGraph *g)
	Sets the base graph of the Hierarchy.
Private Member Functions
void	init (ObservableGraph *g, PropertyFacility *p)
	Initialize Hierarchy.
void	del_node_update (Node node)
	Base graph del node update.
Private Attributes
std::hash_map< Node, Node > *	graphnodes
	Maps Hierarchy nodes to Graph nodes.
std::hash_map< Node, Node > *	hierarchynodes
	Maps Graph nodes to Hierarchy nodes.
ObservableGraph *	obsgraph
	The underlying graph.
bool	own_obsgraph
	Documenting if the underlying graph was created (and should be deleted) by the Hierarchy.

---

Constructor & Destructor Documentation

Hierarchy (   )

Empty constructor. This will create an ObservableGraph, which will be deleted when the Hierarchy is deleted.

Hierarchy (  ObservableGraph *  g, PropertyFacility *  p = NULL )

Constructor.

Hierarchy (  const Hierarchy &  h  )

Copy constructor. This never creates an own graph. It will always be a hierarchy on the graph of the cloned hierarchy.

~Hierarchy (   )  [virtual]

Cleanup.

---

Member Function Documentation

void connect (  Node  node, Node  parent )

Connect a (parentless) hierarchical node to a parent (which can't be in the base graph). This connects a node (which has to have no parent in the hierarchy) to another node (which has to be a node not corresponding to a node in the underlying graph). The embraced preconditions are necessary to maintain a valid tree structure. If they do not hold, an exception is thrown. Connect is done by simply creating a new edge (constant time). Note that if a view is an observer of this hierarchy, this can lead to more actions in the view (see View::new_edge_update()). Exceptions: GraphException  Throws an invalid_node exception if the node had a parent or the parent node was a base graph node. Parameters: node  Child node parent  Parent node

void del_node_update (  Node  node  )  [private]

Base graph del node update. When a node of the base graph was deleted, the hierarchy deletes it's corresponding hierarchy node, and all the parent nodes up until a parent which has children besides the deleted node.

void disconnect (  Node  node  )

Disconnect a hierarchical node from its parent. The disconnect is done by simply deleting an edge (constant time). If the Hierarchy was a tree, it will be a forest after this operation. After disconnecting a Node, it can be connected to another Hierarchy node. Note that if a view is an observer of this hierarchy, this can lead to more actions in the view (see View::del_edge_update()). Parameters: node  The node which will be disconnected from it's parent

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.

ObservableGraph * get_graph (   )  const

Returns the base graph of the Hierarchy. Returns: The base graph

Node graph_node (  const Node  node  )  const

Returns the graph node corresponding to the given hierarchy node. For a detailed explanation, check Hierarchy::hierarchy_node. Complexity (stl hash_map.find): Worst case: O( #graph_nodes ) Average: O( 1 ) Returns: The graph node corresponding to the given hierarchy node, or an invalid node if there is none.

Node hierarchy_node (  const Node  node  )  const

Returns the hierarchy node corresponding to the given graph node. To check if the returned node is valid, use ConstGraph::valid_node(Node node). Complexity (stl hash_map.find): Worst case: O( #graph_nodes ) Average: O( 1 ) Returns: The hierarchy node corresponding to the given graph node, or an invalid node if there is none.

void init (  ObservableGraph *  g, PropertyFacility *  p )  [private]

Initialize Hierarchy.

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_graph (  ObservableGraph *  g  )

Sets the base graph of the Hierarchy. This sets the graph on which the hierarchy is built. Before it does this, it unregisteres itself as an observer from the previous underlying graph (which is deleted if it was created by the hierarchy), and deletes all it's nodes and edges. A fresh hierarchy is then built on the new underlying graph.

Node step (  std::vector< Node > *  children, NodeID  id = NodeID("") )  [inline]

Add a hierarchical node to the hierarchy (calls overloaded step()).

Node step (  std::vector< Node >::const_iterator  children_begin, std::vector< Node >::const_iterator  children_end, NodeID  id = NodeID("") )

Add a hierarchical node to the hierarchy. Behaviour: If the nodes have no parent, a new parent will be generated. If the nodes have a common parent, a new parent will be inserted between the nodes and the common parent. If the nodes have different parents: Returns NULL. The more generic approach of using two iterators to define the range was used, because there are cases in which just a range of a dataset should be used, and then it's more convenient to just pass two iterators instead of copying every node into a new array. In all other cases, it's easy to get the iterators (e.g. vector<Node>::begin(), vector<Node>::end() ). Complexity: Linear in the number of nodes to step Note that if a view is an observer of this hierarchy, this can lead to more actions in the view. Exceptions: GraphException  Throws a cannot_step exception if the nodes in children_begin, children_end have different parents. Parameters: children_begin  An iterator pointing to the begin of a vector of Nodes children_end  An iterator pointing to the end of a vector of Nodes id  The id to give the new parent node Returns: Returns the new node, or NULL if the range children_begin, children_end is empty.

void unstep (  Node  node  )

Delete a hierarchical node from the graph. This will delete a node from the hierarchy (if the node is not a node corresponding to the underlying graph). Also, if the node had a parent node, all it's children are attached to it's parent after the node was deleted. Complexity: O( degree(node) ) Note that if a view is an observer of this hierarchy, this can lead to more actions in the view. Parameters: node  The node

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

Base graph update. This implementation listens only to changes to the nodes of the underlying graph. Edges of the base graph are not inportant for the Hierarchy. Implements Observer.

---

Field Documentation

std::hash_map<Node, Node>* graphnodes [private]

Maps Hierarchy nodes to Graph nodes.

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

Maps Graph nodes to Hierarchy nodes.

ObservableGraph* obsgraph [private]

The underlying graph.

bool own_obsgraph [private]

Documenting if the underlying graph was created (and should be deleted) by the Hierarchy.

---