一种寻路的应用
应用背景
利用长途车进行货物转运的寻路计算。例如从深圳到大连。可以走有很多条长途车的路线。需要根据需求计算出最合适路线。不同的路线的总里程数、总价、需要的时间不一样。客户根据需求进行选择。主要有一些细节：
-
全国的长途车车站的数据的更新：
-
包括位置、发车班次时间点、车站间的里程数等等。常用的路线有18000多条
重庆 重庆 重庆万盛客运中心 308 遵义 遵义市长途汽车站
重庆 重庆 重庆万盛客运中心 360 成都 成都北门汽车站
重庆 重庆 重庆渝中长途汽车站 157 武胜 武胜汽车站
重庆 重庆 重庆渝中长途汽车站 340 遵义 遵义市长途汽车站
重庆 重庆 重庆渝中长途汽车站 360 成都 成都北门汽车站
重庆 重庆 重庆渝中长途汽车站 467 巴中 巴中江北客运中心站
重庆 重庆 重庆渝中长途汽车站 502 广元 广元市长途汽车客运站
-
同城转车的处理
-
有些城市有多个车站，可以在一个城市里转到另外一个车站，再转运到下一站
-
使用发车班次时间表进行总时长的计算
- 预留出合理的时间间隔。例如到达某一站是20:30，但是到下一站的车 最晚一班是15:00 点发车。所以只能等第2天的班车。还有的班次可能一周只有2趟车。 有时 到达某一站是15:00 下一站的发车时间也是15:00 这种就只能等下一班，因为赶不上。
代码实现
初始化
班车路线、城市、车站等
constructor TR_Manager.Create;
begin
_result_path := Tlist<TR_Path>.Create;
_Dict_Province := TDictionary<Integer, TProvince>.Create();
_Dict_City := TDictionary<Integer, TCity>.Create();
_Dict_City_Name := TDictionary<string, TCity>.Create();
_ProvinceList := Tlist<TProvince>.Create();
_StationList := Tlist<TStation>.Create();
_Dict_Station := TDictionary<string, TStation>.Create();
_StationPathList := Tlist<TStation_Path>.Create();
_Dict_CityID_Station := TDictionary < Integer, Tlist < TStation >>.Create();
_Dict_CityID_Xian_Station := TDictionary < Integer, TDictionary < string,
Tlist<TStation> >>.Create(); // hfg 2016-07-23
_StationPathNodeList := Tlist<TStation_Path_Node>.Create();
_Dict_Station_Path_Node := TDictionary<TStation, TStation_Path_Node>.Create();
_Dict_CityID_Path_Node := TDictionary < Integer, Tlist < TStation_Path_Node
>>.Create();
_Node_Tmp := Tlist<TStation_Path_Node>.Create();
_Node_Tmp_2 := Tlist<TStation_Path_Node>.Create();
_Node_Tmp_before_end := Tlist<TStation_Path_Node>.Create();
end;
寻路
StationName_Begin: 起点车站
Station_End: 终点车站
max_step: Integer = 6; 最大转车次数
allow_same_city: boolean = false 是否允许同城转运
function TR_Manager.get_path_quick(StationName_Begin: string;
Station_End: Tlist<TStation>; max_step: Integer = 6;
allow_same_city: boolean = false): boolean;
var
Station: TStation;
node_root, node, node_next: TStation_Path_Node;
i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,
Node_Tmp_before_end_count: Integer;
path: TR_Path;
list: Tlist;
city_station_list: Tlist<TStation_Path_Node>;
begin
Result := false;
clear_result_path();
if Station_End = nil then
exit;
if Station_End.Count <= 0 then
exit;
if not(_Dict_Station.TryGetValue(StationName_begin, Station)) then
exit;
if Station.CityID = Station_End[0].CityID then
begin
path := TR_Path.Create;
path.Mileage := 0;
path.step := 1;
path.StationList.Add(Station);
for i := 0 to Station_End.Count - 1 do
begin
if Station_End[i].Name <> Station.Name then
begin
path.StationList.Add(Station_End[i]);
Break;
end;
end;
if path.StationList.Count < 2 then
path.StationList.Add(Station);
_result_path.Add(path);
end;
if not(_Dict_Station_Path_Node.TryGetValue(Station, node_root)) then
exit;
for i := 0 to _StationPathNodeList.Count - 1 do
_StationPathNodeList[i].reset();
node_root.set_Step(0);
_Node_Tmp[0] := node_root;
Node_Tmp_Count := 1;
Node_Tmp_before_end_count := 0;
for i := 0 to Station_End.Count - 1 do
begin
if _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) then
node.set_is_before_end();
end;
for step := 1 to max_step do
begin
Node_Tmp_2_Count := 0;
for i := 0 to Node_Tmp_Count - 1 do
begin
try
node := _Node_Tmp[i];
if (node.is_before_end) then
begin
_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;
inc(Node_Tmp_before_end_count);
if step > 1 then
Continue;
end;
for k := 0 to node.Next_Station.Count - 1 do
begin
node_next := node.Next_Station[k].Station_Node_Next;
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end
else
begin
if (node_next.step = step) and (step > 1) then
begin
if node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileage
then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
end;
end;
end;
end;
if allow_same_city then
begin
if _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,
city_station_list) then
begin
for k := 0 to city_station_list.Count - 1 do
begin
node_next := city_station_list[k];
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + 0;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end;
end;
end;
end;
except
Node_Tmp_2_Count := Node_Tmp_2_Count - 1;
end;
end;
Node_Tmp_Count := 0;
for i := 0 to Node_Tmp_2_Count - 1 do
begin
if _Node_Tmp_2[i].is_on_path then
begin
if True then
if Node_Tmp_Count < _Node_Tmp.Count then
_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]
else
_Node_Tmp.Add(_Node_Tmp_2[i]);
inc(Node_Tmp_Count);
end;
end;
end;
list := Tlist.Create();
for i := 0 to Node_Tmp_before_end_count - 1 do
begin
path := TR_Path.Create;
node := _Node_Tmp_before_end[i];
path.Mileage := node.path_mileage + node.to_end_mileage;
path.StationList.Add(node.end_Node.Station);
path.StationList.Add(node.Station);
node_next := node.Path_Prior_Station;
for step := 1 to max_step + 1 do
begin
if node_next = nil then
Break;
path.StationList.Add(node_next.Station);
if node_next.step <= 0 then
Break;
node_next := node_next.Path_Prior_Station
end;
path.StationList.Reverse();
list.Add(path);
end;
list.Sort(@ComparePath_city);
for i := 0 to list.Count - 1 do
_result_path.Add(list[i]);
FreeAndNil(list);
Result := _result_path.Count > 0;
end;操作说明
1、登陆时选择“宝安汽车站”
- 发布一条到北京的信息
- 在“深圳”里可以看到刚增加的信息
- 切换到“湖北武汉”，也可以看到这条信息
- 切换到“湖北武汉”，也可以看到这条信息
全部代码
unit U_city_manager;
interface
uses
System.SysUtils, System.Types, System.Classes, Generics.Collections;
type
TCounty = class
private
_Name: string;
_CityID: Integer;
public
constructor Create;
destructor Destroy; override;
property Name: string read _Name write _Name;
property CityID: Integer read _CityID write _CityID;
end;
TProvince = class;
TCity = class
private
_ID: Integer;
_Name: string;
_Code: Integer;
_TelCode: Integer;
_CountyList: Tlist<TCounty>;
Province: TProvince;
procedure clear_CountyList();
public
constructor Create;
destructor Destroy; override;
property CountyList: Tlist<TCounty> read _CountyList;
property ID: Integer read _ID write _ID;
property Name: string read _Name write _Name;
property Code: Integer read _Code write _Code;
property TelCode: Integer read _TelCode write _TelCode;
end;
TProvince = class
private
_ID: Integer;
_Name: string;
_CardCode: string;
_CityList: Tlist<TCity>;
procedure clear_CityList();
public
constructor Create;
destructor Destroy; override;
property CityList: Tlist<TCity> read _CityList;
property ID: Integer read _ID write _ID;
property Name: string read _Name write _Name;
property CardCode: string read _CardCode write _CardCode;
end;
TStation = class
private
_ProvinceName: string;
_CityID: Integer;
_CityName: string;
_Name: string;
_xian: string; // hfg 2016-07-23
_address_id: Integer;
public
constructor Create;
destructor Destroy; override;
property ProvinceName: string read _ProvinceName write _ProvinceName;
property CityID: Integer read _CityID write _CityID;
property CityName: string read _CityName write _CityName;
property Name: string read _Name write _Name;
property xian: string read _xian write _xian; // hfg 2016-07-23
property address_id: Integer read _address_id write _address_id;
end;
TStation_Path = class
private
_Station_Begin: TStation;
_Station_End: TStation;
_Mileage: Integer;
public
constructor Create;
destructor Destroy; override;
property Station_Begin: TStation read _Station_Begin write _Station_Begin;
property Station_End: TStation read _Station_End write _Station_End;
property Mileage: Integer read _Mileage write _Mileage;
end;
TStation_Path_Node = class;
TStation_Next = class
private
_Station_Node_Next: TStation_Path_Node;
_Mileage: Integer;
public
constructor Create;
destructor Destroy; override;
property Station_Node_Next: TStation_Path_Node read _Station_Node_Next
write _Station_Node_Next;
property Mileage: Integer read _Mileage write _Mileage;
end;
TStation_Path_Node = class
private
_Station: TStation;
_Next_Station: Tlist<TStation_Next>;
_Prior_Station: Tlist<TStation_Next>;
_is_on_path: boolean;
_is_end: boolean;
_step: Integer;
_Path_Prior_Station: TStation_Path_Node;
_path_mileage: Integer;
_is_before_end: boolean;
_end_Node: TStation_Path_Node;
_to_end_mileage: Integer;
procedure clear_Next_Station();
procedure clear_Prior_Station();
public
constructor Create;
destructor Destroy; override;
procedure add_next(next_node: TStation_Path_Node; Mileage: Integer);
procedure add_Prior(p_node: TStation_Path_Node; Mileage: Integer);
property Station: TStation read _Station write _Station;
property Next_Station: Tlist<TStation_Next> read _Next_Station
write _Next_Station;
property is_on_path: boolean read _is_on_path;
property is_end: boolean read _is_end;
property step: Integer read _step;
property path_mileage: Integer read _path_mileage write _path_mileage;
property Path_Prior_Station: TStation_Path_Node read _Path_Prior_Station
write _Path_Prior_Station;
property is_before_end: boolean read _is_before_end;
property to_end_mileage: Integer read _to_end_mileage write _to_end_mileage;
property end_Node: TStation_Path_Node read _end_Node;
procedure reset();
procedure set_Step(v: Integer);
procedure set_is_before_end();
end;
TR_Path = class
public
step: Integer;
Mileage: Integer;
StationList: Tlist<TStation>;
public
constructor Create;
destructor Destroy; override;
function get_txt(): string;
function get_txt_with_city(): string;
end;
TR_Manager = class
private
_ProvinceList: Tlist<TProvince>;
_Dict_Province: TDictionary<Integer, TProvince>;
_Dict_City: TDictionary<Integer, TCity>;
_Dict_City_Name: TDictionary<string, TCity>;
_StationList: Tlist<TStation>;
_Dict_Station: TDictionary<string, TStation>;
_Dict_CityID_Station: TDictionary<Integer, Tlist<TStation>>;
_Dict_CityID_Xian_Station
: TDictionary<Integer, TDictionary<string, Tlist<TStation>>>;
// hfg 2016-07-23
_StationPathList: Tlist<TStation_Path>;
_StationPathNodeList: Tlist<TStation_Path_Node>;
_Dict_Station_Path_Node: TDictionary<TStation, TStation_Path_Node>;
_Dict_CityID_Path_Node: TDictionary<Integer, Tlist<TStation_Path_Node>>;
_Node_Tmp: Tlist<TStation_Path_Node>;
_Node_Tmp_2: Tlist<TStation_Path_Node>;
_Node_Tmp_before_end: Tlist<TStation_Path_Node>;
_result_path: Tlist<TR_Path>;
procedure clear_result_path();
procedure clear_ProvinceList();
procedure clear_StationList();
procedure clear_StationPathList();
procedure clear_StationPathNodeList();
procedure clear_Dict_CityID_Xian_Station(); // hfg 2016-07-23
procedure make_StationPathNodeList();
public
constructor Create;
destructor Destroy; override;
property ProvinceList: Tlist<TProvince> read _ProvinceList;
property result_path: Tlist<TR_Path> read _result_path;
procedure load_Province(fn: string);
procedure load_Province_sl(sl: TStringList);
procedure load_City(fn: string);
procedure load_City_sl(sl: TStringList);
procedure load_County(fn: string);
procedure load_Path(fn: string);
procedure load_Path_new(fn: string);
procedure load_Path_new_sl(sl: TStringList); // 2016-10-03
procedure load_xian(fn: string); // hfg 2016-07-23
function get_Province_by_id(ID: Integer): TProvince;
function get_City_by_id(ID: Integer): TCity;
function get_City_by_name(ProvinceName, city_name: string): TCity;
function get_City_by_full_name(full_city_name: string): TCity;
function get_or_add_Station(ProvinceName, CityName, Name: string): TStation;
function get_or_add_Station_new(city_id, Name, xian: string): TStation;
procedure get_station_by_city_id(city_id: Integer;
var list: Tlist<TStation>);
procedure get_station_by_city_id_xian(city_id: Integer; xian: string;
var list: Tlist<TStation>); // hfg 2016-07-23
function get_path_quick(StationName_begin: string;
Station_End: Tlist<TStation>; max_step: Integer = 6;
allow_same_city: boolean = false): boolean;
function get_path_quick_ex(Station_Begin: Tlist<TStation>;
Station_End: Tlist<TStation>; max_step: Integer = 6;
allow_same_city: boolean = false): boolean; // 2016-10-01
function get_StationList: Tlist<TStation>;
procedure save_Station(fn: string);
property StationPathList: Tlist<TStation_Path> read _StationPathList;
end;
implementation
uses u_address_def;
function get_Province_ID_from_City_Code(v: Integer): Integer;
begin
Result := v div 100;
end;
function ComparePath_city(Item1, Item2: TR_Path): Integer;
begin
Result := Item1.StationList.Count - Item2.StationList.Count;
if Result = 0 then
Result := Item1.Mileage - Item2.Mileage;
end;
{ TR_Manager }
procedure TR_Manager.clear_Dict_CityID_Xian_Station; // hfg 2016-07-23
var
pair: TPair<Integer, TDictionary<string, Tlist<TStation>>>;
pair2: TPair<string, Tlist<TStation>>;
begin
for pair in _Dict_CityID_Xian_Station do
begin
for pair2 in pair.Value do
begin
pair2.Value.Free
end;
pair.Value.Free;
end;
_Dict_CityID_Xian_Station.Clear();
end;
procedure TR_Manager.clear_ProvinceList;
var
i: Integer;
begin
for i := 0 to _ProvinceList.Count - 1 do
_ProvinceList[i].Free;
_ProvinceList.Clear();
_Dict_Province.Clear();
_Dict_City.Clear();
_Dict_City_Name.Clear();
end;
procedure TR_Manager.clear_result_path;
var
i: Integer;
begin
for i := 0 to _result_path.Count - 1 do
_result_path[i].Free;
_result_path.Clear();
end;
procedure TR_Manager.clear_StationList;
var
i: Integer;
pair: TPair<Integer, Tlist<TStation>>;
begin
_Dict_Station.Clear();
for i := 0 to _StationList.Count - 1 do
_StationList[i].Free;
_StationList.Clear();
for pair in _Dict_CityID_Station do
begin
pair.Value.Free;
end;
_Dict_CityID_Station.Clear();
end;
procedure TR_Manager.clear_StationPathList;
var
i: Integer;
begin
for i := 0 to _StationPathList.Count - 1 do
_StationPathList[i].Free;
_StationPathList.Clear();
end;
procedure TR_Manager.clear_StationPathNodeList;
var
i: Integer;
pair: TPair<Integer, Tlist<TStation_Path_Node>>;
begin
_Dict_Station_Path_Node.Clear();
for pair in _Dict_CityID_Path_Node do
begin
pair.Value.Free;
end;
_Dict_CityID_Path_Node.Clear();
for i := 0 to _StationPathNodeList.Count - 1 do
_StationPathNodeList[i].Free;
_StationPathNodeList.Clear();
end;
constructor TR_Manager.Create;
begin
_result_path := Tlist<TR_Path>.Create;
_Dict_Province := TDictionary<Integer, TProvince>.Create();
_Dict_City := TDictionary<Integer, TCity>.Create();
_Dict_City_Name := TDictionary<string, TCity>.Create();
_ProvinceList := Tlist<TProvince>.Create();
_StationList := Tlist<TStation>.Create();
_Dict_Station := TDictionary<string, TStation>.Create();
_StationPathList := Tlist<TStation_Path>.Create();
_Dict_CityID_Station := TDictionary < Integer, Tlist < TStation >>.Create();
_Dict_CityID_Xian_Station := TDictionary < Integer, TDictionary < string,
Tlist<TStation> >>.Create(); // hfg 2016-07-23
_StationPathNodeList := Tlist<TStation_Path_Node>.Create();
_Dict_Station_Path_Node := TDictionary<TStation, TStation_Path_Node>.Create();
_Dict_CityID_Path_Node := TDictionary < Integer, Tlist < TStation_Path_Node
>>.Create();
_Node_Tmp := Tlist<TStation_Path_Node>.Create();
_Node_Tmp_2 := Tlist<TStation_Path_Node>.Create();
_Node_Tmp_before_end := Tlist<TStation_Path_Node>.Create();
end;
destructor TR_Manager.Destroy;
begin
clear_result_path();
FreeAndNil(_result_path);
clear_ProvinceList();
FreeAndNil(_ProvinceList);
FreeAndNil(_Dict_Province);
FreeAndNil(_Dict_City);
FreeAndNil(_Dict_City_Name);
clear_StationList();
FreeAndNil(_StationList);
FreeAndNil(_Dict_Station);
clear_StationPathList();
FreeAndNil(_StationPathList);
clear_StationPathNodeList();
FreeAndNil(_StationPathNodeList);
FreeAndNil(_Node_Tmp);
FreeAndNil(_Node_Tmp_2);
FreeAndNil(_Node_Tmp_before_end);
clear_Dict_CityID_Xian_Station(); // hfg 2016-07-23
FreeAndNil(_Dict_CityID_Xian_Station); // hfg 2016-07-23
inherited;
end;
function TR_Manager.get_City_by_full_name(full_city_name: string): TCity;
begin
if not _Dict_City_Name.TryGetValue(full_city_name, Result) then
Result := nil;
end;
function TR_Manager.get_City_by_id(ID: Integer): TCity;
begin
if not _Dict_City.TryGetValue(ID, Result) then
Result := nil;
end;
function TR_Manager.get_City_by_name(ProvinceName, city_name: string): TCity;
begin
if not _Dict_City_Name.TryGetValue(ProvinceName + city_name, Result) then
Result := nil;
end;
function TR_Manager.get_or_add_Station(ProvinceName, CityName, Name: string)
: TStation;
var
city: TCity;
Station: TStation;
CityID: Integer;
l: Tlist<TStation>;
begin
Result := nil;
if _Dict_Station.TryGetValue(Name, Result) then
exit;
if _Dict_City_Name.TryGetValue(ProvinceName + CityName, city) then
CityID := city.ID
else
begin
CityID := 9999999;
exit;
end;
Station := TStation.Create;
Station.ProvinceName := ProvinceName;
Station.CityID := CityID;
Station.CityName := CityName;
Station.Name := Name;
_StationList.Add(Station);
_Dict_Station.AddOrSetValue(Station.Name, Station);
if (not _Dict_CityID_Station.TryGetValue(CityID, l)) then
begin
l := Tlist<TStation>.Create();
_Dict_CityID_Station.AddOrSetValue(CityID, l);
end;
l.Add(Station);
Result := Station;
end;
function TR_Manager.get_or_add_Station_new(city_id, Name, xian: string)
: TStation;
var
city: TCity;
Station: TStation;
CityID: Integer;
l: Tlist<TStation>;
begin
Result := nil;
if _Dict_Station.TryGetValue(Name, Result) then
exit;
CityID := strtointdef(city_id, 9999999);
city := get_City_by_id(CityID);
if city = nil then
exit;
Station := TStation.Create;
Station.ProvinceName := city.Province._Name;
Station.CityID := CityID;
Station.CityName := city.Name;
Station.Name := Name;
Station.xian := xian;
Station.address_id := get_city_xian_id(CityID, xian);
_StationList.Add(Station);
_Dict_Station.AddOrSetValue(Station.Name, Station);
if (not _Dict_CityID_Station.TryGetValue(CityID, l)) then
begin
l := Tlist<TStation>.Create();
_Dict_CityID_Station.AddOrSetValue(CityID, l);
end;
l.Add(Station);
Result := Station;
end;
function TR_Manager.get_path_quick(StationName_begin: string;
Station_End: Tlist<TStation>; max_step: Integer = 6;
allow_same_city: boolean = false): boolean;
var
Station: TStation;
node_root, node, node_next: TStation_Path_Node;
i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,
Node_Tmp_before_end_count: Integer;
path: TR_Path;
list: Tlist;
city_station_list: Tlist<TStation_Path_Node>;
begin
Result := false;
clear_result_path();
if Station_End = nil then
exit;
if Station_End.Count <= 0 then
exit;
if not(_Dict_Station.TryGetValue(StationName_begin, Station)) then
exit;
if Station.CityID = Station_End[0].CityID then
begin
path := TR_Path.Create;
path.Mileage := 0;
path.step := 1;
path.StationList.Add(Station);
for i := 0 to Station_End.Count - 1 do
begin
if Station_End[i].Name <> Station.Name then
begin
path.StationList.Add(Station_End[i]);
Break;
end;
end;
if path.StationList.Count < 2 then
path.StationList.Add(Station);
_result_path.Add(path);
end;
if not(_Dict_Station_Path_Node.TryGetValue(Station, node_root)) then
exit;
for i := 0 to _StationPathNodeList.Count - 1 do
_StationPathNodeList[i].reset();
node_root.set_Step(0);
_Node_Tmp[0] := node_root;
Node_Tmp_Count := 1;
Node_Tmp_before_end_count := 0;
for i := 0 to Station_End.Count - 1 do
begin
if _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) then
node.set_is_before_end();
end;
for step := 1 to max_step do
begin
Node_Tmp_2_Count := 0;
for i := 0 to Node_Tmp_Count - 1 do
begin
try
node := _Node_Tmp[i];
if (node.is_before_end) then
begin
_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;
inc(Node_Tmp_before_end_count);
if step > 1 then
Continue;
end;
for k := 0 to node.Next_Station.Count - 1 do
begin
node_next := node.Next_Station[k].Station_Node_Next;
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end
else
begin
if (node_next.step = step) and (step > 1) then
begin
if node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileage
then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
end;
end;
end;
end;
if allow_same_city then
begin
if _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,
city_station_list) then
begin
for k := 0 to city_station_list.Count - 1 do
begin
node_next := city_station_list[k];
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + 0;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end;
end;
end;
end;
except
Node_Tmp_2_Count := Node_Tmp_2_Count - 1;
end;
end;
Node_Tmp_Count := 0;
for i := 0 to Node_Tmp_2_Count - 1 do
begin
if _Node_Tmp_2[i].is_on_path then
begin
if True then
if Node_Tmp_Count < _Node_Tmp.Count then
_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]
else
_Node_Tmp.Add(_Node_Tmp_2[i]);
inc(Node_Tmp_Count);
end;
end;
end;
list := Tlist.Create();
for i := 0 to Node_Tmp_before_end_count - 1 do
begin
path := TR_Path.Create;
node := _Node_Tmp_before_end[i];
path.Mileage := node.path_mileage + node.to_end_mileage;
path.StationList.Add(node.end_Node.Station);
path.StationList.Add(node.Station);
node_next := node.Path_Prior_Station;
for step := 1 to max_step + 1 do
begin
if node_next = nil then
Break;
path.StationList.Add(node_next.Station);
if node_next.step <= 0 then
Break;
node_next := node_next.Path_Prior_Station
end;
path.StationList.Reverse();
list.Add(path);
end;
list.Sort(@ComparePath_city);
for i := 0 to list.Count - 1 do
_result_path.Add(list[i]);
FreeAndNil(list);
Result := _result_path.Count > 0;
end;
function TR_Manager.get_path_quick_ex(Station_Begin,
Station_End: Tlist<TStation>; max_step: Integer;
allow_same_city: boolean): boolean;
var
Station: TStation;
node_root, node, node_next: TStation_Path_Node;
m, i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,
Node_Tmp_before_end_count: Integer;
path: TR_Path;
list: Tlist;
city_station_list: Tlist<TStation_Path_Node>;
begin
Result := false;
clear_result_path();
if Station_Begin = nil then
exit;
if Station_Begin.Count <= 0 then
exit;
if Station_End = nil then
exit;
if Station_End.Count <= 0 then
exit;
for m := 0 to Station_Begin.Count - 1 do
begin
Station := Station_Begin[m];
if Station.CityID = Station_End[0].CityID then
begin
path := TR_Path.Create;
path.Mileage := 0;
path.step := 1;
path.StationList.Add(Station);
for i := 0 to Station_End.Count - 1 do
begin
if Station_End[i].Name <> Station.Name then
begin
path.StationList.Add(Station_End[i]);
Break;
end;
end;
if path.StationList.Count < 2 then
path.StationList.Add(Station);
_result_path.Add(path);
end;
end;
for i := 0 to _StationPathNodeList.Count - 1 do
_StationPathNodeList[i].reset();
Node_Tmp_Count := 0;
for m := 0 to Station_Begin.Count - 1 do
begin
Station := Station_Begin[m];
if (_Dict_Station_Path_Node.TryGetValue(Station, node_root)) then
begin
_Node_Tmp[Node_Tmp_Count] := node_root;
node_root.set_Step(0);
Node_Tmp_Count := Node_Tmp_Count + 1;
end;
end;
if Node_Tmp_Count = 0 then
exit;
Node_Tmp_before_end_count := 0;
for i := 0 to Station_End.Count - 1 do
begin
if _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) then
node.set_is_before_end();
end;
for step := 1 to max_step do
begin
Node_Tmp_2_Count := 0;
for i := 0 to Node_Tmp_Count - 1 do
begin
try
node := _Node_Tmp[i];
if (node.is_before_end) then
begin
_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;
inc(Node_Tmp_before_end_count);
if step > 1 then
Continue;
end;
for k := 0 to node.Next_Station.Count - 1 do
begin
node_next := node.Next_Station[k].Station_Node_Next;
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end
else
begin
if (node_next.step = step) and (step > 1) then
begin
if node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileage
then
begin
node_next.path_mileage := node.path_mileage + node.Next_Station
[k].Mileage;
node_next.Path_Prior_Station := node;
end;
end;
end;
end;
if allow_same_city then
begin
if _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,
city_station_list) then
begin
for k := 0 to city_station_list.Count - 1 do
begin
node_next := city_station_list[k];
if node_next.is_end then
Continue;
if not node_next.is_on_path then
begin
node_next.path_mileage := node.path_mileage + 0;
node_next.Path_Prior_Station := node;
node_next.set_Step(step);
if Node_Tmp_2_Count < _Node_Tmp_2.Count then
_Node_Tmp_2[Node_Tmp_2_Count] := node_next
else
_Node_Tmp_2.Add(node_next);
inc(Node_Tmp_2_Count);
end;
end;
end;
end;
except
Node_Tmp_2_Count := Node_Tmp_2_Count - 1;
end;
end;
Node_Tmp_Count := 0;
for i := 0 to Node_Tmp_2_Count - 1 do
begin
if _Node_Tmp_2[i].is_on_path then
begin
if True then
if Node_Tmp_Count < _Node_Tmp.Count then
_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]
else
_Node_Tmp.Add(_Node_Tmp_2[i]);
inc(Node_Tmp_Count);
end;
end;
end;
list := Tlist.Create();
for i := 0 to Node_Tmp_before_end_count - 1 do
begin
path := TR_Path.Create;
node := _Node_Tmp_before_end[i];
path.Mileage := node.path_mileage + node.to_end_mileage;
path.StationList.Add(node.end_Node.Station);
path.StationList.Add(node.Station);
node_next := node.Path_Prior_Station;
for step := 1 to max_step + 1 do
begin
if node_next = nil then
Break;
path.StationList.Add(node_next.Station);
if node_next.step <= 0 then
Break;
node_next := node_next.Path_Prior_Station
end;
path.StationList.Reverse();
list.Add(path);
end;
list.Sort(@ComparePath_city);
for i := 0 to list.Count - 1 do
_result_path.Add(list[i]);
FreeAndNil(list);
Result := _result_path.Count > 0;
end;
function TR_Manager.get_Province_by_id(ID: Integer): TProvince;
begin
if not _Dict_Province.TryGetValue(ID, Result) then
Result := nil;
end;
function TR_Manager.get_StationList: Tlist<TStation>;
begin
Result := _StationList;
end;
procedure TR_Manager.get_station_by_city_id(city_id: Integer;
var list: Tlist<TStation>);
begin
if not(_Dict_CityID_Station.TryGetValue(city_id, list)) then
list := nil;
end;
procedure TR_Manager.get_station_by_city_id_xian(city_id: Integer; xian: string;
var list: Tlist<TStation>); // hfg 2016-07-23
var
dict: TDictionary<string, Tlist<TStation>>;
begin
if not _Dict_CityID_Xian_Station.TryGetValue(city_id, dict) then
begin
list := nil;
exit;
end;
if not dict.TryGetValue(xian, list) then
begin
list := nil;
exit;
end;
end;
procedure TR_Manager.load_City(fn: string);
var
sl: TStringList;
begin
sl := TStringList.Create;
sl.LoadFromFile(fn);
load_City_sl(sl);
FreeAndNil(sl);
end;
procedure TR_Manager.load_City_sl(sl: TStringList);
var
i, pid: Integer;
ss: TArray<String>;
c: TCity;
p: TProvince;
begin
_Dict_City.Clear();
_Dict_City_Name.Clear();
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 3 then
begin
c := TCity.Create;
c.ID := strtointdef(ss[0], 0);
c.Name := ss[1];
if length(ss) = 4 then
begin
c.Code := strtointdef(ss[2], 0);
c.TelCode := strtointdef(ss[3], 0);
pid := get_Province_ID_from_City_Code(c.Code);
end
else
begin
pid := strtointdef(ss[2], 0);
end;
p := get_Province_by_id(pid);
if p <> nil then
begin
p.CityList.Add(c);
_Dict_City.AddOrSetValue(c.ID, c);
_Dict_City_Name.AddOrSetValue(p.Name + c.Name, c);
end;
c.Province := p;
end;
SetLength(ss, 0);
end;
end;
procedure TR_Manager.load_County(fn: string);
var
i, pid: Integer;
sl: TStringList;
ss: TArray<String>;
city: TCity;
county: TCounty;
begin
sl := TStringList.Create;
sl.LoadFromFile(fn);
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 2 then
begin
county := TCounty.Create;
county.CityID := strtointdef(ss[0], 0);
county.Name := ss[1];
city := get_City_by_id(pid);
if city <> nil then
begin
city.CountyList.Add(county);
end;
end;
SetLength(ss, 0);
end;
FreeAndNil(sl);
end;
procedure TR_Manager.load_Path(fn: string);
var
i, m: Integer;
sl: TStringList;
ss: TArray<String>;
s_begin, s_end: TStation;
sp: TStation_Path;
begin
clear_StationList;
clear_StationPathList;
sl := TStringList.Create;
sl.LoadFromFile(fn);
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 5 then
begin
get_or_add_Station(ss[0], ss[1], ss[2]);
end;
SetLength(ss, 0);
end;
sl.LoadFromFile(fn);
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 5 then
begin
if (_Dict_Station.TryGetValue(ss[2], s_begin)) and
(_Dict_Station.TryGetValue(ss[5], s_end)) then
begin
m := Round(strtointdef(ss[3], 0));
if m > 0 then
begin
sp := TStation_Path.Create;
sp.Station_Begin := s_begin;
sp.Station_End := s_end;
sp.Mileage := m;
_StationPathList.Add(sp);
end
else
begin
end;
end
else
begin
end;
end;
SetLength(ss, 0);
end;
FreeAndNil(sl);
make_StationPathNodeList();
end;
procedure TR_Manager.load_Path_new(fn: string);
var
sl: TStringList;
begin
// 2016-10-03
sl := TStringList.Create;
sl.LoadFromFile(fn);
load_Path_new_sl(sl);
FreeAndNil(sl);
end;
procedure TR_Manager.load_Path_new_sl(sl: TStringList);
var
i, m: Integer;
ss: TArray<String>;
s_begin, s_end: TStation;
sp: TStation_Path;
begin
// 2016-10-03
clear_StationList;
clear_StationPathList;
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 6 then
begin
get_or_add_Station_new(ss[0], ss[1], ss[2]);
end;
SetLength(ss, 0);
end;
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 5 then
begin
if (_Dict_Station.TryGetValue(ss[1], s_begin)) and
(_Dict_Station.TryGetValue(ss[5], s_end)) then
begin
m := Round(strtointdef(ss[3], 0));
if m > 0 then
begin
sp := TStation_Path.Create;
sp.Station_Begin := s_begin;
sp.Station_End := s_end;
sp.Mileage := m;
_StationPathList.Add(sp);
end
else
begin
end;
end
else
begin
end;
end;
SetLength(ss, 0);
end;
make_StationPathNodeList();
end;
procedure TR_Manager.load_Province(fn: string);
var
sl: TStringList;
begin
sl := TStringList.Create;
sl.LoadFromFile(fn);
load_Province_sl(sl);
FreeAndNil(sl);
end;
procedure TR_Manager.load_Province_sl(sl: TStringList);
var
i: Integer;
ss: TArray<String>;
p: TProvince;
begin
clear_ProvinceList();
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) < 0 then
Continue;
if length(ss) >= 2 then
begin
p := TProvince.Create;
p.ID := strtointdef(ss[0], 0);
p.Name := ss[1];
if length(ss) >= 3 then
p.CardCode := ss[2];
_ProvinceList.Add(p);
_Dict_Province.AddOrSetValue(p.ID, p);
end;
SetLength(ss, 0);
end;
end;
procedure TR_Manager.load_xian(fn: string); // hfg 2016-07-23
var
i: Integer;
sl: TStringList;
ss: TArray<String>;
Station: TStation;
dict: TDictionary<string, Tlist<TStation>>;
list: Tlist<TStation>;
pair: TPair<string, TStation>;
procedure set_xian(v: string);
begin
if Station.xian = '' then
Station.xian := v;
end;
begin
clear_Dict_CityID_Xian_Station();
sl := TStringList.Create;
sl.LoadFromFile(fn);
sl.LoadFromFile(fn);
for i := 0 to sl.Count - 1 do
begin
ss := sl[i].Split([#9]);
if length(ss) = 2 then
begin
if _Dict_Station.TryGetValue(ss[0], Station) then
begin
set_xian(ss[1]);
end;
end;
SetLength(ss, 0);
end;
for pair in _Dict_Station do
begin
Station := pair.Value;
if Station.xian <> '' then
begin
if not _Dict_CityID_Xian_Station.TryGetValue(Station.CityID, dict) then
begin
dict := TDictionary < string, Tlist < TStation >> .Create();
_Dict_CityID_Xian_Station.AddOrSetValue(Station.CityID, dict);
end;
if not dict.TryGetValue(Station.xian, list) then
begin
list := Tlist<TStation>.Create();
dict.AddOrSetValue(Station.xian, list);
end;
list.Add(Station);
end;
end;
FreeAndNil(sl);
end;
procedure TR_Manager.make_StationPathNodeList;
var
i, cid: Integer;
p, p2: TStation_Path_Node;
c_list: Tlist<TStation_Path_Node>;
begin
_Node_Tmp.Clear();
clear_StationPathNodeList();
for i := 0 to _StationList.Count - 1 do
begin
p := TStation_Path_Node.Create;
p.Station := _StationList[i];
_Dict_Station_Path_Node.AddOrSetValue(p.Station, p);
_StationPathNodeList.Add(p);
_Node_Tmp.Add(nil);
_Node_Tmp_2.Add(nil);
_Node_Tmp_before_end.Add(nil);
cid := _StationList[i].CityID;
if not _Dict_CityID_Path_Node.TryGetValue(cid, c_list) then
begin
c_list := Tlist<TStation_Path_Node>.Create;
_Dict_CityID_Path_Node.AddOrSetValue(cid, c_list);
end;
c_list.Add(p);
end;
for i := 0 to _StationPathList.Count - 1 do
begin
if (_Dict_Station_Path_Node.TryGetValue(_StationPathList[i].Station_Begin,
p)) and (_Dict_Station_Path_Node.TryGetValue(_StationPathList[i]
.Station_End, p2)) then
begin
p.add_next(p2, _StationPathList[i].Mileage);
p2.add_Prior(p, _StationPathList[i].Mileage);
end;
end;
end;
procedure TR_Manager.save_Station(fn: string);
var
i: Integer;
sl: TStringList;
s: string;
Station: TStation;
begin
sl := TStringList.Create;
for i := 0 to _StationList.Count - 1 do
begin
Station := _StationList[i];
if i = 0 then
s := 'select ' + Station.CityID.ToString() + ' as CityID,' +
QuotedStr(Station.Name) + ' as station'
else
s := 'union select ' + Station.CityID.ToString() + ',' +
QuotedStr(Station.Name);
sl.Add(s);
end;
sl.SaveToFile(fn);
end;
{ TProvince }
procedure TProvince.clear_CityList;
var
i: Integer;
begin
for i := 0 to _CityList.Count - 1 do
_CityList[i].Free;
_CityList.Clear();
end;
constructor TProvince.Create;
begin
_CityList := Tlist<TCity>.Create();
end;
destructor TProvince.Destroy;
begin
clear_CityList();
FreeAndNil(_CityList);
inherited;
end;
{ TCity }
procedure TCity.clear_CountyList;
var
i: Integer;
begin
for i := 0 to _CountyList.Count - 1 do
_CountyList[i].Free;
_CountyList.Clear();
end;
constructor TCity.Create;
begin
_CountyList := Tlist<TCounty>.Create();
end;
destructor TCity.Destroy;
begin
clear_CountyList();
FreeAndNil(_CountyList);
inherited;
end;
{ TCounty }
constructor TCounty.Create;
begin
//
end;
destructor TCounty.Destroy;
begin
inherited;
end;
{ TStation }
constructor TStation.Create;
begin
//
end;
destructor TStation.Destroy;
begin
inherited;
end;
{ TStation_Path }
constructor TStation_Path.Create;
begin
//
end;
destructor TStation_Path.Destroy;
begin
inherited;
end;
{ TStation_Path_Node }
procedure TStation_Path_Node.add_next(next_node: TStation_Path_Node;
Mileage: Integer);
var
n: TStation_Next;
begin
n := TStation_Next.Create;
n.Station_Node_Next := next_node;
n.Mileage := Mileage;
_Next_Station.Add(n);
end;
procedure TStation_Path_Node.add_Prior(p_node: TStation_Path_Node;
Mileage: Integer);
var
n: TStation_Next;
begin
n := TStation_Next.Create;
n.Station_Node_Next := p_node;
n.Mileage := Mileage;
_Prior_Station.Add(n);
end;
procedure TStation_Path_Node.clear_Next_Station;
var
i: Integer;
begin
for i := 0 to _Next_Station.Count - 1 do
_Next_Station[i].Free;
_Next_Station.Clear;
end;
procedure TStation_Path_Node.clear_Prior_Station;
var
i: Integer;
begin
for i := 0 to _Prior_Station.Count - 1 do
_Prior_Station[i].Free;
_Prior_Station.Clear;
end;
constructor TStation_Path_Node.Create;
begin
_path_mileage := 0;
_is_on_path := false;
_step := -1;
_Next_Station := Tlist<TStation_Next>.Create();
_Prior_Station := Tlist<TStation_Next>.Create();
end;
destructor TStation_Path_Node.Destroy;
begin
clear_Next_Station();
FreeAndNil(_Next_Station);
clear_Prior_Station();
FreeAndNil(_Prior_Station);
inherited;
end;
procedure TStation_Path_Node.reset;
begin
_is_on_path := false;
_is_end := false;
_step := -1;
_is_before_end := false;
_path_mileage := 0;
_Path_Prior_Station := nil;
end;
procedure TStation_Path_Node.set_is_before_end;
var
i: Integer;
begin
_is_end := True;
for i := 0 to _Prior_Station.Count - 1 do
begin
if (_Prior_Station[i].Station_Node_Next.is_before_end) then
if _Prior_Station[i].Station_Node_Next._to_end_mileage < _Prior_Station[i]
._Mileage then
Continue;
_Prior_Station[i].Station_Node_Next._is_before_end := True;
_Prior_Station[i].Station_Node_Next._end_Node := self;
_Prior_Station[i].Station_Node_Next._to_end_mileage :=
_Prior_Station[i]._Mileage;
end;
end;
procedure TStation_Path_Node.set_Step(v: Integer);
begin
_step := v;
_is_on_path := True;
end;
{ TStation_Next }
constructor TStation_Next.Create;
begin
//
end;
destructor TStation_Next.Destroy;
begin
inherited;
end;
{ TR_Path }
constructor TR_Path.Create;
begin
StationList := Tlist<TStation>.Create();
end;
destructor TR_Path.Destroy;
begin
FreeAndNil(StationList);
inherited;
end;
function TR_Path.get_txt: string;
var
i: Integer;
begin
Result := '';
for i := 0 to StationList.Count - 1 do
begin
if i > 0 then
Result := Result + ' -> ';
Result := Result + StationList[i].Name;
end;
Result := Result + ' (' + IntToStr(Mileage) + ')'
end;
function TR_Path.get_txt_with_city: string;
var
i: Integer;
begin
Result := '';
for i := 0 to StationList.Count - 1 do
begin
if i > 0 then
Result := Result + '>';
Result := Result + StationList[i].CityID.ToString() + '|' +
StationList[i].Name;
end;
Result := Result + ':' + IntToStr(Mileage)
end;
end.