k_shortest_path.cpp

中文分词, N-最短路径算法 ICTCLAS研究学习组 http://groups.google.com/group/ictclas?msg=subscribe

#pragma once

#include ".\k_shortest_path.h"
#include <algorithm>
#include <iostream>

using namespace std;

void KShortestPath::Find(const size_t k0, k_paths_t& resPaths)
{
	//	prepare node item list. We have a DAG that has single direction !!
	//	so scan sequentially all the nodes except the first one, 
	for(NODE_ID_TYPE curnode = 1; curnode < c_node_items.size(); ++curnode)
	{		
		node_item_t entryVect; //hold all the pre_node entries
		node_item_t& nt = c_node_items[curnode];  //current node
		
		edge_it_pair it_pair = c_g.in_edges(curnode);

		for(edge_iterator it_edge = it_pair.first; it_edge != it_pair.second; ++it_edge)
		{				
			if(it_edge->m_iS == 0)
			{
				entryVect.push_back(pre_node_entry(0, 0, it_edge->m_cost)); // edge index is not important for the source node
			}
			else
			{
				node_item_t& nt_pre = c_node_items[it_edge->m_iS];
				size_t nSize = nt_pre.size();
				for(size_t i =0; i<nSize; i++)
				{
					entryVect.push_back(pre_node_entry(it_edge->m_iS, i, it_edge->m_cost + nt_pre[i].c_weight));
				}
			}
		}
		
		size_t k = std::min(k0, entryVect.size());
		partial_sort(entryVect.begin(), entryVect.begin()+k, entryVect.end() ); //only sort the best k entries
		nt.assign(entryVect.begin(), entryVect.begin()+k); //keep the shortest k pre_entry

	}

	GetPaths(resPaths);
}

void KShortestPath::GetPaths(k_paths_t& resPaths)
{
	//	begin from last node, trace backward
	const node_item_t& np_last = c_node_items.back();
	size_t nPath = np_last.size();
	resPaths.resize(nPath); //k paths
	
	NODE_ID_TYPE  PreNodeId, PreNodeId2;
	size_t PreEntryIndex;  //the index on the pre-node entry

	for(size_t i=0; i<nPath; i++) //build each path
	{
		resPaths[i].first = np_last[i].c_weight;
		path_id_list_t& path = resPaths[i].second;

		//track backward, pretend we are one node after the last node
		PreNodeId = (NODE_ID_TYPE)(c_node_items.size()-1); // id of the last node 
		PreEntryIndex = i; //the i-th entry on the last node

		while(PreNodeId>0) 
		{
			//path.push_front(PreNodeId);
			path.push_back(PreNodeId);
			PreNodeId2 = c_node_items[PreNodeId][PreEntryIndex].c_PreNode;
			PreEntryIndex = c_node_items[PreNodeId][PreEntryIndex].c_PreIndex;	
			PreNodeId = PreNodeId2;
		} 

		path.push_back(0); //add the first node

		//reverse the path id
		reverse (path.begin(), path.end() );

	}
}