MorphoGraphX
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Types | Public Member Functions | Static Public Attributes | Protected Types | Protected Member Functions | Protected Attributes | List of all members
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc > Class Template Reference

Class representing a VV graph. More...

Classes

struct  neighbor_t
 Structure maintaining the data for a single neighbor. More...
 
struct  NeighborhoodPair
 
struct  search_result_t
 Type of the result of the search for a vertex in a neighborhood. More...
 
struct  single_neighborhood_t
 Type of the neighborhood of a vertex. More...
 

Public Types

typedef Alloc::template rebind
< EdgeContent >::other 
EdgeAlloc
 
typedef vertex_t value_type
 Type of the value of the graph as standard container.
 
typedef Alloc::template rebind
< NeighborhoodPair >::other 
NPAlloc
 
typedef std::vector
< NeighborhoodPair * > 
neighborhood_t
 Type of the list of vertexes, together with the neighborhood.
 
typedef std::unordered_map
< vertex_t, NeighborhoodPair * > 
lookup_t
 Type of the fast-search map.
 
typedef neighborhood_t::value_type neighborhood_value_type
 Shortcut for the value_type of the neighborhood.
 
typedef neighborhood_t::size_type size_type
 Type of a size.
 
Smart pointer types
typedef Alloc::template rebind
< VertexContent >::other 
VertexAlloc
 Smart pointer on a vertex.
 
typedef Vertex< VertexContent,
VertexAlloc
vertex_t
 
typedef Edge< EdgeContent > edge_t
 Weak pointer on an edge.
 
typedef Edge< const EdgeContent > const_edge_t
 Weak pointer on a constant edge.
 
Iterators
typedef
util::SelectMemberPointerIterator
< typename
neighborhood_t::iterator,
const vertex_t,&NeighborhoodPair::vertex > 
iterator
 Iterator on the vertexes.
 
typedef
util::SelectMemberPointerIterator
< typename
neighborhood_t::const_iterator,
const vertex_t,&NeighborhoodPair::vertex > 
const_iterator
 Constant iterator on the vertexes.
 
typedef
util::SelectMemberIterator
< typename
edge_list_t::iterator,
vertex_t,&neighbor_t::target
neighbor_iterator
 Iterator on the neighbors of a vertex.
 
typedef std::pair
< neighbor_iterator,
neighbor_iterator
neighbor_iterator_pair
 Range of the neighbors of a vertex. More...
 
typedef util::CircIterator
< neighbor_iterator
circ_neighbor_iterator
 Iterator used to iterate over the neighbors, but specifying the starting point.
 
typedef std::pair
< circ_neighbor_iterator,
circ_neighbor_iterator
circ_neighbor_iterator_pair
 Range of circular iterators.
 
typedef in_edges_t::iterator ineighbor_iterator
 Iterator on the incoming neighbors of a vertex. More...
 
typedef in_edges_t::const_iterator const_ineighbor_iterator
 
typedef std::pair
< ineighbor_iterator,
ineighbor_iterator
ineighbor_iterator_pair
 Range of the incoming neighbors of a vertex. More...
 
typedef std::pair
< const_ineighbor_iterator,
const_ineighbor_iterator > 
const_ineighbor_iterator_pair
 
typedef
util::SelectMemberIterator
< typename
edge_list_t::const_iterator,
const vertex_t,&neighbor_t::target
const_neighbor_iterator
 Constant iterator on the neighbors of a vertex.
 
typedef std::pair
< const_neighbor_iterator,
const_neighbor_iterator
const_neighbor_iterator_pair
 Constant range of the neighbors of a vertex. More...
 
typedef util::CircIterator
< const_neighbor_iterator
const_circ_neighbor_iterator
 Iterator used to iterate over the neighbors, but spcifying the starting point.
 
typedef std::pair
< const_circ_neighbor_iterator,
const_circ_neighbor_iterator
const_circ_neighbor_iterator_pair
 Range of circular iterators.
 

Public Member Functions

 VVGraph ()
 Default constructor. More...
 
 VVGraph (const VVGraph &copy)
 Copy constructor. More...
 
template<typename Iterator >
 VVGraph (Iterator begin, Iterator end, bool check_unique=true)
 Construct from an existing list of vertices. More...
 
template<typename Container >
 VVGraph (const Container &c, bool check_unique=true)
 Construct from an existing list of vertices. More...
 
