diff options
author | fonsinchen <fonsinchen@openttd.org> | 2013-06-09 13:01:23 +0000 |
---|---|---|
committer | fonsinchen <fonsinchen@openttd.org> | 2013-06-09 13:01:23 +0000 |
commit | 575cabe90a56a23fa13ca24962b12a4ff2216386 (patch) | |
tree | b0ac380fa899cfaf13cece03d08c19ac647074c1 | |
parent | 9824d53d6a7d96e0a7182fa5bae5c05218b6a730 (diff) | |
download | openttd-575cabe90a56a23fa13ca24962b12a4ff2216386.tar.xz |
(svn r25357) -Add: flow mapper for link graph
-rw-r--r-- | projects/openttd_vs100.vcxproj | 2 | ||||
-rw-r--r-- | projects/openttd_vs100.vcxproj.filters | 6 | ||||
-rw-r--r-- | projects/openttd_vs80.vcproj | 8 | ||||
-rw-r--r-- | projects/openttd_vs90.vcproj | 8 | ||||
-rw-r--r-- | source.list | 2 | ||||
-rw-r--r-- | src/linkgraph/flowmapper.cpp | 62 | ||||
-rw-r--r-- | src/linkgraph/flowmapper.h | 34 | ||||
-rw-r--r-- | src/linkgraph/linkgraphschedule.cpp | 5 | ||||
-rw-r--r-- | src/linkgraph/linkgraphschedule.h | 2 |
9 files changed, 127 insertions, 2 deletions
diff --git a/projects/openttd_vs100.vcxproj b/projects/openttd_vs100.vcxproj index fcfb2e61e..48b6a7078 100644 --- a/projects/openttd_vs100.vcxproj +++ b/projects/openttd_vs100.vcxproj @@ -332,6 +332,7 @@ <ClCompile Include="..\src\ini_load.cpp" /> <ClCompile Include="..\src\landscape.cpp" /> <ClCompile Include="..\src\linkgraph\demands.cpp" /> + <ClCompile Include="..\src\linkgraph\flowmapper.cpp" /> <ClCompile Include="..\src\linkgraph\linkgraph.cpp" /> <ClCompile Include="..\src\linkgraph\linkgraphjob.cpp" /> <ClCompile Include="..\src\linkgraph\linkgraphschedule.cpp" /> @@ -476,6 +477,7 @@ <ClInclude Include="..\src\landscape_type.h" /> <ClInclude Include="..\src\language.h" /> <ClInclude Include="..\src\linkgraph\demands.h" /> + <ClInclude Include="..\src\linkgraph\flowmapper.h" /> <ClInclude Include="..\src\linkgraph\init.h" /> <ClInclude Include="..\src\linkgraph\linkgraph.h" /> <ClInclude Include="..\src\linkgraph\linkgraph_base.h" /> diff --git a/projects/openttd_vs100.vcxproj.filters b/projects/openttd_vs100.vcxproj.filters index 23806dfaf..f049a2777 100644 --- a/projects/openttd_vs100.vcxproj.filters +++ b/projects/openttd_vs100.vcxproj.filters @@ -225,6 +225,9 @@ <ClCompile Include="..\src\linkgraph\demands.cpp"> <Filter>Source Files</Filter> </ClCompile> + <ClCompile Include="..\src\linkgraph\flowmapper.cpp"> + <Filter>Source Files</Filter> + </ClCompile> <ClCompile Include="..\src\linkgraph\linkgraph.cpp"> <Filter>Source Files</Filter> </ClCompile> @@ -657,6 +660,9 @@ <ClInclude Include="..\src\linkgraph\demands.h"> <Filter>Header Files</Filter> </ClInclude> + <ClInclude Include="..\src\linkgraph\flowmapper.h"> + <Filter>Header Files</Filter> + </ClInclude> <ClInclude Include="..\src\linkgraph\init.h"> <Filter>Header Files</Filter> </ClInclude> diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj index 3cf722b02..36f89adf7 100644 --- a/projects/openttd_vs80.vcproj +++ b/projects/openttd_vs80.vcproj @@ -599,6 +599,10 @@ > </File> <File + RelativePath=".\..\src\linkgraph\flowmapper.cpp" + > + </File> + <File RelativePath=".\..\src\linkgraph\linkgraph.cpp" > </File> @@ -1179,6 +1183,10 @@ > </File> <File + RelativePath=".\..\src\linkgraph\flowmapper.h" + > + </File> + <File RelativePath=".\..\src\linkgraph\init.h" > </File> diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj index 040ee9154..286b5b720 100644 --- a/projects/openttd_vs90.vcproj +++ b/projects/openttd_vs90.vcproj @@ -596,6 +596,10 @@ > </File> <File + RelativePath=".\..\src\linkgraph\flowmapper.cpp" + > + </File> + <File RelativePath=".\..\src\linkgraph\linkgraph.cpp" > </File> @@ -1176,6 +1180,10 @@ > </File> <File + RelativePath=".\..\src\linkgraph\flowmapper.h" + > + </File> + <File RelativePath=".\..\src\linkgraph\init.h" > </File> diff --git a/source.list b/source.list index 01d4d1f02..0fc1b1909 100644 --- a/source.list +++ b/source.list @@ -40,6 +40,7 @@ ini.cpp ini_load.cpp landscape.cpp linkgraph/demands.cpp +linkgraph/flowmapper.cpp linkgraph/linkgraph.cpp linkgraph/linkgraphjob.cpp linkgraph/linkgraphschedule.cpp @@ -209,6 +210,7 @@ landscape.h landscape_type.h language.h linkgraph/demands.h +linkgraph/flowmapper.h linkgraph/init.h linkgraph/linkgraph.h linkgraph/linkgraph_base.h diff --git a/src/linkgraph/flowmapper.cpp b/src/linkgraph/flowmapper.cpp new file mode 100644 index 000000000..70779e8ec --- /dev/null +++ b/src/linkgraph/flowmapper.cpp @@ -0,0 +1,62 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2. + * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>. + */ + +/** @file flowmapper.cpp Definition of flowmapper. */ + +#include "../stdafx.h" +#include "flowmapper.h" + +/** + * Map the paths generated by the MCF solver into flows associated with nodes. + * @param component the link graph component to be used. + */ +void FlowMapper::Run(LinkGraphJob &job) const +{ + /* Time the graph has been running without being compressed. */ + uint runtime = job.JoinDate() - job.Settings().recalc_time - job.LastCompression(); + + for (NodeID node_id = 0; node_id < job.Size(); ++node_id) { + Node prev_node = job[node_id]; + StationID prev = prev_node.Station(); + PathList &paths = prev_node.Paths(); + for (PathList::iterator i = paths.begin(); i != paths.end(); ++i) { + Path *path = *i; + uint flow = path->GetFlow(); + if (flow == 0) continue; + /* compress to monthly value */ + flow = max(1U, flow * 30 / runtime); + Node node = job[path->GetNode()]; + StationID via = node.Station(); + StationID origin = job[path->GetOrigin()].Station(); + assert(prev != via && via != origin); + /* Mark all of the flow for local consumption at "first". */ + node.Flows().AddFlow(origin, via, flow); + if (prev != origin) { + /* Pass some of the flow marked for local consumption at "prev" on + * to this node. */ + prev_node.Flows().PassOnFlow(origin, via, flow); + } else { + /* Prev node is origin. Simply add flow. */ + prev_node.Flows().AddFlow(origin, via, flow); + } + } + } + + for (NodeID node_id = 0; node_id < job.Size(); ++node_id) { + /* Remove local consumption shares marked as invalid. */ + Node node = job[node_id]; + node.Flows().FinalizeLocalConsumption(node.Station()); + /* Clear paths. */ + PathList &paths = node.Paths(); + for (PathList::iterator i = paths.begin(); i != paths.end(); ++i) { + delete *i; + } + paths.clear(); + } +} diff --git a/src/linkgraph/flowmapper.h b/src/linkgraph/flowmapper.h new file mode 100644 index 000000000..6dc84ffea --- /dev/null +++ b/src/linkgraph/flowmapper.h @@ -0,0 +1,34 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2. + * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>. + */ + +/** @file flowmapper.h Declaration of flow mapper; maps paths into flows at nodes. */ + +#ifndef FLOWMAPPER_H_ +#define FLOWMAPPER_H_ + +#include "linkgraphjob_base.h" + +/** + * Map the path trees generated by the MCF solver into flows. The path tree is + * useful to cache capacities and distances and allow quick disconnecting and + * reconnecting to other paths. The flows show how much cargo from which nodes + * is to be routed in which direction at a given node. This is what we need in + * the end. + */ +class FlowMapper : public ComponentHandler { +public: + virtual void Run(LinkGraphJob &job) const; + + /** + * Virtual destructor has to be defined because of virtual Run(). + */ + virtual ~FlowMapper() {} +}; + +#endif /* FLOWMAPPER_H_ */ diff --git a/src/linkgraph/linkgraphschedule.cpp b/src/linkgraph/linkgraphschedule.cpp index 2cb291853..7e2c66f8f 100644 --- a/src/linkgraph/linkgraphschedule.cpp +++ b/src/linkgraph/linkgraphschedule.cpp @@ -14,6 +14,7 @@ #include "init.h" #include "demands.h" #include "mcf.h" +#include "flowmapper.h" /** * Spawn a thread if possible and run the link graph job in the thread. If @@ -132,7 +133,9 @@ LinkGraphSchedule::LinkGraphSchedule() this->handlers[0] = new InitHandler; this->handlers[1] = new DemandHandler; this->handlers[2] = new MCFHandler<MCF1stPass>; - this->handlers[3] = new MCFHandler<MCF2ndPass>; + this->handlers[3] = new FlowMapper; + this->handlers[4] = new MCFHandler<MCF2ndPass>; + this->handlers[5] = new FlowMapper; } /** diff --git a/src/linkgraph/linkgraphschedule.h b/src/linkgraph/linkgraphschedule.h index f099f062b..911fa389a 100644 --- a/src/linkgraph/linkgraphschedule.h +++ b/src/linkgraph/linkgraphschedule.h @@ -44,7 +44,7 @@ private: friend const SaveLoad *GetLinkGraphScheduleDesc(); protected: - ComponentHandler *handlers[4]; ///< Handlers to be run for each job. + ComponentHandler *handlers[6]; ///< Handlers to be run for each job. GraphList schedule; ///< Queue for new jobs. JobList running; ///< Currently running jobs. |