/**************************************************************************************************/
/*                                                                                                */
/*  Name:  DarC KonQuesT                                                                          */
/*  Program:  #5                                                                                  */
/*  Date:  2005.12.12                                                                             */
/*  Purpose:                                                                                      */
/*      The books implementation of the network class but altered to fit project 14.2 -           */
/*  "backtracking through a network."  Therefore implementing backtracking for this purpose.      */
/*  Finds a path from start to destination where each consecutive edge weight is less than the    */
/*  previous edge's weight.  Depth first iteration.                                               */
/**************************************************************************************************/

#include <iostream>


using namespace std;



#ifndef NETWORK
#define NETWORK


#include <map>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>

using namespace std;

//Class network, implemented by the book, tweaked as described below
template<class vertex, class Compare = less<vertex> >
class network
{
        struct vertex_weight_pair
        {
            vertex to;
            double weight;


            // Postcondition: this vertex_weight_pair has been initialized
            //                from x and y.
            vertex_weight_pair (const vertex& x, const double& y)
            {
                to = x;
                weight = y;
            } // two-parameter constructor



            // Postcondition: true has been returned if this
            //                vertex_weight_pair is less than x.
            //                Otherwise, false has been returned.
            bool operator< (const vertex_weight_pair& p) const
            {
                return weight < p.weight;
            } // operator>


        }; // class vertex_weight_pair


        typedef typename std::list< vertex_weight_pair > vertex_list_class;
        typedef typename vertex_list_class::iterator vertex_list_iterator;
        typedef typename std::map<vertex, vertex_list_class, Compare> map_class;
        typedef typename map_class::iterator map_iterator;


    protected:


        map_class adjacency_map;


    public:

 /*  Name:  void do_path(network<string> cities, string start, string finish)                                          */
 /*  Purpose:  drive the purpose of finding a path where each consecutive edge weight is less than the previous        */
 /*  Parameters:  network<string> cities, string start, string finish                                                  */
 /*  Preconditions:  cities, start, and finish initialized correctly                                                   */
 /*  Postconditions:  path output as specified or "No solution found."                                                 */
        
    void do_path(network<string> cities, string start, string finish)
    {
      stack<vertex>* vertex_stack;
      stack<vertex> success_stack;
      list<string> neighbor_list;
      vertex_list_iterator list_itr;
      vertex v_temp1, v_temp2, finish_v, start_v;
      double temp_weight;
      
      //find the vertex to start with and push it to success_stack
      map_iterator itr = adjacency_map.find(start);
      
      start_v = v_temp1;
      v_temp1 = (*itr).first;  
      success_stack.push(v_temp1);
      //this vertex should not be popped as it is our starting point

      //find vertex of our ending point 
      map_iterator vfin = adjacency_map.find(finish);
      finish_v = (*vfin).first;
     
    pair<list<string>, double> shortestPath;
    
    shortestPath = cities.get_shortest_path(start, finish_v);
    list<string>::iterator vertex_list_itr = shortestPath.first.begin();


    string from_city[100];
    string to_city[100];
    double distance[100];
    if(shortestPath.second != -1)
    {
        // put cities in path into array from_city
        int from_i = 0;
        for (vertex_list_itr = shortestPath.first.begin(); vertex_list_itr != shortestPath.first.end(); vertex_list_itr++)
        {
          from_city[from_i] = *vertex_list_itr; 
          from_i++;
        }
       // put respective to_city for each from_city in to_city array
       for(int j = 1; from_city[j] != ""; j++)
       {
         to_city[j - 1] = from_city[j];
       } 
       
       //find distance of edges formed by from_city[i], to_city[i]
       vertex vto_temp;
       vertex vfrom_temp;
       map_iterator ito_temp;
       map_iterator ifrom_temp;
       for(int x = 0; to_city[x] != ""; x++)
       {
          ito_temp  = adjacency_map.find(to_city[x]);
          ifrom_temp  = adjacency_map.find(from_city[x]);
          vto_temp = (*ito_temp).first;
          
          vfrom_temp = (*ifrom_temp).first;
          temp_weight = cities.get_edge_weight(vfrom_temp, vto_temp);
          distance[x] = temp_weight;
       }
        cout << "FROM CITY" << setw(20) << "TO CITY" << setw(20) << "DISTANCE" << endl;
       for(int q = 0; to_city[q] != ""; q++)
        cout << left << setw(22) << from_city[q] << setw(19) << to_city[q] << distance[q] << endl;
      cout << endl << endl;
    }
    else
      cout << endl << "There is no solution." << endl;
    }
      
