fork download
copy 
  1. #include <algorithm>
  2. #include <list>
  3. #include <map>
  4. #include <queue>
  5. #include <set>
  6. #include <stack>
  7. #include <string>
  8.  
  9. namespace gtc
  10. {
  11.  
  12. /*****************************************************************************
  13.  * class _base_graph                                                         *
  14.  *****************************************************************************/
  15.  
  16.  
  17.  
  18. template <typename K, typename W, typename T>
  19. class _base_graph
  20. {
  21. protected:
  22.  
  23.     _base_graph()
  24.     {
  25.     }
  26.  
  27.     _base_graph(size_t n);
  28.  
  29.     _base_graph(size_t n, const K& k);
  30.  
  31.     template <typename F>
  32.     _base_graph(size_t n, F f);
  33.  
  34. public:
  35.     void add_node(const K& k);
  36.  
  37.     void add_node(const K& k, const T& t);
  38.  
  39.     std::size_t order()
  40.     {
  41.         return nod.size();
  42.     }
  43.  
  44.     size_t size()
  45.     {
  46.         return edg.size();
  47.     }
  48.  
  49.  
  50.     T& operator[] (const K& k);
  51.  
  52.     class iterator
  53.     {
  54.         friend class _base_graph<K, W, T>;
  55.     public:
  56.  
  57.         iterator& operator++()
  58.         {
  59.             ++it;
  60.             return *this;
  61.         }
  62.  
  63.         iterator operator++(int)
  64.         {
  65.             iterator i = (*this);
  66.             ++it;
  67.             return i;
  68.         }
  69.  
  70.         iterator& operator--()
  71.         {
  72.             --it;
  73.             return *this;
  74.         }
  75.  
  76.         iterator operator--(int)
  77.         {
  78.             iterator i = (*this);
  79.             --it;
  80.             return i;
  81.         }
  82.  
  83.         std::pair<const K, T>& operator*()
  84.         {
  85.             return *it;
  86.         }
  87.  
  88.         std::pair<const K, T>* operator-> ()
  89.         {
  90.             return &(*it);
  91.         }
  92.  
  93.         bool operator==(const iterator& i)
  94.         {
  95.             return it == i.it;
  96.         }
  97.  
  98.         bool operator!=(const iterator& i)
  99.         {
  100.             return it != i.it;
  101.         }
  102.  
  103.     private:
  104.         typename std::map<K, T>::iterator begin, end;
  105.         typename std::map<K, T>::iterator it;
  106.     };
  107.  
  108.     virtual iterator begin();
  109.  
  110.     virtual iterator end();
  111.  
  112.     virtual iterator find(const K& k);
  113.  
  114.     class edge
  115.     {
  116.     public:
  117.  
  118.         edge(const K& k1, const K& k2, const W& w = 0) :
  119.         ky1(k1), ky2(k2), wt(w)
  120.         {
  121.         }
  122.  
  123.         bool operator==(const edge& e) const
  124.         {
  125.             return key1() == e.key1() && key2() == e.key2();
  126.         }
  127.  
  128.         bool operator!=(const edge& e) const
  129.         {
  130.             return key1() != e.key1() || key2() != e.key2();
  131.         }
  132.  
  133.         const K& key1() const
  134.         {
  135.             return ky1;
  136.         }
  137.  
  138.         const K& key2() const
  139.         {
  140.             return ky2;
  141.         }
  142.  
  143.  
  144.         const K& key(const K& k);
  145.  
  146.         K& weight()
  147.         {
  148.             return wt;
  149.         }
  150.  
  151.     private:
  152.         K ky1;
  153.         K ky2;
  154.         W wt;
  155.     };
  156.  
  157.     virtual bool is_edge(const K& k1, const K& k2) = 0;
  158.  
  159.     class edge_iterator
  160.     {
  161.         friend class _base_graph<K, W, T>;
  162.     public:
  163.         edge_iterator& operator++();
  164.         edge_iterator operator++(int);
  165.         edge_iterator& operator--();
  166.         edge_iterator operator--(int);
  167.  
  168.         edge& operator*()
  169.         {
  170.             return *it;
  171.         }
  172.  
  173.         edge* operator-> ()
  174.         {
  175.             return &(*it);
  176.         }
  177.  
  178.         bool operator==(const edge_iterator& i)
  179.         {
  180.             return it == i.it;
  181.         }
  182.  
  183.         bool operator!=(const edge_iterator& i)
  184.         {
  185.             return it != i.it;
  186.         }
  187.  
  188.     private:
  189.         typename std::list<edge>::iterator begin, end;
  190.         typename std::list<edge>::iterator it;
  191.  
  192.         K key;
  193.     };
  194.  
  195.     edge_iterator begin(const K& k);
  196.  
  197.     edge_iterator end(const K& k);
  198.  
  199.     template <typename F>
  200.     F BFS(const K& k, F f);
  201.  
  202.     template <typename F>
  203.     F DFS(const K& k, F f);
  204.  
  205. protected:
  206.     std::map<K, T> nod;
  207.     std::list<edge> edg;
  208. };
  209.  
  210. template <typename K, typename W, typename T>
  211. _base_graph<K, W, T>::_base_graph(size_t n)
  212. {
  213.     K key(1);
  214.  
  215.     for (size_t i = 0; i < n; i++)
  216.         nod[key++] = T();
  217. }
  218.  
  219. template <typename K, typename W, typename T>
  220. _base_graph<K, W, T>::_base_graph(size_t n, const K& k)
  221. {
  222.     K key(k);
  223.  
  224.     for (size_t i = 0; i < n; i++)
  225.         nod[key++] = T();
  226. }
  227.  
  228. template <typename K, typename W, typename T>
  229. template <typename F>
  230. _base_graph<K, W, T>::_base_graph(size_t n, F f)
  231. {
  232.     for (size_t i = 0; i < n; i++)
  233.         nod[f()] = T();
  234. }
  235.  
  236. template <typename K, typename W, typename T>
  237. void _base_graph<K, W, T>::add_node(const K& k)
  238. {
  239.     if (nod.find(k) != nod.end())
  240.         throw std::string("_base_graph::add_node - node already exists");
  241.     nod[k] = T();
  242. }
  243.  
  244. template <typename K, typename W, typename T>
  245. void _base_graph<K, W, T>::add_node(const K& k, const T& t)
  246. {
  247.     if (nod.find(k) != nod.end())
  248.         throw std::string("_base_graph::add_node - node already exists");
  249.     nod[k] = t;
  250. }
  251.  
  252. template <typename K, typename W, typename T>
  253. typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::begin()
  254. {
  255.     iterator i;
  256.     i.begin = nod.begin();
  257.     i.end = nod.end();
  258.  
  259.     i.it = i.begin;
  260.  
  261.     return i;
  262. }
  263.  
  264. template <typename K, typename W, typename T>
  265. typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::begin(const K& k)
  266. {
  267.     edge_iterator i;
  268.     i.begin = edg.begin();
  269.     i.end = edg.end();
  270.     i.key = k;
  271.  
  272.     i.it = i.begin;
  273.     while (i.it != i.end && i.it->key1() != i.key && i.it->key2() != i.key)
  274.     {
  275.         i.it++;
  276.     }
  277.  
  278.     return i;
  279. }
  280.  
  281. template <typename K, typename W, typename T>
  282. typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::end()
  283. {
  284.     iterator i;
  285.     i.begin = nod.begin();
  286.     i.end = nod.end();
  287.  
  288.     i.it = i.end;
  289.  
  290.     return i;
  291. }
  292.  
  293. template <typename K, typename W, typename T>
  294. typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::end(const K& k)
  295. {
  296.     edge_iterator i;
  297.     i.begin = edg.begin();
  298.     i.end = edg.end();
  299.     i.key = k;
  300.  
  301.     i.it = i.end;
  302.  
  303.     return i;
  304. }
  305.  
  306. template <typename K, typename W, typename T>
  307. typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::find(const K& k)
  308. {
  309.     iterator i;
  310.     i.begin = nod.begin();
  311.     i.end = nod.end();
  312.     i.it = nod.find(k);
  313.  
  314.     return i;
  315. }
  316.  
  317. template <typename K, typename W, typename T>
  318. template <typename F>
  319. F _base_graph<K, W, T>::BFS(const K& k, F f)
  320. {
  321.     K cur;
  322.     std::queue<K> q;
  323.     std::set<K> v;
  324.  
  325.     q.push(k);
  326.     v.insert(k);
  327.  
  328.     while (!q.empty())
  329.     {
  330.  
  331.         cur = q.front();
  332.         q.pop();
  333.         f(cur);
  334.  
  335.         for (iterator i = begin(); i != end(); i++)
  336.             if (is_edge(cur, i->first))
  337.                 if (v.find(i->first) == v.end())
  338.                 {
  339.                     q.push(i->first);
  340.                     v.insert(i->first);
  341.                 }
  342.     }
  343.  
  344.     return f;
  345. }
  346.  
  347. template <typename K, typename W, typename T>
  348. template <typename F>
  349. F _base_graph<K, W, T>::DFS(const K& k, F f)
  350. {
  351.     K cur = k;
  352.     std::set<K> v;
  353.     std::stack<K> s;
  354.  
  355.     do
  356.     {
  357.         if (v.find(cur) == v.end())
  358.         {
  359.             f(cur);
  360.             s.push(cur);
  361.             v.insert(cur);
  362.         }
  363.         iterator i = begin();
  364.         while (i != end() && v.find(i->first) != v.end())
  365.             i++;
  366.         if (i != end())
  367.             cur = i->first;
  368.         else
  369.         {
  370.             s.pop();
  371.             if (!s.empty())
  372.                 cur = s.top();
  373.         }
  374.     }
  375.     while (!s.empty());
  376.  
  377.     return f;
  378. }
  379.  
  380. template <typename K, typename W, typename T>
  381. T& _base_graph<K, W, T>::operator[] (const K& k)
  382. {
  383.     if (nod.find(k) == nod.end())
  384.         throw std::string("_base_graph::operator[] - node does not exist");
  385.     return nod[k];
  386. }
  387.  
  388. template <typename K, typename W, typename T>
  389. const K& _base_graph<K, W, T>::edge::key(const K& k)
  390. {
  391.     if (k != key1() && k != key2())
  392.         throw std::string("graph::edge::key - key supplied is invalid");
  393.  
  394.     return k == key1() ? key2() : key1();
  395. }
  396.  
  397. template <typename K, typename W, typename T>
  398. typename _base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator++()
  399. {
  400.     ++it;
  401.     while (it != end && it->key1() != key && it->key2() != key)
  402.         ++it;
  403.  
  404.     return *this;
  405. }
  406.  
  407. template <typename K, typename W, typename T>
  408. typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator++(int)
  409. {
  410.     edge_iterator tmp = *this;
  411.  
  412.     ++it;
  413.     while (it != end && it->key1() != key && it->key2() != key)
  414.         ++it;
  415.  
  416.     return tmp;
  417. }
  418.  
  419. template <typename K, typename W, typename T>
  420. typename _base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator--()
  421. {
  422.     --it;
  423.     while (it != begin && it->key1() != key && it->key2() != key)
  424.         --it;
  425.     if (it == begin)
  426.         while (it != end && it->key1() != key && it->key2() != key)
  427.             ++it;
  428.  
  429.     return *this;
  430. }
  431.  
  432. template <typename K, typename W, typename T>
  433. typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator--(int)
  434. {
  435.     edge_iterator tmp = *this;
  436.  
  437.     --it;
  438.     while (it != begin && it->key1() != key && it->key2() != key)
  439.         --it;
  440.     if (it == begin)
  441.         while (it != end && it->key1() != key && it->key2() != key)
  442.             ++it;
  443.  
  444.     return tmp;
  445. }
  446.  
  447. /*****************************************************************************
  448.  * class graph                                                               *
  449.  *****************************************************************************/
  450.  
  451.  
  452. template <typename K, typename T = void*>
  453.         class graph : public _base_graph<K, void*, T>
  454. {
  455. public:
  456.  
  457.     graph() : _base_graph<K, void*, T>()
  458.     {
  459.     }
  460.  
  461.     graph(size_t n) : _base_graph<K, void*, T>(n)
  462.     {
  463.     }
  464.  
  465.     graph(size_t n, const K& k) : _base_graph<K, void*, T>(n, k)
  466.     {
  467.     }
  468.  
  469.     template <typename F>
  470.     graph(size_t n, F f) : _base_graph<K, void*, T>(n, f)
  471.     {
  472.     }
  473.  
  474.     void add_edge(const K& k1, const K& k2);
  475.  
  476.     bool is_edge(const K& k1, const K& k2);
  477.  
  478.     void remove_edge(const K& k1, const K& k2);
  479. };
  480.  
  481. template <typename K, typename T>
  482. void graph<K, T>::add_edge(const K& k1, const K& k2)
  483. {
  484.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  485.         throw std::string("add_edge: Node does not exist");
  486.  
  487.     // Store lower key value in first key of edge
  488.     if (k1 < k2)
  489.         this->edg.push_back(edge(k1, k2));
  490.     else
  491.         this->edg.push_back(edge(k2, k1));
  492. }
  493.  
  494. template <typename K, typename T>
  495. bool graph<K, T>::is_edge(const K& k1, const K& k2)
  496. {
  497.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  498.         throw std::string("is_edge: Node does not exist");
  499.  
  500.     if (k1 < k2)
  501.         return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2)) != this->edg.end();
  502.     return std::find(this->edg.begin(), this->edg.end(), edge(k2, k1)) != this->edg.end();
  503. }
  504.  
  505. template <typename K, typename T>
  506. void graph<K, T>::remove_edge(const K& k1, const K& k2)
  507. {
  508.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  509.         throw std::string("add_edge: Node does not exist");
  510.  
  511.     if (k1 < k2)
  512.         this->edg.remove(edge(k1, k2));
  513.     else
  514.         this->edg.remove(edge(k2, k1));
  515. }
  516.  
  517. /*****************************************************************************
  518.  * class wgraph                                                              *
  519.  *****************************************************************************/
  520.  
  521.  
  522. template <typename K, typename W, typename T = void*>
  523.         class wgraph : public _base_graph<K, W, T>
  524. {
  525. public:
  526.  
  527.     wgraph() : _base_graph<K, W, T>()
  528.     {
  529.     }
  530.  
  531.     wgraph(size_t n) : _base_graph<K, W, T>(n)
  532.     {
  533.     }
  534.  
  535.     wgraph(size_t n, const K& k) : _base_graph<K, W, T>(n, k)
  536.     {
  537.     }
  538.  
  539.     template <typename F>
  540.     wgraph(size_t n, F f) : _base_graph<K, W, T>(n, f)
  541.     {
  542.     }
  543.  
  544.     void add_edge(const K& k1, const K& k2, const W& w);
  545.  
  546.     bool is_edge(const K& k1, const K& k2);
  547.  
  548.     void remove_edge(const K& k1, const K& k2);
  549.  
  550.     W& weight(const K& k1, const K& k2);
  551. };
  552.  
  553. template <typename K, typename W, typename T>
  554. void wgraph<K, W, T>::add_edge(const K& k1, const K& k2, const W& w)
  555. {
  556.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  557.         throw std::string("add_edge: Node does not exist");
  558.  
  559.     // Store lower key value in first key of edge
  560.     if (k1 < k2)
  561.         this->edg.push_back(edge(k1, k2, w));
  562.     else
  563.         this->edg.push_back(edge(k2, k1, w));
  564. }
  565.  
  566. template <typename K, typename W, typename T>
  567. bool wgraph<K, W, T>::is_edge(const K& k1, const K& k2)
  568. {
  569.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  570.         throw std::string("is_edge: Node does not exist");
  571.  
  572.     if (k1 < k2)
  573.         return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2)) != this->edg.end();
  574.     return std::find(this->edg.begin(), this->edg.end(), edge(k2, k1)) != this->edg.end();
  575. }
  576.  
  577. template <typename K, typename W, typename T>
  578. void wgraph<K, W, T>::remove_edge(const K& k1, const K& k2)
  579. {
  580.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  581.         throw std::string("add_edge: Node does not exist");
  582.  
  583.     if (k1 < k2)
  584.         this->edg.remove(edge(k1, k2));
  585.     else
  586.         this->edg.remove(edge(k2, k1));
  587. }
  588.  
  589. template <typename K, typename W, typename T>
  590. W& wgraph<K, W, T>::weight(const K& k1, const K& k2)
  591. {
  592.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  593.         throw std::string("weight: Node does not exist");
  594.     if (!is_edge(k1, k2))
  595.         throw std::string("weight: Edge does not exist");
  596.  
  597.     if (k1 < k2)
  598.         return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2))->weight();
  599.     return std::find(this->edg.begin(), this->edg.end(), edge(k2, k1))->weight();
  600. }
  601.  
  602. /*****************************************************************************
  603.  * class digraph                                                             *
  604.  *****************************************************************************/
  605.  
  606.  
  607. template <typename K, typename T = void*>
  608.         class digraph : public _base_graph<K, void*, T>
  609. {
  610. public:
  611.  
  612.     digraph() : _base_graph<K, void*, T>()
  613.     {
  614.     }
  615.  
  616.     digraph(size_t n) : _base_graph<K, void*, T>(n)
  617.     {
  618.     }
  619.  
  620.     digraph(size_t n, const K& k) : _base_graph<K, void*, T>(n, k)
  621.     {
  622.     }
  623.  
  624.     template <typename F>
  625.     digraph(size_t n, F f) : _base_graph<K, void*, T>(n, f)
  626.     {
  627.     }
  628.  
  629.     void add_edge(const K& k1, const K& k2);
  630.  
  631.     bool is_edge(const K& k1, const K& k2);
  632.  
  633.     void remove_edge(const K& k1, const K& k2);
  634. };
  635.  
  636. template <typename K, typename T>
  637. void digraph<K, T>::add_edge(const K& k1, const K& k2)
  638. {
  639.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  640.         throw std::string("add_edge: Node does not exist");
  641.  
  642.     this->edg.push_back(edge(k1, k2));
  643. }
  644.  
  645. template <typename K, typename T>
  646. bool digraph<K, T>::is_edge(const K& k1, const K& k2)
  647. {
  648.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  649.         throw std::string("is_edge: Node does not exist");
  650.  
  651.     return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2)) != this->edg.end();
  652. }
  653.  
  654. template <typename K, typename T>
  655. void digraph<K, T>::remove_edge(const K& k1, const K& k2)
  656. {
  657.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  658.         throw std::string("add_edge: Node does not exist");
  659.  
  660.     this->edg.remove(edge(k1, k2));
  661. }
  662.  
  663. /*****************************************************************************
  664.  * class wdigraph                                                            *
  665.  *****************************************************************************/
  666.  
  667.  
  668. template <typename K, typename W, typename T = void*>
  669.         class wdigraph : public _base_graph<K, W, T>
  670. {
  671. public:
  672.  
  673.     wdigraph() : _base_graph<K, W, T>()
  674.     {
  675.     }
  676.  
  677.     wdigraph(size_t n) : _base_graph<K, W, T>(n)
  678.     {
  679.     }
  680.  
  681.     wdigraph(size_t n, const K& k) : _base_graph<K, W, T>(n, k)
  682.     {
  683.     }
  684.  
  685.     template <typename F>
  686.     wdigraph(size_t n, F f) : _base_graph<K, W, T>(n, f)
  687.     {
  688.     }
  689.  
  690.     void add_edge(const K& k1, const K& k2, const W& w);
  691.  
  692.     bool is_edge(const K& k1, const K& k2);
  693.  
  694.     void remove_edge(const K& k1, const K& k2);
  695.  
  696.     W& weight(const K& k1, const K& k2);
  697. };
  698.  
  699. template <typename K, typename W, typename T>
  700. void wdigraph<K, W, T>::add_edge(const K& k1, const K& k2, const W& w)
  701. {
  702.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  703.         throw std::string("add_edge: Node does not exist");
  704.  
  705.     this->edg.push_back(edge(k1, k2, w));
  706. }
  707.  
  708. template <typename K, typename W, typename T>
  709. bool wdigraph<K, W, T>::is_edge(const K& k1, const K& k2)
  710. {
  711.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  712.         throw std::string("is_edge: Node does not exist");
  713.  
  714.     return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2)) != this->edg.end();
  715. }
  716.  
  717. template <typename K, typename W, typename T>
  718. void wdigraph<K, W, T>::remove_edge(const K& k1, const K& k2)
  719. {
  720.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  721.         throw std::string("add_edge: Node does not exist");
  722.  
  723.     this->edg.remove(edge(k1, k2));
  724. }
  725.  
  726. template <typename K, typename W, typename T>
  727. W& wdigraph<K, W, T>::weight(const K& k1, const K& k2)
  728. {
  729.     if (this->nod.find(k1) == this->nod.end() || this->nod.find(k2) == this->nod.end())
  730.         throw std::string("weight: Node does not exist");
  731.     if (!is_edge(k1, k2))
  732.         throw std::string("weight: Edge does not exist");
  733.  
  734.     return std::find(this->edg.begin(), this->edg.end(), edge(k1, k2))->weight();
  735. }
  736.  
  737. } // namespace gtc
  738.  
  739.  
  740. int main()
  741. {
  742.     gtc::graph<int> g;
  743.     return 0;
  744. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In member function ‘bool gtc::graph<K, T>::is_edge(const K&, const K&) [with K = int, T = void*]’:
prog.cpp:744:   instantiated from here
prog.cpp:501: error: expected primary-expression
prog.cpp:502: error: expected primary-expression
stdout
copy 
Standard output is empty
https://ideone.com/erbzWA
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!