#include "GraphDefinition.h"

Collaboration diagram for GraphDefinition:

[legend]

Public Member Functions
	GraphDefinition (void)

	~GraphDefinition (void)

bool	construct_graph (edge_t *edges, size_t edge_count, bool has_reverse_cost, bool directed)

int	my_dijkstra1 (edge_t edges, size_t edge_count, int64 start_edge, double start_part, int64 end_edge, double end_part, bool directed, bool has_reverse_cost, path_element_tt path, size_t path_count, char **err_msg, std::vector< PDVI > &ruleList)

int	my_dijkstra2 (edge_t edges, size_t edge_count, int64 start_vertex, int64 end_vertex, bool directed, bool has_reverse_cost, path_element_tt path, size_t path_count, char **err_msg, std::vector< PDVI > &ruleList)

int	my_dijkstra3 (edge_t edges, size_t edge_count, int64 start_vertex, int64 end_vertex, bool directed, bool has_reverse_cost, path_element_tt path, size_t path_count, char **err_msg)

Private Member Functions
bool	addEdge (edge_t edgeIn)

bool	connectEdge (GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)

double	construct_path (int64 ed_id, int64 v_pos)

void	deleteall ()

void	explore (int64 cur_node, GraphEdgeInfo &cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &que)

bool	get_single_cost (double total_cost, path_element_tt *path, size_t path_count)

double	getRestrictionCost (int64 cur_node, GraphEdgeInfo &new_edge, bool isStart)

void	init ()

Private Attributes
bool	isEndVirtual

bool	isStartVirtual

bool	m_bIsGraphConstructed

bool	m_bIsturnRestrictOn

CostHolder *	m_dCost

double	m_dEndPart

double	m_dStartpart

int64	m_lEndEdgeId

int64	m_lStartEdgeId

Long2LongMap	m_mapEdgeId2Index

Long2LongVectorMap	m_mapNodeId2Edge

RuleTable	m_ruleTable

GraphEdgeVector	m_vecEdgeVector

std::vector< path_element_tt >	m_vecPath

int64	max_edge_id

int64	max_node_id

PARENT_PATH *	parent

Detailed Description

Definition at line 115 of file GraphDefinition.h.

Constructor & Destructor Documentation

◆ GraphDefinition()

GraphDefinition::GraphDefinition ( void )

Definition at line 39 of file GraphDefinition.cpp.

                                      {
     m_lStartEdgeId = -1;
     m_lEndEdgeId = 0;
     m_dStartpart = 0.0;
     m_dEndPart = 0.0;
     m_dCost = NULL;
     m_bIsturnRestrictOn = false;
     m_bIsGraphConstructed = false;
     parent = NULL;
     init();
 }

References init(), m_bIsGraphConstructed, m_bIsturnRestrictOn, m_dCost, m_dEndPart, m_dStartpart, m_lEndEdgeId, m_lStartEdgeId, and parent.

◆ ~GraphDefinition()

GraphDefinition::~GraphDefinition ( void )

Definition at line 52 of file GraphDefinition.cpp.

52 {

53 }

Member Function Documentation

◆ addEdge()

bool GraphDefinition::addEdge ( edge_t edgeIn )

private

