12 #include <CircIterator.hpp>
17 #include <UnorderedMap.hpp>
32 namespace mgx {
namespace graph {
65 typename Alloc = std::allocator<VertexContent> >
68 typedef typename Alloc::template rebind<EdgeContent>::other EdgeAlloc;
69 static EdgeAlloc edge_alloc;
76 typedef typename Alloc::template rebind<VertexContent>::other
VertexAlloc;
112 template <
typename Iterator>
VVGraph(Iterator begin, Iterator end,
bool check_unique =
true)
114 insert(begin, end, check_unique);
122 template <
typename Container>
VVGraph(
const Container& c,
bool check_unique =
true)
124 insert(util::ForAll::make_range(c), check_unique);
128 struct single_neighborhood_t;
147 static_cast<EdgeContent&
>(*this) = EdgeContent();
152 neighbor_t& operator=(
const neighbor_t& copy)
154 target = copy.target;
155 static_cast<EdgeContent&
>(*this) =
static_cast<const EdgeContent&
>(copy);
174 return (target == other.
target)
175 && (
static_cast<const EdgeContent&
>(*this) ==
static_cast<const EdgeContent&
>(other));
200 for(
typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
201 if(it->target == *flagged) {
202 flagged = &it->target;
229 for(
typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
230 if(it->target == *flagged) {
231 flagged = &it->target;
246 return edges == other.
edges;
256 :
vertex(copy.vertex), single_neighborhood(copy.single_neighborhood) {}
276 np->~NeighborhoodPair();
277 np_alloc.deallocate(np, 1);
285 typedef typename Alloc::template rebind<NeighborhoodPair>::other NPAlloc;
286 static NPAlloc np_alloc;
297 typedef std::unordered_map<vertex_t, NeighborhoodPair*>
lookup_t;
315 typedef const vertex_t typename std::iterator_traits<typename neighborhood_t::iterator>::value_type::*
316 msvc_bug_workaround_t;
319 reinterpret_cast<msvc_bug_workaround_t
>(&neighborhood_value_type::first)>
366 typedef typename in_edges_t::const_iterator const_ineighbor_iterator;
376 typedef std::pair<const_ineighbor_iterator, const_ineighbor_iterator> const_ineighbor_iterator_pair;
500 bool contains(
const vertex_t& v)
const;
524 const NeighborhoodPair* found = this->findVertex(v);
526 return found->vertex;
527 return vertex_t::null;
534 return neighborhood.size();
541 return neighborhood.empty();
568 const vertex_t& anyIn(
const vertex_t& v)
const;
586 size_type valence(
const vertex_t& v)
const;
609 bool empty(
const vertex_t& v)
const;
632 const vertex_t& iAnyIn(
const vertex_t& v)
const;
651 size_type iValence(
const vertex_t& v)
const;
674 bool iEmpty(
const vertex_t& v)
const;
695 const vertex_t& nextTo(
const vertex_t& v,
const vertex_t& neighbor,
unsigned int n = 1)
const;
716 const vertex_t& prevTo(
const vertex_t& v,
const vertex_t& ref,
unsigned int n = 1)
const;
744 edge_t
edge(
const vertex_t& src,
const vertex_t& tgt);
774 const_edge_t
edge(
const vertex_t& src,
const vertex_t& tgt)
const;
807 bool flag(
const vertex_t& src,
const vertex_t& neighbor);
814 const vertex_t& flagged(
const vertex_t& src)
const;
832 const_neighbor_iterator_pair neighbors(
const vertex_t& v)
const;
849 neighbor_iterator_pair neighbors(
const vertex_t& v);
865 circ_neighbor_iterator_pair neighbors(
const vertex_t& v,
const vertex_t& n);
881 const_circ_neighbor_iterator_pair neighbors(
const vertex_t& v,
const vertex_t& n)
const;
902 ineighbor_iterator_pair iNeighbors(
const vertex_t& v);
923 const_ineighbor_iterator_pair iNeighbors(
const vertex_t& v)
const;
940 const NeighborhoodPair* found = this->findVertex(
vertex_t(edge.
source()));
942 return found->vertex;
943 return vertex_t::null;
961 const NeighborhoodPair* found = this->findVertex(
vertex_t(edge.
target()));
963 return found->vertex;
964 return vertex_t::null;
993 size_type eraseEdge(
const vertex_t& src,
const vertex_t& tgt);
1026 edge_t replace(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1054 edge_t spliceAfter(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1082 edge_t spliceBefore(
const vertex_t& v,
const vertex_t& neighbor,
const vertex_t& new_neighbor);
1102 edge_t insertEdge(
const vertex_t& src,
const vertex_t& tgt);
1124 bool eraseAllEdges(
const vertex_t& v);
1143 bool clear(
const vertex_t& v);
1173 bool operator==(
const VVGraph& other)
const;
1196 void eraseAllEdges();
1213 template <
typename VertexContainer>
VVGraph subgraph(
const VertexContainer& vertexes)
const;
1227 size_type eraseEdge(
const vertex_t& v, neighbor_iterator pos);
1232 size_type eraseEdge(
const vertex_t& v, circ_neighbor_iterator pos);
1243 template <
typename Iterator>
void insert(Iterator first, Iterator last,
bool check_unique =
true);
1248 template <
typename Iterator>
void insert(
const std::pair<Iterator, Iterator>& range,
bool check_unique =
true);
1254 return neighborhood.begin();
1260 return neighborhood.end();
1267 return neighborhood.begin();
1273 return neighborhood.end();
1279 size_type count(
const vertex_t& v)
const;
1290 neighbor_iterator findIn(
const vertex_t& v,
const vertex_t& n);
1300 const_neighbor_iterator findIn(
const vertex_t& v,
const vertex_t& n)
const;
1318 neighborhood.reserve(s);
1324 void eraseAllEdges(NeighborhoodPair* it);
1343 : found(ok) , it(i), neighborhood(n) {}
1349 : found(copy.found), it(copy.it), neighborhood(copy.neighborhood) {}
1397 NeighborhoodPair* findVertex(
const vertex_t& v);
1402 const NeighborhoodPair* findVertex(
const vertex_t& v)
const;
1407 typename neighborhood_t::iterator findIterator(
const NeighborhoodPair* np);
1408 typename neighborhood_t::const_iterator findIterator(
const NeighborhoodPair* np)
const;
1435 std::pair<ineighbor_iterator, bool> insertInEdge(
const vertex_t& v,
const vertex_t& new_neighbor);
1459 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1461 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1464 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1467 typename neighborhood_t::iterator it;
1468 for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1469 NeighborhoodPair::Delete(*it);
1472 neighborhood.clear();
1476 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1481 NeighborhoodPair::Delete(*it.
base());
1482 *it.
base() = neighborhood.back();
1483 neighborhood.pop_back();
1486 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1490 if(eraseAllEdges(v)) {
1493 typename neighborhood_t::iterator it = this->findIterator(np);
1494 NeighborhoodPair::Delete(np);
1495 *it = neighborhood.back();
1496 neighborhood.pop_back();
1501 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1504 for(
typename neighborhood_t::iterator it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1505 it->single_neighborhood.edges.
clear();
1506 it->single_neighborhood.in_edges.clear();
1507 it->single_neighborhood.flagged = 0;
1511 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1516 eraseAllEdges(it_found);
1522 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1525 const vertex_t& v = np->vertex;
1526 for(
typename edge_list_t::iterator it_el = np->single_neighborhood.edges.begin();
1527 it_el != np->single_neighborhood.edges.end(); ++it_el) {
1528 in_edges_t& ie = lookup[it_el->target]->single_neighborhood.in_edges;
1529 typename in_edges_t::iterator it_found = std::find(ie.begin(), ie.end(), v);
1532 np->single_neighborhood.edges.clear();
1533 np->single_neighborhood.flagged = 0;
1535 in_edges_t& in_edges = np->single_neighborhood.in_edges;
1536 for(
typename in_edges_t::iterator it = in_edges.begin(); it != in_edges.end(); ++it) {
1537 neighbor_found_t found = findInVertex(*it, v);
1538 found.neighborhood->edges.erase(found.it);
1539 if(found.neighborhood->flagged && *found.neighborhood->flagged == v)
1540 found.neighborhood->flagged = 0;
1545 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1548 eraseAllEdges(*it_found.
base());
1551 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1554 typename neighborhood_t::iterator it_found = this->findVertex(v);
1555 if(it_found != neighborhood.end()) {
1562 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1566 for(
typename edge_list_t::iterator it_el = it.
base()->single_neighborhood.edges.begin();
1567 it_el != it.
base()->single_neighborhood.edges.end(); ++it_el) {
1568 typename neighborhood_t::iterator it_found = this->findVertex(it_el->target);
1569 in_edges_t& ie = it_found->single_neighborhood.in_edges;
1570 typename in_edges_t::iterator it_found2 = std::find(ie.begin(), ie.end(), v);
1571 ie.erase(it_found2);
1573 it.
base()->single_neighborhood.edges.clear();
1576 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1580 return lookup.
count(v);
1583 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1587 typename lookup_t::iterator it_found = lookup.find(v);
1588 if(it_found == lookup.end()) {
1590 neighborhood.push_back(np);
1596 return findIterator(it_found->second);
1599 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1603 return this->insert(v);
1606 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1607 template <
typename Iterator>
1610 insert(range.first, range.second, check_unique);
1613 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1614 template <
typename Iterator>
1618 for(Iterator it = first; it != last; ++it) {
1622 for(Iterator it = first; it != last; ++it) {
1624 neighborhood.push_back(np);
1630 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1634 if(neighborhood.empty())
1635 return vertex_t::null;
1639 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1643 typename neighborhood_t::const_iterator it = neighborhood.
begin();
1644 std::advance(it, idx);
1645 return (*it)->vertex;
1648 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1653 return vertex_t::null;
1655 if(not it_found || it_found->single_neighborhood.
edges.empty())
1656 return vertex_t::null;
1658 return lst.front().target;
1661 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1670 return it_found->single_neighborhood.edges.size();
1673 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1681 return it_found->single_neighborhood.edges.empty();
1684 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1689 return vertex_t::null;
1691 if(not it_found || it_found->single_neighborhood.
in_edges.empty())
1692 return vertex_t::null;
1694 return *lst.begin();
1697 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1706 return it_found->single_neighborhood.in_edges.size();
1709 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1717 return it_found->single_neighborhood.in_edges.empty();
1720 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1724 return std::find(neighborhood.begin(), neighborhood.end(), np);
1727 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1731 return std::find(neighborhood.begin(), neighborhood.end(), np);
1734 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1735 typename VVGraph<VertexContent, EdgeContent, Alloc>::NeighborhoodPair*
1738 typename lookup_t::const_iterator it_found = lookup.find(v);
1739 if(it_found != lookup.end())
1740 return it_found->second;
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>
1763 edge_list_t& lst = it_found->single_neighborhood.edges;
1765 for(
typename edge_list_t::iterator it = lst.begin(); it != lst.end(); ++it) {
1766 if(it->target == n) {
1773 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1782 const edge_list_t& lst = it_found->single_neighborhood.edges;
1784 for(
typename edge_list_t::const_iterator it = lst.begin(); it != lst.end(); ++it) {
1785 if(it->target == n) {
1792 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1802 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1812 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1823 in_edges_t& ie = it_found2->single_neighborhood.in_edges;
1824 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1825 if(it_found_ie != ie.end()) {
1826 ie.erase(it_found_ie);
1827 typename edge_list_t::iterator it = pos.
base();
1828 it_found->single_neighborhood.edges.erase(it);
1834 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1838 return eraseEdge(v, pos.base());
1841 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1851 in_edges_t& ie = lookup[n]->single_neighborhood.in_edges;
1852 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1853 ie.erase(it_found_ie);
1857 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1860 return this->findVertex(v);
1863 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1864 std::pair<typename VVGraph<VertexContent, EdgeContent, Alloc>::ineighbor_iterator,
bool>
1867 typename lookup_t::iterator found = lookup.find(new_neighbor);
1868 if(found == lookup.end())
1870 in_edges_t& ie = found->second->single_neighborhood.in_edges;
1871 typename in_edges_t::iterator it_found = std::find(ie.begin(), ie.end(), v);
1872 if(it_found != ie.end())
1873 return std::make_pair(it_found,
false);
1877 return std::make_pair(it,
true);
1880 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1883 typename lookup_t::iterator found = lookup.find(new_neighbor);
1887 if(found == lookup.end())
1889 found->single_neighborhood.single_neighborhood.in_edges.
erase(it);
1892 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1897 if(new_neighbor.
isNull() or (v == new_neighbor) or (neighbor == new_neighbor))
1905 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
1909 typename in_edges_t::iterator it_found_ie = std::find(ie.begin(), ie.end(), v);
1910 ie.erase(it_found_ie);
1911 found.
it->target = new_neighbor;
1912 found.
it->clear_edge();
1913 if(n_found->single_neighborhood.
flagged and *n_found->single_neighborhood.
flagged == neighbor)
1914 n_found->single_neighborhood.
flagged = 0;
1918 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1924 return vertex_t::null;
1925 typename edge_list_t::const_iterator it = found.
it;
1927 for(
unsigned int i = 0; i < n; ++i) {
1935 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1941 return vertex_t::null;
1942 typename edge_list_t::const_iterator it = found.
it;
1944 for(
unsigned int i = 0; i < n; ++i) {
1945 if(it == lst.begin())
1952 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1962 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1972 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1982 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1987 if(not found or found->single_neighborhood.
flagged == 0)
1988 return vertex_t::null;
1989 return *found->single_neighborhood.
flagged;
1992 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
1997 if(new_neighbor.
isNull() || v == new_neighbor)
2004 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2008 typename edge_list_t::iterator new_edge_it
2010 return edge_t(v.
id(), new_neighbor.
id(), &*new_edge_it);
2013 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2018 if(new_neighbor.
isNull() || v == new_neighbor)
2025 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2028 typename edge_list_t::iterator new_edge_it
2030 return edge_t(v.
id(), new_neighbor.
id(), &*new_edge_it);
2033 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2037 if(v.
isNull() || new_neighbor.
isNull() || v == new_neighbor)
2044 util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2047 edge_list_t& lst = it_found->single_neighborhood.edges;
2048 lst.push_front(
neighbor_t(new_neighbor, EdgeContent()));
2049 typename edge_list_t::iterator it = lst.begin();
2050 return edge_t(v.
id(), new_neighbor.
id(), &*it);
2053 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2063 const edge_list_t& lst = it_found->single_neighborhood.edges;
2068 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2078 edge_list_t& lst = it_found->single_neighborhood.edges;
2084 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2100 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2116 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2117 typename VVGraph<VertexContent, EdgeContent, Alloc>::const_ineighbor_iterator_pair
2120 const_ineighbor_iterator_pair result;
2126 const in_edges_t& lst = it_found->single_neighborhood.in_edges;
2127 result.first = const_ineighbor_iterator(lst.begin());
2128 result.second = const_ineighbor_iterator(lst.end());
2132 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2142 in_edges_t& lst = it_found->single_neighborhood.in_edges;
2148 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2149 template <
typename VertexContainer>
2153 typename VertexContainer::const_iterator it;
2156 for(it = verts.begin(); it != verts.end(); ++it) {
2159 const NeighborhoodPair* it_orign;
2160 typename neighborhood_t::iterator it_n;
2161 typename edge_list_t::const_reverse_iterator it_sn;
2164 const vertex_t& v = (*it_n)->vertex;
2166 it_orign = this->findVertex(v);
2167 const edge_list_t& orig_lst = it_orign->single_neighborhood.edges;
2168 edge_list_t& lst = (*it_n)->single_neighborhood.edges;
2170 for(it_sn = orig_lst.rbegin(); it_sn != orig_lst.rend(); ++it_sn) {
2173 if(result.
contains(it_sn->target)) {
2175 ineighbor_iterator it_in = result.
insertInEdge(v, it_sn->target).first;
2177 lst.push_front(neighbor_t(it_sn->target, *it_sn));
2181 if(it_orign->single_neighborhood.flagged and result.
contains(*it_orign->single_neighborhood.flagged)) {
2182 const_neighbor_found_t found = this->findInVertex(v, *it_orign->single_neighborhood.flagged);
2183 (*it_n)->single_neighborhood.flagged = &(found.it->target);
2189 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2191 : modified_vertices(false)
2196 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2201 for(
typename neighborhood_t::const_iterator it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2203 typename lookup_t::const_iterator it_found = other.
lookup.find(v1);
2204 if(it_found == other.
lookup.end())
2206 if(it->single_neighborhood.edges.empty()) {
2207 if(!it_found->single_neighborhood.single_neighborhood.edges.empty())
2210 const edge_list_t& lst = it->single_neighborhood.edges;
2211 const edge_list_t& olst = it_found->second->single_neighborhood.edges;
2212 if(lst.size() != olst.size())
2214 const vertex_t& v2 = lst.begin()->target;
2216 for(
typename edge_list_t::const_iterator it_olst = olst.begin(); it_olst != olst.end(); ++it_olst) {
2217 if(it_olst->target == v2) {
2219 for(
typename edge_list_t::const_iterator it_lst = lst.begin(); it_lst != lst.end(); ++it_lst) {
2220 if(it_lst->target != it_olst->target)
2223 if(it_olst == olst.end())
2224 it_olst = olst.begin();
2236 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2239 typename neighborhood_t::iterator it;
2240 for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2241 std::reverse((*it)->single_neighborhood.edges.begin(), (*it)->single_neighborhood.edges.end());
2246 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2249 typename neighborhood_t::const_iterator it_o;
2250 typename neighborhood_t::iterator it;
2251 for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2252 NeighborhoodPair::Delete(*it);
2255 neighborhood.clear();
2257 it = neighborhood.end();
2260 neighborhood.push_back(np);
2261 lookup[(*it_o)->vertex] = np;
2276 template <
typename VertexContent,
typename EdgeContent,
typename Alloc>
2280 lookup.swap(other.
lookup);
2283 template <
typename Graph>
void create_graph_methods(Graph& G)
2286 if(G.valence(G.any()) > G.size()) {
2288 typename Graph::vertex_t v = G.any();
2307 G.source(
typename Graph::edge_t());
2308 G.target(
typename Graph::edge_t());
2311 G.spliceAfter(v, v, v);
2312 G.spliceBefore(v, v, v);
2321 const Graph& cG = G;
2337 cG.source(
typename Graph::edge_t());
2338 cG.target(
typename Graph::edge_t());
VVGraph(const Container &c, bool check_unique=true)
Construct from an existing list of vertices.
Definition: VVGraph.hpp:122
Iterator it
Iterator pointing in the edge list.
Definition: VVGraph.hpp:1365
identity_t id() const
Return the identifier of a vertex.
Definition: Vertex.hpp:281
Alloc::template rebind< VertexContent >::other VertexAlloc
Smart pointer on a vertex.
Definition: VVGraph.hpp:76
Type of the result of the search for a vertex in a neighborhood.
Definition: VVGraph.hpp:1331
std::pair< const_neighbor_iterator, const_neighbor_iterator > const_neighbor_iterator_pair
Constant range of the neighbors of a vertex.
Definition: VVGraph.hpp:388
iterator end()
Returns an iterator on the end of the set of vertexes of the graph.
Definition: VVGraph.hpp:1259
bool operator==(const single_neighborhood_t &other) const
Equality of two neighborhood.
Definition: VVGraph.hpp:245
Edge of a vv graph.
Definition: Edge.hpp:35
const vertex_t * flagged
Iterator toward the flagged neighbor.
Definition: VVGraph.hpp:222
in_edges_t::iterator ineighbor_iterator
Iterator on the incoming neighbors of a vertex.
Definition: VVGraph.hpp:365
search_result_t()
Default constructor.
Definition: VVGraph.hpp:1337
This file contains the defines the forall loops.
search_result_t(const search_result_t ©)
Copy constructor.
Definition: VVGraph.hpp:1348
std::unordered_map< vertex_t, NeighborhoodPair * > lookup_t
Type of the fast-search map.
Definition: VVGraph.hpp:297
std::pair< circ_neighbor_iterator, circ_neighbor_iterator > circ_neighbor_iterator_pair
Range of circular iterators.
Definition: VVGraph.hpp:357
std::vector< NeighborhoodPair * > neighborhood_t
Type of the list of vertexes, together with the neighborhood.
Definition: VVGraph.hpp:292
VVGraph()
Default constructor.
Definition: VVGraph.hpp:98
std::vector< vertex_t > in_edges_t
Type of the list of sources of the in-edges.
Definition: VVGraph.hpp:187
const vertex_t & source(const edge_t &edge) const
Return the source vertex of the edge.
Definition: VVGraph.hpp:938
bool operator==(const VVGraph &other) const
Test equality for the graphs.
Definition: VVGraph.hpp:2197
base_iterator base() const
Direct access to the base iterator.
Definition: MemberIterator.hpp:184
bool modified_vertices
If true, the vertex list has been modified.
Definition: VVGraph.hpp:1456
edge_list_t::iterator int_neighbor_iterator
Iterator on the outgoing edges.
Definition: VVGraph.hpp:1375
iterator begin()
Returns an iterator on the beginning of the set of vertexes of the graph.
Definition: VVGraph.hpp:1253
Contains all the classes related to the graphs.
Definition: VVGraph.hpp:45
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:346
neighborhood_t::value_type neighborhood_value_type
Shortcut for the value_type of the neighborhood.
Definition: VVGraph.hpp:302
size_type erase(const vertex_t &v)
Remove a vertex from the graph.
Definition: VVGraph.hpp:1488
const_iterator end() const
Returns an iterator on the end of the set of vertexes of the graph.
Definition: VVGraph.hpp:1272
identity_t source() const
Returns the identifier of the source of the edge.
Definition: Edge.hpp:162
util::SelectMemberPointerIterator< typename neighborhood_t::const_iterator, const vertex_t,&NeighborhoodPair::vertex > const_iterator
Constant iterator on the vertexes.
Definition: VVGraph.hpp:334
const vertex_t & reference(vertex_t v) const
Get a reference on the vertex in the graph.
Definition: VVGraph.hpp:522
bool empty() const
Test if there is any vertex in the graph.
Definition: VVGraph.hpp:540
util::SelectMemberPointerIterator< typename neighborhood_t::iterator, const vertex_t,&NeighborhoodPair::vertex > iterator
Iterator on the vertexes.
Definition: VVGraph.hpp:329
Edge< const EdgeContent > const_edge_t
Weak pointer on a constant edge.
Definition: VVGraph.hpp:85
in_edges_t in_edges
Set of the sources of the incoming edges.
Definition: VVGraph.hpp:217
Define the Edge class to be used with the VVGraph class.
lookup_t lookup
Hash map to optimise look-up.
Definition: VVGraph.hpp:1451
std::list< neighbor_t > edge_list_t
Type of the list of outgoing neighbors.
Definition: VVGraph.hpp:137
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:1865
Iterate over a container of structure, dereferencing only a member of it.
Definition: MemberIterator.hpp:231
Structure maintaining the data for a single neighbor.
Definition: VVGraph.hpp:133
vvgraph::vertex_t vertex
Type of a vertex.
Definition: Mesh.hpp:39
util::CircIterator< const_neighbor_iterator > const_circ_neighbor_iterator
Iterator used to iterate over the neighbors, but spcifying the starting point.
Definition: VVGraph.hpp:394
bool operator==(const neighbor_t &other) const
Equality of two neighbors/edge.
Definition: VVGraph.hpp:172
std::pair< ineighbor_iterator, ineighbor_iterator > ineighbor_iterator_pair
Range of the incoming neighbors of a vertex.
Definition: VVGraph.hpp:375
search_result_t(Iterator i, Neighborhood *n, bool ok=true)
Successful constructor.
Definition: VVGraph.hpp:1342
bool clear(const vertex_t &v)
Clear the outgoing edges of a vertex.
Definition: VVGraph.hpp:1552
Type of the neighborhood of a vertex.
Definition: VVGraph.hpp:192
size_type size() const
Return the number of vertexes on the graph.
Definition: VVGraph.hpp:533
vertex_t value_type
Type of the value of the graph as standard container.
Definition: VVGraph.hpp:91
neighborhood_t::size_type size_type
Type of a size.
Definition: VVGraph.hpp:307
neighborhood_t neighborhood
Main data structure containing everything.
Definition: VVGraph.hpp:1446
identity_t target() const
Returns the identifier of the target of the edge.
Definition: Edge.hpp:171
neighbor_t::edge_list_t edge_list_t
Type of the list of outgoing neighbors.
Definition: VVGraph.hpp:182
Definition: VVGraph.hpp:251
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:1388
bool found
True if the search was completely successful.
Definition: VVGraph.hpp:1361
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:1578
edge_list_t edges
List of the outgoing edges.
Definition: VVGraph.hpp:212
bool contains(const vertex_t &v) const
Test if v is in the graph.
Definition: VVGraph.hpp:1858
Edge< EdgeContent > edge_t
Weak pointer on an edge.
Definition: VVGraph.hpp:81
void reserve(size_type s)
Reserve space for more vertices.
Definition: VVGraph.hpp:1317
Definition: MemberIterator.hpp:319
void swap(VVGraph &other)
Swap the content of both graphs.
Definition: VVGraph.hpp:2277
util::CircIterator< neighbor_iterator > circ_neighbor_iterator
Iterator used to iterate over the neighbors, but specifying the starting point.
Definition: VVGraph.hpp:352
search_result_t< single_neighborhood_t, int_neighbor_iterator > neighbor_found_t
Result of a search in the neighborhood.
Definition: VVGraph.hpp:1384
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:382
VVGraph(Iterator begin, Iterator end, bool check_unique=true)
Construct from an existing list of vertices.
Definition: VVGraph.hpp:112
VVGraph & reverse()
Reverse the order of all the neighbors.
Definition: VVGraph.hpp:2237
std::pair< const_circ_neighbor_iterator, const_circ_neighbor_iterator > const_circ_neighbor_iterator_pair
Range of circular iterators.
Definition: VVGraph.hpp:399
Defines the SelectMemberIterator class template.
edge_list_t::const_iterator int_const_neighbor_iterator
Constant iterator on the outgoing edges.
Definition: VVGraph.hpp:1379
Defines the util::tie function.
bool isNull() const
Test if a vertex is a null vertex.
Definition: Vertex.hpp:274
const vertex_t & target(const edge_t &edge) const
Return the target vertex of the edge.
Definition: VVGraph.hpp:959
Creates a circular iterator from a range of forward iterators.
Definition: CircIterator.hpp:15
const_iterator begin() const
Returns an iterator on the beginning of the set of vertexes of the graph.
Definition: VVGraph.hpp:1266
VVGraph & operator=(const VVGraph &other)
Copy the graph into another graph.
Definition: VVGraph.hpp:2247
Neighborhood * neighborhood
Neighborhood containing the element.
Definition: VVGraph.hpp:1369
util::SelectMemberIterator< typename edge_list_t::iterator, vertex_t,&neighbor_t::target > neighbor_iterator
Iterator on the neighbors of a vertex.
Definition: VVGraph.hpp:340
vvgraph::edge_t edge
Type of an edge.
Definition: Mesh.hpp:42
iterator insert(const vertex_t &v)
Insert a new vertex in the graph.
Definition: VVGraph.hpp:1585
neighbor_t(const vertex_t &tgt, const EdgeContent &e)
Constructor.
Definition: VVGraph.hpp:142
vertex_t target
Target of the edge.
Definition: VVGraph.hpp:164
Class representing a VV graph.
Definition: VVGraph.hpp:66