adj_list.h

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

#pragma once


#include <vector>
#include <map>
typedef  double COST_TYPE;//the type of element
typedef  unsigned short  NODE_ID_TYPE;
struct edge
{
	NODE_ID_TYPE m_iS ;	//index for source vertex 
	NODE_ID_TYPE m_iT ;	//index for Target vertex 
		
	COST_TYPE m_cost;		//The cost of the edge

	//Edge Id can be the key for accessing an edge property map. 
	//The edge property map should hold any other info for the edge.
	//in the case of ICTCLAS, the property includes other data member in struct tagArrayChain.
	unsigned long GetEdgeId()  const
	{
		unsigned long id = m_iS;
		id = (id<<16) + m_iT;
		return id;
	}

};

typedef std::vector<edge> edge_vect;
typedef edge_vect::iterator edge_iterator;

typedef  std::pair<edge_iterator, edge_iterator> edge_it_pair;

enum adj_list_type
{
	eInEdge_Only,
	eOutEdge_Only,
	eInOutEdge
};

class adj_list
{
public:
	adj_list(adj_list_type eType);
	~adj_list(void);

	void addEdge(const edge& eNew);

	edge_it_pair in_edges(NODE_ID_TYPE nodeTarget);
	edge_it_pair out_edges(NODE_ID_TYPE nodeSource);
	size_t 	get_vert_count();  

	bool hasInEdge();
	bool hasOutEdge();

protected:
	typedef std::map<NODE_ID_TYPE, edge_vect> edge_map;
	typedef edge_map::iterator  edge_map_iterator;

	void addEdge(edge_map& map1, NODE_ID_TYPE iNode, const edge& eNew);
protected:

	//bool m_bNewEdge;
	adj_list_type m_eType;
	//edge_vect  m_vInEdge;  //sorted by edge::m_iS
	//edge_vect  m_vOutEdge; //sorted by edge::m_iT

	edge_map m_InEdgeMap;  //indexed by edge::m_iS
	edge_map m_OutEdgeMap; //indexed by edge::m_iT
	
};