From 575cabe90a56a23fa13ca24962b12a4ff2216386 Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Sun, 9 Jun 2013 13:01:23 +0000 Subject: (svn r25357) -Add: flow mapper for link graph --- src/linkgraph/flowmapper.cpp | 62 +++++++++++++++++++++++++++++++++++++ src/linkgraph/flowmapper.h | 34 ++++++++++++++++++++ src/linkgraph/linkgraphschedule.cpp | 5 ++- src/linkgraph/linkgraphschedule.h | 2 +- 4 files changed, 101 insertions(+), 2 deletions(-) create mode 100644 src/linkgraph/flowmapper.cpp create mode 100644 src/linkgraph/flowmapper.h (limited to 'src/linkgraph') 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 . + */ + +/** @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 . + */ + +/** @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; - this->handlers[3] = new MCFHandler; + this->handlers[3] = new FlowMapper; + this->handlers[4] = new MCFHandler; + 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. -- cgit v1.2.3-54-g00ecf