qgar::GenUGraph< TNODE, TEDGE > Class Template Reference
[Graphs and trees]

#include <qgarlib/GenUGraph.H>

List of all members.

---

Detailed Description

template<class TNODE, class TEDGE>
class qgar::GenUGraph< TNODE, TEDGE >

Parameterized undirected graph.

A node is described by class qgar::GenNode. It contains:

• an object of type TNODE, called the node type,
• an integer flag, at client's disposal,
• a STL list of (pointers to) edges adjacent to the node.

An edge is described by class qgar::GenEdge. It contains:

• an object of type TEDGE, called the edge type,
• an integer flag, at client's disposal,
• two (pointers to its) adjacent nodes, arbitrarily called source and target nodes.

A graph is represented as:

• A STL list of pointers to its nodes, called the nodes list. The first node of the list is called the entry node.
• A STL list of pointers to its edges called the edges list. The first edge of the list is called the entry edge.

Partially inspired by the LEDA library (when it was a free software). See http://www.mpi-sb.mpg.de/LEDA/.

Warning:

• The class is not supposed to be derived: No function member (destructor or whatever else) is virtual.

• Neither copy constructor nor assignment operator are defined.

• For efficiency reasons, the validity of pointers given as arguments to function members is not checked. In particular:

  • pointers may be equal to 0, which will undoubtedly be the cause of a further program abortion,
  • pointed nodes or edges may not belong to the current graph, with similar consequences.

• The deletion of a graph causes the deletion of all its nodes and edges. Consequently, a program abortion may occur when:

  • a (pointer to a) same node or a same edge belongs to different graphs,
  • the nodes (resp. edges) list of a graph contains multiple occurrences of (pointers to) a same node (resp. edge), or contains null pointers,
  • nodes (resp. edges) of the nodes (resp. edges) list of a graph are explicitely deleted, using operator <tt>delete, before exiting the block of program containing the graph,
  • local variables are used to insert nodes (resp. edges) in a graph, for example:

    GenUGraph<int,int> g;
    GenNode<int,int> n(1);
    GenEdge<int,int> e(1);
    
    g.addNode(&n);  // prohibited!
    g.addEdge(&e);  // prohibited!
    

Author:

Gérald Masini

Date:

July 29, 2004 17:18

Since:

Qgar 2.2

Definition at line 143 of file GenUGraph.H.

Public Types
Types
typedef TNODE	node_type
	Type of the data stored in a node.
typedef node_type &	node_type_reference
	Reference to qgar::GenUGraph::node_type.
typedef const node_type &	node_type_const_reference
	Constant reference to qgar::GenUGraph::node_type.
typedef node_type *	node_type_pointer
	Pointer to qgar::GenUGraph::node_type.
typedef const node_type *	node_type_const_pointer
	Constant pointer to qgar::GenUGraph::node_type.
typedef TEDGE	edge_type
	Type of the data stored in an edge.
typedef edge_type &	edge_type_reference
	Reference to qgar::GenUGraph::edge_type.
typedef const edge_type &	edge_type_const_reference
	Constant reference to qgar::GenUGraph::edge_type.
typedef edge_type *	edge_type_pointer
	Pointer to qgar::GenUGraph::edge_type.
typedef const edge_type *	edge_type_const_pointer
	Constant pointer to qgar::GenUGraph::edge_type.
typedef std::list< GenNode< node_type, edge_type > * >	nodes_list_type
	Type of the nodes list.
typedef std::list< GenEdge< node_type, edge_type > * >	edges_list_type
	Type of the edges list.
Public Member Functions
Constructors
	GenUGraph ()
	Default constructor.
	GenUGraph (GenNode< node_type, edge_type > *const aPNode)
	Initialize from (a pointer to) a node.
	GenUGraph (GenEdge< node_type, edge_type > *const aPEdge)
	Initialize from (a pointer to) an edge.
Destructor
Copy constructor.
virtual	~GenUGraph ()
	Virtual destructor.
Graph characteristics
bool	empty () const
	Return true if the graph is empty.
int	sizeNodes () const
	Return the number of nodes.
int	sizeEdges () const
	Return the number of edges.
Node access
GenNode< node_type, edge_type > *	pEntryNode () const
	Return a pointer to the entry node, or 0 if the nodes list is empty.