        class iterator;
        friend class iterator;


        class iterator
        {
            friend class network;


            protected:


                 map_iterator adj_iterator;


            public:

//operator overloading
                bool operator== (const iterator& other)
                {
                    return adj_iterator == other.adj_iterator;
                }


                bool operator!= (const iterator& other)
                {
                    return !(*this == other);
                }


                pair<vertex, list< vertex_weight_pair> > operator*()
                {
                    return *adj_iterator;
                }


                iterator operator++ (int)
                {
                    iterator temp_itr;
                    temp_itr.adj_iterator = adj_iterator++;
                    return temp_itr;
                }
        }; // class iterator



      struct edge_triple
      {
          vertex from,
                 to;


          double weight;


          // Postcondition: this edge_triple has been constructed from
          //                from, to and weight.
          edge_triple (const vertex& from, const vertex& to, double weight)
          {
              this -> from = from;
              this -> to = to;
              this -> weight = weight;
          } // three-parameter constructor



         // Postcondition: true has been returned if this edge_triple's
         //                weight is greater than other_edge_triple's
         //                weight.  Otherwise, false has been returned.
         bool operator> (const edge_triple& other_edge_triple) const
         {
             return weight > other_edge_triple.weight;
         } // operator>
      }; // struct edge_triple


        class breadth_first_iterator;
        friend class breadth_first_iterator;


        class breadth_first_iterator
        {
            friend class network;


            protected:


                queue<vertex>* vertex_queue;
                map<vertex, bool, Compare>* reached;
                map_class* map_ptr;


                // Postcondition: this breadth_first_iterator has been
                //                initialized at start.
                breadth_first_iterator (const vertex& start,
                                        map_class* ptr)
                {
                    map_ptr = ptr;
                    reached = new map<vertex, bool, Compare>();
                    vertex_queue = new queue<vertex>();


                    // Mark each vertex as not reached:
                    //                    map_class::iterator itr;
                    map_iterator itr;
                    for (itr = (*map_ptr).begin(); itr  !=(*map_ptr).end(); itr++)
                        (*reached)[(*itr).first] = false;


                    (*reached)[start] = true;
                    (*vertex_queue).push (start);
                } // two-parameter constructor 


            public:


                // Postcondition: this breadth_first_iterator is empty.
                breadth_first_iterator() { }



                // Postcondition: true has been returned if this and other are
                //                the same breadth_first_iterator.  Otherwise,
                //                false has been returned.
                bool operator== (const breadth_first_iterator& other)
                {
                    return (vertex_queue == other.vertex_queue) &&
                           (reached == other.reached) &&
                           (map_ptr == other.map_ptr);
                } // operator==



                // Postcondition: true has been returned if this and other are
                //                the different breadth_first_iterators.
                //                Otherwise, false has been returned.
                bool operator!= (const breadth_first_iterator& other)
                {
                    return !(*this == other);
                } // operator==



                // Postcondition: the vertex that this breadth_first_iterator
                //                is positioned at has been returned.
                vertex operator*()
                {
                    return (*vertex_queue).front();
                } // operator*



                // Precondition: this breadth_first_iterator has not yet
                //               reached all of the reachable vertices in this
                //               network.
                // Postcondition: this breadth_first_iterator has been advanced
                //                to the next reachable vertex in this network;
                //                the pre-advanced iterator has been returned.
                breadth_first_iterator operator++ (int)
                {
                    breadth_first_iterator temp = *this;
                    vertex current = (*vertex_queue).front();
                    (*vertex_queue).pop();


                    //                    map_class::iterator itr = (*map_ptr).find (current);
                    map_iterator itr = (*map_ptr).find (current);
                    vertex_list_iterator list_itr;


                    // Iterate through the list of neighbors of current
                    for (list_itr = (*itr).second.begin();
                         list_itr != (*itr).second.end();
                         list_itr++)
                    {
                        vertex to = (*list_itr).to;
                        if ((*reached) [to] == false)
                        {
                            (*reached) [to] = true;
                            (*vertex_queue).push (to);
                        } // if
                    } // for
                    if ((*vertex_queue).empty())
                    {
                        vertex_queue = NULL;
                        reached = NULL;
                        map_ptr = NULL;
                    } // if queue empty
                    return temp;
                } // operator++
        }; // class breadth_first_iterator