template<typename VertexContainer >
VVGraph< VertexContent,
EdgeContent, Alloc > 
subgraph (const VertexContainer &verts) const
 
Vertex set edition methods
size_type erase (const vertex_t &v)
 Remove a vertex from the graph. More...
 
iterator insert (const vertex_t &v)
 Insert a new vertex in the graph. More...
 
Vertex set lookup methods
const vertex_tany () const
 Return a vertex from the graph. More...
 
const vertex_toperator[] (size_type idx) const
 Return the element of index idx. More...
 
bool contains (const vertex_t &v) const
 Test if v is in the graph. More...
 
const vertex_treference (vertex_t v) const
 Get a reference on the vertex in the graph. More...
 
size_type size () const
 Return the number of vertexes on the graph.
 
bool empty () const
 Test if there is any vertex in the graph.
 
Neighborhood lookup methods
const vertex_tanyIn (const vertex_t &v) const
 Return a vertex in the neighborhood of v. More...
 
size_type valence (const vertex_t &v) const
 Returns the number of neighbors of v. More...
 
bool empty (const vertex_t &v) const
 Test if a vertex has a neighbor. More...
 
const vertex_tiAnyIn (const vertex_t &v) const
 Returns any incoming neighbor of v. More...
 
size_type iValence (const vertex_t &v) const
 Returns the number of incoming neighbors of v. More...
 
bool iEmpty (const vertex_t &v) const
 Test if a vertex has an incoming neighbor. More...
 
const vertex_tnextTo (const vertex_t &v, const vertex_t &neighbor, unsigned int n=1) const
 Returns the nth vertex after neighbor in the neighborhood of v. More...
 
const vertex_tprevTo (const vertex_t &v, const vertex_t &ref, unsigned int n=1) const
 Returns the nth vertex before ref in the neighborhood of v. More...
 
edge_t edge (const vertex_t &src, const vertex_t &tgt)
 Returns the edge from src to tgt. More...
 
const_edge_t edge (const vertex_t &src, const vertex_t &tgt) const
 Returns the edge from src to tgt. More...
 
bool flag (const vertex_t &src, const vertex_t &neighbor)
 Flag a neighbor for quick retrieval. More...
 
const vertex_tflagged (const vertex_t &src) const
 Return the flagged neighbor or a null vertex is no neighbor have been flagged. More...
 
const_neighbor_iterator_pair neighbors (const vertex_t &v) const
 Return the constant range of neighbors of v. More...
 
neighbor_iterator_pair neighbors (const vertex_t &v)
 Return the range of neighbors of v. More...
 
circ_neighbor_iterator_pair neighbors (const vertex_t &v, const vertex_t &n)
 Return the range of neighbors of v, starting at n. More...
 
const_circ_neighbor_iterator_pair neighbors (const vertex_t &v, const vertex_t &n) const
 Return the range of neighbors of v, starting at n. More...
 
ineighbor_iterator_pair iNeighbors (const vertex_t &v)
 Return the range of incoming neighbors of v. More...
 
const_ineighbor_iterator_pair iNeighbors (const vertex_t &v) const
 Return the range of incoming neighbors of v. More...
 
const vertex_tsource (const edge_t &edge) const
 Return the source vertex of the edge. More...
 
const vertex_ttarget (const edge_t &edge) const
 Return the target vertex of the edge. More...
 
Neighborhood edition methods
size_type eraseEdge (const vertex_t &src, const vertex_t &tgt)
 Erase the edge from src to tgt. More...
 
edge_t replace (const vertex_t &v, const vertex_t &neighbor, const vertex_t &new_neighbor)
 Replace a vertex by another in a neighborhood. More...
 
edge_t spliceAfter (const vertex_t &v, const vertex_t &neighbor, const vertex_t &new_neighbor)
 Insert neighbor in the neighborhood of v after reference. More...
 
edge_t spliceBefore (const vertex_t &v, const vertex_t &neighbor, const vertex_t &new_neighbor)
 Insert neighbor in the neighborhood of v before reference. More...
 
edge_t insertEdge (const vertex_t &src, const vertex_t &tgt)
 Insert a new edge in the graph, without ordering. More...
 
bool eraseAllEdges (const vertex_t &v)
 Clear the neighborhood of a vertex. More...
 
bool clear (const vertex_t &v)
 Clear the outgoing edges of a vertex. More...
 
