digraph.cpp

来自「《无线通信系统仿真——c++使用模型》这本书的源代码」· C++ 代码 · 共 181 行

//
//  File = digraph.cpp
//

#include <stdlib.h>
#include <fstream>
#include "digraph.h"
#ifdef _DEBUG
extern std::ofstream *DebugFile;
#endif

//===============================================

DirectedGraph::DirectedGraph( void )
{
  Vertex_List = new std::vector<obj_id_type>;
  Edge_List = new std::vector<obj_id_type>;
  Row_List = new std::deque<std::vector<int>* >;
  Num_Verts = 0;
  Num_Edges = 0;
}
//===============================================
DirectedGraph::~DirectedGraph( void )
{
  delete Vertex_List;
  delete Edge_List;
};
//===============================================
int DirectedGraph::GetNumVerts( void )
{
  return(Num_Verts);
};
//===============================================
int DirectedGraph::GetNumEdges( void )
{
  return(Num_Edges);
};
//===============================================
int DirectedGraph::AddVertex(obj_id_type vertex_id)
{
  int i;
  
  Vertex_List->push_back(vertex_id);
  //------------------------------------
  //  Add row to adjacency matrix

  std::vector<int>* new_row = new std::vector<int>;
  for(i=0; i<Num_Verts; i++)
    {
    new_row->push_back(-1);
    }
  Row_List->push_back(new_row);

  //------------------------------------
  //  Add column to adjacency matrix

  for(i=0; i<=Num_Verts; i++)
    {
    (Row_List->at(i))->push_back(-1);
    }
  Num_Verts++;

  return(Num_Verts-1);
}
//================================================
int DirectedGraph::AddEdge( obj_id_type edge_id,
                            int fm_vtx_num,
                            int to_vtx_num)
{
  Edge_List->push_back(edge_id);

  // insert new_edge_num (==Num_Edges) into
  // adjacency matrix at row fm_vtx_num and column to_vtx_num
  //
  // pointer to the desired row vector: Row_List->at(fm_vtx_num)

  (Row_List->at(fm_vtx_num))->at(to_vtx_num) = Num_Edges;

  Num_Edges++;
  return(Num_Edges-1);
};
//================================================
int DirectedGraph::AddEdge( obj_id_type edge_id,
                            obj_id_type fm_vtx_id,
                            obj_id_type to_vtx_id)
{
  int i, fm_vtx_num, to_vtx_num;
  
  Edge_List->push_back(edge_id);

  // search Vertex_List to find vertex number corresponding
  // to fm_vtx_id

  fm_vtx_num = -1;
  for(i=0; i<Num_Verts; i++)
    {
    if(Vertex_List->at(i) == fm_vtx_id) fm_vtx_num = i;
    }
  if(fm_vtx_num < 0)
    {
    // error: source vertex not found in graph
    return(-1);
    }

  // search Vertex_List to find vertex number corresponding
  // to to_vtx_id

  to_vtx_num = -1;
  for(i=0; i<Num_Verts; i++)
    {
    if(Vertex_List->at(i) == to_vtx_id) to_vtx_num = i;
    }
  if(to_vtx_num < 0)
    {
    // error: destination vertex not found in graph
    return(-1);
    }

  // insert new_edge_num (==Num_Edges) into
  // adjacency matrix at row fm_vtx_num and column to_vtx_num

  (Row_List->at(fm_vtx_num))->at(to_vtx_num) = Num_Edges;

  Num_Edges++;
  return(Num_Edges-1);
};
//================================================
int DirectedGraph::GetEdgeNum(int fm_vtx_num,
                              int to_vtx_num)
{
  int edge_num;
  edge_num = (Row_List->at(fm_vtx_num))->at(to_vtx_num);
  return(edge_num);
}
//================================================
int DirectedGraph::GetEdgeNum(obj_id_type edge_id)
{
  int edge_num = -1;
  for(int i=0; i<Num_Edges; i++)
    {
    if( Edge_List->at(i) == edge_id ) edge_num = i;
    }
  if(edge_num < 0)
    {
    // error: specified vertex not found in graph
    return(-1);
    }
  return(edge_num);
}
//================================================
int DirectedGraph::GetVertexNum(obj_id_type vtx_id)
{
  int vtx_num = -1;
  for(int i=0; i<Num_Verts; i++)
    {
    if( Vertex_List->at(i) == vtx_id ) vtx_num = i;
    }
  if(vtx_num < 0)
    {
    // error: specified vertex not found in graph
    return(-1);
    }
  return(vtx_num);
}
//================================================
obj_id_type DirectedGraph::GetEdgeId(int edge_num)
{
  if( edge_num >= 0 && edge_num < Num_Edges )
    return( Edge_List->at(edge_num) );
  else
    return(NULL);
}
//================================================
obj_id_type DirectedGraph::GetVertexId(int vtx_num)
{
  if( vtx_num >= 0 && vtx_num < Num_Verts )
    return( Vertex_List->at(vtx_num) );
  else
    return(NULL);
}