ConstGraph Class Reference

#include <ConstGraph.hpp>

Inheritance diagram for ConstGraph:

[legend]Collaboration diagram for ConstGraph:

[legend]

---

Detailed Description

Base graph class, methods to modify nodes and edges are protected and cannot be modified from outside (const).

This Graph class uses a boost Graph for the underlying graph structure. The IDs of the nodes and edges can only be modified through the appropriate methods. All other properties can be stored in the PropertyFacility.

If a method does not specify the behaviour for invalid arguments (e.g. if an invalid node is passed to indeg(Node n) ) then the result is undefined. If you are unsure if the Node or Edge is valid and part of the graph, check with node_exists(Node n) or edge_exists(Edge e).

Internals

Originally, the IDs of the graph were put into the boost graph object as node / edge properties. The boost documentation though explicitly stated that the behaviour is undefined when the boost property facililty is asked for a node which does not exist. To realize a method for checking if a node does exist in the graph, the IDs were moved out of the boost properties and into stl::hash_map, mapping Node->ID and ID->Node.

A first_edge(Node) and last_edge(Node) method does not exist because boost does not provide this functionality. Only *_in_edge and *_out_edge are supported.

Public Member Functions
	ConstGraph ()
	Empty constructor.
	ConstGraph (PropertyFacility *p)
	Constructor.
	ConstGraph (const ConstGraph &g)
	Copy constructor.
virtual	~ConstGraph ()
	Destructor.
virtual bool	node_exists (Node n) const
	Checks if the node is valid and part of the graph.
virtual bool	node_exists (NodeID id) const
	Checks if there is a Node with a specific ID.
virtual Node	node (const NodeID id) const
	Returns the Node with the given ID.
virtual NodeID	node_id (const Node n) const
	Returns the ID of a node.
virtual void	node_id (Node n, const NodeID id)
	Set the ID of a node.
virtual bool	edge_exists (Edge e) const
	Checks if the edge is valid and part of the graph.
virtual bool	edge_exists (const EdgeID id) const
	8 Checks if there is an Edge with a specific ID.
virtual Edge	edge (const EdgeID id) const
	Returns the Edge with the given ID.
virtual Edge	edge (const Node u, const Node v) const
	Returns an Edge from Node u to Node v.
virtual EdgeID	edge_id (const Edge e) const
	Returns the ID of a node.
virtual void	edge_id (Edge e, const EdgeID id)
	Set the ID of an edge.
virtual void	print () const
	Print the graph to stdout.
long	num_nodes () const
	Returns the number of nodes in the graph.
long	num_edges () const
	Returns the number of edges in the graph.
long	indeg (const Node n) const
	Returns the number of incoming edges of a node.
long	outdeg (const Node n) const
	Returns the number of outgoing edges of a node.
Node	source (const Edge e) const
	Returns the source node of an edge.
Node	target (const Edge e) const
	Returns the target node of an edge.
Node	opposite (const Edge e, const Node n) const
	Returns the node of an edge opposite of the given node.
NodeIter	first_node () const
	Returns the iterator for the first node.
NodeIter	last_node () const
	Returns the iterator for the end of the nodes.
EdgeIter	first_edge () const
	Returns the iterator for the first edge.
EdgeIter	last_edge () const
	Returns the iterator for the end of the edges.
OutEdgeIter	first_out_edge (const Node n) const
	Returns the iterator for the first outgoing edge.
OutEdgeIter	last_out_edge (const Node n) const
	Returns the iterator for the last outgoing edge.
InEdgeIter	first_in_edge (const Node n) const
	Returns the iterator for the first incoming edge.
InEdgeIter	last_in_edge (const Node n) const
	Returns the iterator for the last incoming edge.
PropertyFacility *	properties () const
	Returns the property facility used by the graph.
bool	valid_node (Node n) const
	Checks if the node is valid.
bool	valid_edge (Edge e) const
	Checks if the edge is valid.
Protected Types
typedef std::hash_map< NodeID, Node >	id_node_map_t
	Type for NodeID->Node map.
typedef std::hash_map< EdgeID, Edge >	id_edge_map_t
	Type for EdgeID->Edge map.
typedef std::hash_map< Node, NodeID >	node_id_map_t
	Type for Node->NodeID map.
typedef std::hash_map< Edge, EdgeID >	edge_id_map_t
	Type for Edge->EdgeID map.
Protected Member Functions
virtual Node	priv_new_node (NodeID id="")
	Add a node to the graph.
virtual void	priv_del_node (Node n)
	Delete a node from the graph and removes all edges adjacent to this node.
virtual Edge	priv_new_edge (Node u, Node v, EdgeID id="")
	Add an edge to the graph.
virtual void	priv_del_edge (Edge e)
	Delete an edge from the graph.
virtual void	priv_del_edge (Node u, Node v)
	Delete a(ll) directed (u,v) edge(s) from the graph.
virtual void	priv_add_nodes (int num, int start)
	Convenient method to add nodes to the graph.
virtual std::map< Node, Node > *	init_copy (const ConstGraph *g, bool return_map)
	Init a graph by making a copy of another graph.