Whole structure methods
VVGraphoperator= (const VVGraph &other)
 Copy the graph into another graph.
 
VVGraphreverse ()
 Reverse the order of all the neighbors.
 
void swap (VVGraph &other)
 Swap the content of both graphs.
 
bool operator== (const VVGraph &other) const
 Test equality for the graphs. More...
 
void clear ()
 Clear the graph.
 
void eraseAllEdges ()
 Clear all the edges in the graph. More...
 
template<typename VertexContainer >
VVGraph subgraph (const VertexContainer &vertexes) const
 Extract the subgraph containing the vertexes. More...
 
STL compatibility methods
void erase (iterator pos)
 Erase element at position pos.
 
size_type eraseEdge (const vertex_t &v, neighbor_iterator pos)
 Erase the edge pointed to by the iterator.
 
size_type eraseEdge (const vertex_t &v, circ_neighbor_iterator pos)
 Erase the edge pointed to by the iterator.
 
iterator insert (iterator pos, const vertex_t &v)
 Insert a new vertex in the graph. More...
 
template<typename Iterator >
void insert (Iterator first, Iterator last, bool check_unique=true)
 Insert all the vertexes from first to last-1 in the graph.
 
template<typename Iterator >
void insert (const std::pair< Iterator, Iterator > &range, bool check_unique=true)
 Insert all the vertexes from range.first to range.last-1 in the graph.
 
iterator begin ()
 Returns an iterator on the beginning of the set of vertexes of the graph.
 
iterator end ()
 Returns an iterator on the end of the set of vertexes of the graph.
 
const_iterator begin () const
 Returns an iterator on the beginning of the set of vertexes of the graph.
 
const_iterator end () const
 Returns an iterator on the end of the set of vertexes of the graph.
 
size_type count (const vertex_t &v) const
 Count the number of vertexes v in the graph (can be 0 or 1 only)
 
neighbor_iterator findIn (const vertex_t &v, const vertex_t &n)
 Find the vertex n in the neighborhood of v. More...
 
const_neighbor_iterator findIn (const vertex_t &v, const vertex_t &n) const
 Find the vertex n in the neighborhood of v. More...
 
void eraseAllEdges (iterator it)
 Clear the neighborhood of a vertex. More...
 
void clear (iterator it)
 Clear the outgoing edges of a vertex.
 
void reserve (size_type s)
 Reserve space for more vertices.
 

Static Public Attributes

static EdgeAlloc edge_alloc
 
static NPAlloc np_alloc
 

Protected Types

typedef neighbor_t::edge_list_t edge_list_t
 Type of the list of outgoing neighbors.
 
typedef std::vector< vertex_tin_edges_t
 Type of the list of sources of the in-edges.
 
typedef edge_list_t::iterator int_neighbor_iterator
 Iterator on the outgoing edges.
 
typedef edge_list_t::const_iterator int_const_neighbor_iterator
 Constant iterator on the outgoing edges.
 
typedef search_result_t
< single_neighborhood_t,
int_neighbor_iterator
neighbor_found_t
 Result of a search in the neighborhood.
 
typedef search_result_t< const
single_neighborhood_t,
int_const_neighbor_iterator
const_neighbor_found_t
 Constant result of a search in the neighborhood.
 

Protected Member Functions

void eraseAllEdges (NeighborhoodPair *it)
 
NeighborhoodPairfindVertex (const vertex_t &v)
 Find a vertex in the graph and returns the iterator on it. More...
 
const NeighborhoodPairfindVertex (const vertex_t &v) const
 Constant version of findVertex(const vertex_t&)
 
neighborhood_t::iterator findIterator (const NeighborhoodPair *np)
 Find the iterator for a given neighborhood pair.
 
neighborhood_t::const_iterator findIterator (const NeighborhoodPair *np) const
 
neighbor_found_t findInVertex (const vertex_t &v, const vertex_t &neighbor)
 Find a vertex neighbor in the neighborhood of v. More...
 
const_neighbor_found_t findInVertex (const vertex_t &v, const vertex_t &neighbor) const
 Constant version of findInVertex(const vertex_t&, const vertex_t&)
 
std::pair< ineighbor_iterator,
bool > 
insertInEdge (const vertex_t &v, const vertex_t &new_neighbor)
 Insert v in the in_edges of new_neighbor and return true if the insertion was actually done, or false if v was already there.
 