Definition at line 594 of file GraphDefinition.cpp.

                                            {
     // int64 lTest;
     Long2LongMap::iterator itMap = m_mapEdgeId2Index.find(edgeIn.id);
     if (itMap != m_mapEdgeId2Index.end())
         return false;
  
  
     GraphEdgeInfo* newEdge = new GraphEdgeInfo();
     newEdge->m_vecStartConnectedEdge.clear();
     newEdge->m_vecEndConnedtedEdge.clear();
     newEdge->m_vecRestrictedEdge.clear();
     newEdge->m_lEdgeID = edgeIn.id;
     newEdge->m_lEdgeIndex = static_cast<int64>(m_vecEdgeVector.size());
     newEdge->m_lStartNode = edgeIn.source;
     newEdge->m_lEndNode = edgeIn.target;
     newEdge->m_dCost = edgeIn.cost;
     newEdge->m_dReverseCost = edgeIn.reverse_cost;
  
     if (edgeIn.id > max_edge_id) {
         max_edge_id = edgeIn.id;
     }
  
     if (newEdge->m_lStartNode > max_node_id) {
         max_node_id = newEdge->m_lStartNode;
     }
     if (newEdge->m_lEndNode > max_node_id) {
         max_node_id = newEdge->m_lEndNode;
     }
  
     // Searching the start node for connectivity
     Long2LongVectorMap::iterator itNodeMap = m_mapNodeId2Edge.find(
         edgeIn.source);
     if (itNodeMap != m_mapNodeId2Edge.end()) {
         // Connect current edge with existing edge with start node
         // connectEdge(
         int64 lEdgeCount = static_cast<int64>(itNodeMap->second.size());
         int64 lEdgeIndex;
         for (lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++) {
             int64 lEdge = itNodeMap->second.at(static_cast<size_t>(lEdgeIndex));
             connectEdge(*newEdge, *m_vecEdgeVector[static_cast<size_t>(lEdge)], true);
         }
     }
  
  
     // Searching the end node for connectivity
     itNodeMap = m_mapNodeId2Edge.find(edgeIn.target);
     if (itNodeMap != m_mapNodeId2Edge.end()) {
         // Connect current edge with existing edge with end node
         // connectEdge(
         int64 lEdgeCount = static_cast<int64>(itNodeMap->second.size());
         int64 lEdgeIndex;
         for (lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++) {
             int64 lEdge = itNodeMap->second.at(static_cast<size_t>(lEdgeIndex));
             connectEdge(*newEdge, *m_vecEdgeVector[static_cast<size_t>(lEdge)], false);
         }
     }
  
  
  
     // Add this node and edge into the data structure
     m_mapNodeId2Edge[edgeIn.source].push_back(newEdge->m_lEdgeIndex);
     m_mapNodeId2Edge[edgeIn.target].push_back(newEdge->m_lEdgeIndex);
  
  
     // Adding edge to the list
     m_mapEdgeId2Index.insert(std::make_pair(newEdge->m_lEdgeID,
         m_vecEdgeVector.size()));
     m_vecEdgeVector.push_back(newEdge);
  
     //
  
  
     return true;
 }

References connectEdge(), edge_t::cost, edge_t::id, GraphEdgeInfo::m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeID, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, m_mapEdgeId2Index, m_mapNodeId2Edge, m_vecEdgeVector, GraphEdgeInfo::m_vecEndConnedtedEdge, GraphEdgeInfo::m_vecRestrictedEdge, GraphEdgeInfo::m_vecStartConnectedEdge, max_edge_id, max_node_id, edge_t::reverse_cost, edge_t::source, and edge_t::target.

Referenced by construct_graph(), and my_dijkstra1().

◆ connectEdge()

bool GraphDefinition::connectEdge	(	GraphEdgeInfo &	firstEdge,
		GraphEdgeInfo &	secondEdge,
		bool	bIsStartNodeSame
	)

private

Definition at line 561 of file GraphDefinition.cpp.

                                                       {
     if (bIsStartNodeSame) {
         if (firstEdge.m_dReverseCost >= 0.0)
             firstEdge.m_vecStartConnectedEdge.push_back(
                 secondEdge.m_lEdgeIndex);
         if (firstEdge.m_lStartNode == secondEdge.m_lStartNode) {
             if (secondEdge.m_dReverseCost >= 0.0)
                 secondEdge.m_vecStartConnectedEdge.push_back(
                     firstEdge.m_lEdgeIndex);
         } else {
             if (secondEdge.m_dCost >= 0.0)
                 secondEdge.m_vecEndConnedtedEdge.push_back(
                     firstEdge.m_lEdgeIndex);
         }
     } else {
         if (firstEdge.m_dCost >= 0.0)
             firstEdge.m_vecEndConnedtedEdge.push_back(secondEdge.m_lEdgeIndex);
         if (firstEdge.m_lEndNode == secondEdge.m_lStartNode) {
             if (secondEdge.m_dReverseCost >= 0.0)
                 secondEdge.m_vecStartConnectedEdge.push_back(
                     firstEdge.m_lEdgeIndex);
         } else {
             if (secondEdge.m_dCost >= 0.0)
                 secondEdge.m_vecEndConnedtedEdge.push_back(
                     firstEdge.m_lEdgeIndex);
         }
     }
     return true;
 }

References GraphEdgeInfo::m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, GraphEdgeInfo::m_vecEndConnedtedEdge, and GraphEdgeInfo::m_vecStartConnectedEdge.

Referenced by addEdge().

◆ construct_graph()

bool GraphDefinition::construct_graph	(	edge_t *	edges,
		size_t	edge_count,
		bool	has_reverse_cost,
		bool	directed
	)

Definition at line 543 of file GraphDefinition.cpp.

                                           {
     for (size_t i = 0; i < edge_count; i++) {
         if (!has_reverse_cost) {
             if (directed) {
                 edges[i].reverse_cost = -1.0;
             } else {
                 edges[i].reverse_cost = edges[i].cost;
             }
         }
         addEdge(edges[i]);
     }
     m_bIsGraphConstructed = true;
     return true;
 }

