www.pudn.com > KSP.rar > QYKShortestPaths.cpp
// ____________________________________________________________________________
//
// General Information:
//
// File Name: QYKShortestPaths.cpp
// Author: Yan Qi
// Project: KShortestPath
//
// Description: Implementation of class(es) CQYKShortestPaths
//
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Revision History:
//
// 11/23/2006 Yan Initial Version
//
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Copyright Notice:
//
// Copyright (c) 2006 Your Company Inc.
//
// Warning: This computer program is protected by copyright law and
// international treaties. Unauthorized reproduction or distribution
// of this program, or any portion of it, may result in severe civil and
// criminal penalties, and will be prosecuted to the maximum extent
// possible under the law.
//
// ____________________________________________________________________________
#pragma warning(disable: 4786)
#include "QYKShortestPaths.h"
namespace asu_emit_qyan
{
using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CQYKShortestPaths::CQYKShortestPaths( const CQYDirectedGraph& rGraph, int nSource, int nTerminal, int nTopk )
: m_rGraph(rGraph), m_nSourceNodeId(nSource), m_nTargetNodeId(nTerminal), m_nTopK(nTopk)
{
m_pIntermediateGraph = NULL;
m_pShortestPath4IntermediateGraph = NULL;
}
CQYKShortestPaths::~CQYKShortestPaths()
{
for (std::vector::iterator pos=m_vTopShortestPaths.begin(); pos!=m_vTopShortestPaths.end(); ++pos)
{
delete *pos;
}
//
if (m_pShortestPath4IntermediateGraph != NULL)
{
delete m_pShortestPath4IntermediateGraph;
}
}
/************************************************************************/
/* Get the top k shortest paths.
/************************************************************************/
vector CQYKShortestPaths::GetTopKShortestPaths()
{
_SearchTopKShortestPaths();
return m_vTopShortestPaths;
}
/************************************************************************/
/* The main function to do searching
/************************************************************************/
void CQYKShortestPaths::_SearchTopKShortestPaths()
{
//////////////////////////////////////////////////////////////////////////
// first, find the shortest path in the graph
m_pShortestPath4IntermediateGraph = new CQYShortestPath(m_rGraph);
CQYDirectedPath* the_shortest_path =
m_pShortestPath4IntermediateGraph->GetShortestPath(m_nSourceNodeId, m_nTargetNodeId);
// check the validity of the result
if(the_shortest_path->GetId() < 0) // the shortest path doesn't exist!
{
std::cerr << "The shortest path doesn't exist!" << std::endl;
return;
}else
{
the_shortest_path->SetId(0);
}
// update the intermediate variables
m_candidatePathsSet.insert(the_shortest_path);
m_pathDeviatedNodeMap.insert(pair(0, m_nSourceNodeId));
//////////////////////////////////////////////////////////////////////////
// second, start to find the other results
int cur_path_id = 0;
while (m_candidatePathsSet.size() != 0 && cur_path_id < m_nTopK)
{
// Fetch the smallest one from a queue of candidates;
// Note that it's one of results.
CQYDirectedPath* cur_path = (*m_candidatePathsSet.begin());
m_candidatePathsSet.erase(m_candidatePathsSet.begin());
// Put this candidate into the result list.
m_vTopShortestPaths.push_back(cur_path);
++cur_path_id;
// initiate temporal variables
int deviated_node_id = m_pathDeviatedNodeMap[cur_path->GetId()];
vector node_list_in_path = cur_path->GetVertexList();
// Construct a temporal graph in order to determine the next shortest paths
m_pIntermediateGraph = new CQYDirectedGraph(m_rGraph);
// Determine the costs of nodes in the graph
_DetermineCost2Target(node_list_in_path, deviated_node_id);
// Iterations for the restoration of nodes and edges
int path_length = node_list_in_path.size();
for (int i=path_length-2; i>=0 && node_list_in_path.at(i) != deviated_node_id; --i)
{
_RestoreEdges4CostAjustment(node_list_in_path, node_list_in_path.at(i), node_list_in_path.at(i+1));
}
// Call _Restore4CostAjustment again for the deviated_node
_RestoreEdges4CostAjustment(node_list_in_path, deviated_node_id, node_list_in_path.at(i+1), true);
delete m_pIntermediateGraph;
}
}
/************************************************************************/
/* Remove vertices in the input, and recalculate the
/************************************************************************/
void CQYKShortestPaths::_DetermineCost2Target(vector vertices_list, int deviated_node_id)
{
// first: generate a temporary graph with only parts of the original graph
int count4vertices = m_pIntermediateGraph->GetNumberOfVertices();
/// remove edges according to the algorithm
int count = vertices_list.size();
for (int i=0; iGetNumberOfEdges();
if (m_pIntermediateGraph->GetWeight(remove_node_id, j) < CQYDirectedGraph::DISCONNECT)
{
m_pIntermediateGraph->SetWeight(remove_node_id, j, CQYDirectedGraph::DISCONNECT);
--cur_edges_count;
}
m_pIntermediateGraph->SetNumberOfEdges(cur_edges_count);
}
}
/// reverse the direction of edges in the temporary graph
_ReverseEdgesInGraph(*m_pIntermediateGraph);
// second: run the shortest paths algorithm, but with the target as m_nSource.
// run the shortest paths algorithm to get the cost of each nodes in the rest of the graph
if (m_pShortestPath4IntermediateGraph != NULL)
{
delete m_pShortestPath4IntermediateGraph;
}
m_pShortestPath4IntermediateGraph = new CQYShortestPath(*m_pIntermediateGraph);
m_pShortestPath4IntermediateGraph->ConstructPathTree(m_nTargetNodeId);
// third: reverse the edges in the graph again, go back to the original
_ReverseEdgesInGraph(*m_pIntermediateGraph);
}
/************************************************************************/
/* Restore edges connecting start_node to end_node
/************************************************************************/
void CQYKShortestPaths::_RestoreEdges4CostAjustment(vector vertices_list,
int start_node_id, int end_node_id, bool is_deviated_node)
{
/// first: restore the arcs from 'start_node_id' except that reaching 'end_node_id';
// restore the arcs and recalculate the cost of relative nodes
int i;
bool is_updated = false;
int count4vertices = m_pIntermediateGraph->GetNumberOfVertices();
for (i=0; iSetWeight(start_node_id, i, edge_weight); //??? correct? if the node cost below is 'disconnect'??
// update the distance if the restored arc makes for a shorter path to the target.
double node_cost = m_pShortestPath4IntermediateGraph->GetDistance(i);
if ( node_cost < CQYDirectedGraph::DISCONNECT
&& (edge_weight+node_cost) < m_pShortestPath4IntermediateGraph->GetDistance(start_node_id))
{
m_pShortestPath4IntermediateGraph->SetDistance(start_node_id, edge_weight+node_cost);
m_pShortestPath4IntermediateGraph->SetNextNodeId(start_node_id, i);
is_updated = true;
}
}
}
// if possible, correct the labels and update the paths pool
double cost_of_start_node =
m_pShortestPath4IntermediateGraph->GetDistance(start_node_id);
if ( cost_of_start_node < CQYDirectedGraph::DISCONNECT)
{
if(is_updated) _UpdateWeight4CostUntilNode(start_node_id); // a condition checking is added @ 20080111
//// construct the new path into result vector.
// the next shortest path: the order of nodes is from the source to the terminal.
vector new_path;
int i;
int path_length = vertices_list.size();
for (i=0; vertices_list.at(i) != start_node_id; ++i)
{
new_path.push_back(vertices_list.at(i));
}
// stop if the cost of the new path is too large, it's required that its cost before deviated node is small enough.
int next_node_id = start_node_id;
do
{
new_path.push_back(next_node_id);
next_node_id = m_pShortestPath4IntermediateGraph->GetNextNodeId(next_node_id);
} while(next_node_id != m_nTargetNodeId);
new_path.push_back(m_nTargetNodeId);
// calculate the cost of the new path
double cost_new_path = 0;
int length_new_path = new_path.size();
for (i=0; i(new_node_id, start_node_id));
}
// second: restore the arc from 'start_node_id' to 'end_node_id';
double edge_weight = m_rGraph.GetWeight(start_node_id, end_node_id);
double cost_of_end_node = m_pShortestPath4IntermediateGraph->GetDistance(end_node_id);
m_pIntermediateGraph->SetWeight(start_node_id, end_node_id, edge_weight);
if (cost_of_start_node > edge_weight+cost_of_end_node)
{
m_pShortestPath4IntermediateGraph->SetDistance(start_node_id, edge_weight+cost_of_end_node);
m_pShortestPath4IntermediateGraph->SetNextNodeId(start_node_id, end_node_id);
//
_UpdateWeight4CostUntilNode(start_node_id);
}
}
/************************************************************************/
/* Update the weight of arcs before node_id in the graph
/* TODO: Is there any way to improve the function below!??
/************************************************************************/
void CQYKShortestPaths::_UpdateWeight4CostUntilNode(int node_id)
{
int count4vertices = m_pIntermediateGraph->GetNumberOfVertices();
std::vector candidate_node_list;
int cur_pos = 0;
candidate_node_list.push_back(node_id);
do
{
int cur_node_id = candidate_node_list.at(cur_pos++);
for (int i=0; iGetWeight(i, cur_node_id);
double cost_node = m_pShortestPath4IntermediateGraph->GetDistance(i);
double cost_cur_node = m_pShortestPath4IntermediateGraph->GetDistance(cur_node_id);
if (edge_weight < CQYDirectedGraph::DISCONNECT
&& cost_node > cost_cur_node + edge_weight)
{
m_pShortestPath4IntermediateGraph->SetDistance(i, cost_cur_node+edge_weight);
m_pShortestPath4IntermediateGraph->SetNextNodeId(i, cur_node_id);
if(std::find(candidate_node_list.begin(), candidate_node_list.end(), i)
== candidate_node_list.end())
{
candidate_node_list.push_back(i);
}
}
}
} while(cur_pos < candidate_node_list.size());
}
/************************************************************************/
/* Reverse directions of all edges in the graph
/************************************************************************/
void CQYKShortestPaths::_ReverseEdgesInGraph( CQYDirectedGraph& g )
{
int i;
int count4vertices = g.GetNumberOfVertices();
for (i=0; i cur_path_list = cur_shortest_path->GetVertexList();
vector::iterator loc_of_start_id =
std::find(cur_path_list.begin(), cur_path_list.end(), start_node_id);
if (loc_of_start_id == cur_path_list.end())
{
continue;
}else
{
++loc_of_start_id;
if (*loc_of_start_id == end_node_id)
{
return true;
}
}
}
return false;
}
} // namespace