graph.H

Go to the documentation of this file.

// Copyright (C) 2006 University of Louisiana at Lafayette
// Authors: Suresh Golconda, Pablo Mejia

#ifndef CAJUN_GRAPH_H
#define CAJUN_GRAPH_H

#include  <map>
#include <vector>

namespace cajun
{
template <typename ID_T>
class graph_t
{
public:
        class edge_t;
        class vertex_t
        {
        public:
                ID_T const &id () const
                { return m_id; }
                // Front edges
                edge_t *add_edge (vertex_t *dst_, double cost_)
                {
                        edge_t *edge = new edge_t (dst_, cost_);
                        m_edges.push_back (edge);
                        return edge;
                }
                unsigned num_edges () const { return m_edges.size (); }
                edge_t *edge (unsigned i) const { return m_edges[i]; }

                //Back edges
                edge_t *add_back_edge (vertex_t *dst_, double cost_)
                {
                        edge_t *edge = new edge_t (dst_, cost_);
                        m_back_edges.push_back (edge);
                        return edge;
                }
                unsigned num_back_edges () const { return m_back_edges.size (); }
                edge_t *back_edge (unsigned i) const { return m_back_edges[i]; }

                bool operator == (vertex_t const &v_) const
                        { return (m_id == v_.id ()); }
                void set_cost (unsigned edge_id_, double cost_)
                        { m_edges[edge_id_].set_cost (cost_); }
        private:
                friend class graph_t;
                vertex_t (ID_T id_): m_id (id_) {}
                ID_T m_id;
                std::vector<edge_t *> m_edges;
                std::vector<edge_t *> m_back_edges;
        };

        class edge_t
        {
        public:
                double cost () { return m_cost; }
                void set_cost (double cost_) { m_cost = cost_;}
                edge_t (vertex_t *des_,double cost_):
                        m_cost (cost_), m_dest (des_){}
                vertex_t* get_vertex () {return m_dest;}
        private:
                double m_cost;
                vertex_t *m_dest;
        };

        void flush () //fixme: free memory for existing vertices
        { m_vertex.clear (); }


        vertex_t* add_vertex (ID_T const &id_)
        {
                //add to map m_vertex
                vertex_t *new_vertex = new vertex_t (id_);

                m_vertex.insert (make_pair (id_, new_vertex));
                if (m_vertex.find (id_) == m_vertex.end ())
                {
                        printf ("Failed to insert the item \n");
                        return NULL;
                }
                return new_vertex;
        }

        bool find_vertex (ID_T const &id_,
                          std::vector<vertex_t*> &vertex_list_)
        {
                typename std::multimap<ID_T, vertex_t *, ID_T>::iterator iter;
                for (iter = m_vertex.lower_bound (id_);
                     iter != m_vertex.upper_bound (id_); iter++)
                {
                        vertex_list_.push_back (iter->second);
                }

                return true;
        }

        void print_graph ()
        {
                typename std::multimap<ID_T, vertex_t *, ID_T>::iterator ver;
                for (ver = m_vertex.begin (); ver != m_vertex.end (); ver++)
                {
                        printf ("Vertex: ");
                        ver->first.print ();

                        for (unsigned i =0; i < ver->second->num_edges ();i++)
                        {
                                vertex_t *nv= (ver->second->edge (i))->get_vertex ();
                                printf ("\tedge cost (%.2f): ",
                                        (ver->second->edge (i)->cost ()));
                                nv->id ().print ();
                        }
                        //back ward edges
                        for (unsigned i =0; i < ver->second->num_back_edges ();i++)
                        {
                                vertex_t *nv= (ver->second->back_edge (i))->get_vertex ();
                                printf ("\t\t back edge cost (%.2f): ",
                                        (ver->second->back_edge (i)->cost ()));
                                nv->id ().print ();
                        }
                }
        }

private:
        std::multimap<ID_T, vertex_t *> m_vertex;
};
};

#endif

---