nodes_list_type &	getNodes ()
	Get the nodes list.
const nodes_list_type &	accessNodes () const
	Get (a constant reference to) the nodes list.
nodes_list_type	nodes () const
	Get a copy of the nodes list.
Edge access
GenEdge< node_type, edge_type > *	pEntryEdge () const
	Get a pointer to the entry edge, or 0 if the edges list is empty.
edges_list_type &	getEdges ()
	Get the edges list.
const edges_list_type &	accessEdges () const
	Get (a constant reference to) the edges list.
edges_list_type	edges () const
	Get a copy of the edges list.
Insertion of created nodes
GenNode< node_type, edge_type > *	addNode (node_type_const_reference aData, short int aFlag=0)
	Just insert a new node created from given data and flag.
GenNode< node_type, edge_type > *	addNode (GenEdge< node_type, edge_type > *const aPEdge, node_type_const_reference aData, short int aFlag=0)
	Insert a new node and link it to given edge of the graph.
GenNode< node_type, edge_type > *	addNode (GenEdge< node_type, edge_type > *const aPEdge1, GenEdge< node_type, edge_type > *const aPEdge2, node_type_const_reference aData, short int aFlag=0)
	Insert a new node between given edges of the graph.
GenNode< node_type, edge_type > *	addNodeAtSource (GenEdge< node_type, edge_type > *const aPEdge, node_type_const_reference aData, short int aFlag=0)
	Insert a new node as source of given edge of the graph.
GenNode< node_type, edge_type > *	addNodeAtTarget (GenEdge< node_type, edge_type > *const aPEdge, node_type_const_reference aData, short int aFlag=0)
	Insert a new node as target of given edge of the graph.
Insertion of existing nodes
GenNode< node_type, edge_type > *	addNode (GenNode< node_type, edge_type > *const aPNode)
	Just insert (a pointer to) a node in the graph.
GenNode< node_type, edge_type > *	addNode (GenNode< node_type, edge_type > *const aPNode, GenEdge< node_type, edge_type > *const aPEdge)
	Insert given (pointer to) node in the graph, as source or target of given (pointed) edge.
GenNode< node_type, edge_type > *	addNode (GenNode< node_type, edge_type > *const aPNode, GenEdge< node_type, edge_type > *const aPEdge1, GenEdge< node_type, edge_type > *const aPEdge2)
	Insert a node between two given edges of the graph.
GenNode< node_type, edge_type > *	addNodeAtSource (GenNode< node_type, edge_type > *const aPNode, GenEdge< node_type, edge_type > *const aPEdge)
	Insert given node as source of given edge of the graph.
GenNode< node_type, edge_type > *	addNodeAtTarget (GenNode< node_type, edge_type > *const aPNode, GenEdge< node_type, edge_type > *const aPEdge)
	Insert given node as target of given edge of the graph.
Insertion of created edges
GenEdge< node_type, edge_type > *	addEdge (edge_type_const_reference aData, short int aFlag=0)
	Just insert a new edge created from given data and flag.
GenEdge< node_type, edge_type > *	addEdge (GenNode< node_type, edge_type > *const aPNode, edge_type_const_reference aData, short int aFlag=0)
	Insert a new edge in the graph, so that given (pointed) node becomes its source.
GenEdge< node_type, edge_type > *	addEdge (GenNode< node_type, edge_type > *const aPSource, GenNode< node_type, edge_type > *const aPTarget, edge_type_const_reference aData, short int aFlag=0)
	Insert an new edge between two given nodes of the graph.
Insertion of existing edges
GenEdge< node_type, edge_type > *	addEdge (GenEdge< node_type, edge_type > *const aPEdge)
	Insert (a pointer to) an edge in the graph.
GenEdge< node_type, edge_type > *	addEdge (GenEdge< node_type, edge_type > *const aPEdge, GenNode< node_type, edge_type > *const aPNode)
	Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its source or its target.
GenEdge< node_type, edge_type > *	addEdge (GenEdge< node_type, edge_type > *const aPEdge, GenNode< node_type, edge_type > *const aPNode1, GenNode< node_type, edge_type > *const aPNode2)
	Insert an edge between two given nodes of the graph.
