MorphoGraphX
|
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 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_t & | any () const |
Return a vertex from the graph. More... | |
const vertex_t & | operator[] (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_t & | reference (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_t & | anyIn (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_t & | iAnyIn (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_t & | 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 . More... | |
const vertex_t & | 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. 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_t & | flagged (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_t & | source (const edge_t &edge) const |
Return the source vertex of the edge. More... | |
const vertex_t & | target (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 | |
VVGraph & | operator= (const VVGraph &other) |
Copy the graph into another graph. | |
VVGraph & | reverse () |
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_t > | in_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) |
NeighborhoodPair * | findVertex (const vertex_t &v) |
Find a vertex in the graph and returns the iterator on it. More... | |
const NeighborhoodPair * | findVertex (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. | |
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.
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.
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.
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.
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.
|
inline |
Default constructor.
Creates an empty VV graph
mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::VVGraph | ( | const VVGraph< VertexContent, EdgeContent, Alloc > & | copy | ) |
Copy constructor.
Maintains the caches in a valid state
|
inline |
Construct from an existing list of vertices.
check_unique | If false, there must be not be duplicated vertex in the sequence |
|
inline |
Construct from an existing list of vertices.
check_unique | If false, there must be not be duplicated vertex in the sequence |
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::any | ( | ) | const |
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::anyIn | ( | const vertex_t & | v | ) | const |
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::clear | ( | const vertex_t & | v | ) |
Clear the outgoing edges of a vertex.
Example:
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::contains | ( | const vertex_t & | v | ) | const |
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:
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:
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< VertexContent, EdgeContent, Alloc >::size_type mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::erase | ( | const vertex_t & | v | ) |
Remove a vertex from the graph.
v | vertex to erase |
Example:
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:
void mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::eraseAllEdges | ( | ) |
Clear all the edges in the graph.
Example:
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.
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
.
Example:
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
.
n
in the neighborhood of v
, if foundn
is not found in v
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
.
n
in the neighborhood of v
, if foundn
is not found in v
|
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.
|
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.
bool mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::flag | ( | const vertex_t & | src, |
const vertex_t & | neighbor | ||
) |
Flag a neighbor for quick retrieval.
Example:
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.
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
.
v
, or a null vertex if v
is not in the graph or v
has no incoming neighbor.Example:
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< 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< 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< VertexContent, EdgeContent, Alloc >::iterator mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::insert | ( | const vertex_t & | v | ) |
Insert a new vertex in the graph.
Example:
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 ...
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.
Example:
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< 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< 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< 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< 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:
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
.
Example:
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.
const VVGraph< VertexContent, EdgeContent, Alloc >::vertex_t & mgx::graph::VVGraph< VertexContent, EdgeContent, Alloc >::operator[] | ( | size_type | idx | ) | const |
Return the element of index idx
.
idx
position after the first one (using iterators)Example:
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.
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:
|
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.
Example:
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.
[in] | v | Vertex whose neighborhood is changed. |
[in] | neighbor | Vertex to replace |
[in] | new_neighbor | Vertex replacing neighbor |
If new_neighbor
is already in the neighborhood of v
, then the operation fails and nothing is changed.
v
and new_neighbor
or a null edge if anything goes wrong.Example:
|
inline |
Return the source vertex of the edge.
Example:
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.
Example:
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.
Example:
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:
|
inline |
Return the target vertex of the edge.
Example:
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: