22 #include <CircIterator.hpp> 27 #include <UnorderedMap.hpp> 42 namespace mgx {
namespace graph {
75 typename Alloc = std::allocator<VertexContent> >
78 typedef typename Alloc::template rebind<EdgeContent>::other EdgeAlloc;
79 static EdgeAlloc edge_alloc;
86 typedef typename Alloc::template rebind<VertexContent>::other
VertexAlloc;
122 template <
typename Iterator>
VVGraph(Iterator begin, Iterator end,
bool check_unique =
true)
124 insert(begin, end, check_unique);
132 template <
typename Container>
VVGraph(
const Container& c,
bool check_unique =
true)
134 insert(util::ForAll::make_range(c), check_unique);
138 struct single_neighborhood_t;
152 neighbor_t(
const vertex_t& tgt,
const EdgeContent& e) : EdgeContent(e), target(tgt) {}
157 static_cast<EdgeContent&
>(*this) = EdgeContent();
165 static_cast<EdgeContent&
>(*this) =
static_cast<const EdgeContent&
>(copy);
184 return (target == other.
target)
185 && (
static_cast<const EdgeContent&
>(*this) ==
static_cast<const EdgeContent&
>(other));
210 for(
typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
211 if(it->target == *flagged) {
212 flagged = &it->target;
239 for(
typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
240 if(it->target == *flagged) {
241 flagged = &it->target;
256 return edges == other.
edges;
266 :
vertex(copy.vertex), single_neighborhood(copy.single_neighborhood) {}
286 np->~NeighborhoodPair();
287 np_alloc.deallocate(np, 1);
295 typedef typename Alloc::template rebind<NeighborhoodPair>::other NPAlloc;
296 static NPAlloc np_alloc;
307 typedef std::unordered_map<vertex_t, NeighborhoodPair*>
lookup_t;
325 typedef const vertex_t
typename std::iterator_traits<typename neighborhood_t::iterator>::value_type::*
326 msvc_bug_workaround_t;
329 reinterpret_cast<msvc_bug_workaround_t
>(&neighborhood_value_type::first)>
376 typedef typename in_edges_t::const_iterator const_ineighbor_iterator;
386 typedef std::pair<const_ineighbor_iterator, const_ineighbor_iterator> const_ineighbor_iterator_pair;
431 size_type erase(
const vertex_t& v);
445 iterator insert(
const vertex_t& v);
464 const vertex_t& any()
const;
495 const vertex_t& operator[](size_type idx)
const;
510 bool contains(
const vertex_t& v)
const;
534 const NeighborhoodPair* found = this->findVertex(v);
536 return found->vertex;
537 return vertex_t::null;
544 return neighborhood.size();
551 return neighborhood.empty();
578 const vertex_t& anyIn(
const vertex_t& v)
const;
596 size_type valence(
const vertex_t& v)
const;
619 bool empty(
const vertex_t& v)
const;
642 const vertex_t& iAnyIn(
const vertex_t& v)
const;
661 size_type iValence(
const vertex_t& v)
const;
684 bool iEmpty(
const vertex_t& v)
const;
705 const vertex_t& nextTo(
const vertex_t& v,
const vertex_t& neighbor,
unsigned int n = 1)
const;
726 const vertex_t& prevTo(
const vertex_t& v,
const vertex_t& ref,
unsigned int n = 1)
const;
754 edge_t
edge(
const vertex_t& src,
const vertex_t& tgt);
784 const_edge_t
edge(
const vertex_t& src,
const vertex_t& tgt)
const;
817 bool flag(
const vertex_t& src,
const vertex_t& neighbor);
824 const vertex_t& flagged(
const vertex_t& src)
const;
842 const_neighbor_iterator_pair neighbors(
const vertex_t& v)
const;
859 neighbor_iterator_pair neighbors(
const vertex_t& v);
875 circ_neighbor_iterator_pair neighbors(
const vertex_t& v,
const vertex_t& n);
891 const_circ_neighbor_iterator_pair neighbors(
const vertex_t& v,
const vertex_t& n)
const;
912 ineighbor_iterator_pair iNeighbors(
const vertex_t& v);
933 const_ineighbor_iterator_pair iNeighbors(
const vertex_t& v)
const;
948 const vertex_t&
source(
const edge_t& edge)
const 950 const NeighborhoodPair* found = this->findVertex(vertex_t(edge.
source()));
952 return found->vertex;
953 return vertex_t::null;
969 const vertex_t&
target(
const edge_t& edge)
const 971 const NeighborhoodPair* found = this->findVertex(vertex_t(edge.
target()));
973 return found->vertex;
974 return vertex_t::null;
1003 size_type eraseEdge(
const vertex_t& src,
const vertex_t& tgt);
1036 edge_t replace(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1064 edge_t spliceAfter(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1092 edge_t spliceBefore(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1112 edge_t insertEdge(
const vertex_t& src,
const vertex_t& tgt);
1134 bool eraseAllEdges(
const vertex_t& v);
1153 bool clear(
const vertex_t& v);
1183 bool operator==(
const VVGraph& other)
const;
1206 void eraseAllEdges();
1223 template <
typename VertexContainer>
VVGraph subgraph(
const VertexContainer& vertexes)
const;
1232 void erase(iterator pos);
1237 size_type eraseEdge(
const vertex_t& v, neighbor_iterator pos);
1242 size_type eraseEdge(
const vertex_t& v, circ_neighbor_iterator pos);
1249 iterator insert(iterator pos,
const vertex_t& v);
1253 template <
typename Iterator>
void insert(Iterator first, Iterator last,
bool check_unique =
true);
1258 template <
typename Iterator>
void insert(
const std::pair<Iterator, Iterator>& range,
bool check_unique =
true);
1264 return neighborhood.begin();
1270 return neighborhood.end();
1277 return neighborhood.begin();
1283 return neighborhood.end();
1289 size_type count(
const vertex_t& v)
const;
1300 neighbor_iterator findIn(
const vertex_t& v,
const vertex_t& n);
1317 void eraseAllEdges(iterator it);
1322 void clear(iterator it);
1328 neighborhood.reserve(s);
1334 void eraseAllEdges(NeighborhoodPair* it);
1353 : found(ok) , it(i), neighborhood(n) {}
1359 : found(copy.found), it(copy.it), neighborhood(copy.neighborhood) {}
1407 NeighborhoodPair* findVertex(
const vertex_t& v);
1412 const NeighborhoodPair* findVertex(
const vertex_t& v)
const;
1417 typename neighborhood_t::iterator findIterator(
const NeighborhoodPair* np);
1418 typename neighborhood_t::const_iterator findIterator(
const NeighborhoodPair* np)
const;
1434 neighbor_found_t findInVertex(
const vertex_t& v,
const vertex_t& neighbor);
1439 const_neighbor_found_t findInVertex(
const vertex_t& v,
const vertex_t& neighbor)
const;
1445 std::pair<ineighbor_iterator, bool> insertInEdge(
const vertex_t& v,
const vertex_t& new_neighbor);
1451 void undoInEdge(
const vertex_t& new_neighbor, ineighbor_iterator& it);
1469 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1471 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1474 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1477 typename neighborhood_t::iterator it;
1478 for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1479 NeighborhoodPair::Delete(*it);
1482 neighborhood.clear();
1486 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1491 NeighborhoodPair::Delete(*it.
base());
1492 *it.
base() = neighborhood.back();
1493 neighborhood.pop_back();
1496 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1500 if(eraseAllEdges(v)) {
1503 typename neighborhood_t::iterator it = this->findIterator(np);
1504 NeighborhoodPair::Delete(np);
1505 *it = neighborhood.back();
1506 neighborhood.pop_back();
1511 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1514 for(
typename neighborhood_t::iterator it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1515 it->single_neighborhood.edges.
clear();
1516 it->single_neighborhood.in_edges.clear();
1517 it->single_neighborhood.flagged = 0;
1521 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1526 eraseAllEdges(it_found);
1532 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1536 for(
typename edge_list_t::iterator it_el = np->single_neighborhood.
edges.begin();
1537 it_el != np->single_neighborhood.
edges.end(); ++it_el) {
1538 in_edges_t& ie = lookup[it_el->target]->single_neighborhood.in_edges;
1539 typename in_edges_t::iterator it_found = std::find(ie.begin(), ie.end(), v);
1542 np->single_neighborhood.
edges.clear();
1543 np->single_neighborhood.
flagged = 0;
1546 for(
typename in_edges_t::iterator it = in_edges.begin(); it != in_edges.end(); ++it) {
1555 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1558 eraseAllEdges(*it_found.
base());
1561 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1564 typename neighborhood_t::iterator it_found = this->findVertex(v);
1565 if(it_found != neighborhood.end()) {
1572 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1576 for(
typename edge_list_t::iterator it_el = it.
base()->single_neighborhood.edges.begin();
1577 it_el != it.
base()->single_neighborhood.edges.end(); ++it_el) {
1578 typename neighborhood_t::iterator it_found = this->findVertex(it_el->target);
1579 in_edges_t& ie = it_found->single_neighborhood.in_edges;
1580 typename in_edges_t::iterator it_found2 = std::find(ie.begin(), ie.end(), v);
1581 ie.erase(it_found2);
1583 it.
base()->single_neighborhood.edges.clear();
1586 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1590 return lookup.
count(v);
1593 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1597 typename lookup_t::iterator it_found = lookup.find(v);
1598 if(it_found == lookup.end()) {
1600 neighborhood.push_back(np);
1606 return findIterator(it_found->second);
1609 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1613 return this->insert(v);
1616 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1617 template <
typename Iterator>
1620 insert(range.first, range.second, check_unique);
1623 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1624 template <
typename Iterator>
1628 for(Iterator it = first; it != last; ++it) {
1632 for(Iterator it = first; it != last; ++it) {
1634 neighborhood.push_back(np);
1640 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1644 if(neighborhood.empty())
1645 return vertex_t::null;
1649 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1653 typename neighborhood_t::const_iterator it = neighborhood.
begin();
1654 std::advance(it, idx);
1655 return (*it)->vertex;
1658 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1663 return vertex_t::null;
1665 if(not it_found || it_found->single_neighborhood.
edges.empty())
1666 return vertex_t::null;
1668 return lst.front().target;
1671 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1680 return it_found->single_neighborhood.edges.size();
1683 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1691 return it_found->single_neighborhood.edges.empty();
1694 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1699 return vertex_t::null;
1701 if(not it_found || it_found->single_neighborhood.
in_edges.empty())
1702 return vertex_t::null;
1704 return *lst.begin();
1707 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1716 return it_found->single_neighborhood.in_edges.size();
1719 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1727 return it_found->single_neighborhood.in_edges.empty();
1730 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1734 return std::find(neighborhood.begin(), neighborhood.end(), np);
1737 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1741 return std::find(neighborhood.begin(), neighborhood.end(), np);
1744 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1748 typename lookup_t::const_iterator it_found = lookup.find(v);
1749 if(it_found != lookup.end())
1750 return it_found->second;
1754 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1758 typename lookup_t::const_iterator it_found = lookup.find(v);
1759 if(it_found != lookup.end())
1760 return it_found->second;
1764 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1773 edge_list_t& lst = it_found->single_neighborhood.edges;
1775 for(
typename edge_list_t::iterator it = lst.begin(); it != lst.end(); ++it) {
1776 if(it->target == n) {
1783 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1792 const edge_list_t& lst = it_found->single_neighborhood.edges;
1794 for(
typename edge_list_t::const_iterator it = lst.begin(); it != lst.end(); ++it) {
1795 if(it->target == n) {
1802 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1812 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1822 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1833 in_edges_t& ie = it_found2->single_neighborhood.in_edges;
1834 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1835 if(it_found_ie != ie.end()) {
1836 ie.erase(it_found_ie);
1837 typename edge_list_t::iterator it = pos.
base();
1838 it_found->single_neighborhood.edges.erase(it);
1844 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1848 return eraseEdge(v, pos.base());
1851 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1861 in_edges_t& ie = lookup[n]->single_neighborhood.in_edges;
1862 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1863 ie.erase(it_found_ie);
1867 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1870 return this->findVertex(v);
1873 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1874 std::pair<typename VVGraph<VertexContent, EdgeContent, Alloc>::ineighbor_iterator,
bool>
1877 typename lookup_t::iterator found = lookup.find(new_neighbor);
1878 if(found == lookup.end())
1880 in_edges_t& ie = found->second->single_neighborhood.in_edges;
1881 typename in_edges_t::iterator it_found = std::find(ie.begin(), ie.end(), v);
1882 if(it_found != ie.end())
1883 return std::make_pair(it_found,
false);
1887 return std::make_pair(it,
true);
1890 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1893 typename lookup_t::iterator found = lookup.find(new_neighbor);
1897 if(found == lookup.end())
1899 found->single_neighborhood.single_neighborhood.in_edges.
erase(it);
1902 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1907 if(new_neighbor.
isNull() or (v == new_neighbor) or (neighbor == new_neighbor))
1915 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
1919 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1920 ie.erase(it_found_ie);
1921 found.
it->target = new_neighbor;
1922 found.
it->clear_edge();
1923 if(n_found->single_neighborhood.
flagged and *n_found->single_neighborhood.
flagged == neighbor)
1924 n_found->single_neighborhood.
flagged = 0;
1928 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1934 return vertex_t::null;
1935 typename edge_list_t::const_iterator it = found.
it;
1937 for(
unsigned int i = 0; i < n; ++i) {
1945 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1951 return vertex_t::null;
1952 typename edge_list_t::const_iterator it = found.
it;
1954 for(
unsigned int i = 0; i < n; ++i) {
1955 if(it == lst.begin())
1962 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1972 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1982 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1992 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1997 if(not found or found->single_neighborhood.
flagged == 0)
1998 return vertex_t::null;
1999 return *found->single_neighborhood.
flagged;
2002 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2007 if(new_neighbor.
isNull() || v == new_neighbor)
2014 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2018 typename edge_list_t::iterator new_edge_it
2020 return edge_t(v.
id(), new_neighbor.
id(), &*new_edge_it);
2023 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2028 if(new_neighbor.
isNull() || v == new_neighbor)
2035 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2038 typename edge_list_t::iterator new_edge_it
2040 return edge_t(v.
id(), new_neighbor.
id(), &*new_edge_it);
2043 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2047 if(v.
isNull() || new_neighbor.
isNull() || v == new_neighbor)
2054 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2057 edge_list_t& lst = it_found->single_neighborhood.edges;
2058 lst.push_front(
neighbor_t(new_neighbor, EdgeContent()));
2059 typename edge_list_t::iterator it = lst.begin();
2060 return edge_t(v.
id(), new_neighbor.
id(), &*it);
2063 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2073 const edge_list_t& lst = it_found->single_neighborhood.edges;
2078 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2088 edge_list_t& lst = it_found->single_neighborhood.edges;
2094 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2110 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2126 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2127 typename VVGraph<VertexContent, EdgeContent, Alloc>::const_ineighbor_iterator_pair
2130 const_ineighbor_iterator_pair result;
2136 const in_edges_t& lst = it_found->single_neighborhood.in_edges;
2137 result.first = const_ineighbor_iterator(lst.begin());
2138 result.second = const_ineighbor_iterator(lst.end());
2142 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2152 in_edges_t& lst = it_found->single_neighborhood.in_edges;
2158 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2159 template <
typename VertexContainer>
2163 typename VertexContainer::const_iterator it;
2166 for(it = verts.begin(); it != verts.end(); ++it) {
2170 typename neighborhood_t::iterator it_n;
2171 typename edge_list_t::const_reverse_iterator it_sn;
2174 const vertex_t& v = (*it_n)->vertex;
2176 it_orign = this->findVertex(v);
2178 edge_list_t& lst = (*it_n)->single_neighborhood.edges;
2180 for(it_sn = orig_lst.rbegin(); it_sn != orig_lst.rend(); ++it_sn) {
2183 if(result.
contains(it_sn->target)) {
2187 lst.push_front(
neighbor_t(it_sn->target, *it_sn));
2193 (*it_n)->single_neighborhood.flagged = &(found.
it->target);
2199 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2201 : modified_vertices(false)
2206 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2213 typename lookup_t::const_iterator it_found = other.
lookup.find(v1);
2214 if(it_found == other.
lookup.end())
2216 if(it->single_neighborhood.edges.empty()) {
2217 if(!it_found->single_neighborhood.single_neighborhood.edges.empty())
2220 const edge_list_t& lst = it->single_neighborhood.edges;
2221 const edge_list_t& olst = it_found->second->single_neighborhood.edges;
2222 if(lst.size() != olst.size())
2224 const vertex_t& v2 = lst.begin()->target;
2226 for(
typename edge_list_t::const_iterator it_olst = olst.begin(); it_olst != olst.end(); ++it_olst) {
2227 if(it_olst->target == v2) {
2229 for(
typename edge_list_t::const_iterator it_lst = lst.begin(); it_lst != lst.end(); ++it_lst) {
2230 if(it_lst->target != it_olst->target)
2233 if(it_olst == olst.end())
2234 it_olst = olst.begin();
2246 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2249 typename neighborhood_t::iterator it;
2251 std::reverse((*it)->single_neighborhood.edges.begin(), (*it)->single_neighborhood.edges.end());
2256 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2259 typename neighborhood_t::const_iterator it_o;
2260 typename neighborhood_t::iterator it;
2262 NeighborhoodPair::Delete(*it);
2271 lookup[(*it_o)->vertex] = np;
2286 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2293 template <
typename Graph>
void create_graph_methods(Graph& G)
2296 if(G.valence(G.any()) > G.size()) {
2298 typename Graph::vertex_t v = G.any();
2317 G.source(
typename Graph::edge_t());
2318 G.target(
typename Graph::edge_t());
2321 G.spliceAfter(v, v, v);
2322 G.spliceBefore(v, v, v);
2331 const Graph& cG = G;
2347 cG.source(
typename Graph::edge_t());
2348 cG.target(
typename Graph::edge_t());
VVGraph(const Container &c, bool check_unique=true)
Construct from an existing list of vertices.
Definition: VVGraph.hpp:132
Iterator it
Iterator pointing in the edge list.
Definition: VVGraph.hpp:1375
identity_t id() const
Return the identifier of a vertex.
Definition: Vertex.hpp:291
Alloc::template rebind< VertexContent >::other VertexAlloc
Smart pointer on a vertex.
Definition: VVGraph.hpp:86
Type of the result of the search for a vertex in a neighborhood.
Definition: VVGraph.hpp:1341
std::pair< const_neighbor_iterator, const_neighbor_iterator > const_neighbor_iterator_pair
Constant range of the neighbors of a vertex.
Definition: VVGraph.hpp:398
iterator end()
Returns an iterator on the end of the set of vertexes of the graph.
Definition: VVGraph.hpp:1269
bool operator==(const single_neighborhood_t &other) const
Equality of two neighborhood.
Definition: VVGraph.hpp:255
Edge of a vv graph.
Definition: Edge.hpp:45
const vertex_t * flagged
Iterator toward the flagged neighbor.
Definition: VVGraph.hpp:232
in_edges_t::iterator ineighbor_iterator
Iterator on the incoming neighbors of a vertex.
Definition: VVGraph.hpp:375
search_result_t()
Default constructor.
Definition: VVGraph.hpp:1347
This file contains the defines the forall loops.
search_result_t(const search_result_t ©)
Copy constructor.
Definition: VVGraph.hpp:1358
std::unordered_map< vertex_t, NeighborhoodPair * > lookup_t
Type of the fast-search map.
Definition: VVGraph.hpp:307
std::pair< circ_neighbor_iterator, circ_neighbor_iterator > circ_neighbor_iterator_pair
Range of circular iterators.
Definition: VVGraph.hpp:367
std::vector< NeighborhoodPair * > neighborhood_t
Type of the list of vertexes, together with the neighborhood.
Definition: VVGraph.hpp:302
VVGraph()
Default constructor.
Definition: VVGraph.hpp:108
std::vector< vertex_t > in_edges_t
Type of the list of sources of the in-edges.
Definition: VVGraph.hpp:197
const vertex_t & source(const edge_t &edge) const
Return the source vertex of the edge.
Definition: VVGraph.hpp:948
bool operator==(const VVGraph &other) const
Test equality for the graphs.
Definition: VVGraph.hpp:2207
base_iterator base() const
Direct access to the base iterator.
Definition: MemberIterator.hpp:194
bool modified_vertices
If true, the vertex list has been modified.
Definition: VVGraph.hpp:1466
edge_list_t::iterator int_neighbor_iterator
Iterator on the outgoing edges.
Definition: VVGraph.hpp:1385
iterator begin()
Returns an iterator on the beginning of the set of vertexes of the graph.
Definition: VVGraph.hpp:1263
Contains all the classes related to the graphs.
Definition: VVGraph.hpp:55
This file contain the definition of the graph::Vertex class.
std::pair< neighbor_iterator, neighbor_iterator > neighbor_iterator_pair
Range of the neighbors of a vertex.
Definition: VVGraph.hpp:356
neighborhood_t::value_type neighborhood_value_type
Shortcut for the value_type of the neighborhood.
Definition: VVGraph.hpp:312
size_type erase(const vertex_t &v)
Remove a vertex from the graph.
Definition: VVGraph.hpp:1498
const_iterator end() const
Returns an iterator on the end of the set of vertexes of the graph.
Definition: VVGraph.hpp:1282
identity_t source() const
Returns the identifier of the source of the edge.
Definition: Edge.hpp:172
util::SelectMemberPointerIterator< typename neighborhood_t::const_iterator, const vertex_t,&NeighborhoodPair::vertex > const_iterator
Constant iterator on the vertexes.
Definition: VVGraph.hpp:344
const vertex_t & reference(vertex_t v) const
Get a reference on the vertex in the graph.
Definition: VVGraph.hpp:532
bool empty() const
Test if there is any vertex in the graph.
Definition: VVGraph.hpp:550
util::SelectMemberPointerIterator< typename neighborhood_t::iterator, const vertex_t,&NeighborhoodPair::vertex > iterator
Iterator on the vertexes.
Definition: VVGraph.hpp:339
Edge< const EdgeContent > const_edge_t
Weak pointer on a constant edge.
Definition: VVGraph.hpp:95
in_edges_t in_edges
Set of the sources of the incoming edges.
Definition: VVGraph.hpp:227
Define the Edge class to be used with the VVGraph class.
lookup_t lookup
Hash map to optimise look-up.
Definition: VVGraph.hpp:1461
std::list< neighbor_t > edge_list_t
Type of the list of outgoing neighbors.
Definition: VVGraph.hpp:147
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...
Definition: VVGraph.hpp:1875
Iterate over a container of structure, dereferencing only a member of it.
Definition: MemberIterator.hpp:241
Structure maintaining the data for a single neighbor.
Definition: VVGraph.hpp:143
vvgraph::vertex_t vertex
Type of a vertex.
Definition: Mesh.hpp:49
util::CircIterator< const_neighbor_iterator > const_circ_neighbor_iterator
Iterator used to iterate over the neighbors, but spcifying the starting point.
Definition: VVGraph.hpp:404
bool operator==(const neighbor_t &other) const
Equality of two neighbors/edge.
Definition: VVGraph.hpp:182
This namespace contains all the API of MorphoGraphX.
Definition: Assert.hpp:26
std::pair< ineighbor_iterator, ineighbor_iterator > ineighbor_iterator_pair
Range of the incoming neighbors of a vertex.
Definition: VVGraph.hpp:385
search_result_t(Iterator i, Neighborhood *n, bool ok=true)
Successful constructor.
Definition: VVGraph.hpp:1352
bool clear(const vertex_t &v)
Clear the outgoing edges of a vertex.
Definition: VVGraph.hpp:1562
Type of the neighborhood of a vertex.
Definition: VVGraph.hpp:202
size_type size() const
Return the number of vertexes on the graph.
Definition: VVGraph.hpp:543
vertex_t value_type
Type of the value of the graph as standard container.
Definition: VVGraph.hpp:101
neighborhood_t::size_type size_type
Type of a size.
Definition: VVGraph.hpp:317
neighborhood_t neighborhood
Main data structure containing everything.
Definition: VVGraph.hpp:1456
identity_t target() const
Returns the identifier of the target of the edge.
Definition: Edge.hpp:181
neighbor_t::edge_list_t edge_list_t
Type of the list of outgoing neighbors.
Definition: VVGraph.hpp:192
Definition: VVGraph.hpp:261
search_result_t< const single_neighborhood_t, int_const_neighbor_iterator > const_neighbor_found_t
Constant result of a search in the neighborhood.
Definition: VVGraph.hpp:1398
bool found
True if the search was completely successful.
Definition: VVGraph.hpp:1371
size_type count(const vertex_t &v) const
Count the number of vertexes v in the graph (can be 0 or 1 only)
Definition: VVGraph.hpp:1588
edge_list_t edges
List of the outgoing edges.
Definition: VVGraph.hpp:222
bool contains(const vertex_t &v) const
Test if v is in the graph.
Definition: VVGraph.hpp:1868
Edge< EdgeContent > edge_t
Weak pointer on an edge.
Definition: VVGraph.hpp:91
void reserve(size_type s)
Reserve space for more vertices.
Definition: VVGraph.hpp:1327
Definition: MemberIterator.hpp:329
void swap(VVGraph &other)
Swap the content of both graphs.
Definition: VVGraph.hpp:2287
util::CircIterator< neighbor_iterator > circ_neighbor_iterator
Iterator used to iterate over the neighbors, but specifying the starting point.
Definition: VVGraph.hpp:362
search_result_t< single_neighborhood_t, int_neighbor_iterator > neighbor_found_t
Result of a search in the neighborhood.
Definition: VVGraph.hpp:1394
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.
Definition: VVGraph.hpp:392
VVGraph(Iterator begin, Iterator end, bool check_unique=true)
Construct from an existing list of vertices.
Definition: VVGraph.hpp:122
VVGraph & reverse()
Reverse the order of all the neighbors.
Definition: VVGraph.hpp:2247
std::pair< const_circ_neighbor_iterator, const_circ_neighbor_iterator > const_circ_neighbor_iterator_pair
Range of circular iterators.
Definition: VVGraph.hpp:409
Defines the SelectMemberIterator class template.
edge_list_t::const_iterator int_const_neighbor_iterator
Constant iterator on the outgoing edges.
Definition: VVGraph.hpp:1389
Defines the util::tie function.
bool isNull() const
Test if a vertex is a null vertex.
Definition: Vertex.hpp:284
const vertex_t & target(const edge_t &edge) const
Return the target vertex of the edge.
Definition: VVGraph.hpp:969
Creates a circular iterator from a range of forward iterators.
Definition: CircIterator.hpp:25
const_iterator begin() const
Returns an iterator on the beginning of the set of vertexes of the graph.
Definition: VVGraph.hpp:1276
VVGraph & operator=(const VVGraph &other)
Copy the graph into another graph.
Definition: VVGraph.hpp:2257
Neighborhood * neighborhood
Neighborhood containing the element.
Definition: VVGraph.hpp:1379
util::SelectMemberIterator< typename edge_list_t::iterator, vertex_t,&neighbor_t::target > neighbor_iterator
Iterator on the neighbors of a vertex.
Definition: VVGraph.hpp:350
vvgraph::edge_t edge
Type of an edge.
Definition: Mesh.hpp:52
iterator insert(const vertex_t &v)
Insert a new vertex in the graph.
Definition: VVGraph.hpp:1595
neighbor_t(const vertex_t &tgt, const EdgeContent &e)
Constructor.
Definition: VVGraph.hpp:152
vertex_t target
Target of the edge.
Definition: VVGraph.hpp:174
Class representing a VV graph.
Definition: VVGraph.hpp:76