GenEdge< node_type, edge_type > *	addEdgeBySource (GenEdge< node_type, edge_type > *const aPEdge, GenNode< node_type, edge_type > *const aPNode)
	Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its source.
GenEdge< node_type, edge_type > *	addEdgeByTarget (GenEdge< node_type, edge_type > *const aPEdge, GenNode< node_type, edge_type > *const aPNode)
	Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its target.
Node removal
Warning: The user is in charge of the deletion of the removed nodes.
GenNode< node_type, edge_type > *	remove (GenNode< node_type, edge_type > *const aPNode)
	Remove given (pointer to) node from the graph, and return it.
GenNode< node_type, edge_type > *	remove (typename nodes_list_type::iterator aPos)
	Remove (pointer to) node at given position in the nodes list of the graph, and return it.
Edge removal
Warning: The user is in charge of the deletion of the removed edges.
GenEdge< node_type, edge_type > *	remove (GenEdge< node_type, edge_type > *const aPEdge)
	Remove given (pointer to) edge from the graph, and return it.
GenEdge< node_type, edge_type > *	remove (typename edges_list_type::iterator aPos)
	Remove (pointer to) edge at given position in the edges list of the graph, and return it.
Protected Attributes
Nodes and edges lists
Assignment.
nodes_list_type	_nodes
	List of the nodes of the graph.
edges_list_type	_edges
	List of the edges of the graph.

---

Member Typedef Documentation

template<class TNODE, class TEDGE> typedef TEDGE qgar::GenUGraph< TNODE, TEDGE >::edge_type

Type of the data stored in an edge. Definition at line 182 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef const edge_type* qgar::GenUGraph< TNODE, TEDGE >::edge_type_const_pointer

Constant pointer to qgar::GenUGraph::edge_type. Definition at line 202 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef const edge_type& qgar::GenUGraph< TNODE, TEDGE >::edge_type_const_reference

Constant reference to qgar::GenUGraph::edge_type. Definition at line 192 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef edge_type* qgar::GenUGraph< TNODE, TEDGE >::edge_type_pointer

Pointer to qgar::GenUGraph::edge_type. Definition at line 197 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef edge_type& qgar::GenUGraph< TNODE, TEDGE >::edge_type_reference

Reference to qgar::GenUGraph::edge_type. Definition at line 187 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef std::list< GenEdge<node_type,edge_type>* > qgar::GenUGraph< TNODE, TEDGE >::edges_list_type

Type of the edges list. Definition at line 212 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef TNODE qgar::GenUGraph< TNODE, TEDGE >::node_type

Type of the data stored in a node. Definition at line 157 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef const node_type* qgar::GenUGraph< TNODE, TEDGE >::node_type_const_pointer

Constant pointer to qgar::GenUGraph::node_type. Definition at line 177 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef const node_type& qgar::GenUGraph< TNODE, TEDGE >::node_type_const_reference

Constant reference to qgar::GenUGraph::node_type. Definition at line 167 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef node_type* qgar::GenUGraph< TNODE, TEDGE >::node_type_pointer

Pointer to qgar::GenUGraph::node_type. Definition at line 172 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef node_type& qgar::GenUGraph< TNODE, TEDGE >::node_type_reference

Reference to qgar::GenUGraph::node_type. Definition at line 162 of file GenUGraph.H.

template<class TNODE, class TEDGE> typedef std::list< GenNode<node_type,edge_type>* > qgar::GenUGraph< TNODE, TEDGE >::nodes_list_type

Type of the nodes list. Definition at line 207 of file GenUGraph.H.

---

Constructor & Destructor Documentation

template<class TNODE, class TEDGE> qgar::GenUGraph< TNODE, TEDGE >::GenUGraph (   )

Default constructor. Edges and nodes lists are empty. Definition at line 60 of file GenUGraph.TCC.

template<class TNODE, class TEDGE> qgar::GenUGraph< TNODE, TEDGE >::GenUGraph (  GenNode< node_type, edge_type > *const   aPNode  )

Initialize from (a pointer to) a node. Parameters: aPNode  a pointer to a node: must not be 0!

