summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorfonsinchen <fonsinchen@openttd.org>2013-06-09 13:01:23 +0000
committerfonsinchen <fonsinchen@openttd.org>2013-06-09 13:01:23 +0000
commit575cabe90a56a23fa13ca24962b12a4ff2216386 (patch)
treeb0ac380fa899cfaf13cece03d08c19ac647074c1
parent9824d53d6a7d96e0a7182fa5bae5c05218b6a730 (diff)
downloadopenttd-575cabe90a56a23fa13ca24962b12a4ff2216386.tar.xz
(svn r25357) -Add: flow mapper for link graph
-rw-r--r--projects/openttd_vs100.vcxproj2
-rw-r--r--projects/openttd_vs100.vcxproj.filters6
-rw-r--r--projects/openttd_vs80.vcproj8
-rw-r--r--projects/openttd_vs90.vcproj8
-rw-r--r--source.list2
-rw-r--r--src/linkgraph/flowmapper.cpp62
-rw-r--r--src/linkgraph/flowmapper.h34
-rw-r--r--src/linkgraph/linkgraphschedule.cpp5
-rw-r--r--src/linkgraph/linkgraphschedule.h2
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.