        class depth_first_iterator;
        friend class depth_first_iterator;


        class depth_first_iterator
        {
            friend class network;


            protected:


                stack<vertex>* vertex_stack;
                map<vertex, bool, Compare>* reached;
                map_class* map_ptr;


                // Postcondition: this depth_first_iterator has been
                //                initialized at start.
                depth_first_iterator (const vertex& start, map_class* ptr)
                {
                    map_ptr = ptr;
                    reached = new map<vertex, bool, Compare>();
                    vertex_stack = new stack<vertex>();


                    // Mark each vertex as not reached:
                    map_iterator itr;
                    for (itr = (*map_ptr).begin(); itr != (*map_ptr).end(); itr++)
                        (*reached)[(*itr).first] = false;


                    (*reached)[start] = true;
                    (*vertex_stack).push (start);
                } // two-parameter constructor    
 
            public:


                // Postcondition: this depth_first_iterator is empty.
                depth_first_iterator() { }



                // Postcondition: true has been returned if this and other are
                //                the same depth_first_iterator.  Otherwise,
                //                false has been returned.
                bool operator== (const depth_first_iterator& other)
                {
                    return (vertex_stack == other.vertex_stack) &&
                           (reached == other.reached) &&
                           (map_ptr == other.map_ptr);
                } // operator==



                bool operator!= (const depth_first_iterator& other)
                {
                    return !(*this == other);
                } // operator!=



                // Postcondition: the vertex that this depth_first_iterator
                //                is positioned at has been returned.
                vertex operator*()
                {
                    return (*vertex_stack).top();
                } // operator*



                // Precondition: this depth_first_iterator has not yet
                //               reached all of the reachable vertices in this
                //               network.
                // Postcondition: this depth_first_iterator has been advanced
                //                to the next reachable vertex in this network;
                //                the pre-advanced iterator has been returned.
                depth_first_iterator operator++ (int)
                {
                    depth_first_iterator temp = *this;
                    vertex current = (*vertex_stack).top();
                    (*vertex_stack).pop();


                    map_iterator itr = (*map_ptr).find (current);
                    vertex_list_iterator list_itr;
                    for (list_itr = (*itr).second.begin();
                         list_itr != (*itr).second.end();
                         list_itr++)
                    {
                        vertex to = (*list_itr).to;
                        if ((*reached) [to] == false)
                        {
                            (*reached) [to] = true;
                            (*vertex_stack).push (to);
                        } // if
                    } // for
                    if ((*vertex_stack).empty())
                    {
                        vertex_stack = NULL;
                        reached = NULL;
                        map_ptr = NULL;
                    } // if stack empty
                    return temp;
                } // operator++
        }; // class depth_first_iterator


        
        // Postcondition: this network is empty.
        network() { }



        // Postcondition: this network contains a clone of network.
        network (const network& other)
        {
            adjacency_map = other.adjacency_map;
        } // copy constructor



        // Postcondition: the number of vertices in this network has been
        //                returned.
        unsigned int size()
        {
            return adjacency_map.size();
        } // method size



        // Postcondition: true has been returned if this network contains no
        //                vertices.  Otherwise, false has been returned.
        bool empty()
        {
            return size() == 0;
        } // method empty


        // Postcondition: an iterator positioned at the beginning of this
        //                network has been returned.
        iterator begin()
        {
            iterator temp;
            temp.adj_iterator = adjacency_map.begin();


            return temp;
        } // begin



        // Postcondition: the iterator returned can be used in comparisons
        //                to terminate an iteration of this network.
        iterator end()
        {
            iterator temp;
            temp.adj_iterator = adjacency_map.end();


            return temp;
        } // end



        // Postcondition: the number of edges in this network has been returned.
        unsigned int get_edge_count()
        {
            int count = 0;


            map_iterator itr;


            for (itr = adjacency_map.begin(); itr != adjacency_map.end(); itr++)
                count += (*itr).second.size();
            return count;
        } // method get_edge_count