template<class TNODE, class TEDGE> qgar::GenUGraph< TNODE, TEDGE >::GenUGraph (  GenEdge< node_type, edge_type > *const   aPEdge  )

Initialize from (a pointer to) an edge. Parameters: aPEdge  a pointer to an edge: must not be 0! Definition at line 78 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> qgar::GenUGraph< TNODE, TEDGE >::~GenUGraph (   )  [virtual]

Virtual destructor. Definition at line 90 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges, and qgar::GenUGraph< TNODE, TEDGE >::_nodes.

---

Member Function Documentation

template<class TNODE, class TEDGE> const std::list< GenEdge< TNODE, TEDGE > * > & qgar::GenUGraph< TNODE, TEDGE >::accessEdges (   )  const [inline]

Get (a constant reference to) the edges list. Definition at line 234 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> const std::list< GenNode< TNODE, TEDGE > * > & qgar::GenUGraph< TNODE, TEDGE >::accessNodes (   )  const [inline]

Get (a constant reference to) the nodes list. Definition at line 182 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_nodes.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdge (  GenEdge< node_type, edge_type > *const   aPEdge, GenNode< node_type, edge_type > *const   aPNode1, GenNode< node_type, edge_type > *const   aPNode2 )

Insert an edge between two given nodes of the graph. The given nodes are supposed to belong to the current graph: The edge is included in the edges list of the graph. The first (resp. second) node becomes the source (resp. target) of the edge. The edge is inserted in the edges lists of the nodes. Parameters: aPEdge  pointer to an edge: must not be 0! aPNode1  pointer to a node: must not be 0! aPNode2  pointer to a node: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) edge must not belong to the graph. The given (pointed) nodes must belong to the graph.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdge (  GenEdge< node_type, edge_type > *const   aPEdge, GenNode< node_type, edge_type > *const   aPNode )

Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its source or its target. The given node is supposed to belong to the graph: The edge is inserted in the edges list of the graph. The edge is inserted in the edges list of the node. The node becomes the source of the edge if the source is free. Otherwise, the node becomes the target. Parameters: aPNode  pointer to a node: must not be 0! aPEdge  pointer to an edge: must not be 0! Returns: A pointer to the edge. Warning: The given (pointed) edge must not belong to the graph. The given (pointed) node must belong to the graph.

template<class TNODE, class TEDGE> GenEdge< TNODE, TEDGE > * qgar::GenUGraph< TNODE, TEDGE >::addEdge (  GenEdge< node_type, edge_type > *const   aPEdge  )  [inline]

