The base class for graphs. More...

#include <graph/graph/graph.h>

Inheritance diagram for Graph:

Collaboration diagram for Graph:

[legend]

Public Types
typedef std::set< Vertex * >	VSet

typedef std::set< Edge * >	ESet

typedef carto::rc_ptr< GraphFactory >	FactoryPtr

typedef VSet::value_type	value_type

typedef VSet::pointer	pointer
	pointer is absent from MS Visual C++ / Intel Win32 More...

typedef VSet::reference	reference

typedef VSet::const_reference	const_reference

typedef VSet::iterator	iterator

typedef VSet::const_iterator	const_iterator

typedef VSet::reverse_iterator	reverse_iterator

typedef VSet::const_reverse_iterator	const_reverse_iterator

Public Types inherited from carto::SyntaxedObject< T >
typedef internal::SyntaxedObjectSwitch< T, SUPERSUBCLASS(Interface, T)>::ContentType	ContentType

Public Member Functions
	Graph (const std::string &s="")

	Graph (const FactoryPtr factory, const std::string &s="")

virtual	~Graph ()
	The destructor is responsible for releasing the memory allocated by the addVertex and addEdge methods. More...

template<class InputIterator >
void	extract (Graph &graph, InputIterator iv1, InputIterator iv2)
	Extract a subgraph. More...

Clean up
void	clear ()
	Delete vertices and edges. More...

Vertex handling
Vertex *	addVertex (const std::string &s="")
	Allocate and add a vertex to the graph. More...

Vertex *	cloneVertex (const Vertex *vertex)
	Clone a vertex of the graph, without attaching it to any edge. More...

bool	hasVertex (const Vertex *vertex) const
	Does the graph contain a given vertex? More...

void	removeVertex (Vertex *vertex)
	Delete and remove a vertex from the graph. More...

Vertex *	randomVertex () const
	Return a random vertex (CAUTION: not perfectly random!) More...

const std::set< Vertex * > &	vertices () const
	Return the vertices of the graph. More...

std::set< Vertex * >	getVerticesWith (const std::string &s) const
	Find the vertices which contain a given semantic attribute. More...

template<class T >
std::set< Vertex * >	getVerticesWith (const std::string &s, const T &t) const
	Find the vertices which contain a given semantic attribute/value pair. More...

Edge handling
Edge *	addUndirectedEdge (Vertex vertex1, Vertex vertex2, std::string s)
	Allocate and add to the graph an undirected edge containing the given vertices. More...

Edge *	addEdge (Vertex vertex1, Vertex vertex2, std::string s="")
	A synonym of addUnDirectedEdge - see above. More...

Edge *	addDirectedEdge (Vertex vertex1, Vertex vertex2, std::string s)
	Allocate and add to the graph a directed edge containing the given vertices. More...

bool	hasEdge (const Edge *edge) const
	Does the graph contain a particular edge? More...

void	removeEdge (Edge *edge)
	Delete and remove an edge from the graph. More...

const std::set< Edge * > &	edges () const
	Return the edges of the graph. More...

std::set< Edge * >	edges (const Vertex vertex1, const Vertex vertex2) const
	Return the set of edges linking two given vertices. More...

std::set< Edge * >	getEdgesWith (const std::string &s) const
	Find the edges which contain a given semantic attribute. More...

template<class T >
std::set< Edge * >	getEdgesWith (const std::string &s, const T &t) const
	Find the edges which contain a given pair semantic attribute/value. More...

Iterators iterate on the vertices
iterator	begin ()
	Get the beginning of the vertex collection of the graph. More...

iterator	end ()
	Get the end of the vertex collection of the graph. More...

const_iterator	begin () const
	Get the beginning of the vertex collection of the graph. More...

const_iterator	end () const
	Get the end of the vertex collection of the graph. More...

reverse_iterator	rbegin ()
	Get the beginning of the reversed vertex collection of the graph. More...

reverse_iterator	rend ()
	Get the end of the reversed vertex collection of the graph. More...

const_reverse_iterator	rbegin () const
	Get the beginning of the reversed vertex collection of the graph. More...

const_reverse_iterator	rend () const
	Get the end of the reversed vertex collection of the graph. More...

Property querying methods
size_t	order () const
	The order of a graph is the number of its vertices. More...