References addEdge(), edge_t::cost, m_bIsGraphConstructed, and edge_t::reverse_cost.

Referenced by my_dijkstra1(), and my_dijkstra3().

◆ construct_path()

double GraphDefinition::construct_path	(	int64	ed_id,
		int64	v_pos
	)

private

Definition at line 79 of file GraphDefinition.cpp.

                                                                {
     if (parent[ed_id].ed_ind[v_pos] == -1) {
         path_element_tt pelement;
         GraphEdgeInfo* cur_edge = m_vecEdgeVector[static_cast<size_t>(ed_id)];
         if (v_pos == 0) {
             pelement.vertex_id = cur_edge->m_lStartNode;
             pelement.cost = cur_edge->m_dCost;
         } else {
             pelement.vertex_id = cur_edge->m_lEndNode;
             pelement.cost = cur_edge->m_dReverseCost;
         }
         pelement.edge_id = cur_edge->m_lEdgeID;
  
         m_vecPath.push_back(pelement);
         return pelement.cost;
     }
     double ret = construct_path(parent[ed_id].ed_ind[v_pos],
         parent[ed_id].v_pos[v_pos]);
     path_element_tt pelement;
     GraphEdgeInfo* cur_edge = m_vecEdgeVector[static_cast<size_t>(ed_id)];
     if (v_pos == 0) {
         pelement.vertex_id = cur_edge->m_lStartNode;
         pelement.cost = m_dCost[ed_id].endCost - ret;  // cur_edge.m_dCost;
         ret = m_dCost[ed_id].endCost;
     } else {
         pelement.vertex_id = cur_edge->m_lEndNode;
         pelement.cost = m_dCost[ed_id].startCost - ret;
         ret = m_dCost[ed_id].startCost;
     }
     pelement.edge_id = cur_edge->m_lEdgeID;
  
     m_vecPath.push_back(pelement);
  
     return ret;
 }

References path_element::cost, path_element::edge_id, CostHolder::endCost, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeID, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, m_vecEdgeVector, m_vecPath, parent, CostHolder::startCost, and path_element::vertex_id.

Referenced by my_dijkstra3().

◆ deleteall()

void GraphDefinition::deleteall ( )

private

Definition at line 66 of file GraphDefinition.cpp.

                                 {
     std::vector<GraphEdgeInfo*>::iterator it;
     for (it = m_vecEdgeVector.begin(); it != m_vecEdgeVector.end(); ++it) {
         delete *it;
     }
     m_vecEdgeVector.clear();
  
     delete [] parent;
     delete [] m_dCost;
 }

References m_dCost, m_vecEdgeVector, and parent.

Referenced by my_dijkstra3().

◆ explore()

void GraphDefinition::explore	(	int64	cur_node,
		GraphEdgeInfo &	cur_edge,
		bool	isStart,
		LongVector &	vecIndex,
		std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &	que
	)

private

Definition at line 153 of file GraphDefinition.cpp.

                             {
     double totalCost;
     for (const auto &index : vecIndex) {
         auto new_edge = m_vecEdgeVector[static_cast<size_t>(index)];
         double extCost = 0.0;
         if (m_bIsturnRestrictOn) {
             extCost = getRestrictionCost(cur_edge.m_lEdgeIndex,
                  *new_edge, isStart);
         }
         if (new_edge->m_lStartNode == cur_node) {
             if (new_edge->m_dCost >= 0.0) {
                 if (isStart)
                     totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost +
                     new_edge->m_dCost + extCost;
                 else
                     totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost +
                     new_edge->m_dCost + extCost;
                 if (totalCost < m_dCost[index].endCost) {
                     m_dCost[index].endCost = totalCost;
                     parent[new_edge->m_lEdgeIndex].v_pos[0] = (isStart?0:1);
                     parent[new_edge->m_lEdgeIndex].ed_ind[0] =
                      cur_edge.m_lEdgeIndex;
                     que.push(std::make_pair(totalCost,
                         std::make_pair(new_edge->m_lEdgeIndex, true)));
                 }
             }
         } else {
             if (new_edge->m_dReverseCost >= 0.0) {
                 if (isStart)
                     totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost +
                     new_edge->m_dReverseCost + extCost;
                 else
                     totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost +
                     new_edge->m_dReverseCost + extCost;
                 if (totalCost < m_dCost[index].startCost) {
                     m_dCost[index].startCost = totalCost;
                     parent[new_edge->m_lEdgeIndex].v_pos[1] = (isStart?0:1);
                     parent[new_edge->m_lEdgeIndex].ed_ind[1] =
                     cur_edge.m_lEdgeIndex;
                     que.push(std::make_pair(totalCost,
                         std::make_pair(new_edge->m_lEdgeIndex, false)));
                 }
             }
         }
     }
 }