Insert (a pointer to) an edge in the graph. The (pointer to the) edge is just inserted in the edges list of the graph, and is not connected to any node. Parameters: aPEdge  a pointer to an edge: must not be 0! Returns: A pointer to the new edge. Warning: The given (pointed) edge must not belong to the graph. Definition at line 459 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdge (  GenNode< node_type, edge_type > *const   aPSource, GenNode< node_type, edge_type > *const   aPTarget, edge_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Insert an new edge between two given nodes of the graph. An edge is created, with (pointers to) nodes aPSource and aPTarget as source and target, respectively. The new edge is inserted in the edges list of both nodes, and in the edges list of the graph. Parameters: aPSource  pointer to a node: must not be 0! aPTarget  pointer to a node: must not be 0! aData  data to be contained in the edge aFlag  value of the node flag (default 0) Returns: A pointer to the new edge. Warning: The given (pointed) nodes must belong to the graph.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdge (  GenNode< node_type, edge_type > *const   aPNode, edge_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Insert a new edge in the graph, so that given (pointed) node becomes its source. The (pointer to the) new edge is inserted in the edges list of the node, and in the edges list of the graph. The given node becomes the source of the new edge. Parameters: aPNode  pointer to a node: must not be 0! aData  data to be contained in the edge aFlag  value of the edge flag (default 0) Returns: A pointer to the new edge. Warning: The given (pointed) node must belong to the graph.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdge (  edge_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Just insert a new edge created from given data and flag. The (pointer to the) edge is just inserted in the edges list of the graph, and is not connected to any node. Parameters: aData  data to be contained in the edge aFlag  value of the edge flag (default 0) Returns: a pointer to the new edge.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdgeBySource (  GenEdge< node_type, edge_type > *const   aPEdge, GenNode< node_type, edge_type > *const   aPNode )

Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its source. The given node is supposed to belong to the graph: The edge is inserted in the edges list of the graph. The edge is inserted in the edges list of the node. The node becomes the source of the given edge. Parameters: aPEdge  pointer to an edge: must not be 0! aPNode  pointer to a node: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) edge must not belong to the graph. The given (pointed) node must belong to the graph.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addEdgeByTarget (  GenEdge< node_type, edge_type > *const   aPEdge, GenNode< node_type, edge_type > *const   aPNode )

Insert given (pointer to) edge in the graph, so as given (pointed) node becomes its target. The given node is supposed to belong to the graph: The edge is inserted in the edges list of the graph. The edge is inserted in the edges list of the node. The node becomes the target of the edge. Parameters: aPEdge  pointer to an edge aPNode  pointer to a node Returns: A pointer to the node. Warning: The given (pointed) edge must not belong to the graph. The given (pointed) node must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  GenNode< node_type, edge_type > *const   aPNode, GenEdge< node_type, edge_type > *const   aPEdge1, GenEdge< node_type, edge_type > *const   aPEdge2 )

Insert a node between two given edges of the graph. The given edges are supposed to belong to the current graph: The node is inserted in the nodes list of the graph. The edges are included in the edges list of the node. The node becomes the source of the first (resp. second) edge, if the edge source is free. Otherwise, the node becomes the target of the first (resp. second) edge. Parameters: aPNode  pointer to a node: must not be 0! aPEdge1  pointer to an edge: must not be 0! aPEdge2  pointer to an edge: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) node must not belong to the graph. The given (pointed) edges must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  GenNode< node_type, edge_type > *const   aPNode, GenEdge< node_type, edge_type > *const   aPEdge )

Insert given (pointer to) node in the graph, as source or target of given (pointed) edge. The given edge is supposed to belong to the current graph: The node is inserted in the nodes list of the graph. The edge is inserted in the edges list of the node. The node becomes the source of the edge if the edge source is free. Otherwise, the node becomes the target. Parameters: aPNode  pointer to a node: must not be 0! aPEdge  pointer to an edge: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) node must not belong to the graph. The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  GenNode< node_type, edge_type > *const   aPNode  )  [inline]

Just insert (a pointer to) a node in the graph. The (pointer to the) node is just inserted in the nodes list of the graph, and is not connected to any edge. Parameters: aPNode  a pointer to a node: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) node must not belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  GenEdge< node_type, edge_type > *const   aPEdge1, GenEdge< node_type, edge_type > *const   aPEdge2, node_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Insert a new node between given edges of the graph. The (pointer to the) node is inserted in the nodes list of the graph. The (pointers to the) edges are inserted in the edges list of the node. The new node becomes the source of the first (resp. second) edge if the source is free, otherwise it becomes the target of the first (resp. second) edge. Parameters: aPEdge1  pointer to an edge: must not be 0! aPEdge2  pointer to an edge: must not be 0! aData  data to be contained in the node aFlag  value of the node flag (default 0) Returns: A pointer to the new node. Warning: The 2 given (pointed) edges must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  GenEdge< node_type, edge_type > *const   aPEdge, node_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Insert a new node and link it to given edge of the graph. The (pointer to the) node is inserted in the nodes list of the graph. The (pointer to the) edge is inserted in the edges list of the node. The new node becomes the source of the given edge if the source is free, otherwise it becomes the target of the edge. Parameters: aPEdge  pointer to an edge: must not be 0! aData  data to be contained in the node aFlag  value of the node flag (default 0) Returns: A pointer to the new node. Warning: The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNode (  node_type_const_reference  aData, short int  aFlag = 0 )  [inline]

Just insert a new node created from given data and flag. The (pointer to the) node is just inserted in the nodes list of the graph, and is not connected to any edge. Parameters: aData  data to be contained in the node aFlag  value of the node flag (default 0) Returns: A pointer to the new node.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNodeAtSource (  GenNode< node_type, edge_type > *const   aPNode, GenEdge< node_type, edge_type > *const   aPEdge )

