---

graph.h

/*
 *      gtc.h - Graph Template Classes (alpha)
 *
 *      Copyright (c) 2003 - Norman Lippincott, Jr. - Saylorsburg PA USA
 *      All Rights Reserved
 *
 *      This library is free software; you can redistribute it and/or
 *      modify it under the terms of the GNU Lesser General Public
 *      License as published by the Free Software Foundation; either
 *      version 2.1 of the License, or (at your option) any later version.
 *
 *      This library is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *      Lesser General Public License for more details.
 *
 *      You should have received a copy of the GNU Lesser General Public
 *      License along with this library; if not, write to the Free Software
 *      Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
 *
 *      The author may be contacted via e-mail at nl@acm.org.
 */

/*
 *      Documentation for this library is produced directly from this source file
 *      using the Doxygen documentation system.
 *
 *      Please see http://www.doxygen.org/ for information about Doxygen.
 */

#ifndef GTC_H
#define GTC_H

#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>

/*****************************************************************************
 * namespace gtc                                                             *
 *****************************************************************************/


namespace gtc {

/*****************************************************************************
 * class _base_graph                                                         *
 *****************************************************************************/



template <typename K, typename W, typename T>
class _base_graph {

protected:

        _base_graph () {}

        _base_graph (size_t n);

        _base_graph (size_t n, const K& k);

        template <typename F>
        _base_graph (size_t n, F f);

public:
        void add_node (const K& k);

        void add_node (const K& k, const T& t);

        std::size_t order () { return nod.size(); }

        size_t size() { return edg.size(); }


        T& operator[] (const K& k);


        class iterator {
        friend class _base_graph<K, W, T>;
        public:
                iterator& operator++ () { ++it; return *this; }
                iterator operator++ (int) { iterator i = (*this); ++it; return i; }
                iterator& operator-- () { --it; return *this; }
                iterator operator-- (int) { iterator i = (*this); --it; return i; }

                std::pair<const K, T>& operator* () { return *it; }
                std::pair<const K, T>* operator-> () { return &(*it); }

                bool operator== (const iterator& i) { return it == i.it; }
                bool operator!= (const iterator& i) { return it != i.it; }

        private:
                std::map<K, T>::iterator begin, end;
                std::map<K, T>::iterator it;
        };

        virtual iterator begin ();

        virtual iterator end ();

        virtual iterator find (const K& k);


        class edge {
        public:

                edge (const K& k1, const K& k2, const W& w = 0) :
                        ky1(k1), ky2(k2), wt(w) {}

                bool operator== (const edge& e) const
                        { return key1() == e.key1() && key2() == e.key2(); }
                bool operator!= (const edge& e) const
                        { return key1() != e.key1() || key2() != e.key2(); }

                const K& key1 () const { return ky1; }

                const K& key2 () const { return ky2; }


                const K& key (const K& k);

                K& weight () { return wt; }

        private:
                K ky1;
                K ky2;
                W wt;
        };

        virtual bool is_edge (const K& k1, const K& k2) = 0;


        class edge_iterator {
        friend class _base_graph<K, W, T>;
        public:
                edge_iterator& operator++ ();
                edge_iterator operator++ (int);
                edge_iterator& operator-- ();
                edge_iterator operator-- (int);

                edge& operator* () { return *it; }
                edge* operator-> () { return &(*it); }

                bool operator== (const edge_iterator& i) { return it == i.it; }
                bool operator!= (const edge_iterator& i) { return it != i.it; }

        private:
                std::list<edge>::iterator begin, end;
                std::list<edge>::iterator it;

                K key;
        };

        edge_iterator begin (const K& k);

        edge_iterator end (const K& k);

        template <typename F>
        F BFS (const K& k, F f);

