SUMO - Simulation of Urban MObility
NBAlgorithms_Railway.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2012-2018 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
16 // Algorithms for highway on-/off-ramps computation
17 /****************************************************************************/
18 
19 
20 // ===========================================================================
21 // included modules
22 // ===========================================================================
23 #include <config.h>
24 
25 #include <cassert>
28 #include <utils/common/ToString.h>
33 #include "NBNetBuilder.h"
34 #include "NBAlgorithms.h"
35 #include "NBNodeCont.h"
36 #include "NBEdgeCont.h"
37 #include "NBNode.h"
38 #include "NBEdge.h"
39 #include "NBVehicle.h"
40 #include "NBAlgorithms_Railway.h"
41 
42 //#define DEBUG_SEQSTOREVERSE
43 #define DEBUGNODEID "gneJ34"
44 #define DEBUGNODEID2 "28842974"
45 #define DEBUGEDGEID "22820560#0"
46 #define DEBUGCOND(obj) ((obj != 0 && (obj)->getID() == DEBUGNODEID))
47 
48 #define SHARP_THRESHOLD_SAMEDIR 100
49 #define SHARP_THRESHOLD 80
50 
51 // ===========================================================================
52 // static members
53 // ===========================================================================
54 
55 // ---------------------------------------------------------------------------
56 // Track methods
57 // ---------------------------------------------------------------------------
58 
59 void
61  successors.push_back(track);
62  viaSuccessors.push_back(std::make_pair(track, nullptr));
63  minPermissions &= track->edge->getPermissions();
64 }
65 
66 const std::vector<NBRailwayTopologyAnalyzer::Track*>&
68  if ((minPermissions & svc) != 0) {
69  return successors;
70  } else {
71  if (svcSuccessors.count(svc) == 0) {
72  std::vector<Track*> succ;
73  for (Track* t : successors) {
74  if ((t->edge->getPermissions() & svc) != 0) {
75  succ.push_back(t);
76  }
77  }
78  svcSuccessors[svc] = succ;
79  }
80  return svcSuccessors[svc];
81  }
82 }
83 
84 const std::vector<std::pair<const NBRailwayTopologyAnalyzer::Track*, const NBRailwayTopologyAnalyzer::Track*> >&
86  if ((minPermissions & svc) != 0) {
87  return viaSuccessors;
88  } else {
89  if (svcViaSuccessors.count(svc) == 0) {
90  std::vector<std::pair<const Track*, const Track*> >& succ = svcViaSuccessors[svc];
91  for (const Track* const t : successors) {
92  if ((t->edge->getPermissions() & svc) != 0) {
93  succ.push_back(std::make_pair(t, nullptr));
94  }
95  }
96  }
97  return svcViaSuccessors[svc];
98  }
99 }
100 
101 // ===========================================================================
102 // method definitions
103 // ===========================================================================
104 void
106  getBrokenRailNodes(nb, true);
107 }
108 
109 
110 void
112  extendBidiEdges(nb);
113  reverseEdges(nb);
117  if (OptionsCont::getOptions().getBool("railway.topology.repair.connect-straight")) {
119  }
120 }
121 
122 
123 void
125  int numRailEdges = 0;
126  int numBidiEdges = 0;
127  int numNotCenterEdges = 0;
128  int numAddedBidiEdges = 0;
129  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
130  if ((edge->getPermissions() & SVC_RAIL_CLASSES) != 0) {
131  numRailEdges++;
132  // rebuild connections if given from an earlier network
134  if (!edge->isBidiRail()) {
136  NBEdge* e2 = addBidiEdge(nb, edge, false);
137  if (e2 != nullptr) {
138  numAddedBidiEdges++;
139  }
140  } else {
141  numNotCenterEdges++;
142  }
143  } else {
144  numBidiEdges++;
145  }
146  }
147  }
148  WRITE_MESSAGE("Added " + toString(numAddedBidiEdges) + " bidi-edges to ensure that all tracks are usable in both directions.");
149  if (numNotCenterEdges) {
150  WRITE_WARNING("Ignore " + toString(numNotCenterEdges) + " edges because they have the wrong spreadType");
151  }
152 }
153 
154 NBEdge*
156  assert(edge->getLaneSpreadFunction() == LANESPREAD_CENTER);
157  assert(!edge->isBidiRail());
158  const std::string id2 = (edge->getID()[0] == '-'
159  ? edge->getID().substr(1)
160  : "-" + edge->getID());
161  if (nb.getEdgeCont().retrieve(id2) == nullptr) {
162  NBEdge* e2 = new NBEdge(id2, edge->getToNode(), edge->getFromNode(),
163  edge, edge->getGeometry().reverse());
164  nb.getEdgeCont().insert(e2);
165  if (update) {
166  updateTurns(edge);
167  // reconnected added edges
169  }
170  return e2;
171  } else {
172  WRITE_WARNING("Could not add bidi-edge '" + id2 + "'.");
173  return nullptr;
174  }
175 }
176 
177 void
179  EdgeVector& inEdges, EdgeVector& outEdges) {
180  for (NBEdge* e : node->getIncomingEdges()) {
181  if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
182  inEdges.push_back(e);
183  }
184  }
185  for (NBEdge* e : node->getOutgoingEdges()) {
186  if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
187  outEdges.push_back(e);
188  }
189  }
190 }
191 
192 
193 
194 std::set<NBNode*>
196  std::set<NBNode*> brokenNodes;;
197  OutputDevice& device = OutputDevice::getDevice(verbose
198  ? OptionsCont::getOptions().getString("railway.topology.output")
199  : "/dev/null");
200 
201  device.writeXMLHeader("railwayTopology", "");
202  std::set<NBNode*> railNodes = getRailNodes(nb, verbose);
203  std::map<std::pair<int, int>, std::set<NBNode*, ComparatorIdLess> > types;
204  std::set<NBEdge*, ComparatorIdLess> bidiEdges;
205  std::set<NBEdge*, ComparatorIdLess> bufferStops;
206  for (NBNode* node : railNodes) {
207  EdgeVector inEdges, outEdges;
208  getRailEdges(node, inEdges, outEdges);
209  types[std::make_pair((int)inEdges.size(), (int)outEdges.size())].insert(node);
210  for (NBEdge* e : outEdges) {
211  if (e->isBidiRail() && bidiEdges.count(e->getTurnDestination(true)) == 0) {
212  NBEdge* primary = e;
213  NBEdge* secondary = e->getTurnDestination(true);
214  if (e->getID()[0] == '-') {
215  std::swap(primary, secondary);
216  } else if (primary->getID()[0] != '-' && secondary->getID()[0] != '-' && secondary->getID() < primary->getID()) {
217  std::swap(primary, secondary);
218  }
219  if (bidiEdges.count(secondary) == 0) {
220  // avoid duplicate when both ids start with '-'
221  bidiEdges.insert(primary);
222  }
223  }
224  }
225  }
226 
227  int numBrokenA = 0;
228  int numBrokenB = 0;
229  int numBrokenC = 0;
230  int numBrokenD = 0;
231  int numBufferStops = 0;
232  if (verbose && types.size() > 0) {
233  WRITE_MESSAGE("Railway nodes by number of incoming,outgoing edges:")
234  }
235  for (auto it : types) {
236  int numBrokenType = 0;
237  device.openTag("railNodeType");
238  int in = it.first.first;
239  int out = it.first.second;
240  device.writeAttr("in", in);
241  device.writeAttr("out", out);
242  for (NBNode* n : it.second) {
243  device.openTag(SUMO_TAG_NODE);
244  device.writeAttr(SUMO_ATTR_ID, n->getID());
245  EdgeVector inRail, outRail;
246  getRailEdges(n, inRail, outRail);
247  // check if there is a mismatch between angle and edge direction
248  // a) edge pair angle supports driving but both are outgoing
249  // b) edge pair angle supports driving but both are incoming
250  // c) an incoming edge has a sharp angle to all outgoing edges
251  // d) an outgoing edge has a sharp angle from all incoming edges
252 
253  std::string broken = "";
254  if (in < 2 && hasStraightPair(n, outRail, outRail)) {
255  broken += "a";
256  numBrokenA++;
257  }
258  if (out < 2 && hasStraightPair(n, inRail, inRail)) {
259  broken += "b";
260  numBrokenB++;
261  }
262  if (out > 0) {
263  for (NBEdge* e : inRail) {
264  EdgeVector tmp;
265  tmp.push_back(e);
266  if (allSharp(n, tmp, outRail)) {
267  broken += "c";
268  numBrokenC++;
269  break;
270  }
271  }
272  }
273  if (in > 0) {
274  for (NBEdge* e : outRail) {
275  EdgeVector tmp;
276  tmp.push_back(e);
277  if (allSharp(n, inRail, tmp)) {
278  broken += "d";
279  numBrokenD++;
280  break;
281  }
282  }
283  }
284  // do not mark bidi nodes as broken
285  if (((in == 1 && out == 1) || (in == 2 && out == 2))
286  && allBidi(inRail) && allBidi(outRail)) {
287  broken = "";
288  }
289 
290  if (broken.size() > 0) {
291  device.writeAttr("broken", broken);
292  brokenNodes.insert(n);
293  numBrokenType++;
294  }
295  if (StringUtils::toBool(n->getParameter("buffer_stop", "false"))) {
296  device.writeAttr("buffer_stop", "true");
297  numBufferStops++;
298  }
299  device.closeTag();
300  }
301  device.closeTag();
302  if (verbose) {
303  WRITE_MESSAGE(" " + toString(it.first.first) + "," + toString(it.first.second)
304  + " count: " + toString(it.second.size()) + " broken: " + toString(numBrokenType));
305  }
306 
307  }
308  if (verbose) {
309  WRITE_MESSAGE("Found " + toString(brokenNodes.size()) + " broken railway nodes "
310  + "(A=" + toString(numBrokenA)
311  + " B=" + toString(numBrokenB)
312  + " C=" + toString(numBrokenC)
313  + " D=" + toString(numBrokenD)
314  + ")");
315  WRITE_MESSAGE("Found " + toString(numBufferStops) + " railway nodes marked as buffer_stop");
316  }
317 
318  for (NBEdge* e : bidiEdges) {
319  device.openTag("bidiEdge");
320  device.writeAttr(SUMO_ATTR_ID, e->getID());
321  device.writeAttr("bidi", e->getTurnDestination(true)->getID());
322  device.closeTag();
323  }
324  if (verbose) {
325  WRITE_MESSAGE("Found " + toString(bidiEdges.size()) + " bidirectional rail edges");
326  }
327 
328  device.close();
329  return brokenNodes;
330 }
331 
332 
333 std::set<NBNode*>
335  std::set<NBNode*> railNodes;
336 
337  NBEdgeCont& ec = nb.getEdgeCont();
338  int numRailEdges = 0;
339  for (auto it = ec.begin(); it != ec.end(); it++) {
340  if (isRailway(it->second->getPermissions())) {
341  numRailEdges++;
342  railNodes.insert(it->second->getFromNode());
343  railNodes.insert(it->second->getToNode());
344 
345  }
346  }
347  std::set<NBNode*> railSignals;
348  for (NBNode* node : railNodes) {
349  if (node->getType() == NODETYPE_RAIL_SIGNAL) {
350  railSignals.insert(node);
351  }
352  }
353  if (verbose) {
354  WRITE_MESSAGE("Found " + toString(numRailEdges) + " railway edges and " + toString(railNodes.size()) + " railway nodes (" + toString(railSignals.size()) + " signals).");
355  }
356  return railNodes;
357 }
358 
359 
360 bool
361 NBRailwayTopologyAnalyzer::isStraight(const NBNode* node, const NBEdge* e1, const NBEdge* e2) {
362  const double relAngle = NBHelpers::normRelAngle(e1->getAngleAtNode(node), e2->getAngleAtNode(node));
363  /*
364  std::cout << " isStraight n=" << node->getID()
365  << " e1=" << e1->getID()
366  << " e2=" << e2->getID()
367  << " a1=" << e1->getAngleAtNode(node)
368  << " a2=" << e2->getAngleAtNode(node)
369  << " rel=" << relAngle
370  << "\n";
371  */
372  if ((e1->getToNode() == node && e2->getFromNode() == node)
373  || (e1->getFromNode() == node && e2->getToNode() == node)) {
374  // edges go in the same direction
375  return fabs(relAngle) < SHARP_THRESHOLD;
376  } else {
377  // edges go in the opposite direction (both incoming or outgoing)
378  return fabs(relAngle) > SHARP_THRESHOLD_SAMEDIR;
379  }
380 }
381 
382 
383 bool
385  const EdgeVector& edges2) {
386 #ifdef DEBUG_SEQSTOREVERSE
387  //if (node->getID() == DEBUGNODEID2) {
388  // std::cout << " edges=" << toString(edges) << " edges2=" << toString(edges2) << "\n";
389  //}
390 #endif
391  for (NBEdge* e1 : edges) {
392  for (NBEdge* e2 : edges2) {
393  //if (e1->getID() == "195411601#2" && e2->getID() == "93584120#3") {
394  // std::cout
395  // << " DEBUG normRelA=" << NBHelpers::normRelAngle(
396  // e1->getAngleAtNode(node),
397  // e2->getAngleAtNode(node))
398  // << "\n";
399  //}
400  if (e1 != e2 && isStraight(node, e1, e2)) {
401  return true;
402  }
403  }
404  }
405  return false;
406 }
407 
408 
409 bool
410 NBRailwayTopologyAnalyzer::allBroken(const NBNode* node, NBEdge* candOut, const EdgeVector& in, const EdgeVector& out) {
411  for (NBEdge* e : in) {
412  if (e != candOut && isStraight(node, e, candOut)) {
413  if (gDebugFlag1) {
414  std::cout << " isStraight e=" << e->getID() << " candOut=" << candOut->getID() << "\n";
415  }
416  return false;
417  }
418  }
419  for (NBEdge* e : out) {
420  if (e != candOut && !isStraight(node, e, candOut)) {
421  if (gDebugFlag1) {
422  std::cout << " isSharp e=" << e->getID() << " candOut=" << candOut->getID() << "\n";
423  }
424  return false;
425  }
426  }
427  return true;
428 }
429 
430 
431 bool
432 NBRailwayTopologyAnalyzer::allSharp(const NBNode* node, const EdgeVector& in, const EdgeVector& out, bool countBidiAsSharp) {
433  bool allBidi = true;
434  for (NBEdge* e1 : in) {
435  for (NBEdge* e2 : out) {
436  if (e1 != e2 && isStraight(node, e1, e2)) {
437  return false;
438  }
439  if (!e1->isBidiRail(true)) {
440  //std::cout << " allSharp node=" << node->getID() << " e1=" << e1->getID() << " is not bidi\n";
441  allBidi = false;
442  }
443  }
444  }
445  return !allBidi || countBidiAsSharp;
446 }
447 
448 
449 bool
451  for (NBEdge* e : edges) {
452  if (!e->isBidiRail()) {
453  return false;
454  }
455  }
456  return true;
457 }
458 
459 
460 int
462  int added = 0;
463  std::set<NBNode*> railNodes = getRailNodes(nb);
464  NBEdgeCont& ec = nb.getEdgeCont();
465  for (auto it = ec.begin(); it != ec.end(); it++) {
466  NBEdge* e = it->second;
467  if (e->isBidiRail()) {
468  added += extendBidiEdges(nb, e->getFromNode(), e->getTurnDestination(true));
469  added += extendBidiEdges(nb, e->getToNode(), e);
470  }
471  }
472  //if (added > 0) {
473  // std::cout << "Addeded " << added << " bidi-edges as extension of existing bidi edges\n";
474  //}
475  return added;
476 }
477 
478 
479 int
481  assert(bidiIn->getToNode() == node);
482  NBEdge* bidiOut = bidiIn->getTurnDestination(true);
483  if (bidiOut == nullptr) {
484  WRITE_WARNING("Could not find bidi-edge for edge '" + bidiIn->getID() + "'");
485  return 0;
486  }
487  EdgeVector tmpBidiOut;
488  tmpBidiOut.push_back(bidiOut);
489  EdgeVector tmpBidiIn;
490  tmpBidiIn.push_back(bidiIn);
491  int added = 0;
492  EdgeVector inRail, outRail;
493  getRailEdges(node, inRail, outRail);
494  for (NBEdge* cand : outRail) {
495  //std::cout << " extendBidiEdges n=" << node->getID() << " bidiIn=" << bidiIn->getID() << " cand=" << cand->getID() << " isStraight=" << isStraight(node, bidiIn, cand) << " allSharp=" << allSharp(node, inRail, tmpBidiOut, true) << "\n";
496  if (!cand->isBidiRail() && isStraight(node, bidiIn, cand)
497  && cand->getLaneSpreadFunction() == LANESPREAD_CENTER
498  && allSharp(node, inRail, tmpBidiOut, true)) {
499  NBEdge* e2 = addBidiEdge(nb, cand);
500  if (e2 != nullptr) {
501  added += 1 + extendBidiEdges(nb, cand->getToNode(), cand);
502  }
503  }
504  }
505  for (NBEdge* cand : inRail) {
506  //std::cout << " extendBidiEdges n=" << node->getID() << " bidiOut=" << bidiOut->getID() << " cand=" << cand->getID() << " isStraight=" << isStraight(node, cand, bidiOut) << " allSharp=" << allSharp(node, outRail, tmpBidiIn, true) << "\n";
507  if (!cand->isBidiRail() && isStraight(node, cand, bidiOut)
508  && cand->getLaneSpreadFunction() == LANESPREAD_CENTER
509  && allSharp(node, outRail, tmpBidiIn, true)) {
510  NBEdge* e2 = addBidiEdge(nb, cand);
511  if (e2 != nullptr) {
512  added += 1 + extendBidiEdges(nb, cand->getFromNode(), e2);
513  }
514  }
515  }
516  return added;
517 }
518 
519 
520 void
522  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
523  // find reversible edge sequences between broken nodes
524  std::vector<EdgeVector> seqsToReverse;
525  for (NBNode* n : brokenNodes) {
526  EdgeVector inRail, outRail;
527  getRailEdges(n, inRail, outRail);
528  for (NBEdge* start : outRail) {
529  EdgeVector tmp;
530  tmp.push_back(start);
531  // only reverse edges where the node would be unbroken afterwards
532  if (!allBroken(n, start, inRail, outRail)
533  || (inRail.size() == 1 && outRail.size() == 1)) {
534 #ifdef DEBUG_SEQSTOREVERSE
535  if (n->getID() == DEBUGNODEID) {
536  std::cout << " abort at start n=" << n->getID() << " (not all broken)\n";
537  }
538 #endif
539  continue;
540  }
541  //std::cout << " get sequences from " << start->getID() << "\n";
542  bool forward = true;
543  EdgeVector seq;
544  while (forward) {
545  seq.push_back(start);
546  //std::cout << " seq=" << toString(seq) << "\n";
547  NBNode* n2 = start->getToNode();
548  EdgeVector inRail2, outRail2;
549  getRailEdges(n2, inRail2, outRail2);
550  if (brokenNodes.count(n2) != 0) {
551  EdgeVector tmp2;
552  tmp2.push_back(start);
553  if (allBroken(n2, start, outRail2, inRail2)) {
554  seqsToReverse.push_back(seq);
555  } else {
556 #ifdef DEBUG_SEQSTOREVERSE
557  if (n->getID() == DEBUGNODEID) {
558  std::cout << " abort at n2=" << n2->getID() << " (not all broken)\n";
559  }
560 #endif
561  }
562  forward = false;
563  } else {
564  if (outRail2.size() == 0) {
565  // stop at network border
566  forward = false;
567 #ifdef DEBUG_SEQSTOREVERSE
568  if (n->getID() == DEBUGNODEID) {
569  std::cout << " abort at n2=" << n2->getID() << " (border)\n";
570  }
571 #endif
572  } else if (outRail2.size() > 1 || inRail2.size() > 1) {
573  // stop at switch
574  forward = false;
575 #ifdef DEBUG_SEQSTOREVERSE
576  if (n->getID() == DEBUGNODEID) {
577  std::cout << " abort at n2=" << n2->getID() << " (switch)\n";
578  }
579 #endif
580  } else {
581  start = outRail2.front();
582  }
583  }
584  }
585  }
586  }
587  // sort by sequence length
588  if (seqsToReverse.size() > 0) {
589  WRITE_MESSAGE("Found " + toString(seqsToReverse.size()) + " reversible edge sequences between broken rail nodes");
590  }
591  std::sort(seqsToReverse.begin(), seqsToReverse.end(),
592  [](const EdgeVector & a, const EdgeVector & b) {
593  return a.size() < b.size();
594  });
595  int numReversed = 0;
596  std::set<NBNode*> affectedEndpoints;
597  std::set<std::string> reversedIDs;
598  std::map<int, int> seqLengths;
599  for (EdgeVector& seq : seqsToReverse) {
600  NBNode* seqStart = seq.front()->getFromNode();
601  NBNode* seqEnd = seq.back()->getToNode();
602  // avoid reversing sequenes on both sides of a broken node
603  if (affectedEndpoints.count(seqStart) == 0
604  && affectedEndpoints.count(seqEnd) == 0) {
605  affectedEndpoints.insert(seqStart);
606  affectedEndpoints.insert(seqEnd);
607  //WRITE_MESSAGE(" reversed seq=" + toString(seq));
608  for (NBEdge* e : seq) {
609  e->reinitNodes(e->getToNode(), e->getFromNode());
610  e->setGeometry(e->getGeometry().reverse());
611  reversedIDs.insert(e->getID());
612  }
613  seqLengths[(int)seq.size()]++;
614  numReversed++;
615  }
616  }
617  if (numReversed > 0) {
618  WRITE_MESSAGE("Reversed " + toString(numReversed) + " sequences (count by length: " + joinToString(seqLengths, " ", ":") + ")");
619  for (auto& item : nb.getPTStopCont().getStops()) {
620  if (reversedIDs.count(item.second->getEdgeId())) {
621  item.second->findLaneAndComputeBusStopExtend(nb.getEdgeCont());
622  }
623  }
624  }
625 }
626 
627 
628 void
630  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
631  std::set<NBNode*> railNodes = getRailNodes(nb);
632  // find buffer stops and ensure that thay are connect to the network in both directions
633  int numBufferStops = 0;
634  int numAddedBidiTotal = 0;
635  for (NBNode* node : railNodes) {
636  if (StringUtils::toBool(node->getParameter("buffer_stop", "false"))) {
637  if (node->getEdges().size() != 1) {
638  WRITE_WARNING("Ignoring buffer stop junction '" + node->getID() + "' with " + toString(node->getEdges().size()) + " edges\n");
639  continue;
640  }
641  int numAddedBidi = 0;
642  numBufferStops++;
643  NBEdge* prev = nullptr;
644  NBEdge* prev2 = nullptr;
645  EdgeVector inRail, outRail;
646  getRailEdges(node, inRail, outRail);
647  bool addAway = true; // add new edges away from buffer stop
648  while (prev == nullptr || (inRail.size() + outRail.size()) == 3) {
649  NBEdge* e = nullptr;
650  if (prev == nullptr) {
651  assert(node->getEdges().size() == 1);
652  e = node->getEdges().front();
653  addAway = node == e->getToNode();
654  } else {
655  if (addAway) {
656  // XXX if node is broken we need to switch direction
657  assert(inRail.size() == 2);
658  e = inRail.front() == prev2 ? inRail.back() : inRail.front();
659  } else {
660  // XXX if node is broken we need to switch direction
661  assert(outRail.size() == 2);
662  e = outRail.front() == prev2 ? outRail.back() : outRail.front();
663  }
664  }
666  NBNode* e2From = nullptr;
667  NBNode* e2To = nullptr;
668  if (addAway) {
669  e2From = node;
670  e2To = e->getFromNode();
671  node = e2To;
672  } else {
673  e2From = e->getToNode();
674  e2To = node;
675  node = e2From;
676  }
677  NBEdge* e2 = addBidiEdge(nb, e);
678  if (e2 == nullptr) {
679  break;
680  }
681  prev = e;
682  prev2 = e2;
683  numAddedBidi++;
684  numAddedBidiTotal++;
685  inRail.clear();
686  outRail.clear();
687  getRailEdges(node, inRail, outRail);
688  }
689  //if (numAddedBidi > 0) {
690  // WRITE_MESSAGE(" added " + toString(numAddedBidi) + " edges between buffer stop junction '" + bufferStop->getID() + "' and junction '" + node->getID() + "'");
691  //}
692  }
693  }
694  if (numAddedBidiTotal > 0) {
695  WRITE_MESSAGE("Added " + toString(numAddedBidiTotal) + " edges to connect " + toString(numBufferStops) + " buffer stops in both directions.");
696  }
697 }
698 
699 NBEdge*
701  EdgeVector inRail, outRail;
702  getRailEdges(n, inRail, outRail);
703  if (inRail.size() == 2 && outRail.size() == 1 && isStraight(n, inRail.front(), inRail.back())) {
704  if (isStraight(n, inRail.front(), outRail.front())) {
705  return inRail.front();
706  } else if (isStraight(n, inRail.back(), outRail.front())) {
707  return inRail.back();
708  }
709  }
710  if (inRail.size() == 1 && outRail.size() == 2 && isStraight(n, outRail.front(), outRail.back())) {
711  if (isStraight(n, outRail.front(), inRail.front())) {
712  return outRail.front();
713  } else if (isStraight(n, outRail.back(), inRail.front())) {
714  return outRail.back();
715  }
716  }
717  return nullptr;
718 }
719 
720 
721 void
723  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
724  std::map<int, int> seqLengths;
725  int numAdded = 0;
726  int numSeqs = 0;
727  for (NBNode* n : brokenNodes) {
728  NBEdge* edge = isBidiSwitch(n);
729  if (edge != nullptr) {
730  std::vector<NBNode*> nodeSeq;
731  EdgeVector edgeSeq;
732  NBNode* prev = n;
733  nodeSeq.push_back(prev);
734  edgeSeq.push_back(edge);
735  bool forward = true;
736  //std::cout << "Looking for potential bidi-edge sequence starting at junction '" << n->getID() << "' with edge '" + edge->getID() << "'\n";
737  // find a suitable end point for adding bidi edges
738  while (forward) {
739  NBNode* next = edge->getFromNode() == prev ? edge->getToNode() : edge->getFromNode();
740  EdgeVector allRail;
741  getRailEdges(next, allRail, allRail);
742  if (allRail.size() == 2 && isStraight(next, allRail.front(), allRail.back())) {
743  prev = next;
744  edge = allRail.front() == edge ? allRail.back() : allRail.front();
745  nodeSeq.push_back(prev);
746  edgeSeq.push_back(edge);
747  } else {
748  forward = false;
749  EdgeVector inRail2, outRail2;
750  getRailEdges(next, inRail2, outRail2);
751  if (isBidiSwitch(next) == edge) {
752  // suitable switch found as endpoint, add reverse edges
753  //WRITE_MESSAGE("Adding " + toString(edgeSeq.size())
754  // + " bidi-edges between switches junction '" + n->getID() + "' and junction '" + next->getID() + "'");
755  for (NBEdge* e : edgeSeq) {
756  addBidiEdge(nb, e);
757  }
758  seqLengths[(int)edgeSeq.size()]++;
759  numSeqs++;
760  numAdded += (int)edgeSeq.size();
761  } else {
762  //std::cout << " sequence ended at junction " << next->getID()
763  // << " in=" << inRail2.size()
764  // << " out=" << outRail2.size()
765  // << " bidiSwitch=" << Named::getIDSecure(isBidiSwitch(next))
766  // << "\n";
767  }
768 
769  }
770  }
771 
772  }
773  }
774  if (seqLengths.size() > 0) {
775  WRITE_MESSAGE("Added " + toString(numAdded) + " bidi-edges between " + toString(numSeqs) + " pairs of railway switches (count by length: " + joinToString(seqLengths, " ", ":") + ")");
776  }
777 }
778 
779 
780 void
782  // generate bidirectional routing graph
783  NBEdgeCont& ec = nb.getEdgeCont();
784  std::vector<Track*> tracks;
785  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
786  tracks.push_back(new Track(edge));
787  }
788  const int numEdges = (int)tracks.size();
789  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
790  tracks.push_back(new Track(edge, (int)tracks.size(), edge->getID() + "_reverse"));
791  }
792  // add special tracks for starting end ending in both directions
793  std::map<NBEdge*, std::pair<Track*, Track*> > stopTracks;
794  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
795  if ((edge->getPermissions() & SVC_RAIL_CLASSES) != 0) {
796  Track* start = new Track(edge, (int)tracks.size(), edge->getID() + "_start");
797  tracks.push_back(start);
798  Track* end = new Track(edge, (int)tracks.size(), edge->getID() + "_end");
799  tracks.push_back(end);
800  stopTracks[edge] = std::make_pair(start, end);
801  }
802  }
803  // set successors based on angle (connections are not yet built)
804  for (NBNode* node : getRailNodes(nb)) {
805  EdgeVector railEdges;
806  getRailEdges(node, railEdges, railEdges);
807  for (NBEdge* e1 : railEdges) {
808  for (NBEdge* e2 : railEdges) {
809  if (e1 != e2 && isStraight(node, e1, e2)) {
810  int i = e1->getNumericalID();
811  int i2 = e2->getNumericalID();
812  if (e1->getToNode() == node) {
813  if (e2->getFromNode() == node) {
814  // case 1) plain forward connection
815  tracks[i]->addSuccessor(tracks[i2]);
816  // reverse edge (numerical id incremented by numEdges)
817  tracks[i2 + numEdges]->addSuccessor(tracks[i + numEdges]);
818  } else {
819  // case 2) both edges pointing towards each ohter
820  tracks[i]->addSuccessor(tracks[i2 + numEdges]);
821  tracks[i2]->addSuccessor(tracks[i + numEdges]);
822  }
823  } else {
824  if (e2->getFromNode() == node) {
825  // case 3) both edges pointing away from each other
826  tracks[i + numEdges]->addSuccessor(tracks[i2]);
827  tracks[i2 + numEdges]->addSuccessor(tracks[i]);
828  } else {
829  // already handled via case 1)
830  }
831  }
832 
833  }
834  }
835  }
836  }
837  // define start and end successors
838  for (auto& item : stopTracks) {
839  const int index = item.first->getNumericalID();
840  // start
841  item.second.first->addSuccessor(tracks[index]);
842  item.second.first->addSuccessor(tracks[index + numEdges]);
843  // end
844  tracks[index]->addSuccessor(item.second.second);
845  tracks[index + numEdges]->addSuccessor(item.second.second);
846  }
847  // DEBUG
848  /*
849  for (Track* t : tracks) {
850  std::cout << "track " << t->getID() << " e=" << t->edge->getID() << " i=" << t->getNumericalID() << " succ:\n";
851  for (Track* s : t->getSuccessors(SVC_IGNORING)) {
852  std::cout << " succ=" << s->getID() << "\n";
853  }
854  }
855  */
856 
859  tracks, true, &NBRailwayTopologyAnalyzer::getTravelTimeStatic, nullptr, true);
860 
861  int added = 0;
862  int numDisconnected = 0;
863  std::set<NBEdge*> addBidiStops;
864  std::set<NBEdge*> addBidiEdges;
865  std::set<std::pair<NBPTStop*, NBPTStop*> > visited;
866  for (NBPTLine* line : nb.getPTLineCont().getLines()) {
867  std::vector<NBPTStop*> stops = line->getStops();
868  if (stops.size() < 2) {
869  continue;
870  }
871  for (auto it = stops.begin(); it + 1 != stops.end(); ++it) {
872  std::pair<NBPTStop*, NBPTStop*> trip(*it, *(it + 1));
873  if (visited.count(trip) != 0) {
874  continue;
875  } else {
876  visited.insert(trip);
877  }
878  NBEdge* fromEdge = ec.getByID((*it)->getEdgeId());
879  NBEdge* toEdge = ec.getByID((*(it + 1))->getEdgeId());
880  if (fromEdge == nullptr || toEdge == nullptr) {
881  continue;
882  }
883  if (stopTracks.count(fromEdge) == 0
884  || stopTracks.count(toEdge) == 0) {
885  continue;
886  }
887  NBVehicle veh(line->getRef(), (SUMOVehicleClass)(fromEdge->getPermissions() & SVC_RAIL_CLASSES));
888  std::vector<const Track*> route;
889  router->compute(stopTracks[fromEdge].first, stopTracks[toEdge].second, &veh, 0, route);
890  //if (fromEdge->getID() == "356053025#1" && toEdge->getID() == "23256161") {
891  // std::cout << "DEBUG: route=" << toString(route) << "\n";
892  //}
893  if (route.size() > 0) {
894  assert(route.size() > 2);
895  for (int i = 1; i < (int)route.size() - 1; ++i) {
896  if (route[i]->getNumericalID() >= numEdges) {
897  NBEdge* edge = route[i]->edge;
898  if (addBidiEdges.count(edge) == 0) {
899  if (!edge->isBidiRail(true)) {
900  bool isStop = i == 1 || i == (int)route.size() - 2;
901  if (edge->getLaneSpreadFunction() == LANESPREAD_CENTER) {
902  addBidiEdges.insert(edge);
903  if (isStop) {
904  addBidiStops.insert(edge);
905  }
906  } else {
907  if (isStop) {
908  WRITE_WARNING("Stop on edge " + fromEdge->getID() + " can only be reached in reverse but edge has the wrong spreadType");
909  }
910  }
911  }
912  }
913  }
914  }
915  } else {
916  WRITE_WARNING("No connection found between stops on edge '" + fromEdge->getID() + "' and edge '" + toEdge->getID() + "'");
917  numDisconnected++;
918  }
919  }
920  }
921  for (NBEdge* edge : addBidiEdges) {
922  if (!edge->isBidiRail()) {
923  NBEdge* e2 = addBidiEdge(nb, edge);
924  //std::cout << " add bidiEdge for stop at edge " << edge->getID() << "\n";
925  if (e2 != nullptr) {
926  added++;
927  added += extendBidiEdges(nb, edge->getToNode(), edge);
928  added += extendBidiEdges(nb, edge->getFromNode(), e2);
929  }
930  }
931  }
932 
933  if (addBidiEdges.size() > 0 || numDisconnected > 0) {
934  WRITE_MESSAGE("Added " + toString(addBidiStops.size()) + " bidi-edges for public transport stops and a total of "
935  + toString(added) + " bidi-edges to ensure connectivity of stops ("
936  + toString(numDisconnected) + " stops remain disconnected)");
937  }
938 
939  // clean up
940  for (Track* t : tracks) {
941  delete t;
942  }
943  delete router;
944 }
945 
946 
947 void
949  int added = 0;
950  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
951  for (const auto& e : nb.getEdgeCont()) {
952  if (!isRailway(e.second->getPermissions())) {
953  continue;
954  }
955  NBNode* const from = e.second->getFromNode();
956  NBNode* const to = e.second->getToNode();
957  if (brokenNodes.count(from) == 0 && brokenNodes.count(to) == 0) {
958  continue;
959  }
960  EdgeVector inRailFrom, outRailFrom, inRailTo, outRailTo;
961  getRailEdges(from, inRailFrom, outRailFrom);
962  getRailEdges(to, inRailTo, outRailTo);
963  bool haveReverse = false;
964  for (const NBEdge* cand : outRailTo) {
965  if (cand->getToNode() == from) {
966  haveReverse = true;
967  break;
968  }
969  }
970  if (haveReverse) {
971  continue;
972  }
973  bool haveStraightFrom = false;
974  for (const NBEdge* fromStraightCand : outRailFrom) {
975  if (fromStraightCand != e.second && isStraight(from, fromStraightCand, e.second)) {
976  haveStraightFrom = true;
977  break;
978  }
979  }
980  if (!haveStraightFrom) {
981  continue;
982  }
983  for (const NBEdge* toStraightCand : inRailTo) {
984  if (toStraightCand != e.second && isStraight(to, toStraightCand, e.second)) {
985  NBEdge* e2 = addBidiEdge(nb, e.second);
986  //std::cout << " add bidiEdge for straight connectivity at edge " << e.second->getID() << " fromBroken=" << brokenNodes.count(from) << " toBroken=" << brokenNodes.count(to) << "\n";
987  if (e2 != nullptr) {
988  added++;
989  added += extendBidiEdges(nb, to, e.second);
990  added += extendBidiEdges(nb, from, e2);
991  }
992  break;
993  }
994  }
995  }
996  if (added > 0) {
997  WRITE_MESSAGE("Added " + toString(added) + " bidi-edges to ensure connectivity of straight tracks.");
998  }
999 }
1000 
1001 
1002 void
1006 }
1007 
1008 
1009 double
1010 NBRailwayTopologyAnalyzer::getTravelTimeStatic(const Track* const track, const NBVehicle* const veh, double time) {
1011  return NBEdge::getTravelTimeStatic(track->edge, veh, time);
1012 }
1013 
1014 /****************************************************************************/
1015 
LaneSpreadFunction getLaneSpreadFunction() const
Returns how this edge&#39;s lanes&#39; lateral offset is computed.
Definition: NBEdge.h:704
bool gDebugFlag1
global utility flags for debugging
Definition: StdDefs.cpp:32
void invalidateConnections(bool reallowSetting=false)
invalidate current connections of edge
Definition: NBEdge.cpp:1348
#define SHARP_THRESHOLD_SAMEDIR
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:256
NBEdge * getByID(const std::string &edgeID) const
Returns the edge with id if it exists.
void close()
Closes the device and removes it from the dictionary.
static bool allBidi(const EdgeVector &edges)
static bool isStraight(const NBNode *node, const NBEdge *e1, const NBEdge *e2)
static NBEdge * addBidiEdge(NBNetBuilder &nb, NBEdge *edge, bool update=true)
add bidi-edge for the given edge
static std::set< NBNode * > getRailNodes(NBNetBuilder &nb, bool verbose=false)
std::vector< std::pair< const Track *, const Track * > > viaSuccessors
static bool allBroken(const NBNode *node, NBEdge *candOut, const EdgeVector &in, const EdgeVector &out)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
static double normRelAngle(double angle1, double angle2)
ensure that reverse relAngles (>=179.999) always count as turnarounds (-180)
Definition: NBHelpers.cpp:60
static void repairTopology(NBNetBuilder &nb)
static void addBidiEdgesForStraightConnectivity(NBNetBuilder &nb)
add bidi-edges to connect straight tracks
The representation of a single edge during network building.
Definition: NBEdge.h:65
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
bool isBidiRail(bool ignoreSpread=false) const
whether this edge is part of a bidirectional railway
Definition: NBEdge.cpp:668
const std::vector< NBPTLine * > & getLines() const
Definition: NBPTLineCont.h:53
NBPTStopCont & getPTStopCont()
Returns a reference to the pt stop container.
Definition: NBNetBuilder.h:176
NBEdge * getTurnDestination(bool possibleDestination=false) const
Definition: NBEdge.cpp:3013
Track(NBEdge *e, int i=-1, const std::string &_id="")
static void updateTurns(NBEdge *edge)
recompute turning directions for both nodes of the given edge
NBPTLineCont & getPTLineCont()
Returns a reference to the pt line container.
Definition: NBNetBuilder.h:181
PositionVector reverse() const
reverse position vector
std::map< std::string, NBEdge * >::const_iterator end() const
Returns the pointer to the end of the stored edges.
Definition: NBEdgeCont.h:193
const std::string & getID() const
Returns the id.
Definition: Named.h:78
bool isRailway(SVCPermissions permissions)
Returns whether an edge with the given permission is a railway edge.
const std::vector< std::pair< const Track *, const Track * > > & getViaSuccessors(SUMOVehicleClass svc=SVC_IGNORING) const
static std::set< NBNode * > getBrokenRailNodes(NBNetBuilder &nb, bool verbose=false)
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:241
std::map< SUMOVehicleClass, std::vector< std::pair< const Track *, const Track * > > > svcViaSuccessors
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:58
const EdgeVector & getOutgoingEdges() const
Returns this node&#39;s outgoing edges (The edges which start at this node)
Definition: NBNode.h:255
static bool toBool(const std::string &sData)
converts a string into the bool value described by it by calling the char-type converter ...
void invalidateIncomingConnections()
invalidate incoming connections
Definition: NBNode.cpp:1518
static void analyzeTopology(NBNetBuilder &nb)
Computes highway on-/off-ramps (if wished)
std::map< std::string, NBEdge * >::const_iterator begin() const
Returns the pointer to the begin of the stored edges.
Definition: NBEdgeCont.h:185
static void reverseEdges(NBNetBuilder &nb)
reverse edges sequences that are to broken nodes on both sides
bool insert(NBEdge *edge, bool ignorePrunning=false)
Adds an edge to the dictionary.
Definition: NBEdgeCont.cpp:152
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:49
Computes the shortest path through a network using the Dijkstra algorithm.
bool writeXMLHeader(const std::string &rootElement, const std::string &schemaFile, std::map< SumoXMLAttr, std::string > attrs=std::map< SumoXMLAttr, std::string >())
Writes an XML header with optional configuration.
static void addBidiEdgesForBufferStops(NBNetBuilder &nb)
add bidi-edges to connect buffers stops in both directions
classes which drive on tracks
NBEdgeCont & getEdgeCont()
Definition: NBNetBuilder.h:150
static void getRailEdges(const NBNode *node, EdgeVector &inEdges, EdgeVector &outEdges)
filter out rail edges among all edges of a the given node
#define SHARP_THRESHOLD
Storage for edges, including some functionality operating on multiple edges.
Definition: NBEdgeCont.h:61
double getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge&#39;s geometry at the given node.
Definition: NBEdge.cpp:1801
static void makeAllBidi(NBNetBuilder &nb)
A vehicle as used by router.
Definition: NBVehicle.h:44
static void addBidiEdgesForStops(NBNetBuilder &nb)
add bidi-edges to connect successive public transport stops
#define DEBUGNODEID
static bool allSharp(const NBNode *node, const EdgeVector &in, const EdgeVector &out, bool countBidiAsSharp=false)
SVCPermissions getPermissions(int lane=-1) const
get the union of allowed classes over all lanes or for a specific lane
Definition: NBEdge.cpp:3331
static NBEdge * isBidiSwitch(const NBNode *n)
static void computeTurnDirectionsForNode(NBNode *node, bool warn)
Computes turnaround destinations for all incoming edges of the given nodes (if any) ...
std::map< SUMOVehicleClass, std::vector< Track * > > svcSuccessors
const PositionVector & getGeometry() const
Returns the geometry of the edge.
Definition: NBEdge.h:622
const std::map< std::string, NBPTStop * > & getStops() const
Definition: NBPTStopCont.h:62
EdgeVector getAllEdges() const
return all edges
const EdgeVector & getIncomingEdges() const
Returns this node&#39;s incoming edges (The edges which yield in this node)
Definition: NBNode.h:250
Instance responsible for building networks.
Definition: NBNetBuilder.h:109
static OutputDevice & getDevice(const std::string &name)
Returns the described OutputDevice.
static void addBidiEdgesBetweenSwitches(NBNetBuilder &nb)
add bidi-edges to connect switches that are approached in both directions
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:34
NBEdge * retrieve(const std::string &id, bool retrieveExtracted=false) const
Returns the edge that has the given id.
Definition: NBEdgeCont.cpp:245
int size() const
Returns the number of edges.
Definition: NBEdgeCont.h:306
alternative definition for junction
const std::vector< Track * > & getSuccessors(SUMOVehicleClass svc=SVC_IGNORING) const
const std::string getParameter(const std::string &key, const std::string &defaultValue="") const
Returns the value for a given key.
static double getTravelTimeStatic(const NBEdge *const edge, const NBVehicle *const, double)
Definition: NBEdge.h:1270
Represents a single node (junction) during network building.
Definition: NBNode.h:68
Static storage of an output device and its base (abstract) implementation.
Definition: OutputDevice.h:64
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
static bool hasStraightPair(const NBNode *node, const EdgeVector &edges, const EdgeVector &edges2)
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:434
static double getTravelTimeStatic(const Track *const track, const NBVehicle *const veh, double time)
void setLaneSpreadFunction(LaneSpreadFunction spread)
(Re)sets how the lanes lateral offset shall be computed
Definition: NBEdge.cpp:861
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:242
static int extendBidiEdges(NBNetBuilder &nb)
add further bidi-edges near existing bidi-edges
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:441
std::string joinToString(const std::vector< T > &v, const T_BETWEEN &between, std::streamsize accuracy=gPrecision)
Definition: ToString.h:237
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.