References PARENT_PATH::ed_ind, CostHolder::endCost, getRestrictionCost(), m_bIsturnRestrictOn, m_dCost, GraphEdgeInfo::m_lEdgeIndex, m_vecEdgeVector, parent, CostHolder::startCost, and PARENT_PATH::v_pos.

Referenced by my_dijkstra3().

◆ get_single_cost()

bool GraphDefinition::get_single_cost	(	double	total_cost,
		path_element_tt **	path,
		size_t *	path_count
	)

private

Definition at line 506 of file GraphDefinition.cpp.

                          {
     GraphEdgeInfo* start_edge_info =
     m_vecEdgeVector[static_cast<size_t>(m_mapEdgeId2Index[m_lStartEdgeId])];
     if (m_dEndPart >= m_dStartpart) {
         if (start_edge_info->m_dCost >= 0.0 && start_edge_info->m_dCost *
             (m_dEndPart - m_dStartpart) <= total_cost) {
             *path = reinterpret_cast<path_element_tt *>(malloc(
                         sizeof(path_element_tt) * (1)));
             *path_count = 1;
             (*path)[0].vertex_id = -1;
             (*path)[0].edge_id = m_lStartEdgeId;
             (*path)[0].cost = start_edge_info->m_dCost *
             (m_dEndPart - m_dStartpart);
  
             return true;
         }
     } else {
         if (start_edge_info->m_dReverseCost >= 0.0 &&
             start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart) <=
             total_cost) {
             *path = reinterpret_cast<path_element_tt *>(malloc(
                         sizeof(path_element_tt) * (1)));
             *path_count = 1;
             (*path)[0].vertex_id = -1;
             (*path)[0].edge_id = m_lStartEdgeId;
             (*path)[0].cost = start_edge_info->m_dReverseCost *
             (m_dStartpart - m_dEndPart);
  
             return true;
         }
     }
     return false;
 }

References GraphEdgeInfo::m_dCost, m_dEndPart, GraphEdgeInfo::m_dReverseCost, m_dStartpart, m_lStartEdgeId, m_mapEdgeId2Index, m_vecEdgeVector, and path_element::vertex_id.

Referenced by my_dijkstra3().

◆ getRestrictionCost()

double GraphDefinition::getRestrictionCost	(	int64	cur_node,
		GraphEdgeInfo &	new_edge,
		bool	isStart
	)

private

Definition at line 117 of file GraphDefinition.cpp.

                   {
     double cost = 0.0;
     int64 edge_id = new_edge.m_lEdgeID;
     if (m_ruleTable.find(edge_id) == m_ruleTable.end()) {
         return(0.0);
     }
     std::vector<Rule> vecRules = m_ruleTable[edge_id];
     int64 st_edge_ind = edge_ind;
     for (const auto &rule : vecRules) {
         bool flag = true;
         int64 v_pos = (isStart?0:1);
         edge_ind = st_edge_ind;
         for (auto const &precedence : rule.precedencelist) {
             if (edge_ind == -1) {
                 flag = false;
                 break;
             }
             if (precedence != m_vecEdgeVector[static_cast<size_t>(edge_ind)]->m_lEdgeID) {
                 flag = false;
                 break;
             }
             auto parent_ind = parent[static_cast<size_t>(edge_ind)].ed_ind[static_cast<size_t>(v_pos)];
             v_pos = parent[edge_ind].v_pos[v_pos];
             edge_ind = parent_ind;
         }
         if (flag)
             cost += rule.cost;
     }
     return cost;
 }

References GraphEdgeInfo::m_lEdgeID, m_ruleTable, m_vecEdgeVector, parent, and PARENT_PATH::v_pos.

Referenced by explore().

◆ init()

void GraphDefinition::init ( )

private

Definition at line 57 of file GraphDefinition.cpp.

                            {
     max_edge_id = 0;
     max_node_id = 0;
     isStartVirtual = false;
     isEndVirtual = false;
 }

References isEndVirtual, isStartVirtual, max_edge_id, and max_node_id.

Referenced by GraphDefinition(), my_dijkstra1(), and my_dijkstra3().

◆ my_dijkstra1()

