(svn r25357) -Add: flow mapper for link graph

4 files changed, 101 insertions, 2 deletions

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.