mtp_graph.h

   1
   2 ///////////////////////////////////////////////////////////////////////////
   3 // This program is free software: you can redistribute it and/or modify  //
   4 // it under the terms of the version 3 of the GNU General Public License //
   5 // as published by the Free Software Foundation.                         //
   6 //                                                                       //
   7 // This program is distributed in the hope that it will be useful, but   //
   8 // WITHOUT ANY WARRANTY; without even the implied warranty of            //
   9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU      //
  10 // General Public License for more details.                              //
  11 //                                                                       //
  12 // You should have received a copy of the GNU General Public License     //
  13 // along with this program. If not, see <http://www.gnu.org/licenses/>.  //
  14 //                                                                       //
  15 // Written by and Copyright (C) Francois Fleuret                         //
  16 // Contact <francois.fleuret@idiap.ch> for comments & bug reports        //
  17 ///////////////////////////////////////////////////////////////////////////
  18
  19 #ifndef MTP_GRAPH_H
  20 #define MTP_GRAPH_H
  21
  22 #include <iostream>
  23 #include <cmath>
  24
  25 using namespace std;
  26
  27 #include "misc.h"
  28 #include "path.h"
  29
  30 class Vertex;
  31 class Edge;
  32
  33 class MTPGraph {
  34   void update_positivized_lengths();
  35   void force_positivized_lengths();
  36   // Set the edge pred_edge_toward_source correspondingly to the path
  37   // of shortest length.
  38   void find_shortest_path();
  39   // Follows the path starting on edge e and returns its length. If
  40   // nodes is non-null, stores in it the nodes met along the path.
  41   int retrieve_one_path(Edge *e, Path *path);
  42
  43   Vertex **_front, **_new_front;
  44
  45   int _nb_vertices, _nb_edges;
  46   Vertex *_source, *_sink;
  47
  48   Edge *_edges;
  49   Vertex *_vertices;
  50
  51 public:
  52
  53   // These variables are filled when retrieve_disjoint_paths is called
  54   int nb_paths;
  55   Path **paths;
  56
  57   MTPGraph(int nb_vertices, int nb_edges, int *from, int *to,
  58            int source, int sink);
  59
  60   ~MTPGraph();
  61
  62   void find_best_paths(scalar_t *lengths);
  63   void retrieve_disjoint_paths();
  64
  65   void print(ostream *os);
  66   void print_dot(ostream *os);
  67 };
  68
  69 #endif