Insert given node as source of given edge of the graph. The given edge is supposed to belong to the current graph: The node is inserted in the nodes list of the graph. The edge is included in the edges list of the node. The node becomes the source of the edge. Parameters: aPNode  pointer to a node: must not be 0! aPEdge  pointer to an edge: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) node must not belong to the graph. The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNodeAtSource (  GenEdge< node_type, edge_type > *const   aPEdge, node_type_const_reference  aData, short int  aFlag = 0 )

Insert a new node as source of given edge of the graph. The node is inserted in the nodes list of the graph. The edge is included in the edges list of the node. The node becomes the source of the edge. Parameters: aPEdge  pointer to an edge: must not be 0! aData  data to be contained in the node aFlag  value of the node flag (default 0) Returns: A pointer to the node. Warning: The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNodeAtTarget (  GenNode< node_type, edge_type > *const   aPNode, GenEdge< node_type, edge_type > *const   aPEdge )

Insert given node as target of given edge of the graph. The given edge is supposed to belong to the current graph: The node is inserted in the nodes list of the graph. The edge is included in the edges list of the node. The node becomes the target of the edge. Parameters: aPNode  pointer to a node: must not be 0! aPEdge  pointer to an edge: must not be 0! Returns: A pointer to the node. Warning: The given (pointed) node must not belong to the graph. The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::addNodeAtTarget (  GenEdge< node_type, edge_type > *const   aPEdge, node_type_const_reference  aData, short int  aFlag = 0 )

Insert a new node as target of given edge of the graph. The node is inserted in the nodes list of the graph. The edge is included in the edges list of the node. The node becomes the target of the edge. Parameters: aPEdge  pointer to an edge: must not be 0! aData  data to be contained in the node aFlag  value of the node flag (default 0) Returns: A pointer to the node. Warning: The given (pointed) edge must belong to the graph.

template<class TNODE, class TEDGE> std::list< GenEdge< TNODE, TEDGE > * > qgar::GenUGraph< TNODE, TEDGE >::edges (   )  const [inline]

Get a copy of the edges list. Definition at line 243 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> bool qgar::GenUGraph< TNODE, TEDGE >::empty (   )  const [inline]

Return true if the graph is empty. Definition at line 119 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges, and qgar::GenUGraph< TNODE, TEDGE >::_nodes.

template<class TNODE, class TEDGE> std::list< GenEdge< TNODE, TEDGE > * > & qgar::GenUGraph< TNODE, TEDGE >::getEdges (   )  [inline]

Get the edges list. Definition at line 224 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> std::list< GenNode< TNODE, TEDGE > * > & qgar::GenUGraph< TNODE, TEDGE >::getNodes (   )  [inline]

Get the nodes list. Definition at line 172 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_nodes.

template<class TNODE, class TEDGE> std::list< GenNode< TNODE, TEDGE > * > qgar::GenUGraph< TNODE, TEDGE >::nodes (   )  const [inline]

Get a copy of the nodes list. Definition at line 191 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_nodes.

template<class TNODE, class TEDGE> GenEdge< TNODE, TEDGE > * qgar::GenUGraph< TNODE, TEDGE >::pEntryEdge (   )  const [inline]

Get a pointer to the entry edge, or 0 if the edges list is empty. Definition at line 207 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> GenNode< TNODE, TEDGE > * qgar::GenUGraph< TNODE, TEDGE >::pEntryNode (   )  const [inline]

Return a pointer to the entry node, or 0 if the nodes list is empty. Definition at line 155 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_nodes.

template<class TNODE, class TEDGE> GenEdge<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::remove (  typename edges_list_type::iterator  aPos  )

Remove (pointer to) edge at given position in the edges list of the graph, and return it. If the given position is the end of the edges list of the graph, the graph remains unchanged and the function returns 0. Otherwise, the given edge is removed from the edges list of its source and target nodes, and is removed from the edges list of the graph. Parameters: aPos  a position in the edges list of the graph Returns: a pointer to the removed edge.

template<class TNODE, class TEDGE> GenEdge< TNODE, TEDGE > * qgar::GenUGraph< TNODE, TEDGE >::remove (  GenEdge< node_type, edge_type > *const   aPEdge  )  [inline]