int GraphDefinition::my_dijkstra1	(	edge_t *	edges,
		size_t	edge_count,
		int64	start_edge,
		double	start_part,
		int64	end_edge,
		double	end_part,
		bool	directed,
		bool	has_reverse_cost,
		path_element_tt **	path,
		size_t *	path_count,
		char **	err_msg,
		std::vector< PDVI > &	ruleList
	)

Definition at line 210 of file GraphDefinition.cpp.

                                    {
     if (!m_bIsGraphConstructed) {
             init();
             construct_graph(edges, edge_count, has_reverse_cost, directed);
             m_bIsGraphConstructed = true;
         }
         GraphEdgeInfo* start_edge_info =
         m_vecEdgeVector[static_cast<size_t>(m_mapEdgeId2Index[static_cast<int64>(start_edge_id)])];
         edge_t start_edge;
         int64 start_vertex, end_vertex;
         m_dStartpart = start_part;
         m_dEndPart = end_part;
         m_lStartEdgeId = start_edge_id;
         m_lEndEdgeId = end_edge_id;
  
         if (start_part == 0.0) {
             start_vertex = start_edge_info->m_lStartNode;
         } else if (start_part == 1.0) {
             start_vertex = start_edge_info->m_lEndNode;
         } else {
             isStartVirtual = true;
             m_lStartEdgeId = start_edge_id;
             start_vertex = max_node_id + 1;
             max_node_id++;
             start_edge.id = max_edge_id + 1;
             max_edge_id++;
             start_edge.source = start_vertex;
             start_edge.reverse_cost = -1.0;
             if (start_edge_info->m_dCost >= 0.0) {
                 start_edge.target = start_edge_info->m_lEndNode;
                 start_edge.cost = (1.0 - start_part) * start_edge_info->m_dCost;
                 addEdge(start_edge);
                 edge_count++;
             }
             if (start_edge_info->m_dReverseCost >= 0.0) {
                 start_edge.id = max_edge_id + 1;
                 max_edge_id++;
                 start_edge.target = start_edge_info->m_lStartNode;
                 start_edge.cost = start_part * start_edge_info->m_dReverseCost;
                 addEdge(start_edge);
                 edge_count++;
             }
         }
  
     GraphEdgeInfo* end_edge_info =
     m_vecEdgeVector[static_cast<size_t>(m_mapEdgeId2Index[static_cast<int64>(end_edge_id)])];
     edge_t end_edge;
  
     if (end_part == 0.0) {
         end_vertex = end_edge_info->m_lStartNode;
     } else if (end_part == 1.0) {
         end_vertex = end_edge_info->m_lEndNode;
     } else {
         isEndVirtual = true;
         m_lEndEdgeId = end_edge_id;
         end_vertex = max_node_id + 1;
         max_node_id++;
         end_edge.id = max_edge_id + 1;
         max_edge_id++;
         end_edge.target = end_vertex;
         end_edge.reverse_cost = -1.0;
         if (end_edge_info->m_dCost >= 0.0) {
             end_edge.source = end_edge_info->m_lStartNode;
             end_edge.cost = end_part * end_edge_info->m_dCost;
             addEdge(end_edge);
             edge_count++;
         }
         if (end_edge_info->m_dReverseCost >= 0.0) {
             end_edge.source = end_edge_info->m_lEndNode;
             end_edge.id = max_edge_id + 1;
             end_edge.cost = (1.0 - end_part) * end_edge_info->m_dReverseCost;
             addEdge(end_edge);
             edge_count++;
         }
     }
  
     return(my_dijkstra2(
                 edges, edge_count,
                 start_vertex, end_vertex,
                 directed, has_reverse_cost,
  
                 path, path_count, err_msg,
  
                 ruleList));
 }

References addEdge(), construct_graph(), edge_t::cost, edge_t::id, init(), isEndVirtual, isStartVirtual, m_bIsGraphConstructed, GraphEdgeInfo::m_dCost, m_dEndPart, GraphEdgeInfo::m_dReverseCost, m_dStartpart, m_lEndEdgeId, GraphEdgeInfo::m_lEndNode, m_lStartEdgeId, GraphEdgeInfo::m_lStartNode, m_mapEdgeId2Index, m_vecEdgeVector, max_edge_id, max_node_id, my_dijkstra2(), edge_t::reverse_cost, edge_t::source, and edge_t::target.

Referenced by trsp_edge_wrapper().

◆ my_dijkstra2()

int GraphDefinition::my_dijkstra2	(	edge_t *	edges,
		size_t	edge_count,
		int64	start_vertex,
		int64	end_vertex,
		bool	directed,
		bool	has_reverse_cost,
		path_element_tt **	path,
		size_t *	path_count,
		char **	err_msg,
		std::vector< PDVI > &	ruleList
	)

