digraph.cpp
上传用户:jtjnyq9001
上传日期:2014-11-21
资源大小:3974k
文件大小:4k
源码类别:

3G开发

开发平台:

Visual C++

  1. //
  2. //  File = digraph.cpp
  3. //
  4. #include <stdlib.h>
  5. #include <fstream>
  6. #include "digraph.h"
  7. #ifdef _DEBUG
  8. extern std::ofstream *DebugFile;
  9. #endif
  10. //===============================================
  11. DirectedGraph::DirectedGraph( void )
  12. {
  13.   Vertex_List = new std::vector<obj_id_type>;
  14.   Edge_List = new std::vector<obj_id_type>;
  15.   Row_List = new std::deque<std::vector<int>* >;
  16.   Num_Verts = 0;
  17.   Num_Edges = 0;
  18. }
  19. //===============================================
  20. DirectedGraph::~DirectedGraph( void )
  21. {
  22.   delete Vertex_List;
  23.   delete Edge_List;
  24. };
  25. //===============================================
  26. int DirectedGraph::GetNumVerts( void )
  27. {
  28.   return(Num_Verts);
  29. };
  30. //===============================================
  31. int DirectedGraph::GetNumEdges( void )
  32. {
  33.   return(Num_Edges);
  34. };
  35. //===============================================
  36. int DirectedGraph::AddVertex(obj_id_type vertex_id)
  37. {
  38.   int i;
  39.   
  40.   Vertex_List->push_back(vertex_id);
  41.   //------------------------------------
  42.   //  Add row to adjacency matrix
  43.   std::vector<int>* new_row = new std::vector<int>;
  44.   for(i=0; i<Num_Verts; i++)
  45.     {
  46.     new_row->push_back(-1);
  47.     }
  48.   Row_List->push_back(new_row);
  49.   //------------------------------------
  50.   //  Add column to adjacency matrix
  51.   for(i=0; i<=Num_Verts; i++)
  52.     {
  53.     (Row_List->at(i))->push_back(-1);
  54.     }
  55.   Num_Verts++;
  56.   return(Num_Verts-1);
  57. }
  58. //================================================
  59. int DirectedGraph::AddEdge( obj_id_type edge_id,
  60.                             int fm_vtx_num,
  61.                             int to_vtx_num)
  62. {
  63.   Edge_List->push_back(edge_id);
  64.   // insert new_edge_num (==Num_Edges) into
  65.   // adjacency matrix at row fm_vtx_num and column to_vtx_num
  66.   //
  67.   // pointer to the desired row vector: Row_List->at(fm_vtx_num)
  68.   (Row_List->at(fm_vtx_num))->at(to_vtx_num) = Num_Edges;
  69.   Num_Edges++;
  70.   return(Num_Edges-1);
  71. };
  72. //================================================
  73. int DirectedGraph::AddEdge( obj_id_type edge_id,
  74.                             obj_id_type fm_vtx_id,
  75.                             obj_id_type to_vtx_id)
  76. {
  77.   int i, fm_vtx_num, to_vtx_num;
  78.   
  79.   Edge_List->push_back(edge_id);
  80.   // search Vertex_List to find vertex number corresponding
  81.   // to fm_vtx_id
  82.   fm_vtx_num = -1;
  83.   for(i=0; i<Num_Verts; i++)
  84.     {
  85.     if(Vertex_List->at(i) == fm_vtx_id) fm_vtx_num = i;
  86.     }
  87.   if(fm_vtx_num < 0)
  88.     {
  89.     // error: source vertex not found in graph
  90.     return(-1);
  91.     }
  92.   // search Vertex_List to find vertex number corresponding
  93.   // to to_vtx_id
  94.   to_vtx_num = -1;
  95.   for(i=0; i<Num_Verts; i++)
  96.     {
  97.     if(Vertex_List->at(i) == to_vtx_id) to_vtx_num = i;
  98.     }
  99.   if(to_vtx_num < 0)
  100.     {
  101.     // error: destination vertex not found in graph
  102.     return(-1);
  103.     }
  104.   // insert new_edge_num (==Num_Edges) into
  105.   // adjacency matrix at row fm_vtx_num and column to_vtx_num
  106.   (Row_List->at(fm_vtx_num))->at(to_vtx_num) = Num_Edges;
  107.   Num_Edges++;
  108.   return(Num_Edges-1);
  109. };
  110. //================================================
  111. int DirectedGraph::GetEdgeNum(int fm_vtx_num,
  112.                               int to_vtx_num)
  113. {
  114.   int edge_num;
  115.   edge_num = (Row_List->at(fm_vtx_num))->at(to_vtx_num);
  116.   return(edge_num);
  117. }
  118. //================================================
  119. int DirectedGraph::GetEdgeNum(obj_id_type edge_id)
  120. {
  121.   int edge_num = -1;
  122.   for(int i=0; i<Num_Edges; i++)
  123.     {
  124.     if( Edge_List->at(i) == edge_id ) edge_num = i;
  125.     }
  126.   if(edge_num < 0)
  127.     {
  128.     // error: specified vertex not found in graph
  129.     return(-1);
  130.     }
  131.   return(edge_num);
  132. }
  133. //================================================
  134. int DirectedGraph::GetVertexNum(obj_id_type vtx_id)
  135. {
  136.   int vtx_num = -1;
  137.   for(int i=0; i<Num_Verts; i++)
  138.     {
  139.     if( Vertex_List->at(i) == vtx_id ) vtx_num = i;
  140.     }
  141.   if(vtx_num < 0)
  142.     {
  143.     // error: specified vertex not found in graph
  144.     return(-1);
  145.     }
  146.   return(vtx_num);
  147. }
  148. //================================================
  149. obj_id_type DirectedGraph::GetEdgeId(int edge_num)
  150. {
  151.   if( edge_num >= 0 && edge_num < Num_Edges )
  152.     return( Edge_List->at(edge_num) );
  153.   else
  154.     return(NULL);
  155. }
  156. //================================================
  157. obj_id_type DirectedGraph::GetVertexId(int vtx_num)
  158. {
  159.   if( vtx_num >= 0 && vtx_num < Num_Verts )
  160.     return( Vertex_List->at(vtx_num) );
  161.   else
  162.     return(NULL);
  163. }