virtual void	init (PropertyFacility *p)
	Initializes Graph.
Protected Attributes
Graph_t *	graph
	Vertices: list, Edges: list, bidirectional.
PropertyFacility *	prop
	PropertyFacility of the Graph.
node_id_map_t	node_id_map
	Map mapping nodes to their node id.
id_node_map_t	id_node_map
	Map for getting nodes by NodeID.
edge_id_map_t	edge_id_map
	Map mapping edges to their edge id.
id_edge_map_t	id_edge_map
	Map for getting edges by EdgeID.

---

Member Typedef Documentation

typedef std::hash_map<Edge, EdgeID> edge_id_map_t [protected]

Type for Edge->EdgeID map.

typedef std::hash_map<EdgeID, Edge> id_edge_map_t [protected]

Type for EdgeID->Edge map.

typedef std::hash_map<NodeID, Node> id_node_map_t [protected]

Type for NodeID->Node map.

typedef std::hash_map<Node, NodeID> node_id_map_t [protected]

Type for Node->NodeID map.

---

Constructor & Destructor Documentation

ConstGraph (   )

Empty constructor.

ConstGraph (  PropertyFacility *  p  )

Constructor. Parameters: p  If given, uses the PropertyFacility p (and does not delete it when the graph is destroyed).

ConstGraph (  const ConstGraph &  g  )

Copy constructor.

~ConstGraph (   )  [virtual]

Destructor.

---

Member Function Documentation

Edge edge (  const Node  u, const Node  v )  const [virtual]