Definition at line 307 of file GraphDefinition.cpp.

                                {
     m_ruleTable.clear();
     LongVector vecsource;
     for (const auto &rule : ruleList) {
         size_t j;
         size_t seq_cnt = rule.second.size();
         std::vector<int64> temp_precedencelist;
         temp_precedencelist.clear();
         for (j = 1; j < seq_cnt; j++) {
             temp_precedencelist.push_back(rule.second[j]);
         }
         int64 dest_edge_id = rule.second[0];
         if (m_ruleTable.find(dest_edge_id) != m_ruleTable.end()) {
             m_ruleTable[dest_edge_id].push_back(Rule(rule.first,
                 temp_precedencelist));
         } else {
             std::vector<Rule> temprules;
             temprules.clear();
             temprules.push_back(Rule(rule.first, temp_precedencelist));
             m_ruleTable.insert(std::make_pair(dest_edge_id, temprules));
         }
  
         if (isStartVirtual) {
             if (seq_cnt == 2 && rule.second[1] == m_lStartEdgeId) {
                 vecsource = m_mapNodeId2Edge[start_vertex];
                 for (const auto &source : vecsource) {
                     temp_precedencelist.clear();
                     temp_precedencelist.push_back(
                         m_vecEdgeVector[static_cast<size_t>(source)]->m_lEdgeID);
                     m_ruleTable[dest_edge_id].push_back(Rule(rule.first,
                         temp_precedencelist));
                 }
             }
         }
     }
     if (isEndVirtual) {
         if (m_ruleTable.find(m_lEndEdgeId) != m_ruleTable.end()) {
             std::vector<Rule> tmpRules = m_ruleTable[m_lEndEdgeId];
             vecsource = m_mapNodeId2Edge[end_vertex];
             for (const auto &source : vecsource) {
                 m_ruleTable.insert(std::make_pair(
                     m_vecEdgeVector[static_cast<size_t>(source)]->m_lEdgeID, tmpRules));
             }
         }
     }
     m_bIsturnRestrictOn = true;
     return(my_dijkstra3(
                 edges, edge_count,
                 start_vertex, end_vertex,
                 directed, has_reverse_cost,
                 path, path_count, err_msg));
 }

References isEndVirtual, isStartVirtual, m_bIsturnRestrictOn, m_lEndEdgeId, m_lStartEdgeId, m_mapNodeId2Edge, m_ruleTable, m_vecEdgeVector, and my_dijkstra3().

Referenced by my_dijkstra1().

◆ my_dijkstra3()

int GraphDefinition::my_dijkstra3	(	edge_t *	edges,
		size_t	edge_count,
		int64	start_vertex,
		int64	end_vertex,
		bool	directed,
		bool	has_reverse_cost,
		path_element_tt **	path,
		size_t *	path_count,
		char **	err_msg
	)

