MorphoGraphX
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
VVGraph.hpp
Go to the documentation of this file.
1 #ifndef VV_GRAPH_HPP
2 #define VV_GRAPH_HPP
3 
10 #include <Config.hpp>
11 
12 #include <CircIterator.hpp>
13 #include <Edge.hpp>
14 #include <Forall.hpp>
15 #include <MemberIterator.hpp>
16 #include <Tie.hpp>
17 #include <UnorderedMap.hpp>
18 #include <Vertex.hpp>
19 
20 #include <algorithm>
21 #include <iostream>
22 #include <iterator>
23 #include <list>
24 #include <memory>
25 #include <utility>
26 #include <vector>
27 
28 namespace std {
29 using namespace tr1;
30 }
31 
32 namespace mgx { namespace graph {
33 
46  _EmptyEdgeContent& operator=(const _EmptyEdgeContent& /*other*/) {
47  return *this;
48  }
49  };
50 
64  template <typename VertexContent, typename EdgeContent = _EmptyEdgeContent,
65  typename Alloc = std::allocator<VertexContent> >
66  class VVGraph {
67  public:
68  typedef typename Alloc::template rebind<EdgeContent>::other EdgeAlloc;
69  static EdgeAlloc edge_alloc;
70 
72 
73 
76  typedef typename Alloc::template rebind<VertexContent>::other VertexAlloc;
87 
92 
98  VVGraph() : modified_vertices(false) {}
99 
105  VVGraph(const VVGraph& copy);
106 
112  template <typename Iterator> VVGraph(Iterator begin, Iterator end, bool check_unique = true)
113  {
114  insert(begin, end, check_unique);
115  }
116 
122  template <typename Container> VVGraph(const Container& c, bool check_unique = true)
123  {
124  insert(util::ForAll::make_range(c), check_unique);
125  }
126 
127  protected:
128  struct single_neighborhood_t;
129 
133  struct neighbor_t : public EdgeContent {
137  typedef std::list<neighbor_t> edge_list_t;
138 
142  neighbor_t(const vertex_t& tgt, const EdgeContent& e) : EdgeContent(e), target(tgt) {}
143 
144  neighbor_t(const neighbor_t& copy) : EdgeContent(copy) , target(copy.target) {}
145 
146  void clear_edge() {
147  static_cast<EdgeContent&>(*this) = EdgeContent();
148  }
149 
150  ~neighbor_t() {}
151 
152  neighbor_t& operator=(const neighbor_t& copy)
153  {
154  target = copy.target;
155  static_cast<EdgeContent&>(*this) = static_cast<const EdgeContent&>(copy);
156  return *this;
157  }
158 
165 
172  bool operator==(const neighbor_t& other) const
173  {
174  return (target == other.target)
175  && (static_cast<const EdgeContent&>(*this) == static_cast<const EdgeContent&>(other));
176  }
177  };
178 
182  typedef typename neighbor_t::edge_list_t edge_list_t;
183 
187  typedef std::vector<vertex_t> in_edges_t;
188 
193 
194  single_neighborhood_t() : flagged(0) {}
195 
197  : edges(copy.edges), in_edges(copy.in_edges), flagged(copy.flagged)
198  {
199  if(flagged) {
200  for(typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
201  if(it->target == *flagged) {
202  flagged = &it->target;
203  break;
204  }
205  }
206  }
207  }
208 
213 
218 
223 
224  single_neighborhood_t& operator=(const single_neighborhood_t& other)
225  {
226  edges = other.edges;
227  in_edges = other.in_edges;
228  if(other.flagged) {
229  for(typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
230  if(it->target == *flagged) {
231  flagged = &it->target;
232  break;
233  }
234  }
235  } else
236  flagged = 0;
237  return *this;
238  }
239 
245  bool operator==(const single_neighborhood_t& other) const {
246  return edges == other.edges;
247  }
248  };
249 
250  public:
252  protected:
253  NeighborhoodPair(const vertex_t& v) : vertex(v) {}
254 
256  : vertex(copy.vertex), single_neighborhood(copy.single_neighborhood) {}
257 
258  public:
259  NeighborhoodPair* copy() const
260  {
261  NeighborhoodPair* np = np_alloc.allocate(1);
262  ::new (np) NeighborhoodPair(*this);
263  return np;
264  }
265 
266  static NeighborhoodPair* New(const vertex_t& v)
267  {
268  NeighborhoodPair* np = np_alloc.allocate(1);
269  ::new (np) NeighborhoodPair(v);
270  return np;
271  }
272 
273  static void Delete(NeighborhoodPair* np)
274  {
275  if(np) {
276  np->~NeighborhoodPair();
277  np_alloc.deallocate(np, 1);
278  }
279  }
280 
282  single_neighborhood_t single_neighborhood;
283  };
284 
285  typedef typename Alloc::template rebind<NeighborhoodPair>::other NPAlloc;
286  static NPAlloc np_alloc;
287 
288  // typedef std::map<vertex_t, single_neighborhood_t> neighborhood_t;
292  typedef std::vector<NeighborhoodPair*> neighborhood_t;
293 
297  typedef std::unordered_map<vertex_t, NeighborhoodPair*> lookup_t;
298 
302  typedef typename neighborhood_t::value_type neighborhood_value_type;
303 
307  typedef typename neighborhood_t::size_type size_type;
308 
310 
311 
314  #ifdef _MSC_VER
315  typedef const vertex_t typename std::iterator_traits<typename neighborhood_t::iterator>::value_type::*
316  msvc_bug_workaround_t;
317 
318  typedef util::SelectMemberPointerIterator<typename neighborhood_t::iterator, const vertex_t,
319  reinterpret_cast<msvc_bug_workaround_t>(&neighborhood_value_type::first)>
320  iterator;
324  typedef util::SelectMemberPointerIterator<typename neighborhood_t::const_iterator, const vertex_t,
325  reinterpret_cast<msvc_bug_workaround_t>(&neighborhood_value_type::vertex)>
327  #else
328  typedef util::SelectMemberPointerIterator<typename neighborhood_t::iterator, const vertex_t,
333  typedef util::SelectMemberPointerIterator<typename neighborhood_t::const_iterator, const vertex_t,
335  #endif
336 
346  typedef std::pair<neighbor_iterator, neighbor_iterator> neighbor_iterator_pair;
347 
353 
357  typedef std::pair<circ_neighbor_iterator, circ_neighbor_iterator> circ_neighbor_iterator_pair;
358 
365  typedef typename in_edges_t::iterator ineighbor_iterator;
366  typedef typename in_edges_t::const_iterator const_ineighbor_iterator;
367 
375  typedef std::pair<ineighbor_iterator, ineighbor_iterator> ineighbor_iterator_pair;
376  typedef std::pair<const_ineighbor_iterator, const_ineighbor_iterator> const_ineighbor_iterator_pair;
377 
388  typedef std::pair<const_neighbor_iterator, const_neighbor_iterator> const_neighbor_iterator_pair;
389 
395 
399  typedef std::pair<const_circ_neighbor_iterator, const_circ_neighbor_iterator> const_circ_neighbor_iterator_pair;
400 
402 
404 
405 
421  size_type erase(const vertex_t& v);
422 
435  iterator insert(const vertex_t& v);
436 
438 
440 
441 
454  const vertex_t& any() const;
455 
485  const vertex_t& operator[](size_type idx) const;
486 
500  bool contains(const vertex_t& v) const;
501 
522  const vertex_t& reference(vertex_t v) const
523  {
524  const NeighborhoodPair* found = this->findVertex(v);
525  if(found)
526  return found->vertex;
527  return vertex_t::null; // vertex_t(0);
528  }
529 
533  size_type size() const {
534  return neighborhood.size();
535  }
536 
540  bool empty() const {
541  return neighborhood.empty();
542  }
543 
545 
547 
548 
568  const vertex_t& anyIn(const vertex_t& v) const;
569 
586  size_type valence(const vertex_t& v) const;
587 
609  bool empty(const vertex_t& v) const;
610 
632  const vertex_t& iAnyIn(const vertex_t& v) const;
633 
651  size_type iValence(const vertex_t& v) const;
652 
674  bool iEmpty(const vertex_t& v) const;
675 
695  const vertex_t& nextTo(const vertex_t& v, const vertex_t& neighbor, unsigned int n = 1) const;
696 
716  const vertex_t& prevTo(const vertex_t& v, const vertex_t& ref, unsigned int n = 1) const;
717 
744  edge_t edge(const vertex_t& src, const vertex_t& tgt);
745 
774  const_edge_t edge(const vertex_t& src, const vertex_t& tgt) const;
775 
807  bool flag(const vertex_t& src, const vertex_t& neighbor);
808 
814  const vertex_t& flagged(const vertex_t& src) const;
815 
832  const_neighbor_iterator_pair neighbors(const vertex_t& v) const;
849  neighbor_iterator_pair neighbors(const vertex_t& v);
850 
865  circ_neighbor_iterator_pair neighbors(const vertex_t& v, const vertex_t& n);
866 
881  const_circ_neighbor_iterator_pair neighbors(const vertex_t& v, const vertex_t& n) const;
882 
902  ineighbor_iterator_pair iNeighbors(const vertex_t& v);
903 
923  const_ineighbor_iterator_pair iNeighbors(const vertex_t& v) const;
924 
938  const vertex_t& source(const edge_t& edge) const
939  {
940  const NeighborhoodPair* found = this->findVertex(vertex_t(edge.source()));
941  if(found)
942  return found->vertex;
943  return vertex_t::null; // vertex_t(0);
944  }
945 
959  const vertex_t& target(const edge_t& edge) const
960  {
961  const NeighborhoodPair* found = this->findVertex(vertex_t(edge.target()));
962  if(found)
963  return found->vertex;
964  return vertex_t::null; // vertex_t(0);
965  }
966 
968 
970 
971 
993  size_type eraseEdge(const vertex_t& src, const vertex_t& tgt);
994 
1026  edge_t replace(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1027 
1054  edge_t spliceAfter(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1055 
1082  edge_t spliceBefore(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1083 
1102  edge_t insertEdge(const vertex_t& src, const vertex_t& tgt);
1103 
1124  bool eraseAllEdges(const vertex_t& v);
1125 
1143  bool clear(const vertex_t& v);
1144 
1146 
1148 
1149 
1152  VVGraph& operator=(const VVGraph& other);
1153 
1157  VVGraph& reverse();
1158 
1162  void swap(VVGraph& other);
1163 
1173  bool operator==(const VVGraph& other) const;
1174 
1178  void clear();
1179 
1196  void eraseAllEdges();
1197 
1213  template <typename VertexContainer> VVGraph subgraph(const VertexContainer& vertexes) const;
1215 
1217 
1218 
1222  void erase(iterator pos);
1223 
1227  size_type eraseEdge(const vertex_t& v, neighbor_iterator pos);
1228 
1232  size_type eraseEdge(const vertex_t& v, circ_neighbor_iterator pos);
1233 
1239  iterator insert(iterator pos, const vertex_t& v);
1243  template <typename Iterator> void insert(Iterator first, Iterator last, bool check_unique = true);
1244 
1248  template <typename Iterator> void insert(const std::pair<Iterator, Iterator>& range, bool check_unique = true);
1249 
1254  return neighborhood.begin();
1255  }
1260  return neighborhood.end();
1261  }
1262 
1267  return neighborhood.begin();
1268  }
1273  return neighborhood.end();
1274  }
1275 
1279  size_type count(const vertex_t& v) const;
1280 
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;
1301 
1307  void eraseAllEdges(iterator it);
1308 
1312  void clear(iterator it);
1313 
1317  void reserve(size_type s) {
1318  neighborhood.reserve(s);
1319  }
1320 
1322 
1323  protected:
1324  void eraseAllEdges(NeighborhoodPair* it);
1331  template <class Neighborhood, class Iterator> struct search_result_t {
1337  search_result_t() : found(false), neighborhood(0) {}
1338 
1342  search_result_t(Iterator i, Neighborhood* n, bool ok = true)
1343  : found(ok) , it(i), neighborhood(n) {}
1344 
1349  : found(copy.found), it(copy.it), neighborhood(copy.neighborhood) {}
1350 
1354  operator bool() {
1355  return found;
1356  }
1357 
1361  bool found;
1365  Iterator it;
1369  Neighborhood* neighborhood;
1370  };
1371 
1375  typedef typename edge_list_t::iterator int_neighbor_iterator;
1379  typedef typename edge_list_t::const_iterator int_const_neighbor_iterator;
1380 
1384  typedef search_result_t<single_neighborhood_t, int_neighbor_iterator> neighbor_found_t;
1388  typedef search_result_t<const single_neighborhood_t, int_const_neighbor_iterator> const_neighbor_found_t;
1389 
1397  NeighborhoodPair* findVertex(const vertex_t& v);
1398 
1402  const NeighborhoodPair* findVertex(const vertex_t& v) const;
1403 
1407  typename neighborhood_t::iterator findIterator(const NeighborhoodPair* np);
1408  typename neighborhood_t::const_iterator findIterator(const NeighborhoodPair* np) const;
1409 
1424  neighbor_found_t findInVertex(const vertex_t& v, const vertex_t& neighbor);
1425 
1429  const_neighbor_found_t findInVertex(const vertex_t& v, const vertex_t& neighbor) const;
1430 
1435  std::pair<ineighbor_iterator, bool> insertInEdge(const vertex_t& v, const vertex_t& new_neighbor);
1436 
1441  void undoInEdge(const vertex_t& new_neighbor, ineighbor_iterator& it);
1442 
1447 
1452 
1457  };
1458 
1459  template <typename VertexContent, typename EdgeContent, typename Alloc>
1460  typename VVGraph<VertexContent, EdgeContent, Alloc>::EdgeAlloc VVGraph<VertexContent, EdgeContent, Alloc>::edge_alloc;
1461  template <typename VertexContent, typename EdgeContent, typename Alloc>
1462  typename VVGraph<VertexContent, EdgeContent, Alloc>::NPAlloc VVGraph<VertexContent, EdgeContent, Alloc>::np_alloc;
1463 
1464  template <typename VertexContent, typename EdgeContent, typename Alloc>
1466  {
1467  typename neighborhood_t::iterator it;
1468  for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1469  NeighborhoodPair::Delete(*it);
1470  *it = 0;
1471  }
1472  neighborhood.clear();
1473  lookup.clear();
1474  }
1475 
1476  template <typename VertexContent, typename EdgeContent, typename Alloc>
1478  {
1479  eraseAllEdges(it);
1480  lookup.erase(*it);
1481  NeighborhoodPair::Delete(*it.base());
1482  *it.base() = neighborhood.back();
1483  neighborhood.pop_back();
1484  }
1485 
1486  template <typename VertexContent, typename EdgeContent, typename Alloc>
1489  {
1490  if(eraseAllEdges(v)) {
1491  NeighborhoodPair* np = lookup[v];
1492  lookup.erase(v);
1493  typename neighborhood_t::iterator it = this->findIterator(np);
1494  NeighborhoodPair::Delete(np);
1495  *it = neighborhood.back();
1496  neighborhood.pop_back();
1497  return 1;
1498  }
1499  return 0;
1500  }
1501  template <typename VertexContent, typename EdgeContent, typename Alloc>
1503  {
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;
1508  }
1509  }
1510 
1511  template <typename VertexContent, typename EdgeContent, typename Alloc>
1513  {
1514  NeighborhoodPair* it_found = this->findVertex(v);
1515  if(it_found) {
1516  eraseAllEdges(it_found);
1517  return true;
1518  }
1519  return false;
1520  }
1521 
1522  template <typename VertexContent, typename EdgeContent, typename Alloc>
1524  {
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);
1530  ie.erase(it_found);
1531  }
1532  np->single_neighborhood.edges.clear();
1533  np->single_neighborhood.flagged = 0;
1534  // Remove the incoming edges
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;
1541  }
1542  in_edges.clear();
1543  }
1544 
1545  template <typename VertexContent, typename EdgeContent, typename Alloc>
1547  {
1548  eraseAllEdges(*it_found.base());
1549  }
1550 
1551  template <typename VertexContent, typename EdgeContent, typename Alloc>
1553  {
1554  typename neighborhood_t::iterator it_found = this->findVertex(v);
1555  if(it_found != neighborhood.end()) {
1556  clear(it_found);
1557  return true;
1558  }
1559  return false;
1560  }
1561 
1562  template <typename VertexContent, typename EdgeContent, typename Alloc>
1564  {
1565  const vertex_t& v = *it;
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);
1572  }
1573  it.base()->single_neighborhood.edges.clear();
1574  }
1575 
1576  template <typename VertexContent, typename EdgeContent, typename Alloc>
1579  {
1580  return lookup.count(v);
1581  }
1582 
1583  template <typename VertexContent, typename EdgeContent, typename Alloc>
1586  {
1587  typename lookup_t::iterator it_found = lookup.find(v);
1588  if(it_found == lookup.end()) {
1589  NeighborhoodPair* np = NeighborhoodPair::New(v);
1590  neighborhood.push_back(np);
1591  lookup[v] = np;
1592  iterator it = neighborhood.end();
1593  --it;
1594  return it;
1595  }
1596  return findIterator(it_found->second);
1597  }
1598 
1599  template <typename VertexContent, typename EdgeContent, typename Alloc>
1602  {
1603  return this->insert(v);
1604  }
1605 
1606  template <typename VertexContent, typename EdgeContent, typename Alloc>
1607  template <typename Iterator>
1608  void VVGraph<VertexContent, EdgeContent, Alloc>::insert(const std::pair<Iterator, Iterator>& range, bool check_unique)
1609  {
1610  insert(range.first, range.second, check_unique);
1611  }
1612 
1613  template <typename VertexContent, typename EdgeContent, typename Alloc>
1614  template <typename Iterator>
1615  void VVGraph<VertexContent, EdgeContent, Alloc>::insert(Iterator first, Iterator last, bool check_unique)
1616  {
1617  if(check_unique) {
1618  for(Iterator it = first; it != last; ++it) {
1619  insert(*it);
1620  }
1621  } else {
1622  for(Iterator it = first; it != last; ++it) {
1623  NeighborhoodPair* np = NeighborhoodPair::New(*it);
1624  neighborhood.push_back(np);
1625  lookup[*it] = np;
1626  }
1627  }
1628  }
1629 
1630  template <typename VertexContent, typename EdgeContent, typename Alloc>
1633  {
1634  if(neighborhood.empty())
1635  return vertex_t::null;
1636  return *begin();
1637  }
1638 
1639  template <typename VertexContent, typename EdgeContent, typename Alloc>
1642  {
1643  typename neighborhood_t::const_iterator it = neighborhood.begin();
1644  std::advance(it, idx);
1645  return (*it)->vertex;
1646  }
1647 
1648  template <typename VertexContent, typename EdgeContent, typename Alloc>
1651  {
1652  if(v.isNull())
1653  return vertex_t::null; // vertex_t(0);
1654  const NeighborhoodPair* it_found = this->findVertex(v);
1655  if(not it_found || it_found->single_neighborhood.edges.empty())
1656  return vertex_t::null; // vertex_t(0);
1657  const edge_list_t& lst = it_found->single_neighborhood.edges;
1658  return lst.front().target;
1659  }
1660 
1661  template <typename VertexContent, typename EdgeContent, typename Alloc>
1664  {
1665  if(v.isNull())
1666  return 0;
1667  const NeighborhoodPair* it_found = this->findVertex(v);
1668  if(not it_found)
1669  return 0;
1670  return it_found->single_neighborhood.edges.size();
1671  }
1672 
1673  template <typename VertexContent, typename EdgeContent, typename Alloc>
1675  {
1676  if(v.isNull())
1677  return true;
1678  const NeighborhoodPair* it_found = this->findVertex(v);
1679  if(not it_found)
1680  return true;
1681  return it_found->single_neighborhood.edges.empty();
1682  }
1683 
1684  template <typename VertexContent, typename EdgeContent, typename Alloc>
1687  {
1688  if(v.isNull())
1689  return vertex_t::null; // vertex_t(0);
1690  const NeighborhoodPair& it_found = this->findVertex(v);
1691  if(not it_found || it_found->single_neighborhood.in_edges.empty())
1692  return vertex_t::null; // vertex_t(0);
1693  const in_edges_t& lst = it_found->single_neighborhood.in_edges;
1694  return *lst.begin();
1695  }
1696 
1697  template <typename VertexContent, typename EdgeContent, typename Alloc>
1700  {
1701  if(v.isNull())
1702  return 0;
1703  const NeighborhoodPair* it_found = this->findVertex(v);
1704  if(not it_found)
1705  return 0;
1706  return it_found->single_neighborhood.in_edges.size();
1707  }
1708 
1709  template <typename VertexContent, typename EdgeContent, typename Alloc>
1711  {
1712  if(v.isNull())
1713  return true;
1714  const NeighborhoodPair* it_found = this->findVertex(v);
1715  if(not it_found)
1716  return true;
1717  return it_found->single_neighborhood.in_edges.empty();
1718  }
1719 
1720  template <typename VertexContent, typename EdgeContent, typename Alloc>
1723  {
1724  return std::find(neighborhood.begin(), neighborhood.end(), np);
1725  }
1726 
1727  template <typename VertexContent, typename EdgeContent, typename Alloc>
1729  VVGraph<VertexContent, EdgeContent, Alloc>::findIterator(const NeighborhoodPair* np) const
1730  {
1731  return std::find(neighborhood.begin(), neighborhood.end(), np);
1732  }
1733 
1734  template <typename VertexContent, typename EdgeContent, typename Alloc>
1735  typename VVGraph<VertexContent, EdgeContent, Alloc>::NeighborhoodPair*
1737  {
1738  typename lookup_t::const_iterator it_found = lookup.find(v);
1739  if(it_found != lookup.end())
1740  return it_found->second;
1741  return 0;
1742  }
1743 
1744  template <typename VertexContent, typename EdgeContent, typename Alloc>
1747  {
1748  typename lookup_t::const_iterator it_found = lookup.find(v);
1749  if(it_found != lookup.end())
1750  return it_found->second;
1751  return 0;
1752  }
1753 
1754  template <typename VertexContent, typename EdgeContent, typename Alloc>
1757  {
1758  if(v.isNull() || n.isNull() || v == n)
1759  return neighbor_found_t();
1760  NeighborhoodPair* it_found = this->findVertex(v);
1761  if(not it_found)
1762  return neighbor_found_t();
1763  edge_list_t& lst = it_found->single_neighborhood.edges;
1764  single_neighborhood_t* neighborhood = &it_found->single_neighborhood;
1765  for(typename edge_list_t::iterator it = lst.begin(); it != lst.end(); ++it) {
1766  if(it->target == n) {
1767  return neighbor_found_t(it, neighborhood);
1768  }
1769  }
1770  return neighbor_found_t(lst.end(), neighborhood, false);
1771  }
1772 
1773  template <typename VertexContent, typename EdgeContent, typename Alloc>
1776  {
1777  if(v.isNull() || n.isNull() || v == n)
1778  return const_neighbor_found_t();
1779  const NeighborhoodPair* it_found = this->findVertex(v);
1780  if(not it_found)
1781  return const_neighbor_found_t();
1782  const edge_list_t& lst = it_found->single_neighborhood.edges;
1783  const single_neighborhood_t* neighborhood = &it_found->single_neighborhood;
1784  for(typename edge_list_t::const_iterator it = lst.begin(); it != lst.end(); ++it) {
1785  if(it->target == n) {
1786  return const_neighbor_found_t(it, neighborhood);
1787  }
1788  }
1789  return const_neighbor_found_t(lst.end(), neighborhood, false);
1790  }
1791 
1792  template <typename VertexContent, typename EdgeContent, typename Alloc>
1795  {
1796  neighbor_found_t found = this->findInVertex(v, n);
1797  if(found.neighborhood)
1798  return neighbor_iterator(found.it);
1799  return neighbor_iterator();
1800  }
1801 
1802  template <typename VertexContent, typename EdgeContent, typename Alloc>
1805  {
1806  const_neighbor_found_t found = this->findInVertex(v, n);
1807  if(found.neighborhood)
1808  return const_neighbor_iterator(found.it);
1809  return const_neighbor_iterator(found.it);
1810  }
1811 
1812  template <typename VertexContent, typename EdgeContent, typename Alloc>
1815  {
1816  NeighborhoodPair* it_found = this->findVertex(v);
1817  if(not it_found)
1818  return 0;
1819  const vertex_t& n = *pos;
1820  NeighborhoodPair* it_found2 = this->findVertex(n);
1821  if(not it_found2)
1822  return 0;
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);
1829  return 1;
1830  }
1831  return 0;
1832  }
1833 
1834  template <typename VertexContent, typename EdgeContent, typename Alloc>
1837  {
1838  return eraseEdge(v, pos.base());
1839  }
1840 
1841  template <typename VertexContent, typename EdgeContent, typename Alloc>
1844  {
1845  neighbor_found_t found = this->findInVertex(v, n);
1846  if(!found)
1847  return 0;
1848  if(found.neighborhood->flagged && *found.neighborhood->flagged == n)
1849  found.neighborhood->flagged = 0;
1850  found.neighborhood->edges.erase(found.it);
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);
1854  return 1;
1855  }
1856 
1857  template <typename VertexContent, typename EdgeContent, typename Alloc>
1859  {
1860  return this->findVertex(v);
1861  }
1862 
1863  template <typename VertexContent, typename EdgeContent, typename Alloc>
1864  std::pair<typename VVGraph<VertexContent, EdgeContent, Alloc>::ineighbor_iterator, bool>
1866  {
1867  typename lookup_t::iterator found = lookup.find(new_neighbor);
1868  if(found == lookup.end())
1869  return std::make_pair(ineighbor_iterator(), false);
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);
1874  ie.push_back(v);
1875  ineighbor_iterator it = ie.end();
1876  --it;
1877  return std::make_pair(it, true);
1878  }
1879 
1880  template <typename VertexContent, typename EdgeContent, typename Alloc>
1882  {
1883  typename lookup_t::iterator found = lookup.find(new_neighbor);
1884  // typename neighborhood_t::iterator found = neighborhood.find(new_neighbor);
1885  // if(found == neighborhood.end())
1886  // return;
1887  if(found == lookup.end())
1888  return;
1889  found->single_neighborhood.single_neighborhood.in_edges.erase(it);
1890  }
1891 
1892  template <typename VertexContent, typename EdgeContent, typename Alloc>
1895  const vertex_t& new_neighbor)
1896  {
1897  if(new_neighbor.isNull() or (v == new_neighbor) or (neighbor == new_neighbor))
1898  return edge_t();
1899  neighbor_found_t found = this->findInVertex(v, neighbor);
1900  if(!found)
1901  return edge_t();
1902  NeighborhoodPair* n_found = this->findVertex(neighbor);
1903  ineighbor_iterator it_in;
1904  bool inserted;
1905  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
1906  if(!inserted)
1907  return edge_t();
1908  in_edges_t& ie = n_found->single_neighborhood.in_edges;
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;
1915  return edge_t(v.id(), new_neighbor.id(), &*found.it);
1916  }
1917 
1918  template <typename VertexContent, typename EdgeContent, typename Alloc>
1920  VVGraph<VertexContent, EdgeContent, Alloc>::nextTo(const vertex_t &v, const vertex_t &ref, unsigned int n) const
1921  {
1922  const_neighbor_found_t found = this->findInVertex(v, ref);
1923  if(!found)
1924  return vertex_t::null; // vertex_t(0);
1925  typename edge_list_t::const_iterator it = found.it;
1926  const edge_list_t& lst = found.neighborhood->edges;
1927  for(unsigned int i = 0; i < n; ++i) {
1928  ++it;
1929  if(it == lst.end())
1930  it = lst.begin();
1931  }
1932  return it->target;
1933  }
1934 
1935  template <typename VertexContent, typename EdgeContent, typename Alloc>
1937  VVGraph<VertexContent, EdgeContent, Alloc>::prevTo(const vertex_t &v, const vertex_t &ref, unsigned int n) const
1938  {
1939  const_neighbor_found_t found = this->findInVertex(v, ref);
1940  if(!found)
1941  return vertex_t::null; // vertex_t(0);
1942  typename edge_list_t::const_iterator it = found.it;
1943  const edge_list_t& lst = found.neighborhood->edges;
1944  for(unsigned int i = 0; i < n; ++i) {
1945  if(it == lst.begin())
1946  it = lst.end();
1947  --it;
1948  }
1949  return it->target;
1950  }
1951 
1952  template <typename VertexContent, typename EdgeContent, typename Alloc>
1955  {
1956  neighbor_found_t found = this->findInVertex(src, tgt);
1957  if(!found)
1958  return edge_t();
1959  return edge_t(src.id(), tgt.id(), &*found.it);
1960  }
1961 
1962  template <typename VertexContent, typename EdgeContent, typename Alloc>
1965  {
1966  const_neighbor_found_t found = this->findInVertex(src, tgt);
1967  if(!found)
1968  return const_edge_t();
1969  return const_edge_t(src.id(), tgt.id(), &*found.it);
1970  }
1971 
1972  template <typename VertexContent, typename EdgeContent, typename Alloc>
1974  {
1975  neighbor_found_t found = this->findInVertex(src, neighbor);
1976  if(!found)
1977  return false;
1978  found.neighborhood->flagged = &(found.it->target);
1979  return true;
1980  }
1981 
1982  template <typename VertexContent, typename EdgeContent, typename Alloc>
1985  {
1986  const NeighborhoodPair* found = this->findVertex(src);
1987  if(not found or found->single_neighborhood.flagged == 0)
1988  return vertex_t::null;
1989  return *found->single_neighborhood.flagged;
1990  }
1991 
1992  template <typename VertexContent, typename EdgeContent, typename Alloc>
1995  const vertex_t& new_neighbor)
1996  {
1997  if(new_neighbor.isNull() || v == new_neighbor)
1998  return edge_t();
1999  neighbor_found_t found = this->findInVertex(v, neighbor);
2000  if(!found)
2001  return edge_t();
2002  ineighbor_iterator it_in;
2003  bool inserted;
2004  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2005  if(!inserted)
2006  return edge_t();
2007  ++found.it;
2008  typename edge_list_t::iterator new_edge_it
2009  = found.neighborhood->edges.insert(found.it, neighbor_t(new_neighbor, EdgeContent()));
2010  return edge_t(v.id(), new_neighbor.id(), &*new_edge_it);
2011  }
2012 
2013  template <typename VertexContent, typename EdgeContent, typename Alloc>
2016  const vertex_t& new_neighbor)
2017  {
2018  if(new_neighbor.isNull() || v == new_neighbor)
2019  return edge_t();
2020  neighbor_found_t found = this->findInVertex(v, neighbor);
2021  if(!found)
2022  return edge_t();
2023  ineighbor_iterator it_in;
2024  bool inserted;
2025  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2026  if(!inserted)
2027  return edge_t();
2028  typename edge_list_t::iterator new_edge_it
2029  = found.neighborhood->edges.insert(found.it, neighbor_t(new_neighbor, EdgeContent()));
2030  return edge_t(v.id(), new_neighbor.id(), &*new_edge_it);
2031  }
2032 
2033  template <typename VertexContent, typename EdgeContent, typename Alloc>
2036  {
2037  if(v.isNull() || new_neighbor.isNull() || v == new_neighbor)
2038  return edge_t();
2039  NeighborhoodPair* it_found = this->findVertex(v);
2040  if(not it_found)
2041  return edge_t();
2042  ineighbor_iterator it_in;
2043  bool inserted;
2044  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2045  if(!inserted)
2046  return edge_t();
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);
2051  }
2052 
2053  template <typename VertexContent, typename EdgeContent, typename Alloc>
2056  {
2058  if(v.isNull())
2059  return result;
2060  const NeighborhoodPair* it_found = this->findVertex(v);
2061  if(not it_found)
2062  return result;
2063  const edge_list_t& lst = it_found->single_neighborhood.edges;
2064  result.first = const_neighbor_iterator(lst.begin());
2065  result.second = const_neighbor_iterator(lst.end());
2066  return result;
2067  }
2068  template <typename VertexContent, typename EdgeContent, typename Alloc>
2071  {
2072  neighbor_iterator_pair result;
2073  if(v.isNull())
2074  return result;
2075  NeighborhoodPair* it_found = this->findVertex(v);
2076  if(not it_found)
2077  return result;
2078  edge_list_t& lst = it_found->single_neighborhood.edges;
2079  result.first = neighbor_iterator(lst.begin());
2080  result.second = neighbor_iterator(lst.end());
2081  return result;
2082  }
2083 
2084  template <typename VertexContent, typename EdgeContent, typename Alloc>
2087  {
2089  if(v.isNull())
2090  return result;
2091  const_neighbor_found_t found = this->findInVertex(v, n);
2092  if(!found)
2093  return result;
2094  const edge_list_t& lst = found.neighborhood->edges;
2095  result.first = const_circ_neighbor_iterator(lst.begin(), lst.end(), found.it);
2096  result.second = const_circ_neighbor_iterator(lst.begin(), lst.end());
2097  return result;
2098  }
2099 
2100  template <typename VertexContent, typename EdgeContent, typename Alloc>
2103  {
2105  if(v.isNull())
2106  return result;
2107  neighbor_found_t found = this->findInVertex(v, n);
2108  if(!found)
2109  return result;
2110  edge_list_t& lst = found.neighborhood->edges;
2111  result.first = circ_neighbor_iterator(lst.begin(), lst.end(), found.it);
2112  result.second = circ_neighbor_iterator(lst.begin(), lst.end());
2113  return result;
2114  }
2115 
2116  template <typename VertexContent, typename EdgeContent, typename Alloc>
2117  typename VVGraph<VertexContent, EdgeContent, Alloc>::const_ineighbor_iterator_pair
2119  {
2120  const_ineighbor_iterator_pair result;
2121  if(v.isNull())
2122  return result;
2123  const NeighborhoodPair* it_found = this->findVertex(v);
2124  if(not it_found)
2125  return 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());
2129  return result;
2130  }
2131 
2132  template <typename VertexContent, typename EdgeContent, typename Alloc>
2135  {
2136  ineighbor_iterator_pair result;
2137  if(v.isNull())
2138  return result;
2139  NeighborhoodPair* it_found = this->findVertex(v);
2140  if(not it_found)
2141  return result;
2142  in_edges_t& lst = it_found->single_neighborhood.in_edges;
2143  result.first = ineighbor_iterator(lst.begin());
2144  result.second = ineighbor_iterator(lst.end());
2145  return result;
2146  }
2147 
2148  template <typename VertexContent, typename EdgeContent, typename Alloc>
2149  template <typename VertexContainer>
2151  VVGraph<VertexContent, EdgeContent, Alloc>::subgraph(const VertexContainer& verts) const
2152  {
2153  typename VertexContainer::const_iterator it;
2154  VVGraph result;
2155  // First, insert the vertexes in the result graph
2156  for(it = verts.begin(); it != verts.end(); ++it) {
2157  result.insert(*it);
2158  }
2159  const NeighborhoodPair* it_orign;
2160  typename neighborhood_t::iterator it_n;
2161  typename edge_list_t::const_reverse_iterator it_sn;
2162  // Then, creates the in and out edges
2163  for(it_n = result.neighborhood.begin(); it_n != result.neighborhood.end(); ++it_n) {
2164  const vertex_t& v = (*it_n)->vertex;
2165  // For each vertex, find out which edges to add
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;
2169  // Going backward because it is easier to retrieve the iterator ...
2170  for(it_sn = orig_lst.rbegin(); it_sn != orig_lst.rend(); ++it_sn) {
2171  // For each existing edge from the vertex, keep only the ones whose
2172  // target are on the subgraph
2173  if(result.contains(it_sn->target)) {
2174  // Insert the incoming edge
2175  ineighbor_iterator it_in = result.insertInEdge(v, it_sn->target).first;
2176  // Insert the outgoing edge
2177  lst.push_front(neighbor_t(it_sn->target, *it_sn));
2178  }
2179  }
2180  // At last, update the flag, if any
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);
2184  }
2185  }
2186  return result;
2187  }
2188 
2189  template <typename VertexContent, typename EdgeContent, typename Alloc>
2191  : modified_vertices(false)
2192  {
2193  *this = copy;
2194  }
2195 
2196  template <typename VertexContent, typename EdgeContent, typename Alloc>
2198  {
2199  if(neighborhood.size() != other.neighborhood.size())
2200  return false;
2201  for(typename neighborhood_t::const_iterator it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2202  const vertex_t& v1 = it->vertex;
2203  typename lookup_t::const_iterator it_found = other.lookup.find(v1);
2204  if(it_found == other.lookup.end())
2205  return false;
2206  if(it->single_neighborhood.edges.empty()) {
2207  if(!it_found->single_neighborhood.single_neighborhood.edges.empty())
2208  return false;
2209  } else {
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())
2213  return false;
2214  const vertex_t& v2 = lst.begin()->target;
2215  bool found = false;
2216  for(typename edge_list_t::const_iterator it_olst = olst.begin(); it_olst != olst.end(); ++it_olst) {
2217  if(it_olst->target == v2) {
2218  found = true;
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)
2221  return false;
2222  ++it_olst;
2223  if(it_olst == olst.end())
2224  it_olst = olst.begin();
2225  }
2226  break;
2227  }
2228  }
2229  if(!found)
2230  return false;
2231  }
2232  }
2233  return true;
2234  }
2235 
2236  template <typename VertexContent, typename EdgeContent, typename Alloc>
2238  {
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());
2242  }
2243  return *this;
2244  }
2245 
2246  template <typename VertexContent, typename EdgeContent, typename Alloc>
2248  {
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);
2253  *it = 0;
2254  }
2255  neighborhood.clear();
2256  lookup.clear();
2257  it = neighborhood.end();
2258  for(it_o = other.neighborhood.begin(); it_o != other.neighborhood.end(); ++it_o) {
2259  NeighborhoodPair* np = (*it_o)->copy();
2260  neighborhood.push_back(np);
2261  lookup[(*it_o)->vertex] = np;
2262  }
2263  return *this;
2264 
2265  // Copy the structure
2266  /*
2267  * neighborhood = other.neighborhood;
2268  * lookup.clear();
2269  * typename neighborhood_t::iterator it;
2270  * for(it = neighborhood.begin() ; it != neighborhood.end() ; ++it)
2271  * lookup[it->vertex] = it;
2272  * return *this;
2273  */
2274  }
2275 
2276  template <typename VertexContent, typename EdgeContent, typename Alloc>
2278  {
2279  neighborhood.swap(other.neighborhood);
2280  lookup.swap(other.lookup);
2281  }
2282 
2283  template <typename Graph> void create_graph_methods(Graph& G)
2284  {
2285  if(G.size()) {
2286  if(G.valence(G.any()) > G.size()) {
2287  // Call all fcts
2288  typename Graph::vertex_t v = G.any();
2289  G.erase(v);
2290  G.insert(v);
2291  G[10];
2292  G.reference(v);
2293  G.empty();
2294  G.anyIn(v);
2295  G.valence(v);
2296  G.empty(v);
2297  G.iAnyIn(v);
2298  G.iValence(v);
2299  G.iEmpty(v);
2300  G.nextTo(v, v);
2301  G.prevTo(v, v);
2302  G.edge(v, v);
2303  G.flag(v, v);
2304  G.flagged(v);
2305  G.neighbors(v);
2306  G.iNeighbors(v);
2307  G.source(typename Graph::edge_t());
2308  G.target(typename Graph::edge_t());
2309  G.eraseEdge(v, v);
2310  G.replace(v, v, v);
2311  G.spliceAfter(v, v, v);
2312  G.spliceBefore(v, v, v);
2313  G.insertEdge(v, v);
2314  G.eraseAllEdges(v);
2315  G.begin();
2316  G.end();
2317  G.find(v);
2318  G.count(v);
2319  G.findIn(v, v);
2320  {
2321  const Graph& cG = G;
2322  cG[10];
2323  cG.reference(v);
2324  cG.empty();
2325  cG.anyIn(v);
2326  cG.valence(v);
2327  cG.empty(v);
2328  cG.iAnyIn(v);
2329  cG.iValence(v);
2330  cG.iEmpty(v);
2331  cG.nextTo(v, v);
2332  cG.prevTo(v, v);
2333  cG.edge(v, v);
2334  cG.flagged(v);
2335  cG.neighbors(v);
2336  cG.iNeighbors(v);
2337  cG.source(typename Graph::edge_t());
2338  cG.target(typename Graph::edge_t());
2339  cG.begin();
2340  cG.end();
2341  cG.find(v);
2342  cG.count(v);
2343  cG.findIn(v, v);
2344  }
2345  }
2346  }
2347  }
2348 
2349 }}
2350 
2351 #endif
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)
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