        template <typename F>
        F DFS (const K& k, F f);

protected:
        std::map<K, T> nod;
        std::list<edge> edg;
};

template <typename K, typename W, typename T>
_base_graph<K, W, T>::_base_graph (size_t n)
{
        K key(1);

        for (size_t i = 0; i < n; i++)
                nod[key++] = T();
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::_base_graph (size_t n, const K& k)
{
        K key(k);

        for (size_t i = 0; i < n; i++)
                nod[key++] = T();
}

template <typename K, typename W, typename T>
template <typename F>
_base_graph<K, W, T>::_base_graph (size_t n, F f)
{
        for (size_t i = 0; i < n; i++)
                nod[f()] = T();
}

template <typename K, typename W, typename T>
void _base_graph<K, W, T>::add_node (const K& k)
{
        if (nod.find(k) != nod.end())
                throw std::string("_base_graph::add_node - node already exists");
        nod[k] = T();
}

template <typename K, typename W, typename T>
void _base_graph<K, W, T>::add_node (const K& k, const T& t)
{
        if (nod.find(k) != nod.end())
                throw std::string("_base_graph::add_node - node already exists");
        nod[k] = t;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::iterator _base_graph<K, W, T>::begin ()
{
        iterator i;
        i.begin = nod.begin();
        i.end = nod.end();

        i.it = i.begin;

        return i;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::begin (const K& k)
{
        edge_iterator i;
        i.begin = edg.begin();
        i.end = edg.end();
        i.key = k;

        i.it = i.begin;
        while (i.it != i.end && i.it->key1() != i.key && i.it->key2() != i.key) {
                i.it++;
        }

        return i;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::iterator _base_graph<K, W, T>::end ()
{
        iterator i;
        i.begin = nod.begin();
        i.end = nod.end();

        i.it = i.end;

        return i;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::end (const K& k)
{
        edge_iterator i;
        i.begin = edg.begin();
        i.end = edg.end();
        i.key = k;

        i.it = i.end;

        return i;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::iterator _base_graph<K, W, T>::find (const K& k)
{
        iterator i;
        i.begin = nod.begin();
        i.end = nod.end();
        i.it = nod.find(k);

        return i;
}

template <typename K, typename W, typename T>
template <typename F>
F _base_graph<K, W, T>::BFS (const K& k, F f)
{
         K cur;
         std::queue<K> q;
         std::set<K> v;

         q.push(k);
         v.insert(k);

         while (!q.empty()) {

                cur = q.front();
                q.pop();
                f(cur);

                for (iterator i = begin(); i != end(); i++)
                        if (is_edge(cur, i->first))
                                if (v.find(i->first) == v.end()) {
                                        q.push(i->first);
                                        v.insert(i->first);
                                }
         }

         return f;
}

template <typename K, typename W, typename T>
template <typename F>
F _base_graph<K, W, T>::DFS (const K& k, F f)
{
        K cur = k;
        std::set<K> v;
        std::stack<K> s;

        do {
                if (v.find(cur) == v.end()) {
                        f(cur);
                        s.push(cur);
                        v.insert(cur);
                }
                iterator i = begin();
                while (i != end() && v.find(i->first) != v.end())
                        i++;
                if (i != end())
                        cur = i->first;
                else {
                        s.pop();
                        if (!s.empty())
                                cur = s.top();
                }
        } while (!s.empty());

        return f;
}

template <typename K, typename W, typename T>
T& _base_graph<K, W, T>::operator[] (const K& k)
{
        if (nod.find(k) == nod.end())
                throw std::string("_base_graph::operator[] - node does not exist");
        return nod[k];
}

template <typename K, typename W, typename T>
const K& _base_graph<K, W, T>::edge::key (const K& k)
{
        if (k != key1() && k != key2())
                throw std::string("graph::edge::key - key supplied is invalid");

        return k == key1() ? key2() : key1();
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator++ ()
{
        ++it;
        while (it != end && it->key1() != key && it->key2() != key)
                ++it;

        return *this;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator++ (int)
{
        edge_iterator tmp = *this;

        ++it;
        while (it != end && it->key1() != key && it->key2() != key)
                ++it;

        return tmp;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator-- ()
{
        --it;
        while (it != begin && it->key1() != key && it->key2() != key)
                --it;
        if (it == begin)
                while (it != end && it->key1() != key && it->key2() != key)
                        ++it;

        return *this;
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator-- (int)
{
        edge_iterator tmp = *this;

        --it;
        while (it != begin && it->key1() != key && it->key2() != key)
                --it;
        if (it == begin)
                while (it != end && it->key1() != key && it->key2() != key)
                        ++it;

        return tmp;
}

/*****************************************************************************
 * class graph                                                               *
 *****************************************************************************/


template <typename K, typename T = void*>
class graph : public _base_graph<K, void*, T> {

public:
        graph () : _base_graph<K, void*, T>() {}

        graph (size_t n) : _base_graph<K, void*, T>(n) {}

        graph (size_t n, const K& k) : _base_graph<K, void*, T>(n, k) {}

        template <typename F>
        graph (size_t n, F f) : _base_graph<K, void*, T>(n, f) {}

        void add_edge (const K& k1, const K& k2);

        bool is_edge (const K& k1, const K& k2);

        void remove_edge (const K& k1, const K& k2);
};

template <typename K, typename T>
void graph<K, T>::add_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        // Store lower key value in first key of edge
        if (k1 < k2)
                edg.push_back(edge(k1, k2));
        else
                edg.push_back(edge(k2, k1));
}

template <typename K, typename T>
bool graph<K, T>::is_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("is_edge: Node does not exist");

        if (k1 < k2)
                return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
        return std::find(edg.begin(), edg.end(), edge(k2, k1)) != edg.end();
}

template <typename K, typename T>
void graph<K, T>::remove_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        if (k1 < k2)
                edg.remove(edge(k1, k2));
        else
                edg.remove(edge(k2, k1));
}

/*****************************************************************************
 * class wgraph                                                              *
 *****************************************************************************/


template <typename K, typename W, typename T = void*>
class wgraph : public _base_graph<K, W, T> {

public:
        wgraph () : _base_graph<K, W, T>() {}

        wgraph (size_t n) : _base_graph<K, W, T>(n) {}

        wgraph (size_t n, const K& k) : _base_graph<K, W, T>(n, k) {}

        template <typename F>
        wgraph (size_t n, F f) : _base_graph<K, W, T>(n, f) {}

        void add_edge (const K& k1, const K& k2, const W& w);

        bool is_edge (const K& k1, const K& k2);

        void remove_edge (const K& k1, const K& k2);

        W& weight (const K& k1, const K& k2);
};

template <typename K, typename W, typename T>
void wgraph<K, W, T>::add_edge (const K& k1, const K& k2, const W& w)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        // Store lower key value in first key of edge
        if (k1 < k2)
                edg.push_back(edge(k1, k2, w));
        else
                edg.push_back(edge(k2, k1, w));
}

template <typename K, typename W, typename T>
bool wgraph<K, W, T>::is_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("is_edge: Node does not exist");

        if (k1 < k2)
                return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
        return std::find(edg.begin(), edg.end(), edge(k2, k1)) != edg.end();
}

template <typename K, typename W, typename T>
void wgraph<K, W, T>::remove_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        if (k1 < k2)
                edg.remove(edge(k1, k2));
        else
                edg.remove(edge(k2, k1));
}

template <typename K, typename W, typename T>
W& wgraph<K, W, T>::weight (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("weight: Node does not exist");
        if (!is_edge(k1, k2))
                throw std::string("weight: Edge does not exist");

        if (k1 < k2)
                return std::find(edg.begin(), edg.end(), edge(k1, k2))->weight();
        return std::find(edg.begin(), edg.end(), edge(k2, k1))->weight();
}

/*****************************************************************************
 * class digraph                                                             *
 *****************************************************************************/


template <typename K, typename T = void*>
class digraph : public _base_graph<K, void*, T> {

public:
        digraph () : _base_graph<K, void*, T>() {}

        digraph (size_t n) : _base_graph<K, void*, T>(n) {}

        digraph (size_t n, const K& k) : _base_graph<K, void*, T>(n, k) {}

        template <typename F>
        digraph (size_t n, F f) : _base_graph<K, void*, T>(n, f) {}

        void add_edge (const K& k1, const K& k2);

        bool is_edge (const K& k1, const K& k2);

        void remove_edge (const K& k1, const K& k2);
};

template <typename K, typename T>
void digraph<K, T>::add_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        edg.push_back(edge(k1, k2));
}

template <typename K, typename T>
bool digraph<K, T>::is_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("is_edge: Node does not exist");

        return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
}

template <typename K, typename T>
void digraph<K, T>::remove_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        edg.remove(edge(k1, k2));
}

/*****************************************************************************
 * class wdigraph                                                            *
 *****************************************************************************/


template <typename K, typename W, typename T = void*>
class wdigraph : public _base_graph<K, W, T> {

public:
        wdigraph () : _base_graph<K, W, T>() {}

        wdigraph (size_t n) : _base_graph<K, W, T>(n) {}

        wdigraph (size_t n, const K& k) : _base_graph<K, W, T>(n, k) {}

        template <typename F>
        wdigraph (size_t n, F f) : _base_graph<K, W, T>(n, f) {}

        void add_edge (const K& k1, const K& k2, const W& w);

        bool is_edge (const K& k1, const K& k2);

        void remove_edge (const K& k1, const K& k2);

        W& weight (const K& k1, const K& k2);
};

template <typename K, typename W, typename T>
void wdigraph<K, W, T>::add_edge (const K& k1, const K& k2, const W& w)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        edg.push_back(edge(k1, k2, w));
}

template <typename K, typename W, typename T>
bool wdigraph<K, W, T>::is_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("is_edge: Node does not exist");

        return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
}

template <typename K, typename W, typename T>
void wdigraph<K, W, T>::remove_edge (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("add_edge: Node does not exist");

        edg.remove(edge(k1, k2));
}

template <typename K, typename W, typename T>
W& wdigraph<K, W, T>::weight (const K& k1, const K& k2)
{
        if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
                throw std::string("weight: Node does not exist");
        if (!is_edge(k1, k2))
                throw std::string("weight: Edge does not exist");

        return std::find(edg.begin(), edg.end(), edge(k1, k2))->weight();
}

} // namespace gtc

#endif

---