Graph: Generic attributed relational graphs


Graph Class Reference

The base class for graphs. More...

#include <graph/graph/graph.h>

Inheritance diagram for Graph:
Collaboration diagram for Graph:

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< class >
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) throw (std::range_error)
 Extract a subgraph. More...
 
Clean up
void clear ()
 Delete vertices and edges. More...
 
Vertex handling
VertexaddVertex (const std::string &s="")
 Allocate and add a vertex to the graph. More...
 
VertexcloneVertex (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) throw (std::range_error)
 Delete and remove a vertex from the graph. More...
 
VertexrandomVertex () 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
EdgeaddUndirectedEdge (Vertex *vertex1, Vertex *vertex2, std::string s) throw (std::range_error)
 Allocate and add to the graph an undirected edge containing the given vertices. More...
 
EdgeaddEdge (Vertex *vertex1, Vertex *vertex2, std::string s="") throw (std::range_error)
 A synonym of addUnDirectedEdge - see above. More...
 
EdgeaddDirectedEdge (Vertex *vertex1, Vertex *vertex2, std::string s) throw (std::range_error)
 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) throw (std::range_error)
 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< class >
 SyntaxedObject (const std::string &s)
 
 SyntaxedObject (const SyntaxedObject &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

typedef VSet::const_iterator Graph::const_iterator

Definition at line 88 of file graph.h.

typedef VSet::const_reference Graph::const_reference

Definition at line 86 of file graph.h.

typedef VSet::const_reverse_iterator Graph::const_reverse_iterator

Definition at line 90 of file graph.h.

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

Definition at line 77 of file graph.h.

Definition at line 79 of file graph.h.

typedef VSet::iterator Graph::iterator

Definition at line 87 of file graph.h.

typedef VSet::pointer Graph::pointer

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

Definition at line 83 of file graph.h.

typedef VSet::reference Graph::reference

Definition at line 85 of file graph.h.

typedef VSet::reverse_iterator Graph::reverse_iterator

Definition at line 89 of file graph.h.

typedef VSet::value_type Graph::value_type

Definition at line 80 of file graph.h.

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

Definition at line 76 of file graph.h.

Constructor & Destructor Documentation

Graph::Graph ( const std::string &  s = "")
Parameters
ssyntactic attribute of the new graph
Graph::Graph ( const FactoryPtr  factory,
const std::string &  s = "" 
)
Parameters
factoryabstract factory used instead of the default factory
ssyntactic attribute of the new 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

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

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
vertex1first vertex
vertex2second vertex
ssyntactic attribute of the new edge
Exceptions
range_errorif a vertex is not in the graph
Edge * Graph::addEdge ( Vertex vertex1,
Vertex vertex2,
std::string  s = "" 
)
throw (std::range_error
)
inline

A synonym of addUnDirectedEdge - see above.

Definition at line 514 of file graph.h.

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

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
vertex1first vertex
vertex2second vertex
ssyntactic attribute of the new edge
Exceptions
range_errorif a vertex is not in the graph
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
ssyntactic attribute of the new vertex
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 564 of file graph.h.

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 580 of file graph.h.

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

Reimplemented to check children recursively.

Parameters
syntaxsyntax to check against
missingcompleted with the names of missing attributes
Returns
true if the object is valid, false otherwise
void Graph::clear ( )

Delete vertices and edges.

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
vertexpointer to the vertex to clone
Returns
a clone of the given vertex
const std::set< Edge * > & Graph::edges ( ) const
inline

Return the edges of the graph.

Returns
the internal collection of edge pointers

Definition at line 523 of file graph.h.

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

Return the set of edges linking two given vertices.

Parameters
vertex1is the source vertex
vertex2is the sink vertex
Returns
the edges linking the source to the sink
size_t Graph::edgesSize ( ) const

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

Returns
number of edges in the graph
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 572 of file graph.h.

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 588 of file graph.h.

template<class InputIterator >
void Graph::extract ( Graph graph,
InputIterator  iv1,
InputIterator  iv2 
)
throw (std::range_error
)
inline

Extract a subgraph.

Parameters
graphextracted graph
iv1iterator on the first vertex to extract
iv2iterator on the last vertex to extract
Exceptions
range_errorif a vertex is not in the graph

Definition at line 555 of file graph.h.

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

Find the edges which contain a given semantic attribute.

Parameters
ssemantic attribute to look for
Returns
the set of edges with this semantic attribute
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
ssemantic attribute to look for
tvalue this semantic attribute must match
Returns
the set of edges that have the right pair attribute/value

Definition at line 532 of file graph.h.

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

Find the vertices which contain a given semantic attribute.

Parameters
ssemantic attribute to look for
Returns
the set of vertices with this semantic attribute
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
ssemantic attribute to look for
tvalue this semantic attribute must match
Returns
the set of vertices that have the right pair

Definition at line 492 of file graph.h.

bool Graph::hasEdge ( const Edge edge) const

Does the graph contain a particular edge?

Returns
true if the graph contains it, false otherwise
Parameters
edgepointer to the edge to check
bool Graph::hasVertex ( const Vertex vertex) const

Does the graph contain a given vertex?

Returns
true if the graph contains it, false otherwise
Parameters
vertexpointer to the vertex to check
virtual bool Graph::isDirected ( ) const
virtual

Does the graph contain only directed edges?

Returns
true if all the vertices are directed, true otherwise
virtual bool Graph::isUndirected ( ) const
virtual

Does the graph contain only undirected edges?

Returns
tue if all the vertices are undirected, false otherwise
size_t Graph::order ( ) const

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

Returns
number of vertices in the graph
Vertex* Graph::randomVertex ( ) const

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

Returns
a random vertex
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 596 of file graph.h.

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 611 of file graph.h.

void Graph::removeEdge ( Edge edge)
throw (std::range_error
)

Delete and remove an edge from the graph.

The pointer becomes invalid and should not be used afterwards.

Parameters
edgepointer to the edge to remove
Exceptions
range_errorif edge is not in the graph
void Graph::removeVertex ( Vertex vertex)
throw (std::range_error
)

Delete and remove a vertex from the graph.

The pointer becomes invalid and should not be used afterwards.

Parameters
vertexpointer to the vertex to remove
Exceptions
range_errorif vertex is not in the graph
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 604 of file graph.h.

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 619 of file graph.h.

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_t Graph::size ( )
const std::set< Vertex * > & Graph::vertices ( ) const
inline

Return the vertices of the graph.

Returns
the internal collection of vertex pointers

Definition at line 483 of file graph.h.

Member Data Documentation

FactoryPtr Graph::_factory
protected

Abstract factory used to create vertices and edges.

Definition at line 449 of file graph.h.


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