        // Postcondition: if <v1, v2> forms an edge in this network, the weight
        //                of that edge has been returned. Otherwise, -1.0 has
        //                been returned.
        double get_edge_weight (const vertex& v1, const vertex& v2)
        {
            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return -1.0;


            vertex_list_iterator list_itr;
            for (list_itr = ((*itr).second).begin();
                 list_itr != ((*itr).second).end();
                 list_itr++)
                if ((*list_itr).to == v2)
                    return (*list_itr).weight;
            return -1.0; // there is no edge <v1, v2>
        } // method get_edge_weight



        // Postcondition: true has been returned if this network contains v;
        //                otherwise, false has been returned.
        bool contains_vertex (vertex v)
        {
            return adjacency_map.find (v) != adjacency_map.end();
        } // method contains_vertex



        // Postcondition: true has been returned if this network contains the
        //                edge <v1, v2>.  Otherwise, false has been returned.
        bool contains_edge (const vertex& v1, const vertex& v2)
        {
            vertex_list_iterator list_itr;


            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return false;
            for (list_itr = ((*itr).second).begin();
                        list_itr != ((*itr).second).end();
                        list_itr++)
                if ((*list_itr).to == v2)
                    return true;
            return false;
        } // method contains_edge



        // Postcondition: if v is already in this network, false has been
        //                returned. Otherwise, the map with v and an empty list
        //                has been added to this network and true has been
        //                returned.
        bool insert_vertex (const vertex& v)
        {
                return adjacency_map.insert (
                        pair<vertex, list<vertex_weight_pair> >
                        (v, list<vertex_weight_pair>())).second;        
        } // method insert_vertex



        // Postcondition: if the edge <v1, v2> is already in this network false
        //                has been returned. Otherwise, that edge with the
        //                given weight has been inserted in this network and
        //                true has been returned.
        bool insert_edge (const vertex& v1, const vertex& v2, const double& weight)
        {
            if (contains_edge (v1, v2))
                return false;
            insert_vertex (v1);
            insert_vertex (v2);
            (*(adjacency_map.find (v1))).second.push_back
                            (vertex_weight_pair (v2, weight));
            return true;
        } // method insert_edge



        // Postcondition: if v is a vertex in this network, v and all of its
        //                edges have been deleted from this network and true has
        //                been returned.  Otherwise, false has been returned.
        bool erase_vertex (const vertex& v)
        {
            map_iterator itr = adjacency_map.find (v);
            if (itr == adjacency_map.end())
                return false;
            adjacency_map.erase (itr);
            vertex_list_iterator list_itr;
            for (itr = adjacency_map.begin(); itr != adjacency_map.end(); itr++)


                // Delete any pair with v from the list (*itr).second
                for (list_itr = (*itr).second.begin();
                     list_itr != (*itr).second.end();
                     list_itr++)
                    if ((*list_itr).to == v)
                    {
                        (*itr).second.erase (list_itr);
                        break;
                    } // v found in the list (*itr).second
            return true;
        } // erase_vertex