Remove given (pointer to) edge from the graph, and return it. If the given (pointer to) edge is not in the edges list of the graph, the graph remains unchanged and the function returns 0. Otherwise, the given edge is removed from the edges list of its source and target nodes, and is removed from the edges list of the graph. Parameters: aPEdge  a pointer to an edge: should not be 0! Returns: A pointer to the removed edge. Definition at line 614 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges, and qgar::GenUGraph< TNODE, TEDGE >::remove().

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::remove (  typename nodes_list_type::iterator  aPos  )

Remove (pointer to) node at given position in the nodes list of the graph, and return it. If the given position is the end of the nodes list of the graph, the graph remains unchanged and the function returns 0. Otherwise, each edge adjacent to the given node is removed from the graph, and the given node is removed from the nodes list of the graph. Parameters: aPos  a position in the nodes list of the graph Returns: A pointer to the removed node. Warning: Each edge adjacent to the removed node is deleted. The edges list of the returned (pointed) node is cleared. Todo: Maybe the way adjacent edges of the nodes are deleted could be more efficient. In particular, the use of function qgar::GenUGraph::removeEdge implies: a copy of the edges list of the current node, an update of the edges list of the current node each time an edge is removed from the graph, whereas this edges list could be cleared in one time, once all edges are removed.

template<class TNODE, class TEDGE> GenNode<node_type,edge_type>* qgar::GenUGraph< TNODE, TEDGE >::remove (  GenNode< node_type, edge_type > *const   aPNode  )  [inline]

Remove given (pointer to) node from the graph, and return it. If the given (pointer to) node is not in the nodes list of the graph, the graph remains unchanged and the function returns 0. Otherwise, each edge adjacent to the given node is removed from the graph, and the given node is removed from the nodes list of the graph. Parameters: aPNode  a pointer to a node: must not be 0! Returns: A pointer to the removed node. Warning: Each edge adjacent to the removed node is deleted. The edges list of the returned (pointed) node is cleared. Referenced by qgar::GenUGraph< TNODE, TEDGE >::remove().

template<class TNODE, class TEDGE> int qgar::GenUGraph< TNODE, TEDGE >::sizeEdges (   )  const [inline]

Return the number of edges. Definition at line 139 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_edges.

template<class TNODE, class TEDGE> int qgar::GenUGraph< TNODE, TEDGE >::sizeNodes (   )  const [inline]

Return the number of nodes. Definition at line 129 of file GenUGraph.TCC. References qgar::GenUGraph< TNODE, TEDGE >::_nodes.

---

Member Data Documentation

template<class TNODE, class TEDGE> edges_list_type qgar::GenUGraph< TNODE, TEDGE >::_edges [protected]

List of the edges of the graph. Definition at line 885 of file GenUGraph.H. Referenced by qgar::GenUGraph< TNODE, TEDGE >::accessEdges(), qgar::GenUGraph< TNODE, TEDGE >::addEdge(), qgar::GenUGraph< TNODE, TEDGE >::edges(), qgar::GenUGraph< TNODE, TEDGE >::empty(), qgar::GenUGraph< TNODE, TEDGE >::GenUGraph(), qgar::GenUGraph< TNODE, TEDGE >::getEdges(), qgar::GenUGraph< TNODE, TEDGE >::pEntryEdge(), qgar::GenUGraph< TNODE, TEDGE >::remove(), qgar::GenUGraph< TNODE, TEDGE >::sizeEdges(), and qgar::GenUGraph< TNODE, TEDGE >::~GenUGraph().

template<class TNODE, class TEDGE> nodes_list_type qgar::GenUGraph< TNODE, TEDGE >::_nodes [protected]

List of the nodes of the graph. Definition at line 880 of file GenUGraph.H. Referenced by qgar::GenUGraph< TNODE, TEDGE >::accessNodes(), qgar::GenUGraph< TNODE, TEDGE >::empty(), qgar::GenUGraph< TNODE, TEDGE >::getNodes(), qgar::GenUGraph< TNODE, TEDGE >::nodes(), qgar::GenUGraph< TNODE, TEDGE >::pEntryNode(), qgar::GenUGraph< TNODE, TEDGE >::sizeNodes(), and qgar::GenUGraph< TNODE, TEDGE >::~GenUGraph().

---

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

• GenUGraph.H
• GenUGraph.TCC