size_t	size () const __attribute__((__deprecated__("use edgeSize() for " "the number of edges. In a future release

size_t	size () will return the " "number properties as it does in GenericObject")))

size_t	edgesSize () const
	The edgesSize of a graph is the number of its edges. More...

virtual bool	isUndirected () const
	Does the graph contain only undirected edges? More...

virtual bool	isDirected () const
	Does the graph contain only directed edges? More...

virtual bool	check (const carto::SyntaxSet &syntax, std::set< std::string > &missing) const
	Reimplemented to check children recursively. More...

Public Member Functions inherited from GraphObject
virtual	~GraphObject ()

Public Member Functions inherited from carto::SyntaxedObject< T >
	SyntaxedObject (const std::string &s)

	SyntaxedObject (const SyntaxedObject &x)

	SyntaxedObject (const SyntaxedObject< PropertySet > &x)

Protected Attributes
FactoryPtr	_factory
	Abstract factory used to create vertices and edges. More...

Additional Inherited Members
Protected Member Functions inherited from GraphObject
	GraphObject (const std::string &s)
	The programmer should not call the constructor of an abstract base class. More...

	GraphObject (const GraphObject &x)

Detailed Description

The base class for graphs.

It contains and manages Vertex and Edge objects.

Definition at line 71 of file graph.h.

Member Typedef Documentation

◆ const_iterator

typedef VSet::const_iterator Graph::const_iterator

Definition at line 88 of file graph.h.

◆ const_reference

typedef VSet::const_reference Graph::const_reference

Definition at line 86 of file graph.h.

◆ const_reverse_iterator

typedef VSet::const_reverse_iterator Graph::const_reverse_iterator

Definition at line 90 of file graph.h.

◆ ESet

typedef std::set<Edge*> Graph::ESet

Definition at line 77 of file graph.h.

◆ FactoryPtr

typedef carto::rc_ptr<GraphFactory> Graph::FactoryPtr

Definition at line 79 of file graph.h.

◆ iterator

typedef VSet::iterator Graph::iterator

Definition at line 87 of file graph.h.

◆ pointer

typedef VSet::pointer Graph::pointer

pointer is absent from MS Visual C++ / Intel Win32

Definition at line 83 of file graph.h.

◆ reference

typedef VSet::reference Graph::reference

Definition at line 85 of file graph.h.

◆ reverse_iterator

typedef VSet::reverse_iterator Graph::reverse_iterator

Definition at line 89 of file graph.h.

◆ value_type

typedef VSet::value_type Graph::value_type

Definition at line 80 of file graph.h.

◆ VSet

typedef std::set<Vertex*> Graph::VSet

Definition at line 76 of file graph.h.

Constructor & Destructor Documentation

◆ Graph() [1/2]

Graph::Graph ( const std::string & s = "" )

Parameters

s	syntactic attribute of the new graph

◆ Graph() [2/2]

Graph::Graph	(	const FactoryPtr	factory,
		const std::string &	s = `""`
	)

Parameters

factory	abstract factory used instead of the default factory
s	syntactic attribute of the new graph

◆ ~Graph()

virtual Graph::~Graph ( )

virtual

The destructor is responsible for releasing the memory allocated by the addVertex and addEdge methods.

The programmer should never delete vertex and edge objects; they are managed by the graph.

Member Function Documentation

◆ addDirectedEdge()

Edge* Graph::addDirectedEdge	(	Vertex *	vertex1,
		Vertex *	vertex2,
		std::string	s
	)

Allocate and add to the graph a directed edge containing the given vertices.

Note that the pointer returned by this method is to be seen as a simple identifier for the new edge; the programmer should never delete it. It is the responsability of the graph which creates the edge to delete it.

Returns: a pointer to the allocated edge

Parameters

vertex1	first vertex
vertex2	second vertex
s	syntactic attribute of the new edge

Exceptions

range_error if a vertex is not in the graph

◆ addEdge()

Edge * Graph::addEdge	(	Vertex *	vertex1,
		Vertex *	vertex2,
		std::string	s = `""`
	)

inline

A synonym of addUnDirectedEdge - see above.

Definition at line 509 of file graph.h.

◆ addUndirectedEdge()

Edge* Graph::addUndirectedEdge	(	Vertex *	vertex1,
		Vertex *	vertex2,
		std::string	s
	)

Allocate and add to the graph an undirected edge containing the given vertices.

Note that the pointer returned by this method is to be seen as a simple identifier for the new edge; the programmer should never delete it. It is the responsability of the graph which creates the edge to delete it.

Returns: a pointer to the allocated edge

Parameters

vertex1	first vertex
vertex2	second vertex
s	syntactic attribute of the new edge

Exceptions

range_error if a vertex is not in the graph

◆ addVertex()

Vertex* Graph::addVertex ( const std::string & s = "" )

Allocate and add a vertex to the graph.

Note that the pointer returned by this method is to be seen as a simple identifier for the new vertex; the programmer should never delete it. It is the responsability of the graph which creates the vertex to delete it.

Returns: a pointer to the allocated vertex

Parameters

s	syntactic attribute of the new vertex

◆ begin() [1/2]

Graph::iterator Graph::begin ( )

inline

Get the beginning of the vertex collection of the graph.

Returns: an iterator pointing to the beginning of the vertex collection

Definition at line 557 of file graph.h.

◆ begin() [2/2]

Graph::const_iterator Graph::begin ( ) const

inline

Get the beginning of the vertex collection of the graph.

Returns: a const_iterator pointing to the beginning of the vertex collection

Definition at line 573 of file graph.h.

◆ check()

virtual bool Graph::check	(	const carto::SyntaxSet &	syntax,
		std::set< std::string > &	missing
	)		const

virtual

Reimplemented to check children recursively.

Parameters

syntax	syntax to check against
missing	completed with the names of missing attributes

Returns: true if the object is valid, false otherwise

◆ clear()

void Graph::clear ( )

Delete vertices and edges.

◆ cloneVertex()

Vertex* Graph::cloneVertex ( const Vertex * vertex )

Clone a vertex of the graph, without attaching it to any edge.

This a commodity method for copying the attributes, not the topology of the graph! Note that the pointer returned by this method is to be seen as a simple identifier for the new vertex; the programmer should never delete it. It is the responsability of the graph which creates the vertex to delete it.

Parameters

vertex pointer to the vertex to clone

Returns: a clone of the given vertex

◆ edges() [1/2]

const std::set< Edge * > & Graph::edges ( ) const

inline

Return the edges of the graph.

Returns: the internal collection of edge pointers

Definition at line 517 of file graph.h.

◆ edges() [2/2]

std::set<Edge*> Graph::edges	(	const Vertex *	vertex1,
		const Vertex *	vertex2
	)		const

Return the set of edges linking two given vertices.

Parameters

vertex1	is the source vertex
vertex2	is the sink vertex

Returns: the edges linking the source to the sink

◆ edgesSize()

size_t Graph::edgesSize ( ) const

The edgesSize of a graph is the number of its edges.

Returns: number of edges in the graph

◆ end() [1/2]

Graph::iterator Graph::end ( )

inline

Get the end of the vertex collection of the graph.

Returns: an iterator pointing to the end of the vertex collection

Definition at line 565 of file graph.h.

◆ end() [2/2]

Graph::const_iterator Graph::end ( ) const

inline

Get the end of the vertex collection of the graph.

Returns: a const_iterator pointing to the end of the vertex collection

Definition at line 581 of file graph.h.

◆ extract()

template<class InputIterator >

void Graph::extract	(	Graph &	graph,
		InputIterator	iv1,
		InputIterator	iv2
	)

inline

Extract a subgraph.

Parameters

graph	extracted graph
iv1	iterator on the first vertex to extract
iv2	iterator on the last vertex to extract

Exceptions

range_error if a vertex is not in the graph

Definition at line 549 of file graph.h.

◆ getEdgesWith() [1/2]

std::set<Edge*> Graph::getEdgesWith ( const std::string & s ) const

Find the edges which contain a given semantic attribute.

Parameters

s	semantic attribute to look for

Returns: the set of edges with this semantic attribute

◆ getEdgesWith() [2/2]

template<class T >

std::set< Edge * > Graph::getEdgesWith	(	const std::string &	s,
		const T &	t
	)		const

inline

Find the edges which contain a given pair semantic attribute/value.

Parameters

s	semantic attribute to look for
t	value this semantic attribute must match

Returns: the set of edges that have the right pair attribute/value

Definition at line 526 of file graph.h.

◆ getVerticesWith() [1/2]

std::set<Vertex*> Graph::getVerticesWith ( const std::string & s ) const

Find the vertices which contain a given semantic attribute.

Parameters

s	semantic attribute to look for

Returns: the set of vertices with this semantic attribute

◆ getVerticesWith() [2/2]

template<class T >

std::set< Vertex * > Graph::getVerticesWith	(	const std::string &	s,
		const T &	t
	)		const

inline

Find the vertices which contain a given semantic attribute/value pair.

Parameters

s	semantic attribute to look for
t	value this semantic attribute must match

Returns: the set of vertices that have the right pair

Definition at line 487 of file graph.h.

◆ hasEdge()

bool Graph::hasEdge ( const Edge * edge ) const

Does the graph contain a particular edge?

Returns: true if the graph contains it, false otherwise

Parameters

edge	pointer to the edge to check

◆ hasVertex()

bool Graph::hasVertex ( const Vertex * vertex ) const

Does the graph contain a given vertex?

Returns: true if the graph contains it, false otherwise

Parameters

vertex pointer to the vertex to check

◆ isDirected()

virtual bool Graph::isDirected ( ) const

virtual

Does the graph contain only directed edges?

Returns: true if all the vertices are directed, true otherwise

◆ isUndirected()

virtual bool Graph::isUndirected ( ) const

virtual

Does the graph contain only undirected edges?

Returns: tue if all the vertices are undirected, false otherwise

◆ order()

size_t Graph::order ( ) const

The order of a graph is the number of its vertices.

Returns: number of vertices in the graph

◆ randomVertex()

Vertex* Graph::randomVertex ( ) const

Return a random vertex (CAUTION: not perfectly random!)

Returns: a random vertex

◆ rbegin() [1/2]

Graph::reverse_iterator Graph::rbegin ( )

inline

Get the beginning of the reversed vertex collection of the graph.

Returns: a reverse_iterator pointing to the beginning of the reversed vertex collection

Definition at line 589 of file graph.h.

◆ rbegin() [2/2]

Graph::const_reverse_iterator Graph::rbegin ( ) const

inline

Get the beginning of the reversed vertex collection of the graph.

Returns: a const_reverse_iterator pointing to the beginning of the reversed vertex collection

Definition at line 604 of file graph.h.

◆ removeEdge()

void Graph::removeEdge ( Edge * edge )

Delete and remove an edge from the graph.

The pointer becomes invalid and should not be used afterwards.

Parameters

edge	pointer to the edge to remove

Exceptions

range_error if edge is not in the graph

◆ removeVertex()

void Graph::removeVertex ( Vertex * vertex )

Delete and remove a vertex from the graph.

The pointer becomes invalid and should not be used afterwards.

Parameters

vertex pointer to the vertex to remove

Exceptions

range_error if vertex is not in the graph

◆ rend() [1/2]

Graph::reverse_iterator Graph::rend ( )

inline

Get the end of the reversed vertex collection of the graph.

Returns: a reverse_iterator pointing to the end of the reversed vertex collection

Definition at line 597 of file graph.h.

◆ rend() [2/2]

Graph::const_reverse_iterator Graph::rend ( ) const

inline

Get the end of the reversed vertex collection of the graph.

Returns: a const_reverse_iterator pointing to the end of the reversed vertex collection

Definition at line 612 of file graph.h.

References DECLARE_GENERIC_OBJECT_TYPE.

◆ size() [1/2]

size_t Graph::size ( ) const

Deprecated:: {specialization deprecated because ambiguous: use edgesSize() for the number of edges.

In a future release, size() will return the number properties as it does in GenericObject}

◆ size() [2/2]

size_t Graph::size ( )

◆ vertices()

const std::set< Vertex * > & Graph::vertices ( ) const

inline

Return the vertices of the graph.

Returns: the internal collection of vertex pointers

Definition at line 478 of file graph.h.

Member Data Documentation

◆ _factory

FactoryPtr Graph::_factory

protected

Abstract factory used to create vertices and edges.

Definition at line 444 of file graph.h.

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

graph/graph/graph.h

Public Types

Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reference

◆ const_reverse_iterator

◆ ESet

◆ FactoryPtr

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ value_type

◆ VSet

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

◆ ~Graph()

Member Function Documentation

◆ addDirectedEdge()

◆ addEdge()

◆ addUndirectedEdge()

◆ addVertex()

◆ begin() [1/2]

◆ begin() [2/2]

◆ check()

◆ clear()

◆ cloneVertex()

◆ edges() [1/2]

◆ edges() [2/2]

◆ edgesSize()

◆ end() [1/2]

◆ end() [2/2]

◆ extract()

◆ getEdgesWith() [1/2]

◆ getEdgesWith() [2/2]

◆ getVerticesWith() [1/2]

◆ getVerticesWith() [2/2]

◆ hasEdge()

◆ hasVertex()

◆ isDirected()

◆ isUndirected()

◆ order()

◆ randomVertex()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ removeEdge()

◆ removeVertex()

◆ rend() [1/2]

◆ rend() [2/2]

◆ size() [1/2]

◆ size() [2/2]

◆ vertices()

Member Data Documentation

◆ _factory