        // Postcondition: if <v1, v2> is an edge in this network, that edge has
        //                been removed and true has been returned.  Otherwise,
        //                false has been returned.
        bool erase_edge (const vertex& v1, const vertex& v2)
        {
            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                        adjacency_map.find (v2) == adjacency_map.end())
                return false;
            vertex_list_iterator list_itr;
            for (list_itr = (*itr).second.begin();
                 list_itr != (*itr).second.end();
                 list_itr++)
                if ((*list_itr).to == v2)
                {
                    (*itr).second.erase (list_itr);
                    return true;
                } // if
            return false;
        } // method erase_edge



        // Precondition: vertex v is in this network.
        // Postcondition: a breadth_first_iterator over all vertices reachable
        //                from v has been returned.
        breadth_first_iterator breadth_first_begin (const vertex& v)
        {
            breadth_first_iterator b_itr (v, &adjacency_map);
            return b_itr;
        } // method breadth_first_begin



        // Postcondition: the breadth_first_iterator returned can be used in
        //                comparisons to terminate this iteration of this
        //                network.
        breadth_first_iterator breadth_first_end()
        {
           breadth_first_iterator b_itr;
           b_itr.vertex_queue = NULL;
           b_itr.reached = NULL;
           b_itr.map_ptr = NULL;
           return b_itr;
        } // breadth_first_end



        // Precondition: vertex v is in this network.
        // Postcondition: a depth_first_iterator over all vertices reachable
        //                from v has been returned.
        depth_first_iterator depth_first_begin (const vertex& v)
        {
            depth_first_iterator d_itr (v, &adjacency_map);
            return d_itr;
        } // method depth_first_begin



        // Postcondition: the depth_first_iterator returned can be used in
        //                comparisons to terminate this iteration of this
        //                network.
        depth_first_iterator depth_first_end()
        {
           depth_first_iterator d_itr;
           d_itr.vertex_stack = NULL;
           d_itr.reached = NULL;
           d_itr.map_ptr = NULL;
           return d_itr;
        } // depth_first_end



        // Postcondition: true has been returned if this network is connected.
        //                Otherwise, false has been returned.
        bool is_connected()
        {
            map_iterator itr;


            // For each vertex v, see if the number of vertices reachable from v
            // is equal to the total number of vertices in this network.
            for (itr = adjacency_map.begin(); itr != adjacency_map.end();itr++)
            {
                vertex v = (*itr).first;


                // Count the vertices reachable from v.
                unsigned int count = 0;
                breadth_first_iterator b_itr;
                for (b_itr = breadth_first_begin (v);
                     b_itr != breadth_first_end();
                     b_itr++)
                    count++;
                if (count < adjacency_map.size())
                    return false;
            } // while itr1 not finished iterating
            return true;
        } // method is_connected



        // Precondition: v is in this network.
        // Postcondition: the list of neighbors of v has been returned.
        list<vertex > get_neighbor_list (const vertex& v)
        {
            vertex_list_iterator list_itr;
            list<vertex> vertex_list;
            for (list_itr = adjacency_map [v].begin(); 
                 list_itr != adjacency_map [v].end();
                 list_itr++)
                vertex_list.push_back (list_itr -> to);
            return vertex_list;
        } // method get_neighbor_list



        // Precondition: this network is connected.
        // Postcondition: a minimum spanning tree for this network has
        //                been returned.
        network<vertex> get_minimum_spanning_tree() {


               network min_spanning_tree; // the minimum spanning tree is a
                                          // network so weights can be included


               priority_queue<edge_triple,
                              vector<edge_triple>,
                              greater<edge_triple> > pq;


               vertex root,
                      x,
                      y,
                      z;


               iterator itr;


               list< vertex_weight_pair > adjacency_list;
               vertex_list_iterator list_itr1;


               double weight;


               if (empty())
                   return min_spanning_tree;
               itr = begin();
               root = (*itr).first;
               min_spanning_tree.insert_vertex (root);


               adjacency_list = adjacency_map [root];
               for (list_itr1 = adjacency_list.begin();
                         list_itr1 != adjacency_list.end();
                         list_itr1++)
                   pq.push (edge_triple (root, list_itr1 -> to,
                                       list_itr1 -> weight));
               while (min_spanning_tree.size() < size())
               {
                   x = pq.top().from;
                   y = pq.top().to;
                   weight = pq.top().weight;
                   pq.pop();
                   if (!min_spanning_tree.contains_vertex (y)) {


                       min_spanning_tree.insert_vertex (y);
                       min_spanning_tree.insert_edge (x, y, weight);


                       adjacency_list = adjacency_map [y];
                       for (list_itr1 = adjacency_list.begin();
                            list_itr1 != adjacency_list.end();
                            list_itr1++)
                       {
                           z = list_itr1 -> to;
                           if (!min_spanning_tree.contains_vertex (z))
                           {
                               weight = list_itr1 -> weight;
                               pq.push (edge_triple (y, z, weight));
                        } // z not already in tree
                    } // iterating over y's neighbors
                } // y not already in tree
            } // tree has fewer vertices than this Network
            return min_spanning_tree;
         } // method get_minimum_spanningTree




 /*  Name:  pair<list<vertex>, double> get_shortest_path (const vertex& v1,const vertex& v2)                           */
 /*  Purpose: Altered get_shortest_path to return path where each consecutive edge weight is less than the previous'   */
 /*  Parameters: const vertex& v1,const vertex& v2                                                                     */
 /*  Preconditions: v1, v2 initialized correctly                                                                       */
 /*  Postconditions: path as specified is returned in a pair<list<vertex>, double>                                     */
        
        pair<list<vertex>, double> get_shortest_path (const vertex& v1,
                                                      const vertex& v2)
        {
            const double MAX_PATH_WEIGHT = 0.0;


            map<vertex, vertex, Compare> predecessor;
            map<vertex, double, Compare> weight_sum;
            queue<vertex_weight_pair> v_q;
//we're using a queue instead of priority queue
            list< vertex_weight_pair> adjacency_list;
            vertex_list_iterator list_itr;


            depth_first_iterator b_itr;


            vertex to,
                   from;


            double weight;


            if (adjacency_map.find (v1) == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return pair<list<vertex>, double> (list<vertex>(), -1.0);


            bool found_v2 = false;
            for (b_itr = depth_first_begin (v1); b_itr != depth_first_end();
                           b_itr++)
                if (*b_itr == v2)
                {
                    found_v2 = true;
                    break;
                } // if
            if (!found_v2)
                return pair<list<vertex>, double> (list<vertex>(), -1.0);


            weight_sum [v1] = 0.0;
            predecessor [v1] = v1;
            for (b_itr = depth_first_begin (v1);
                 b_itr != depth_first_end();
                 b_itr++)
            {
                weight_sum [*b_itr] = MAX_PATH_WEIGHT;
                predecessor [*b_itr] = vertex();
            } // initializing weight_sum and predecessor


            adjacency_list = adjacency_map [v1];
            for (list_itr = adjacency_list.begin();
                 list_itr != adjacency_list.end();
                 list_itr++)
            {
                weight_sum [list_itr -> to] = list_itr -> weight;
                predecessor [list_itr -> to] = v1;
                v_q.push (vertex_weight_pair (*list_itr));
            }// adjusting weight_sum, predecessor, pq for vertices adjacent to v1


            bool path_found = false;
            while (!path_found)
            {
              if(v_q.empty())
                return pair<list<vertex>, double> (list<vertex>(), -1.0);
                from = v_q.front().to;  
                v_q.pop();
                
                if (from == v2)
                    path_found = true;
                else
                {
                    adjacency_list = adjacency_map [from];
                    for (list_itr = adjacency_list.begin();
                         list_itr != adjacency_list.end();
                         list_itr++)
                    {
                        to = list_itr -> to;
                        weight_sum[to] = list_itr -> weight;
                        if (weight_sum [to] < weight_sum [from])
                        {
                            predecessor [to] = from;
                            v_q.push (vertex_weight_pair (to, weight_sum [to]));
                        } // if from_weight_sum + weight > to_weight_sum
                    } // for iterating over from's list
                } // else path not yet found
            } // while path not found


            list<vertex> path;
            vertex current = v2;
            while (current != v1)
            {
                path.push_front (current);
                current = predecessor [current];
            } // while not yet back to v1
            path.push_front (v1);


            return pair<list<vertex>, double> (path, weight_sum [v2]);
        } // method get_shortest_path



        // Precondition: every vertex in this network is a neighbor of every
        //               other vertex.
        // Postcondition: the pair returned consisted of a cycle -- as a list
        //                of vertices -- and the sum of the weights of the
        //                edges in the cycle.
        pair< list<vertex>, double> get_cycle()
        {
            pair< list<vertex>, double> cycle;


            list<vertex> cycle_list;


            double weight,
                   cycle_weight = 0.0;


            list< vertex_weight_pair > adjacency_list;
            vertex_list_iterator adjacency_list_itr;


            network::iterator itr = begin();


            vertex v,
                   start = (*itr).first;


            cycle_list.push_back (start);
            v = start;
            while (cycle_list.size() < size())
            {
                adjacency_list = adjacency_map [v];
                adjacency_list_itr = adjacency_list.begin();
                do
                {
                    v = adjacency_list_itr -> to;
                    weight = adjacency_list_itr -> weight;
                    adjacency_list_itr++;
                } // do
                while (find (cycle_list.begin(), cycle_list.end(), v)
                       != cycle_list.end() && adjacency_list_itr != adjacency_list.end());
                if (find (cycle_list.begin(), cycle_list.end(), v)
                    == cycle_list.end())
                {
                    cycle_list.push_back (v);
                    cycle_weight += weight;
                } // if
            } // while
            cycle_list.push_back (start);
            cycle_weight += get_edge_weight (v, start);
            cycle.first = cycle_list;
            cycle.second = cycle_weight;
            return cycle;
        } // method get_cycle
}; // class network



#endif