Returns an Edge from Node u to Node v. Complexity: Worst case: O( #out_edges(u) ) If no edge exists from u to v, an invalid edge is returned (check via valid_edge()). If there are multiple edges between u and v, the first one found is returned. Parameters: u  Source node v  Target node Returns: An edge between u and v.

Edge edge (  const EdgeID  id  )  const [virtual]

Returns the Edge with the given ID. Complexity (see stl hash_map): Worst case: Linar in the size of edge_id_map Average: Constant Exceptions: GraphException  Throws an invalid_edge_id exception if there is no edge with the given ID. Parameters: id  The EdgeID Returns: Returns the Edge with the given ID

bool edge_exists (  const EdgeID  id  )  const [virtual]

8 Checks if there is an Edge with a specific ID. Complexity (see stl hash_map): Worst case: Linar in the size of edge_id_map Average: Constant Parameters: id  The EdgeID Returns: Returns true if an edge with the given ID exists, false otherwise 8

bool edge_exists (  Edge  e  )  const [virtual]

Checks if the edge is valid and part of the graph. Complexity (see stl hash_map): Worst case: Linar in the size of edge_id_map Average: Constant Parameters: e  The edge to check

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

Set the ID of an edge. Complexity (see stl hash_map): Worst case: Linar in the size of edge_id_map Average: Constant Exceptions: GraphException  Throws a duplicate_id exception if the EdgeID is already in use by another edge. Throws an invalid_edge exception if the given edge is not in the graph. Parameters: e  The edge id  The new id. This must not be an id currently used by another edge in the graph. Reimplemented in Hierarchy, ObservableGraph, and View.

EdgeID edge_id (  const Edge  e  )  const [virtual]

Returns the ID of a node. Complexity (see stl hash_map): Worst case: Linar in the size of edge_id_map Average: Constant Exceptions: GraphException  Throws an invalid_edge exception if the given edge is not in the graph. Parameters: e  The Edge Returns: Returns the ID of the given Edge

EdgeIter first_edge (   )  const

Returns the iterator for the first edge. Complexity: Boost: Constant time

InEdgeIter first_in_edge (  const Node  n  )  const

Returns the iterator for the first incoming edge. Complexity: Boost: Constant time Parameters: n  The node whose edges are queried

NodeIter first_node (   )  const

Returns the iterator for the first node. Complexity: Boost: Constant time

OutEdgeIter first_out_edge (  const Node  n  )  const

Returns the iterator for the first outgoing edge. Complexity: Boost: Constant time Parameters: n  The node whose edges are queried

long indeg (  const Node  n  )  const

Returns the number of incoming edges of a node. Complexity: Boost: O( #in_edges ) Parameters: n  The node whose in-degree is queried

void init (  PropertyFacility *  p  )  [protected, virtual]

Initializes Graph. Parameters: p  If not NULL, uses the PropertyFacility p (and does not delete it when the graph is destroyed).

std::map< Node, Node > * init_copy (  const ConstGraph *  g, bool  return_map )  [protected, virtual]

Init a graph by making a copy of another graph. Parameters: g  The other graph return_map  If true, map will not be deleted and returned

EdgeIter last_edge (   )  const

Returns the iterator for the end of the edges. Complexity: Boost: Constant time

InEdgeIter last_in_edge (  const Node  n  )  const

Returns the iterator for the last incoming edge. Complexity: Boost: Constant time Parameters: n  The node whose edges are queried

NodeIter last_node (   )  const

Returns the iterator for the end of the nodes. Complexity: Boost: Constant time

OutEdgeIter last_out_edge (  const Node  n  )  const

Returns the iterator for the last outgoing edge. Complexity: Boost: Constant time Parameters: n  The node whose edges are queried

Node node (  const NodeID  id  )  const [virtual]

Returns the Node with the given ID. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map Average: Constant Exceptions: GraphException  Throws an invalid_node_id exception if there is no node with the given ID. Parameters: id  The NodeID Returns: Returns the Node with the given ID

bool node_exists (  NodeID  id  )  const [virtual]

Checks if there is a Node with a specific ID. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map Average: Constant Parameters: id  The NodeID Returns: Returns true if a node with the given ID exists, false otherwise

bool node_exists (  Node  n  )  const [virtual]

Checks if the node is valid and part of the graph. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map Average: Constant Parameters: n  The node to check

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

Set the ID of a node. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map Average: Constant Exceptions: GraphException  Throws a duplicate_id exception if the NodeID is already in use by another node. Throws an invalid_node exception if the given node is not in the graph. Parameters: n  The node id  The new id. This must not be an id currently used by another node in the graph. Reimplemented in Hierarchy, ObservableGraph, and View.

NodeID node_id (  const Node  n  )  const [virtual]

Returns the ID of a node. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map Average: Constant Exceptions: GraphException  Throws an invalid_node exception if the given node is not in the graph. Parameters: n  The Node Returns: Returns the ID of the given Node

long num_edges (   )  const

Returns the number of edges in the graph.

long num_nodes (   )  const

Returns the number of nodes in the graph.

Node opposite (  const Edge  e, const Node  n )  const

Returns the node of an edge opposite of the given node. Complexity: Boost: Constant time Parameters: e  The edge for which the opposite node is queried n  The node which is not the opposite

long outdeg (  const Node  n  )  const

Returns the number of outgoing edges of a node. Complexity: Boost: O( #out_edges ) Parameters: n  The node whose out-degree is queried

void print (   )  const [virtual]

Print the graph to stdout.

void priv_add_nodes (  int  num, int  start )  [protected, virtual]

Convenient method to add nodes to the graph. Adds num nodes with IDs starting from start (e.g.: num == 2, start == 4: new nodes with ids "4" and "5"). Complexity: O( num * O(priv_add_node()) ) Parameters: num  Number of nodes to add start  Start of id sequence

void priv_del_edge (  Node  u, Node  v )  [protected, virtual]

Delete a(ll) directed (u,v) edge(s) from the graph. This also deletes the properties of the edge(s). Complexity: Worst case: O( #u-v-edges * (#edges + #properties(e.id)) ) Parameters: u  The source node of the directed edge to delete v  The target node of the directed edge to delete

void priv_del_edge (  Edge  e  )  [protected, virtual]

Delete an edge from the graph. This also deletes the properties of the edge. Complexity: Worst case: O( #edges + #properties(e.id) ) Parameters: e  The edge to delete

void priv_del_node (  Node  n  )  [protected, virtual]

Delete a node from the graph and removes all edges adjacent to this node. This also deleted the properties of the node. Complexity: Worst case: O( degree(n) * O(priv_del_edge()) + #nodes + #edges ) Parameters: n  The node to delete

Edge priv_new_edge (  Node  u, Node  v, EdgeID  id = "" )  [protected, virtual]

Add an edge to the graph. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map+edge_id_map Average: Constant Exceptions: GraphException  Throws a duplicate_id exception if the ID is not "" and already used by another node or edge Parameters: u  The source node of the directed edge v  The target node of the directed edge id  The id of the new edge

Node priv_new_node (  NodeID  id = ""  )  [protected, virtual]

Add a node to the graph. Complexity (see stl hash_map): Worst case: Linar in the size of node_id_map+edge_id_map Average: Constant Exceptions: GraphException  Throws a duplicate_id exception if the ID is not "" and already used by another node or edge Parameters: id  The id of the new node

PropertyFacility * properties (   )  const

Returns the property facility used by the graph. Complexity: Constant time

Node source (  const Edge  e  )  const

Returns the source node of an edge. Complexity: Boost: Constant time Parameters: e  The edge for which the source is queried

Node target (  const Edge  e  )  const

Returns the target node of an edge. Complexity: Boost: Constant time Parameters: e  The edge for which the target is queried

bool valid_edge (  Edge  e  )  const

Checks if the edge is valid. Checks if the boost properties of an edge are NULL. Complexity: Constant time Parameters: e  The edge to check

bool valid_node (  Node  n  )  const

Checks if the node is valid. Currently, checks for != NULL. Complexity: Constant time Parameters: n  The node to check

---

Field Documentation

edge_id_map_t edge_id_map [protected]

Map mapping edges to their edge id.

Graph_t* graph [protected]

Vertices: list, Edges: list, bidirectional.

id_edge_map_t id_edge_map [protected]

Map for getting edges by EdgeID.

id_node_map_t id_node_map [protected]

Map for getting nodes by NodeID.

node_id_map_t node_id_map [protected]

Map mapping nodes to their node id.

PropertyFacility* prop [protected]

PropertyFacility of the Graph.

---