void undoInEdge (const vertex_t &new_neighbor, ineighbor_iterator &it)
 Undo the insertion of an in edge as a roll-back mechanism if the whole edge insertion fails.
 

Protected Attributes

neighborhood_t neighborhood
 Main data structure containing everything.
 
lookup_t lookup
 Hash map to optimise look-up.
 
bool modified_vertices
 If true, the vertex list has been modified.
 

Detailed Description

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
class mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >

Class representing a VV graph.

A VV graph is a graph rotation system, that is, a graph where the neighbors of vertices are stored in a circular order.

VertexContent is the type used to hold the vertex data.

EdgeContent is the type used to hold the edge data. If no type is specified for EdgeContent, then an empty structure is used.

Member Typedef Documentation

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
typedef std::pair<const_neighbor_iterator, const_neighbor_iterator> mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::const_neighbor_iterator_pair

Constant range of the neighbors of a vertex.

The first element of the pair is a constant iterator on the beginning of the range, the second element is the past-the-end constant iterator.

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
typedef in_edges_t::iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::ineighbor_iterator

Iterator on the incoming neighbors of a vertex.

An incoming neighbor is a source vertex of an edge whose target is the current vertex.

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
typedef std::pair<ineighbor_iterator, ineighbor_iterator> mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::ineighbor_iterator_pair

Range of the incoming neighbors of a vertex.

The first element of the pair is an iterator on the beginning of the range, the second element is the past-the-end iterator.

See Also
ineighbor_iterator
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
typedef std::pair<neighbor_iterator, neighbor_iterator> mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::neighbor_iterator_pair

Range of the neighbors of a vertex.

The first element of the pair is an iterator on the beginning of the range, the second element is the past-the-end iterator.

Constructor & Destructor Documentation

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::VVGraph ( )
inline

Default constructor.

Creates an empty VV graph

template<typename VertexContent , typename EdgeContent , typename Alloc >
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::VVGraph ( const VVGraph< VertexContent, EdgeContent, Alloc > &  copy)

Copy constructor.

Maintains the caches in a valid state

template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
template<typename Iterator >
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::VVGraph ( Iterator  begin,
Iterator  end,
bool  check_unique = true 
)
inline

Construct from an existing list of vertices.

Parameters
check_uniqueIf false, there must be not be duplicated vertex in the sequence
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
template<typename Container >
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::VVGraph ( const Container &  c,
bool  check_unique = true 
)
inline

Construct from an existing list of vertices.

Parameters
check_uniqueIf false, there must be not be duplicated vertex in the sequence

Member Function Documentation

template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::any ( ) const

Return a vertex from the graph.

Returns
A vertex of the graph, or a null vertex if the graph is empty.

Example:

// Add vertices in S
const vertex& v = S.any(); // Get a vertex in S
template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::anyIn ( const vertex_t v) const

Return a vertex in the neighborhood of v.

Returns
A vertex in the neighborhood of v, or a null vertex if v is not in the graph or v has no neighborhood.

Example:

