MorphoGraphX
VVGraph.hpp
Go to the documentation of this file.
1 //
2 // This file is part of MorphoGraphX - http://www.MorphoGraphX.org
3 // Copyright (C) 2012-2015 Richard S. Smith and collaborators.
4 //
5 // If you use MorphoGraphX in your work, please cite:
6 // http://dx.doi.org/10.7554/eLife.05864
7 //
8 // MorphoGraphX is free software, and is licensed under under the terms of the
9 // GNU General (GPL) Public License version 2.0, http://www.gnu.org/licenses.
10 //
11 #ifndef VV_GRAPH_HPP
12 #define VV_GRAPH_HPP
13 
20 #include <Config.hpp>
21 
22 #include <CircIterator.hpp>
23 #include <Edge.hpp>
24 #include <Forall.hpp>
25 #include <MemberIterator.hpp>
26 #include <Tie.hpp>
27 #include <UnorderedMap.hpp>
28 #include <Vertex.hpp>
29 
30 #include <algorithm>
31 #include <iostream>
32 #include <iterator>
33 #include <list>
34 #include <memory>
35 #include <utility>
36 #include <vector>
37 
38 namespace std {
39 using namespace tr1;
40 }
41 
42 namespace mgx { namespace graph {
43 
56  _EmptyEdgeContent& operator=(const _EmptyEdgeContent& /*other*/) {
57  return *this;
58  }
59  };
60 
74  template <typename VertexContent, typename EdgeContent = _EmptyEdgeContent,
75  typename Alloc = std::allocator<VertexContent> >
76  class VVGraph {
77  public:
78  typedef typename Alloc::template rebind<EdgeContent>::other EdgeAlloc;
79  static EdgeAlloc edge_alloc;
80 
82 
83 
86  typedef typename Alloc::template rebind<VertexContent>::other VertexAlloc;
97 
101  typedef vertex_t value_type;
102 
108  VVGraph() : modified_vertices(false) {}
109 
115  VVGraph(const VVGraph& copy);
116 
122  template <typename Iterator> VVGraph(Iterator begin, Iterator end, bool check_unique = true)
123  {
124  insert(begin, end, check_unique);
125  }
126 
132  template <typename Container> VVGraph(const Container& c, bool check_unique = true)
133  {
134  insert(util::ForAll::make_range(c), check_unique);
135  }
136 
137  protected:
138  struct single_neighborhood_t;
139 
143  struct neighbor_t : public EdgeContent {
147  typedef std::list<neighbor_t> edge_list_t;
148 
152  neighbor_t(const vertex_t& tgt, const EdgeContent& e) : EdgeContent(e), target(tgt) {}
153 
154  neighbor_t(const neighbor_t& copy) : EdgeContent(copy) , target(copy.target) {}
155 
156  void clear_edge() {
157  static_cast<EdgeContent&>(*this) = EdgeContent();
158  }
159 
160  ~neighbor_t() {}
161 
162  neighbor_t& operator=(const neighbor_t& copy)
163  {
164  target = copy.target;
165  static_cast<EdgeContent&>(*this) = static_cast<const EdgeContent&>(copy);
166  return *this;
167  }
168 
174  vertex_t target;
175 
182  bool operator==(const neighbor_t& other) const
183  {
184  return (target == other.target)
185  && (static_cast<const EdgeContent&>(*this) == static_cast<const EdgeContent&>(other));
186  }
187  };
188 
192  typedef typename neighbor_t::edge_list_t edge_list_t;
193 
197  typedef std::vector<vertex_t> in_edges_t;
198 
203 
204  single_neighborhood_t() : flagged(0) {}
205 
207  : edges(copy.edges), in_edges(copy.in_edges), flagged(copy.flagged)
208  {
209  if(flagged) {
210  for(typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
211  if(it->target == *flagged) {
212  flagged = &it->target;
213  break;
214  }
215  }
216  }
217  }
218 
222  edge_list_t edges;
223 
227  in_edges_t in_edges;
228 
232  const vertex_t* flagged;
233 
234  single_neighborhood_t& operator=(const single_neighborhood_t& other)
235  {
236  edges = other.edges;
237  in_edges = other.in_edges;
238  if(other.flagged) {
239  for(typename edge_list_t::iterator it = edges.begin(); it != edges.end(); ++it) {
240  if(it->target == *flagged) {
241  flagged = &it->target;
242  break;
243  }
244  }
245  } else
246  flagged = 0;
247  return *this;
248  }
249 
255  bool operator==(const single_neighborhood_t& other) const {
256  return edges == other.edges;
257  }
258  };
259 
260  public:
262  protected:
263  NeighborhoodPair(const vertex_t& v) : vertex(v) {}
264 
266  : vertex(copy.vertex), single_neighborhood(copy.single_neighborhood) {}
267 
268  public:
269  NeighborhoodPair* copy() const
270  {
271  NeighborhoodPair* np = np_alloc.allocate(1);
272  ::new (np) NeighborhoodPair(*this);
273  return np;
274  }
275 
276  static NeighborhoodPair* New(const vertex_t& v)
277  {
278  NeighborhoodPair* np = np_alloc.allocate(1);
279  ::new (np) NeighborhoodPair(v);
280  return np;
281  }
282 
283  static void Delete(NeighborhoodPair* np)
284  {
285  if(np) {
286  np->~NeighborhoodPair();
287  np_alloc.deallocate(np, 1);
288  }
289  }
290 
291  vertex_t vertex;
292  single_neighborhood_t single_neighborhood;
293  };
294 
295  typedef typename Alloc::template rebind<NeighborhoodPair>::other NPAlloc;
296  static NPAlloc np_alloc;
297 
298  // typedef std::map<vertex_t, single_neighborhood_t> neighborhood_t;
302  typedef std::vector<NeighborhoodPair*> neighborhood_t;
303 
307  typedef std::unordered_map<vertex_t, NeighborhoodPair*> lookup_t;
308 
312  typedef typename neighborhood_t::value_type neighborhood_value_type;
313 
317  typedef typename neighborhood_t::size_type size_type;
318 
320 
321 
324  #ifdef _MSC_VER
325  typedef const vertex_t typename std::iterator_traits<typename neighborhood_t::iterator>::value_type::*
326  msvc_bug_workaround_t;
327 
328  typedef util::SelectMemberPointerIterator<typename neighborhood_t::iterator, const vertex_t,
329  reinterpret_cast<msvc_bug_workaround_t>(&neighborhood_value_type::first)>
330  iterator;
334  typedef util::SelectMemberPointerIterator<typename neighborhood_t::const_iterator, const vertex_t,
335  reinterpret_cast<msvc_bug_workaround_t>(&neighborhood_value_type::vertex)>
337  #else
338  typedef util::SelectMemberPointerIterator<typename neighborhood_t::iterator, const vertex_t,
343  typedef util::SelectMemberPointerIterator<typename neighborhood_t::const_iterator, const vertex_t,
345  #endif
346 
356  typedef std::pair<neighbor_iterator, neighbor_iterator> neighbor_iterator_pair;
357 
363 
367  typedef std::pair<circ_neighbor_iterator, circ_neighbor_iterator> circ_neighbor_iterator_pair;
368 
375  typedef typename in_edges_t::iterator ineighbor_iterator;
376  typedef typename in_edges_t::const_iterator const_ineighbor_iterator;
377 
385  typedef std::pair<ineighbor_iterator, ineighbor_iterator> ineighbor_iterator_pair;
386  typedef std::pair<const_ineighbor_iterator, const_ineighbor_iterator> const_ineighbor_iterator_pair;
387 
398  typedef std::pair<const_neighbor_iterator, const_neighbor_iterator> const_neighbor_iterator_pair;
399 
405 
409  typedef std::pair<const_circ_neighbor_iterator, const_circ_neighbor_iterator> const_circ_neighbor_iterator_pair;
410 
412 
414 
415 
431  size_type erase(const vertex_t& v);
432 
445  iterator insert(const vertex_t& v);
446 
448 
450 
451 
464  const vertex_t& any() const;
465 
495  const vertex_t& operator[](size_type idx) const;
496 
510  bool contains(const vertex_t& v) const;
511 
532  const vertex_t& reference(vertex_t v) const
533  {
534  const NeighborhoodPair* found = this->findVertex(v);
535  if(found)
536  return found->vertex;
537  return vertex_t::null; // vertex_t(0);
538  }
539 
543  size_type size() const {
544  return neighborhood.size();
545  }
546 
550  bool empty() const {
551  return neighborhood.empty();
552  }
553 
555 
557 
558 
578  const vertex_t& anyIn(const vertex_t& v) const;
579 
596  size_type valence(const vertex_t& v) const;
597 
619  bool empty(const vertex_t& v) const;
620 
642  const vertex_t& iAnyIn(const vertex_t& v) const;
643 
661  size_type iValence(const vertex_t& v) const;
662 
684  bool iEmpty(const vertex_t& v) const;
685 
705  const vertex_t& nextTo(const vertex_t& v, const vertex_t& neighbor, unsigned int n = 1) const;
706 
726  const vertex_t& prevTo(const vertex_t& v, const vertex_t& ref, unsigned int n = 1) const;
727 
754  edge_t edge(const vertex_t& src, const vertex_t& tgt);
755 
784  const_edge_t edge(const vertex_t& src, const vertex_t& tgt) const;
785 
817  bool flag(const vertex_t& src, const vertex_t& neighbor);
818 
824  const vertex_t& flagged(const vertex_t& src) const;
825 
842  const_neighbor_iterator_pair neighbors(const vertex_t& v) const;
859  neighbor_iterator_pair neighbors(const vertex_t& v);
860 
875  circ_neighbor_iterator_pair neighbors(const vertex_t& v, const vertex_t& n);
876 
891  const_circ_neighbor_iterator_pair neighbors(const vertex_t& v, const vertex_t& n) const;
892 
912  ineighbor_iterator_pair iNeighbors(const vertex_t& v);
913 
933  const_ineighbor_iterator_pair iNeighbors(const vertex_t& v) const;
934 
948  const vertex_t& source(const edge_t& edge) const
949  {
950  const NeighborhoodPair* found = this->findVertex(vertex_t(edge.source()));
951  if(found)
952  return found->vertex;
953  return vertex_t::null; // vertex_t(0);
954  }
955 
969  const vertex_t& target(const edge_t& edge) const
970  {
971  const NeighborhoodPair* found = this->findVertex(vertex_t(edge.target()));
972  if(found)
973  return found->vertex;
974  return vertex_t::null; // vertex_t(0);
975  }
976 
978 
980 
981 
1003  size_type eraseEdge(const vertex_t& src, const vertex_t& tgt);
1004 
1036  edge_t replace(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1037 
1064  edge_t spliceAfter(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1065 
1092  edge_t spliceBefore(const vertex_t& v, const vertex_t& neighbor, const vertex_t& new_neighbor);
1093 
1112  edge_t insertEdge(const vertex_t& src, const vertex_t& tgt);
1113 
1134  bool eraseAllEdges(const vertex_t& v);
1135 
1153  bool clear(const vertex_t& v);
1154 
1156 
1158 
1159 
1162  VVGraph& operator=(const VVGraph& other);
1163 
1167  VVGraph& reverse();
1168 
1172  void swap(VVGraph& other);
1173 
1183  bool operator==(const VVGraph& other) const;
1184 
1188  void clear();
1189 
1206  void eraseAllEdges();
1207 
1223  template <typename VertexContainer> VVGraph subgraph(const VertexContainer& vertexes) const;
1225 
1227 
1228 
1232  void erase(iterator pos);
1233 
1237  size_type eraseEdge(const vertex_t& v, neighbor_iterator pos);
1238 
1242  size_type eraseEdge(const vertex_t& v, circ_neighbor_iterator pos);
1243 
1249  iterator insert(iterator pos, const vertex_t& v);
1253  template <typename Iterator> void insert(Iterator first, Iterator last, bool check_unique = true);
1254 
1258  template <typename Iterator> void insert(const std::pair<Iterator, Iterator>& range, bool check_unique = true);
1259 
1263  iterator begin() {
1264  return neighborhood.begin();
1265  }
1269  iterator end() {
1270  return neighborhood.end();
1271  }
1272 
1276  const_iterator begin() const {
1277  return neighborhood.begin();
1278  }
1282  const_iterator end() const {
1283  return neighborhood.end();
1284  }
1285 
1289  size_type count(const vertex_t& v) const;
1290 
1300  neighbor_iterator findIn(const vertex_t& v, const vertex_t& n);
1310  const_neighbor_iterator findIn(const vertex_t& v, const vertex_t& n) const;
1311 
1317  void eraseAllEdges(iterator it);
1318 
1322  void clear(iterator it);
1323 
1327  void reserve(size_type s) {
1328  neighborhood.reserve(s);
1329  }
1330 
1332 
1333  protected:
1334  void eraseAllEdges(NeighborhoodPair* it);
1341  template <class Neighborhood, class Iterator> struct search_result_t {
1347  search_result_t() : found(false), neighborhood(0) {}
1348 
1352  search_result_t(Iterator i, Neighborhood* n, bool ok = true)
1353  : found(ok) , it(i), neighborhood(n) {}
1354 
1359  : found(copy.found), it(copy.it), neighborhood(copy.neighborhood) {}
1360 
1364  operator bool() {
1365  return found;
1366  }
1367 
1371  bool found;
1375  Iterator it;
1379  Neighborhood* neighborhood;
1380  };
1381 
1385  typedef typename edge_list_t::iterator int_neighbor_iterator;
1389  typedef typename edge_list_t::const_iterator int_const_neighbor_iterator;
1390 
1394  typedef search_result_t<single_neighborhood_t, int_neighbor_iterator> neighbor_found_t;
1398  typedef search_result_t<const single_neighborhood_t, int_const_neighbor_iterator> const_neighbor_found_t;
1399 
1407  NeighborhoodPair* findVertex(const vertex_t& v);
1408 
1412  const NeighborhoodPair* findVertex(const vertex_t& v) const;
1413 
1417  typename neighborhood_t::iterator findIterator(const NeighborhoodPair* np);
1418  typename neighborhood_t::const_iterator findIterator(const NeighborhoodPair* np) const;
1419 
1434  neighbor_found_t findInVertex(const vertex_t& v, const vertex_t& neighbor);
1435 
1439  const_neighbor_found_t findInVertex(const vertex_t& v, const vertex_t& neighbor) const;
1440 
1445  std::pair<ineighbor_iterator, bool> insertInEdge(const vertex_t& v, const vertex_t& new_neighbor);
1446 
1451  void undoInEdge(const vertex_t& new_neighbor, ineighbor_iterator& it);
1452 
1456  neighborhood_t neighborhood;
1457 
1461  lookup_t lookup;
1462 
1467  };
1468 
1469  template <typename VertexContent, typename EdgeContent, typename Alloc>
1470  typename VVGraph<VertexContent, EdgeContent, Alloc>::EdgeAlloc VVGraph<VertexContent, EdgeContent, Alloc>::edge_alloc;
1471  template <typename VertexContent, typename EdgeContent, typename Alloc>
1472  typename VVGraph<VertexContent, EdgeContent, Alloc>::NPAlloc VVGraph<VertexContent, EdgeContent, Alloc>::np_alloc;
1473 
1474  template <typename VertexContent, typename EdgeContent, typename Alloc>
1476  {
1477  typename neighborhood_t::iterator it;
1478  for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
1479  NeighborhoodPair::Delete(*it);
1480  *it = 0;
1481  }
1482  neighborhood.clear();
1483  lookup.clear();
1484  }
1485 
1486  template <typename VertexContent, typename EdgeContent, typename Alloc>
1488  {
1489  eraseAllEdges(it);
1490  lookup.erase(*it);
1491  NeighborhoodPair::Delete(*it.base());
1492  *it.base() = neighborhood.back();
1493  neighborhood.pop_back();
1494  }
1495 
1496  template <typename VertexContent, typename EdgeContent, typename Alloc>
1499  {
1500  if(eraseAllEdges(v)) {
1501  NeighborhoodPair* np = lookup[v];
1502  lookup.erase(v);
1503  typename neighborhood_t::iterator it = this->findIterator(np);
1504  NeighborhoodPair::Delete(np);
1505  *it = neighborhood.back();
1506  neighborhood.pop_back();
1507  return 1;
1508  }
1509  return 0;
1510  }
1511  template <typename VertexContent, typename EdgeContent, typename Alloc>
1513  {
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;
1518  }
1519  }
1520 
1521  template <typename VertexContent, typename EdgeContent, typename Alloc>
1523  {
1524  NeighborhoodPair* it_found = this->findVertex(v);
1525  if(it_found) {
1526  eraseAllEdges(it_found);
1527  return true;
1528  }
1529  return false;
1530  }
1531 
1532  template <typename VertexContent, typename EdgeContent, typename Alloc>
1534  {
1535  const vertex_t& v = np->vertex;
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);
1540  ie.erase(it_found);
1541  }
1542  np->single_neighborhood.edges.clear();
1543  np->single_neighborhood.flagged = 0;
1544  // Remove the incoming edges
1545  in_edges_t& in_edges = np->single_neighborhood.in_edges;
1546  for(typename in_edges_t::iterator it = in_edges.begin(); it != in_edges.end(); ++it) {
1547  neighbor_found_t found = findInVertex(*it, v);
1548  found.neighborhood->edges.erase(found.it);
1549  if(found.neighborhood->flagged && *found.neighborhood->flagged == v)
1550  found.neighborhood->flagged = 0;
1551  }
1552  in_edges.clear();
1553  }
1554 
1555  template <typename VertexContent, typename EdgeContent, typename Alloc>
1557  {
1558  eraseAllEdges(*it_found.base());
1559  }
1560 
1561  template <typename VertexContent, typename EdgeContent, typename Alloc>
1563  {
1564  typename neighborhood_t::iterator it_found = this->findVertex(v);
1565  if(it_found != neighborhood.end()) {
1566  clear(it_found);
1567  return true;
1568  }
1569  return false;
1570  }
1571 
1572  template <typename VertexContent, typename EdgeContent, typename Alloc>
1574  {
1575  const vertex_t& v = *it;
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);
1582  }
1583  it.base()->single_neighborhood.edges.clear();
1584  }
1585 
1586  template <typename VertexContent, typename EdgeContent, typename Alloc>
1589  {
1590  return lookup.count(v);
1591  }
1592 
1593  template <typename VertexContent, typename EdgeContent, typename Alloc>
1596  {
1597  typename lookup_t::iterator it_found = lookup.find(v);
1598  if(it_found == lookup.end()) {
1599  NeighborhoodPair* np = NeighborhoodPair::New(v);
1600  neighborhood.push_back(np);
1601  lookup[v] = np;
1602  iterator it = neighborhood.end();
1603  --it;
1604  return it;
1605  }
1606  return findIterator(it_found->second);
1607  }
1608 
1609  template <typename VertexContent, typename EdgeContent, typename Alloc>
1612  {
1613  return this->insert(v);
1614  }
1615 
1616  template <typename VertexContent, typename EdgeContent, typename Alloc>
1617  template <typename Iterator>
1618  void VVGraph<VertexContent, EdgeContent, Alloc>::insert(const std::pair<Iterator, Iterator>& range, bool check_unique)
1619  {
1620  insert(range.first, range.second, check_unique);
1621  }
1622 
1623  template <typename VertexContent, typename EdgeContent, typename Alloc>
1624  template <typename Iterator>
1625  void VVGraph<VertexContent, EdgeContent, Alloc>::insert(Iterator first, Iterator last, bool check_unique)
1626  {
1627  if(check_unique) {
1628  for(Iterator it = first; it != last; ++it) {
1629  insert(*it);
1630  }
1631  } else {
1632  for(Iterator it = first; it != last; ++it) {
1633  NeighborhoodPair* np = NeighborhoodPair::New(*it);
1634  neighborhood.push_back(np);
1635  lookup[*it] = np;
1636  }
1637  }
1638  }
1639 
1640  template <typename VertexContent, typename EdgeContent, typename Alloc>
1643  {
1644  if(neighborhood.empty())
1645  return vertex_t::null;
1646  return *begin();
1647  }
1648 
1649  template <typename VertexContent, typename EdgeContent, typename Alloc>
1652  {
1653  typename neighborhood_t::const_iterator it = neighborhood.begin();
1654  std::advance(it, idx);
1655  return (*it)->vertex;
1656  }
1657 
1658  template <typename VertexContent, typename EdgeContent, typename Alloc>
1661  {
1662  if(v.isNull())
1663  return vertex_t::null; // vertex_t(0);
1664  const NeighborhoodPair* it_found = this->findVertex(v);
1665  if(not it_found || it_found->single_neighborhood.edges.empty())
1666  return vertex_t::null; // vertex_t(0);
1667  const edge_list_t& lst = it_found->single_neighborhood.edges;
1668  return lst.front().target;
1669  }
1670 
1671  template <typename VertexContent, typename EdgeContent, typename Alloc>
1674  {
1675  if(v.isNull())
1676  return 0;
1677  const NeighborhoodPair* it_found = this->findVertex(v);
1678  if(not it_found)
1679  return 0;
1680  return it_found->single_neighborhood.edges.size();
1681  }
1682 
1683  template <typename VertexContent, typename EdgeContent, typename Alloc>
1685  {
1686  if(v.isNull())
1687  return true;
1688  const NeighborhoodPair* it_found = this->findVertex(v);
1689  if(not it_found)
1690  return true;
1691  return it_found->single_neighborhood.edges.empty();
1692  }
1693 
1694  template <typename VertexContent, typename EdgeContent, typename Alloc>
1697  {
1698  if(v.isNull())
1699  return vertex_t::null; // vertex_t(0);
1700  const NeighborhoodPair& it_found = this->findVertex(v);
1701  if(not it_found || it_found->single_neighborhood.in_edges.empty())
1702  return vertex_t::null; // vertex_t(0);
1703  const in_edges_t& lst = it_found->single_neighborhood.in_edges;
1704  return *lst.begin();
1705  }
1706 
1707  template <typename VertexContent, typename EdgeContent, typename Alloc>
1710  {
1711  if(v.isNull())
1712  return 0;
1713  const NeighborhoodPair* it_found = this->findVertex(v);
1714  if(not it_found)
1715  return 0;
1716  return it_found->single_neighborhood.in_edges.size();
1717  }
1718 
1719  template <typename VertexContent, typename EdgeContent, typename Alloc>
1721  {
1722  if(v.isNull())
1723  return true;
1724  const NeighborhoodPair* it_found = this->findVertex(v);
1725  if(not it_found)
1726  return true;
1727  return it_found->single_neighborhood.in_edges.empty();
1728  }
1729 
1730  template <typename VertexContent, typename EdgeContent, typename Alloc>
1733  {
1734  return std::find(neighborhood.begin(), neighborhood.end(), np);
1735  }
1736 
1737  template <typename VertexContent, typename EdgeContent, typename Alloc>
1740  {
1741  return std::find(neighborhood.begin(), neighborhood.end(), np);
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  typename lookup_t::const_iterator it_found = lookup.find(v);
1759  if(it_found != lookup.end())
1760  return it_found->second;
1761  return 0;
1762  }
1763 
1764  template <typename VertexContent, typename EdgeContent, typename Alloc>
1767  {
1768  if(v.isNull() || n.isNull() || v == n)
1769  return neighbor_found_t();
1770  NeighborhoodPair* it_found = this->findVertex(v);
1771  if(not it_found)
1772  return neighbor_found_t();
1773  edge_list_t& lst = it_found->single_neighborhood.edges;
1774  single_neighborhood_t* neighborhood = &it_found->single_neighborhood;
1775  for(typename edge_list_t::iterator it = lst.begin(); it != lst.end(); ++it) {
1776  if(it->target == n) {
1777  return neighbor_found_t(it, neighborhood);
1778  }
1779  }
1780  return neighbor_found_t(lst.end(), neighborhood, false);
1781  }
1782 
1783  template <typename VertexContent, typename EdgeContent, typename Alloc>
1786  {
1787  if(v.isNull() || n.isNull() || v == n)
1788  return const_neighbor_found_t();
1789  const NeighborhoodPair* it_found = this->findVertex(v);
1790  if(not it_found)
1791  return const_neighbor_found_t();
1792  const edge_list_t& lst = it_found->single_neighborhood.edges;
1793  const single_neighborhood_t* neighborhood = &it_found->single_neighborhood;
1794  for(typename edge_list_t::const_iterator it = lst.begin(); it != lst.end(); ++it) {
1795  if(it->target == n) {
1796  return const_neighbor_found_t(it, neighborhood);
1797  }
1798  }
1799  return const_neighbor_found_t(lst.end(), neighborhood, false);
1800  }
1801 
1802  template <typename VertexContent, typename EdgeContent, typename Alloc>
1805  {
1806  neighbor_found_t found = this->findInVertex(v, n);
1807  if(found.neighborhood)
1808  return neighbor_iterator(found.it);
1809  return neighbor_iterator();
1810  }
1811 
1812  template <typename VertexContent, typename EdgeContent, typename Alloc>
1815  {
1816  const_neighbor_found_t found = this->findInVertex(v, n);
1817  if(found.neighborhood)
1818  return const_neighbor_iterator(found.it);
1819  return const_neighbor_iterator(found.it);
1820  }
1821 
1822  template <typename VertexContent, typename EdgeContent, typename Alloc>
1825  {
1826  NeighborhoodPair* it_found = this->findVertex(v);
1827  if(not it_found)
1828  return 0;
1829  const vertex_t& n = *pos;
1830  NeighborhoodPair* it_found2 = this->findVertex(n);
1831  if(not it_found2)
1832  return 0;
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);
1839  return 1;
1840  }
1841  return 0;
1842  }
1843 
1844  template <typename VertexContent, typename EdgeContent, typename Alloc>
1847  {
1848  return eraseEdge(v, pos.base());
1849  }
1850 
1851  template <typename VertexContent, typename EdgeContent, typename Alloc>
1854  {
1855  neighbor_found_t found = this->findInVertex(v, n);
1856  if(!found)
1857  return 0;
1858  if(found.neighborhood->flagged && *found.neighborhood->flagged == n)
1859  found.neighborhood->flagged = 0;
1860  found.neighborhood->edges.erase(found.it);
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);
1864  return 1;
1865  }
1866 
1867  template <typename VertexContent, typename EdgeContent, typename Alloc>
1869  {
1870  return this->findVertex(v);
1871  }
1872 
1873  template <typename VertexContent, typename EdgeContent, typename Alloc>
1874  std::pair<typename VVGraph<VertexContent, EdgeContent, Alloc>::ineighbor_iterator, bool>
1876  {
1877  typename lookup_t::iterator found = lookup.find(new_neighbor);
1878  if(found == lookup.end())
1879  return std::make_pair(ineighbor_iterator(), false);
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);
1884  ie.push_back(v);
1885  ineighbor_iterator it = ie.end();
1886  --it;
1887  return std::make_pair(it, true);
1888  }
1889 
1890  template <typename VertexContent, typename EdgeContent, typename Alloc>
1892  {
1893  typename lookup_t::iterator found = lookup.find(new_neighbor);
1894  // typename neighborhood_t::iterator found = neighborhood.find(new_neighbor);
1895  // if(found == neighborhood.end())
1896  // return;
1897  if(found == lookup.end())
1898  return;
1899  found->single_neighborhood.single_neighborhood.in_edges.erase(it);
1900  }
1901 
1902  template <typename VertexContent, typename EdgeContent, typename Alloc>
1905  const vertex_t& new_neighbor)
1906  {
1907  if(new_neighbor.isNull() or (v == new_neighbor) or (neighbor == new_neighbor))
1908  return edge_t();
1909  neighbor_found_t found = this->findInVertex(v, neighbor);
1910  if(!found)
1911  return edge_t();
1912  NeighborhoodPair* n_found = this->findVertex(neighbor);
1913  ineighbor_iterator it_in;
1914  bool inserted;
1915  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
1916  if(!inserted)
1917  return edge_t();
1918  in_edges_t& ie = n_found->single_neighborhood.in_edges;
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;
1925  return edge_t(v.id(), new_neighbor.id(), &*found.it);
1926  }
1927 
1928  template <typename VertexContent, typename EdgeContent, typename Alloc>
1930  VVGraph<VertexContent, EdgeContent, Alloc>::nextTo(const vertex_t &v, const vertex_t &ref, unsigned int n) const
1931  {
1932  const_neighbor_found_t found = this->findInVertex(v, ref);
1933  if(!found)
1934  return vertex_t::null; // vertex_t(0);
1935  typename edge_list_t::const_iterator it = found.it;
1936  const edge_list_t& lst = found.neighborhood->edges;
1937  for(unsigned int i = 0; i < n; ++i) {
1938  ++it;
1939  if(it == lst.end())
1940  it = lst.begin();
1941  }
1942  return it->target;
1943  }
1944 
1945  template <typename VertexContent, typename EdgeContent, typename Alloc>
1947  VVGraph<VertexContent, EdgeContent, Alloc>::prevTo(const vertex_t &v, const vertex_t &ref, unsigned int n) const
1948  {
1949  const_neighbor_found_t found = this->findInVertex(v, ref);
1950  if(!found)
1951  return vertex_t::null; // vertex_t(0);
1952  typename edge_list_t::const_iterator it = found.it;
1953  const edge_list_t& lst = found.neighborhood->edges;
1954  for(unsigned int i = 0; i < n; ++i) {
1955  if(it == lst.begin())
1956  it = lst.end();
1957  --it;
1958  }
1959  return it->target;
1960  }
1961 
1962  template <typename VertexContent, typename EdgeContent, typename Alloc>
1965  {
1966  neighbor_found_t found = this->findInVertex(src, tgt);
1967  if(!found)
1968  return edge_t();
1969  return edge_t(src.id(), tgt.id(), &*found.it);
1970  }
1971 
1972  template <typename VertexContent, typename EdgeContent, typename Alloc>
1975  {
1976  const_neighbor_found_t found = this->findInVertex(src, tgt);
1977  if(!found)
1978  return const_edge_t();
1979  return const_edge_t(src.id(), tgt.id(), &*found.it);
1980  }
1981 
1982  template <typename VertexContent, typename EdgeContent, typename Alloc>
1984  {
1985  neighbor_found_t found = this->findInVertex(src, neighbor);
1986  if(!found)
1987  return false;
1988  found.neighborhood->flagged = &(found.it->target);
1989  return true;
1990  }
1991 
1992  template <typename VertexContent, typename EdgeContent, typename Alloc>
1995  {
1996  const NeighborhoodPair* found = this->findVertex(src);
1997  if(not found or found->single_neighborhood.flagged == 0)
1998  return vertex_t::null;
1999  return *found->single_neighborhood.flagged;
2000  }
2001 
2002  template <typename VertexContent, typename EdgeContent, typename Alloc>
2005  const vertex_t& new_neighbor)
2006  {
2007  if(new_neighbor.isNull() || v == new_neighbor)
2008  return edge_t();
2009  neighbor_found_t found = this->findInVertex(v, neighbor);
2010  if(!found)
2011  return edge_t();
2012  ineighbor_iterator it_in;
2013  bool inserted;
2014  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2015  if(!inserted)
2016  return edge_t();
2017  ++found.it;
2018  typename edge_list_t::iterator new_edge_it
2019  = found.neighborhood->edges.insert(found.it, neighbor_t(new_neighbor, EdgeContent()));
2020  return edge_t(v.id(), new_neighbor.id(), &*new_edge_it);
2021  }
2022 
2023  template <typename VertexContent, typename EdgeContent, typename Alloc>
2026  const vertex_t& new_neighbor)
2027  {
2028  if(new_neighbor.isNull() || v == new_neighbor)
2029  return edge_t();
2030  neighbor_found_t found = this->findInVertex(v, neighbor);
2031  if(!found)
2032  return edge_t();
2033  ineighbor_iterator it_in;
2034  bool inserted;
2035  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2036  if(!inserted)
2037  return edge_t();
2038  typename edge_list_t::iterator new_edge_it
2039  = found.neighborhood->edges.insert(found.it, neighbor_t(new_neighbor, EdgeContent()));
2040  return edge_t(v.id(), new_neighbor.id(), &*new_edge_it);
2041  }
2042 
2043  template <typename VertexContent, typename EdgeContent, typename Alloc>
2046  {
2047  if(v.isNull() || new_neighbor.isNull() || v == new_neighbor)
2048  return edge_t();
2049  NeighborhoodPair* it_found = this->findVertex(v);
2050  if(not it_found)
2051  return edge_t();
2052  ineighbor_iterator it_in;
2053  bool inserted;
2054  util::tie(it_in, inserted) = insertInEdge(v, new_neighbor);
2055  if(!inserted)
2056  return edge_t();
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);
2061  }
2062 
2063  template <typename VertexContent, typename EdgeContent, typename Alloc>
2066  {
2068  if(v.isNull())
2069  return result;
2070  const NeighborhoodPair* it_found = this->findVertex(v);
2071  if(not it_found)
2072  return result;
2073  const edge_list_t& lst = it_found->single_neighborhood.edges;
2074  result.first = const_neighbor_iterator(lst.begin());
2075  result.second = const_neighbor_iterator(lst.end());
2076  return result;
2077  }
2078  template <typename VertexContent, typename EdgeContent, typename Alloc>
2081  {
2082  neighbor_iterator_pair result;
2083  if(v.isNull())
2084  return result;
2085  NeighborhoodPair* it_found = this->findVertex(v);
2086  if(not it_found)
2087  return result;
2088  edge_list_t& lst = it_found->single_neighborhood.edges;
2089  result.first = neighbor_iterator(lst.begin());
2090  result.second = neighbor_iterator(lst.end());
2091  return result;
2092  }
2093 
2094  template <typename VertexContent, typename EdgeContent, typename Alloc>
2097  {
2099  if(v.isNull())
2100  return result;
2101  const_neighbor_found_t found = this->findInVertex(v, n);
2102  if(!found)
2103  return result;
2104  const edge_list_t& lst = found.neighborhood->edges;
2105  result.first = const_circ_neighbor_iterator(lst.begin(), lst.end(), found.it);
2106  result.second = const_circ_neighbor_iterator(lst.begin(), lst.end());
2107  return result;
2108  }
2109 
2110  template <typename VertexContent, typename EdgeContent, typename Alloc>
2113  {
2115  if(v.isNull())
2116  return result;
2117  neighbor_found_t found = this->findInVertex(v, n);
2118  if(!found)
2119  return result;
2120  edge_list_t& lst = found.neighborhood->edges;
2121  result.first = circ_neighbor_iterator(lst.begin(), lst.end(), found.it);
2122  result.second = circ_neighbor_iterator(lst.begin(), lst.end());
2123  return result;
2124  }
2125 
2126  template <typename VertexContent, typename EdgeContent, typename Alloc>
2127  typename VVGraph<VertexContent, EdgeContent, Alloc>::const_ineighbor_iterator_pair
2129  {
2130  const_ineighbor_iterator_pair result;
2131  if(v.isNull())
2132  return result;
2133  const NeighborhoodPair* it_found = this->findVertex(v);
2134  if(not it_found)
2135  return 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());
2139  return result;
2140  }
2141 
2142  template <typename VertexContent, typename EdgeContent, typename Alloc>
2145  {
2146  ineighbor_iterator_pair result;
2147  if(v.isNull())
2148  return result;
2149  NeighborhoodPair* it_found = this->findVertex(v);
2150  if(not it_found)
2151  return result;
2152  in_edges_t& lst = it_found->single_neighborhood.in_edges;
2153  result.first = ineighbor_iterator(lst.begin());
2154  result.second = ineighbor_iterator(lst.end());
2155  return result;
2156  }
2157 
2158  template <typename VertexContent, typename EdgeContent, typename Alloc>
2159  template <typename VertexContainer>
2161  VVGraph<VertexContent, EdgeContent, Alloc>::subgraph(const VertexContainer& verts) const
2162  {
2163  typename VertexContainer::const_iterator it;
2164  VVGraph result;
2165  // First, insert the vertexes in the result graph
2166  for(it = verts.begin(); it != verts.end(); ++it) {
2167  result.insert(*it);
2168  }
2169  const NeighborhoodPair* it_orign;
2170  typename neighborhood_t::iterator it_n;
2171  typename edge_list_t::const_reverse_iterator it_sn;
2172  // Then, creates the in and out edges
2173  for(it_n = result.neighborhood.begin(); it_n != result.neighborhood.end(); ++it_n) {
2174  const vertex_t& v = (*it_n)->vertex;
2175  // For each vertex, find out which edges to add
2176  it_orign = this->findVertex(v);
2177  const edge_list_t& orig_lst = it_orign->single_neighborhood.edges;
2178  edge_list_t& lst = (*it_n)->single_neighborhood.edges;
2179  // Going backward because it is easier to retrieve the iterator ...
2180  for(it_sn = orig_lst.rbegin(); it_sn != orig_lst.rend(); ++it_sn) {
2181  // For each existing edge from the vertex, keep only the ones whose
2182  // target are on the subgraph
2183  if(result.contains(it_sn->target)) {
2184  // Insert the incoming edge
2185  ineighbor_iterator it_in = result.insertInEdge(v, it_sn->target).first;
2186  // Insert the outgoing edge
2187  lst.push_front(neighbor_t(it_sn->target, *it_sn));
2188  }
2189  }
2190  // At last, update the flag, if any
2191  if(it_orign->single_neighborhood.flagged and result.contains(*it_orign->single_neighborhood.flagged)) {
2192  const_neighbor_found_t found = this->findInVertex(v, *it_orign->single_neighborhood.flagged);
2193  (*it_n)->single_neighborhood.flagged = &(found.it->target);
2194  }
2195  }
2196  return result;
2197  }
2198 
2199  template <typename VertexContent, typename EdgeContent, typename Alloc>
2201  : modified_vertices(false)
2202  {
2203  *this = copy;
2204  }
2205 
2206  template <typename VertexContent, typename EdgeContent, typename Alloc>
2208  {
2209  if(neighborhood.size() != other.neighborhood.size())
2210  return false;
2211  for(typename neighborhood_t::const_iterator it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2212  const vertex_t& v1 = it->vertex;
2213  typename lookup_t::const_iterator it_found = other.lookup.find(v1);
2214  if(it_found == other.lookup.end())
2215  return false;
2216  if(it->single_neighborhood.edges.empty()) {
2217  if(!it_found->single_neighborhood.single_neighborhood.edges.empty())
2218  return false;
2219  } else {
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())
2223  return false;
2224  const vertex_t& v2 = lst.begin()->target;
2225  bool found = false;
2226  for(typename edge_list_t::const_iterator it_olst = olst.begin(); it_olst != olst.end(); ++it_olst) {
2227  if(it_olst->target == v2) {
2228  found = true;
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)
2231  return false;
2232  ++it_olst;
2233  if(it_olst == olst.end())
2234  it_olst = olst.begin();
2235  }
2236  break;
2237  }
2238  }
2239  if(!found)
2240  return false;
2241  }
2242  }
2243  return true;
2244  }
2245 
2246  template <typename VertexContent, typename EdgeContent, typename Alloc>
2248  {
2249  typename neighborhood_t::iterator it;
2250  for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2251  std::reverse((*it)->single_neighborhood.edges.begin(), (*it)->single_neighborhood.edges.end());
2252  }
2253  return *this;
2254  }
2255 
2256  template <typename VertexContent, typename EdgeContent, typename Alloc>
2258  {
2259  typename neighborhood_t::const_iterator it_o;
2260  typename neighborhood_t::iterator it;
2261  for(it = neighborhood.begin(); it != neighborhood.end(); ++it) {
2262  NeighborhoodPair::Delete(*it);
2263  *it = 0;
2264  }
2265  neighborhood.clear();
2266  lookup.clear();
2267  it = neighborhood.end();
2268  for(it_o = other.neighborhood.begin(); it_o != other.neighborhood.end(); ++it_o) {
2269  NeighborhoodPair* np = (*it_o)->copy();
2270  neighborhood.push_back(np);
2271  lookup[(*it_o)->vertex] = np;
2272  }
2273  return *this;
2274 
2275  // Copy the structure
2276  /*
2277  * neighborhood = other.neighborhood;
2278  * lookup.clear();
2279  * typename neighborhood_t::iterator it;
2280  * for(it = neighborhood.begin() ; it != neighborhood.end() ; ++it)
2281  * lookup[it->vertex] = it;
2282  * return *this;
2283  */
2284  }
2285 
2286  template <typename VertexContent, typename EdgeContent, typename Alloc>
2288  {
2289  neighborhood.swap(other.neighborhood);
2290  lookup.swap(other.lookup);
2291  }
2292 
2293  template <typename Graph> void create_graph_methods(Graph& G)
2294  {
2295  if(G.size()) {
2296  if(G.valence(G.any()) > G.size()) {
2297  // Call all fcts
2298  typename Graph::vertex_t v = G.any();
2299  G.erase(v);
2300  G.insert(v);
2301  G[10];
2302  G.reference(v);
2303  G.empty();
2304  G.anyIn(v);
2305  G.valence(v);
2306  G.empty(v);
2307  G.iAnyIn(v);
2308  G.iValence(v);
2309  G.iEmpty(v);
2310  G.nextTo(v, v);
2311  G.prevTo(v, v);
2312  G.edge(v, v);
2313  G.flag(v, v);
2314  G.flagged(v);
2315  G.neighbors(v);
2316  G.iNeighbors(v);
2317  G.source(typename Graph::edge_t());
2318  G.target(typename Graph::edge_t());
2319  G.eraseEdge(v, v);
2320  G.replace(v, v, v);
2321  G.spliceAfter(v, v, v);
2322  G.spliceBefore(v, v, v);
2323  G.insertEdge(v, v);
2324  G.eraseAllEdges(v);
2325  G.begin();
2326  G.end();
2327  G.find(v);
2328  G.count(v);
2329  G.findIn(v, v);
2330  {
2331  const Graph& cG = G;
2332  cG[10];
2333  cG.reference(v);
2334  cG.empty();
2335  cG.anyIn(v);
2336  cG.valence(v);
2337  cG.empty(v);
2338  cG.iAnyIn(v);
2339  cG.iValence(v);
2340  cG.iEmpty(v);
2341  cG.nextTo(v, v);
2342  cG.prevTo(v, v);
2343  cG.edge(v, v);
2344  cG.flagged(v);
2345  cG.neighbors(v);
2346  cG.iNeighbors(v);
2347  cG.source(typename Graph::edge_t());
2348  cG.target(typename Graph::edge_t());
2349  cG.begin();
2350  cG.end();
2351  cG.find(v);
2352  cG.count(v);
2353  cG.findIn(v, v);
2354  }
2355  }
2356  }
2357  }
2358 
2359 }}
2360 
2361 #endif
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)
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
STL namespace.
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