Definition at line 368 of file GraphDefinition.cpp.

       {
     if (!m_bIsGraphConstructed) {
         init();
         construct_graph(edges, edge_count, has_reverse_cost, directed);
         m_bIsGraphConstructed = true;
     }
  
     std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > que;
     parent = new PARENT_PATH[edge_count + 1];
     m_dCost = new CostHolder[edge_count + 1];
     m_vecPath.clear();
  
     unsigned int i;
     for (i = 0; i <= edge_count; i++) {
         m_dCost[i].startCost = 1e15;
         m_dCost[i].endCost = 1e15;
     }
  
     if (m_mapNodeId2Edge.find(start_vertex) == m_mapNodeId2Edge.end()) {
         *err_msg = const_cast<char *>("Source Not Found");
         deleteall();
         return -1;
     }
  
     if (m_mapNodeId2Edge.find(end_vertex) == m_mapNodeId2Edge.end()) {
         *err_msg = const_cast<char *>("Destination Not Found");
         deleteall();
         return -1;
     }
  
     LongVector vecsource = m_mapNodeId2Edge[start_vertex];
     GraphEdgeInfo* cur_edge = NULL;
  
     for (const auto &source : vecsource) {
         cur_edge = m_vecEdgeVector[static_cast<size_t>(source)];
         if (cur_edge->m_lStartNode == start_vertex) {
             if (cur_edge->m_dCost >= 0.0) {
                 m_dCost[cur_edge->m_lEdgeIndex].endCost = cur_edge->m_dCost;
                 parent[cur_edge->m_lEdgeIndex].v_pos[0] = -1;
                 parent[cur_edge->m_lEdgeIndex].ed_ind[0] = -1;
                 que.push(std::make_pair(cur_edge->m_dCost,
                     std::make_pair(cur_edge->m_lEdgeIndex, true)));
             }
         } else {
             if (cur_edge->m_dReverseCost >= 0.0) {
                 m_dCost[cur_edge->m_lEdgeIndex].startCost =
                 cur_edge->m_dReverseCost;
                 parent[cur_edge->m_lEdgeIndex].v_pos[1] = -1;
                 parent[cur_edge->m_lEdgeIndex].ed_ind[1] = -1;
                 que.push(std::make_pair(cur_edge->m_dReverseCost,
                     std::make_pair(cur_edge->m_lEdgeIndex, false)));
             }
         }
     }
     int64 cur_node = -1;
  
     while (!que.empty()) {
         PDP cur_pos = que.top();
         que.pop();
         int64 cured_index = cur_pos.second.first;
         cur_edge = m_vecEdgeVector[static_cast<size_t>(cured_index)];
  
         if (cur_pos.second.second) {  // explore edges connected to end node
             cur_node = cur_edge->m_lEndNode;
             if (cur_edge->m_dCost < 0.0)
                 continue;
             if (cur_node == end_vertex)
                 break;
             explore(cur_node, *cur_edge, true, cur_edge->m_vecEndConnedtedEdge,
                 que);
         } else {  // explore edges connected to start node
             cur_node = cur_edge->m_lStartNode;
             if (cur_edge->m_dReverseCost < 0.0)
                 continue;
             if (cur_node == end_vertex)
                 break;
             explore(cur_node, *cur_edge, false,
                 cur_edge->m_vecStartConnectedEdge, que);
         }
     }
     if (cur_node != end_vertex) {
         if (m_lStartEdgeId == m_lEndEdgeId) {
             if (get_single_cost(1000.0, path, path_count)) {
                 return 0;
             }
         }
         *err_msg = const_cast<char *>("Path Not Found");
         deleteall();
         return -1;
     } else {
         double total_cost;
         if (cur_node == cur_edge->m_lStartNode) {
             total_cost = m_dCost[cur_edge->m_lEdgeIndex].startCost;
             construct_path(cur_edge->m_lEdgeIndex, 1);
         } else {
             total_cost = m_dCost[cur_edge->m_lEdgeIndex].endCost;
             construct_path(cur_edge->m_lEdgeIndex, 0);
         }
         path_element_tt pelement;
         pelement.vertex_id = end_vertex;
         pelement.edge_id = -1;
         pelement.cost = 0.0;
         m_vecPath.push_back(pelement);
  
         if (m_lStartEdgeId == m_lEndEdgeId) {
             if (get_single_cost(total_cost, path, path_count)) {
                 return 0;
             }
         }
  
         *path = reinterpret_cast<path_element_tt *>(
                 malloc(sizeof(path_element_tt) * (m_vecPath.size() + 1)));
         *path_count = m_vecPath.size();
  
         for (size_t i = 0; i < *path_count; i++) {
             (*path)[i].vertex_id = m_vecPath[i].vertex_id;
             (*path)[i].edge_id = m_vecPath[i].edge_id;
             (*path)[i].cost = m_vecPath[i].cost;
         }
         if (isStartVirtual) {
             (*path)[0].vertex_id = -1;
             (*path)[0].edge_id = m_lStartEdgeId;
         }
         if (isEndVirtual) {
             *path_count = *path_count - 1;
             (*path)[*path_count - 1].edge_id = m_lEndEdgeId;
         }
     }
     deleteall();
     return 0;
 }

References construct_graph(), construct_path(), path_element::cost, deleteall(), PARENT_PATH::ed_ind, path_element::edge_id, CostHolder::endCost, explore(), get_single_cost(), init(), isEndVirtual, isStartVirtual, m_bIsGraphConstructed, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, m_lEndEdgeId, GraphEdgeInfo::m_lEndNode, m_lStartEdgeId, GraphEdgeInfo::m_lStartNode, m_mapNodeId2Edge, m_vecEdgeVector, GraphEdgeInfo::m_vecEndConnedtedEdge, m_vecPath, GraphEdgeInfo::m_vecStartConnectedEdge, parent, CostHolder::startCost, PARENT_PATH::v_pos, and path_element::vertex_id.

Referenced by my_dijkstra2().

Member Data Documentation

◆ isEndVirtual

bool GraphDefinition::isEndVirtual

private

Definition at line 171 of file GraphDefinition.h.

Referenced by init(), my_dijkstra1(), my_dijkstra2(), and my_dijkstra3().