forall(const vertex& v, S)
{
const vertex& n = S.anyIn(v);
if(n)
{
edge e = S.edge(v,n); // e exist !
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::clear ( const vertex_t v)

Clear the outgoing edges of a vertex.

Example:

// Initialize S
forall(const vertex& v, S)
{
if(condition)
{
S.clear(v);
assert(S.empty(v));
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::contains ( const vertex_t v) const

Test if v is in the graph.

Returns
true is v is in the graph.

Example:

vertex v;
S.insert(v);
assert(S.contains(v));
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::edge ( const vertex_t src,
const vertex_t tgt 
)

Returns the edge from src to tgt.

If the edge does not exists, returns a null edge.

Example:

struct VertexContent {};
struct EdgeContent { int a; }
typedef graph::VVGraph<VertexContent,EdgeContent> vvgraph;
typedef vvgraph::vertex_t vertex;
// ...
vvgraph S;
// initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
edge e = S.edge(v,n);
e->a = 10;
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::const_edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::edge ( const vertex_t src,
const vertex_t tgt 
) const

Returns the edge from src to tgt.

If the edge does not exists, returns a null edge.

Example:

struct VertexContent {};
struct EdgeContent { int a; }
typedef graph::VVGraph<VertexContent,EdgeContent> vvgraph;
typedef vvgraph::vertex_t vertex;
typedef vvgraph::const_edge_t const_edge;
// ...
void fct(const vvgraph& S)
{
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
const_edge e = S.edge(v,n);
cout << e->a << endl; // Here e->a cannot be modified
}
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::empty ( const vertex_t v) const

Test if a vertex has a neighbor.

Returns false if it does. If a vertex is not in the graph, it is considered as having no neighbor. In the same way, the null vertex has no neighbors.

Example:

vvgraph S;
// initialize S
forall(cnst vertex& v, S)
{
if(!S.empty(v))
{
const vertex& n = S.anyIn(v);
// Working with n a neighbor of v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::size_type mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::erase ( const vertex_t v)

Remove a vertex from the graph.

Parameters
vvertex to erase
Returns
1 if the vertex was erased, 0 else.

Example:

vvgraph S;
// Add vertices to S
vertex v = S.any();
S.erase(v); // Remove a vertex of S
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::eraseAllEdges ( const vertex_t v)

Clear the neighborhood of a vertex.

All edges, to and from v will be erased.

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
if(condition)
{
S.eraseAllEdges(v);
assert(S.empty(v)); // No outgoing edges
assert(S.iEmpty(v)); // No incoming edges
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
void mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::eraseAllEdges ( )

Clear all the edges in the graph.

Example:

vvgraph S;
// Initialize S
vvgraph::size_type s1 = S.size(); // Save the number of vertices
S.eraseAllEdges();
assert(s1 == S.size()); // The number of vertices didn't change
forall(const vertex& v, S)
{
assert(S.empty(v)); // No neighbor
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
void mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::eraseAllEdges ( iterator  it)

Clear the neighborhood of a vertex.

All edges, to and from *it will be erased.

template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::size_type mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::eraseEdge ( const vertex_t src,
const vertex_t tgt 
)

Erase the edge from src to tgt.

Returns
True if successful.

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
if(condition)
{
S.eraseEdge(v,n);
break; // The iteration must not continue after the neighborhood has been altered
}
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::neighbor_iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::findIn ( const vertex_t v,
const vertex_t n 
)

Find the vertex n in the neighborhood of v.

Returns
  • An iterator on n in the neighborhood of v, if found
  • An iterator on the end of the neighborhood if n is not found in v
  • Otherwise, the result is undefined
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::const_neighbor_iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::findIn ( const vertex_t v,
const vertex_t n 
) const

Find the vertex n in the neighborhood of v.

Returns
  • An iterator on n in the neighborhood of v, if found
  • An iterator on the end of the neighborhood if n is not found in v
  • Otherwise, the result is undefined
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::neighbor_found_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::findInVertex ( const vertex_t v,
const vertex_t neighbor 
)
protected

Find a vertex neighbor in the neighborhood of v.

If 'v' is in the graph and 'neighbor' is in its neighborhood, the result is convertible to true, 'neighborhood' points toward the neighborhood structure and 'it' points toward the neighbor.

If 'v' is in the graph, but 'neighbor' is not in the neighborhood, the result is convertible to false, 'neighborhood' points toward the neighborhood structure and 'it' is neighborhood->edges.end().

If v is not in the graph, the result is convertible to false and the address of the stored neighborhood is 0.

template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::NeighborhoodPair * mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::findVertex ( const vertex_t v)
protected

Find a vertex in the graph and returns the iterator on it.

Goal is to introduce a new optimization. When iterating over the vertices of the graph, they will cache their own iterator. So accessing their neighborhood would be constant time.

template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::flag ( const vertex_t src,
const vertex_t neighbor 
)

Flag a neighbor for quick retrieval.

Returns
true if the vertex has been correctly flagged

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
if(condition(v,n))
{
S.flag(v,n);
break;
}
}
}
// ...
forall(const vertex& v, S)
{
const vertex& n = S.flagged(v);
if(n) // If a neighbor has been flagged
{
// Work with the flagged neighbor
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::flagged ( const vertex_t src) const

Return the flagged neighbor or a null vertex is no neighbor have been flagged.

See Also
VVGraph::flag(const vertex_t&, const vertex_t&)
template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::iAnyIn ( const vertex_t v) const

Returns any incoming neighbor of v.

Returns
A vertex in the incoming neighborhood of v, or a null vertex if v is not in the graph or v has no incoming neighbor.

Example:

vvgraph S;
// initialize S
forall(const vertex& n, S)
{
const vertex& v = S.iAnyIn(v);
if(v)
{
edge e = S.edge(v, n);
// Work with e the edge from v to n
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::iEmpty ( const vertex_t v) const

Test if a vertex has an incoming neighbor.

Returns false if it does. If a vertex is not in the graph, it is considered as having no incoming neighbor. In the same way, the null vertex has no incoming neighbors.

Example:

vvgraph S;
// initialize S
forall(const vertex& n, S)
{
if(!S.iEmpty(n))
{
const vertex& v = S.iAnyIn(n);
edge e = S.edge(v,n); // It exists !
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::ineighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::iNeighbors ( const vertex_t v)

Return the range of incoming neighbors of v.

Iterating over iNeighbors will go through all the vertexes having an edge toward v.

Example:

vvgraph S;
// initialize S
forall(const vertex& n, S)
{
forall(const vertex& v, S.iNeighbors(v))
{
// n is a neighbor of v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::const_ineighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::iNeighbors ( const vertex_t v) const

Return the range of incoming neighbors of v.

Iterating over iNeighbors will go through all the vertexes having an edge toward v.

Example:

vvgraph S;
// initialize S
forall(const vertex& n, S)
{
forall(const vertex& v, S.iNeighbors(v))
{
// n is a neighbor of v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::insert ( const vertex_t v)

Insert a new vertex in the graph.

Returns
An iterator on the inserted vertex.

Example:

vvgraph S;
vertex v; // Create a vertex
S.insert(v); // Insert it in the graph
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::insert ( iterator  pos,
const vertex_t v 
)

Insert a new vertex in the graph.

The iterator is ignored ...

template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::insertEdge ( const vertex_t src,
const vertex_t tgt 
)

Insert a new edge in the graph, without ordering.

If new_neighbor is already in the neighborhood of v, the insertion fails.

Returns
The just created edge if everything succeed, or a null edge.

Example:

vvgraph S;
vertex v1, v2;
S.insert(v1);
S.insert(v2);
S.insertEdge(v1, v2); // Insert the edge between v1 and v2
S.insertEdge(v2, v1); // Insert the edge between v2 and v1
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::size_type mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::iValence ( const vertex_t v) const

Returns the number of incoming neighbors of v.

The incoming neighbors are the set of vertexes with on edge ending on v.

Example:

vvgraph S;
// initialize S
forall(const vertex& n, S)
{
size_t nb_ineighbors = S.iValence(n);
// nb_ineighbors is the number of vertices source of an edge toward n
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::const_neighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::neighbors ( const vertex_t v) const

Return the constant range of neighbors of v.

Example:

vvgraph S;
// initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
// n is a neighbor of v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::neighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::neighbors ( const vertex_t v)

Return the range of neighbors of v.

Example:

vvgraph S;
// initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
// n is a neighbor of v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::circ_neighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::neighbors ( const vertex_t v,
const vertex_t n 
)

Return the range of neighbors of v, starting at n.

Example:

vvgraph S;
// initialize S
forall(const vertex& m, S.neighbors(v,n))
{
// m is a neighbor of v
// on the first loop, m == n
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::const_circ_neighbor_iterator_pair mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::neighbors ( const vertex_t v,
const vertex_t n 
) const

Return the range of neighbors of v, starting at n.

Example:

vvgraph S;
// initialize S
forall(const vertex& m, S.neighbors(v,n))
{
// m is a neighbor of v
// on the first loop, m == n
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::nextTo ( const vertex_t v,
const vertex_t neighbor,
unsigned int  n = 1 
) const

Returns the nth vertex after neighbor in the neighborhood of v.

Returns
The vertex found or a null vertex if there is any problem.

Example:

vvgraph S;
// initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
const vertex& m, S.nextTo(v);
// m is the vertex after n in v
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::operator== ( const VVGraph< VertexContent, EdgeContent, Alloc > &  other) const

Test equality for the graphs.

Two graphs are equal if they shared the sames vertices and their neighborhood are equivalent.

Note
Current implementation do not consider invariance of neighborhood by rotation.
template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::operator[] ( size_type  idx) const

Return the element of index idx.

Note
This is a convenience function whose complexity if O(idx)
Returns
The element idx position after the first one (using iterators)

Example:

vvgraph S;
// Fill in S
size_t i = 0, selected = 0;
forall(const vertex& v, S)
{
if(condition(v))
{
selected = i;
break;
}
++i;
}
// ...
const vertex& v = S[selected]; // Work with the vertex previously selected

This construct is useful is case you need to refer to your vertices by 32bits numbers. It is true if you use selection with OpenGL for example.

template<typename VertexContent , typename EdgeContent , typename Alloc >
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::prevTo ( const vertex_t v,
const vertex_t ref,
unsigned int  n = 1 
) const

Returns the nth vertex before ref in the neighborhood of v.

If ref is not in the neighborhood of v, return a null vertex.

Example:

vvgraph S;
// initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
const vertex& m, S.prevTo(v);
// m is the vertex before n in v
}
}
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
const vertex_t& mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::reference ( vertex_t  v) const
inline

Get a reference on the vertex in the graph.

If the vertex do not exist in the graph, the function returns a null vertex.

Note
This function is useful if you obtained the vertex not from this graph but will use it intensively.

Example:

vvgraph S1, S2;
// Initialize S1 and S2 with the same vertices but different neighborhood
forall(const vertex& v1, S1)
{
const vertex& v2 = S2.reference(v1);
// Use v2 in S2 and v1 in v1 for speed optimizatioN
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::replace ( const vertex_t v,
const vertex_t neighbor,
const vertex_t new_neighbor 
)

Replace a vertex by another in a neighborhood.

Parameters
[in]vVertex whose neighborhood is changed.
[in]neighborVertex to replace
[in]new_neighborVertex replacing neighbor

If new_neighbor is already in the neighborhood of v, then the operation fails and nothing is changed.

Returns
The edge between v and new_neighbor or a null edge if anything goes wrong.

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
if(condition)
{
vertex n1;
S.replace(v,n,n1); // Now n1 is where n was in v
break; // The iteration must not continue after the neighborhood has been altered
}
}
}
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
const vertex_t& mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::source ( const edge_t edge) const
inline

Return the source vertex of the edge.

Example:

void fct(edge e, const vvgraph& S)
{
const vertex& src = S.source(e);
const vertex& tgt = S.target(e);
// Work with the vertices
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::spliceAfter ( const vertex_t v,
const vertex_t neighbor,
const vertex_t new_neighbor 
)

Insert neighbor in the neighborhood of v after reference.

If new_neighbor is already in the neighborhood of v, the insertion fails.

Returns
The just created edge if everything succeed, or a null edge.

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
if(condition)
{
vertex n1;
S.spliceAfter(v,n,n1); // Now n1 is after n in v
break; // The iteration must not continue after the neighborhood has been altered
}
}
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::edge_t mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::spliceBefore ( const vertex_t v,
const vertex_t neighbor,
const vertex_t new_neighbor 
)

Insert neighbor in the neighborhood of v before reference.

If new_neighbor is already in the neighborhood of v, the insertion fails.

Returns
The just created edge if everything succeed, or a null edge.

Example:

vvgraph S;
// Initialize S
forall(const vertex& v, S)
{
forall(const vertex& n, S.neighbors(v))
{
if(condition)
{
vertex n1;
S.spliceBefore(v,n,n1); // Now n1 is before n in v
break; // The iteration must not continue after the neighborhood has been altered
}
}
}
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
template<typename VertexContainer >
VVGraph mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::subgraph ( const VertexContainer &  vertexes) const

Extract the subgraph containing the vertexes.

The subgraph is the set of vertexes and the edges whose source and target are in the extracted vertexes.

Example:

vvgraph S;
// Initialize S
std::vector<vertex> to_keep;
// Fill in to_keep with a subset of the vertices of S
vvgraph S1 = S.subgraph(to_keep);
template<typename VertexContent, typename EdgeContent = _EmptyEdgeContent, typename Alloc = std::allocator<VertexContent>>
const vertex_t& mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::target ( const edge_t edge) const
inline

Return the target vertex of the edge.

Example:

void fct(edge e, const vvgraph& S)
{
const vertex& src = S.source(e);
const vertex& tgt = S.target(e);
// Work with the vertices
}
template<typename VertexContent , typename EdgeContent , typename Alloc >
VVGraph< VertexContent, EdgeContent, Alloc >::size_type mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::valence ( const vertex_t v) const

Returns the number of neighbors of v.

If v is not in the graph, the behavior is undefined.

Example:

vvgraph S;
// initialize S
forall(const vertex& v, S)
{
size_t nb_neighbors = S.valence(v); // Number of neighbors of v in S
// ...
}

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