◆ isStartVirtual

bool GraphDefinition::isStartVirtual

private

Definition at line 170 of file GraphDefinition.h.

Referenced by init(), my_dijkstra1(), my_dijkstra2(), and my_dijkstra3().

◆ m_bIsGraphConstructed

bool GraphDefinition::m_bIsGraphConstructed

private

Definition at line 178 of file GraphDefinition.h.

Referenced by construct_graph(), GraphDefinition(), my_dijkstra1(), and my_dijkstra3().

◆ m_bIsturnRestrictOn

bool GraphDefinition::m_bIsturnRestrictOn

private

Definition at line 177 of file GraphDefinition.h.

Referenced by explore(), GraphDefinition(), and my_dijkstra2().

◆ m_dCost

CostHolder* GraphDefinition::m_dCost

private

Definition at line 175 of file GraphDefinition.h.

Referenced by construct_path(), deleteall(), explore(), GraphDefinition(), and my_dijkstra3().

◆ m_dEndPart

double GraphDefinition::m_dEndPart

private

Definition at line 169 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), and my_dijkstra1().

◆ m_dStartpart

double GraphDefinition::m_dStartpart

private

Definition at line 168 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), and my_dijkstra1().

◆ m_lEndEdgeId

int64 GraphDefinition::m_lEndEdgeId

private

Definition at line 167 of file GraphDefinition.h.

Referenced by GraphDefinition(), my_dijkstra1(), my_dijkstra2(), and my_dijkstra3().

◆ m_lStartEdgeId

int64 GraphDefinition::m_lStartEdgeId

private

Definition at line 166 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), my_dijkstra1(), my_dijkstra2(), and my_dijkstra3().

◆ m_mapEdgeId2Index

Long2LongMap GraphDefinition::m_mapEdgeId2Index

private

Definition at line 162 of file GraphDefinition.h.

Referenced by addEdge(), get_single_cost(), and my_dijkstra1().

◆ m_mapNodeId2Edge

Long2LongVectorMap GraphDefinition::m_mapNodeId2Edge

private

Definition at line 163 of file GraphDefinition.h.

Referenced by addEdge(), my_dijkstra2(), and my_dijkstra3().

◆ m_ruleTable

RuleTable GraphDefinition::m_ruleTable

private

Definition at line 176 of file GraphDefinition.h.

Referenced by getRestrictionCost(), and my_dijkstra2().

◆ m_vecEdgeVector

GraphEdgeVector GraphDefinition::m_vecEdgeVector

private

Definition at line 161 of file GraphDefinition.h.

Referenced by addEdge(), construct_path(), deleteall(), explore(), get_single_cost(), getRestrictionCost(), my_dijkstra1(), my_dijkstra2(), and my_dijkstra3().

◆ m_vecPath

std::vector<path_element_tt> GraphDefinition::m_vecPath

private

Definition at line 173 of file GraphDefinition.h.

Referenced by construct_path(), and my_dijkstra3().

◆ max_edge_id

int64 GraphDefinition::max_edge_id

private

Definition at line 165 of file GraphDefinition.h.

Referenced by addEdge(), init(), and my_dijkstra1().

◆ max_node_id

int64 GraphDefinition::max_node_id

private

Definition at line 164 of file GraphDefinition.h.

Referenced by addEdge(), init(), and my_dijkstra1().

◆ parent

PARENT_PATH* GraphDefinition::parent

private

Definition at line 174 of file GraphDefinition.h.

Referenced by construct_path(), deleteall(), explore(), getRestrictionCost(), GraphDefinition(), and my_dijkstra3().

The documentation for this class was generated from the following files:

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GraphDefinition()

◆ ~GraphDefinition()

Member Function Documentation

◆ addEdge()

◆ connectEdge()

◆ construct_graph()

◆ construct_path()

◆ deleteall()

◆ explore()

◆ get_single_cost()

◆ getRestrictionCost()

◆ init()

◆ my_dijkstra1()

◆ my_dijkstra2()

◆ my_dijkstra3()

Member Data Documentation

◆ isEndVirtual

◆ isStartVirtual

◆ m_bIsGraphConstructed

◆ m_bIsturnRestrictOn

◆ m_dCost

◆ m_dEndPart

◆ m_dStartpart

◆ m_lEndEdgeId

◆ m_lStartEdgeId

◆ m_mapEdgeId2Index

◆ m_mapNodeId2Edge

◆ m_ruleTable

◆ m_vecEdgeVector

◆ m_vecPath

◆ max_edge_id

◆ max_node_id

◆ parent