Eclipse 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-2019 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  device.openTag("legend");
236  device.openTag("error");
237  device.writeAttr(SUMO_ATTR_ID, "a");
238  device.writeAttr("meaning", "edge pair angle supports driving but both are outgoing");
239  device.closeTag();
240  device.openTag("error");
241  device.writeAttr(SUMO_ATTR_ID, "b");
242  device.writeAttr("meaning", "edge pair angle supports driving but both are incoming");
243  device.closeTag();
244  device.openTag("error");
245  device.writeAttr(SUMO_ATTR_ID, "c");
246  device.writeAttr("meaning", "an incoming edge has a sharp angle to all outgoing edges");
247  device.closeTag();
248  device.openTag("error");
249  device.writeAttr(SUMO_ATTR_ID, "d");
250  device.writeAttr("meaning", "an outgoing edge has a sharp angle from all incoming edges");
251  device.closeTag();
252  device.closeTag();
253 
254  for (auto it : types) {
255  int numBrokenType = 0;
256  device.openTag("railNodeType");
257  int in = it.first.first;
258  int out = it.first.second;
259  device.writeAttr("in", in);
260  device.writeAttr("out", out);
261  for (NBNode* n : it.second) {
262  device.openTag(SUMO_TAG_NODE);
263  device.writeAttr(SUMO_ATTR_ID, n->getID());
264  EdgeVector inRail, outRail;
265  getRailEdges(n, inRail, outRail);
266  // check if there is a mismatch between angle and edge direction
267  // (see above)
268 
269  std::string broken = "";
270  if (in < 2 && hasStraightPair(n, outRail, outRail)) {
271  broken += "a";
272  numBrokenA++;
273  }
274  if (out < 2 && hasStraightPair(n, inRail, inRail)) {
275  broken += "b";
276  numBrokenB++;
277  }
278  if (out > 0) {
279  for (NBEdge* e : inRail) {
280  EdgeVector tmp;
281  tmp.push_back(e);
282  if (allSharp(n, tmp, outRail)) {
283  broken += "c";
284  numBrokenC++;
285  break;
286  }
287  }
288  }
289  if (in > 0) {
290  for (NBEdge* e : outRail) {
291  EdgeVector tmp;
292  tmp.push_back(e);
293  if (allSharp(n, inRail, tmp)) {
294  broken += "d";
295  numBrokenD++;
296  break;
297  }
298  }
299  }
300  // do not mark bidi nodes as broken
301  if (((in == 1 && out == 1) || (in == 2 && out == 2))
302  && allBidi(inRail) && allBidi(outRail)) {
303  broken = "";
304  }
305 
306  if (broken.size() > 0) {
307  device.writeAttr("broken", broken);
308  brokenNodes.insert(n);
309  numBrokenType++;
310  }
311  if (StringUtils::toBool(n->getParameter("buffer_stop", "false"))) {
312  device.writeAttr("buffer_stop", "true");
313  numBufferStops++;
314  }
315  device.closeTag();
316  }
317  device.closeTag();
318  if (verbose) {
319  WRITE_MESSAGE(" " + toString(it.first.first) + "," + toString(it.first.second)
320  + " count: " + toString(it.second.size()) + " broken: " + toString(numBrokenType));
321  }
322 
323  }
324  if (verbose) {
325  WRITE_MESSAGE("Found " + toString(brokenNodes.size()) + " broken railway nodes "
326  + "(A=" + toString(numBrokenA)
327  + " B=" + toString(numBrokenB)
328  + " C=" + toString(numBrokenC)
329  + " D=" + toString(numBrokenD)
330  + ")");
331  WRITE_MESSAGE("Found " + toString(numBufferStops) + " railway nodes marked as buffer_stop");
332  }
333 
334  for (NBEdge* e : bidiEdges) {
335  device.openTag("bidiEdge");
336  device.writeAttr(SUMO_ATTR_ID, e->getID());
337  device.writeAttr("bidi", e->getTurnDestination(true)->getID());
338  device.closeTag();
339  }
340  if (verbose) {
341  WRITE_MESSAGE("Found " + toString(bidiEdges.size()) + " bidirectional rail edges");
342  }
343 
344  device.close();
345  return brokenNodes;
346 }
347 
348 
349 std::set<NBNode*>
351  std::set<NBNode*> railNodes;
352 
353  NBEdgeCont& ec = nb.getEdgeCont();
354  int numRailEdges = 0;
355  for (auto it = ec.begin(); it != ec.end(); it++) {
356  if (isRailway(it->second->getPermissions())) {
357  numRailEdges++;
358  railNodes.insert(it->second->getFromNode());
359  railNodes.insert(it->second->getToNode());
360 
361  }
362  }
363  std::set<NBNode*> railSignals;
364  for (NBNode* node : railNodes) {
365  if (node->getType() == NODETYPE_RAIL_SIGNAL) {
366  railSignals.insert(node);
367  }
368  }
369  if (verbose) {
370  WRITE_MESSAGE("Found " + toString(numRailEdges) + " railway edges and " + toString(railNodes.size()) + " railway nodes (" + toString(railSignals.size()) + " signals).");
371  }
372  return railNodes;
373 }
374 
375 
376 bool
377 NBRailwayTopologyAnalyzer::isStraight(const NBNode* node, const NBEdge* e1, const NBEdge* e2) {
378  const double relAngle = NBHelpers::normRelAngle(e1->getAngleAtNode(node), e2->getAngleAtNode(node));
379  /*
380  std::cout << " isStraight n=" << node->getID()
381  << " e1=" << e1->getID()
382  << " e2=" << e2->getID()
383  << " a1=" << e1->getAngleAtNode(node)
384  << " a2=" << e2->getAngleAtNode(node)
385  << " rel=" << relAngle
386  << "\n";
387  */
388  if ((e1->getToNode() == node && e2->getFromNode() == node)
389  || (e1->getFromNode() == node && e2->getToNode() == node)) {
390  // edges go in the same direction
391  return fabs(relAngle) < SHARP_THRESHOLD;
392  } else {
393  // edges go in the opposite direction (both incoming or outgoing)
394  return fabs(relAngle) > SHARP_THRESHOLD_SAMEDIR;
395  }
396 }
397 
398 
399 bool
401  const EdgeVector& edges2) {
402 #ifdef DEBUG_SEQSTOREVERSE
403  //if (node->getID() == DEBUGNODEID2) {
404  // std::cout << " edges=" << toString(edges) << " edges2=" << toString(edges2) << "\n";
405  //}
406 #endif
407  for (NBEdge* e1 : edges) {
408  for (NBEdge* e2 : edges2) {
409  //if (e1->getID() == "195411601#2" && e2->getID() == "93584120#3") {
410  // std::cout
411  // << " DEBUG normRelA=" << NBHelpers::normRelAngle(
412  // e1->getAngleAtNode(node),
413  // e2->getAngleAtNode(node))
414  // << "\n";
415  //}
416  if (e1 != e2 && isStraight(node, e1, e2)) {
417  return true;
418  }
419  }
420  }
421  return false;
422 }
423 
424 
425 bool
426 NBRailwayTopologyAnalyzer::allBroken(const NBNode* node, NBEdge* candOut, const EdgeVector& in, const EdgeVector& out) {
427  for (NBEdge* e : in) {
428  if (e != candOut && isStraight(node, e, candOut)) {
429  if (gDebugFlag1) {
430  std::cout << " isStraight e=" << e->getID() << " candOut=" << candOut->getID() << "\n";
431  }
432  return false;
433  }
434  }
435  for (NBEdge* e : out) {
436  if (e != candOut && !isStraight(node, e, candOut)) {
437  if (gDebugFlag1) {
438  std::cout << " isSharp e=" << e->getID() << " candOut=" << candOut->getID() << "\n";
439  }
440  return false;
441  }
442  }
443  return true;
444 }
445 
446 
447 bool
448 NBRailwayTopologyAnalyzer::allSharp(const NBNode* node, const EdgeVector& in, const EdgeVector& out, bool countBidiAsSharp) {
449  bool allBidi = true;
450  for (NBEdge* e1 : in) {
451  for (NBEdge* e2 : out) {
452  if (e1 != e2 && isStraight(node, e1, e2)) {
453  return false;
454  }
455  if (!e1->isBidiRail(true)) {
456  //std::cout << " allSharp node=" << node->getID() << " e1=" << e1->getID() << " is not bidi\n";
457  allBidi = false;
458  }
459  }
460  }
461  return !allBidi || countBidiAsSharp;
462 }
463 
464 
465 bool
467  for (NBEdge* e : edges) {
468  if (!e->isBidiRail()) {
469  return false;
470  }
471  }
472  return true;
473 }
474 
475 
476 int
478  int added = 0;
479  std::set<NBNode*> railNodes = getRailNodes(nb);
480  NBEdgeCont& ec = nb.getEdgeCont();
481  for (auto it = ec.begin(); it != ec.end(); it++) {
482  NBEdge* e = it->second;
483  if (e->isBidiRail()) {
484  added += extendBidiEdges(nb, e->getFromNode(), e->getTurnDestination(true));
485  added += extendBidiEdges(nb, e->getToNode(), e);
486  }
487  }
488  //if (added > 0) {
489  // std::cout << "Addeded " << added << " bidi-edges as extension of existing bidi edges\n";
490  //}
491  return added;
492 }
493 
494 
495 int
497  assert(bidiIn->getToNode() == node);
498  NBEdge* bidiOut = bidiIn->getTurnDestination(true);
499  if (bidiOut == nullptr) {
500  WRITE_WARNING("Could not find bidi-edge for edge '" + bidiIn->getID() + "'");
501  return 0;
502  }
503  EdgeVector tmpBidiOut;
504  tmpBidiOut.push_back(bidiOut);
505  EdgeVector tmpBidiIn;
506  tmpBidiIn.push_back(bidiIn);
507  int added = 0;
508  EdgeVector inRail, outRail;
509  getRailEdges(node, inRail, outRail);
510  for (NBEdge* cand : outRail) {
511  //std::cout << " extendBidiEdges n=" << node->getID() << " bidiIn=" << bidiIn->getID() << " cand=" << cand->getID() << " isStraight=" << isStraight(node, bidiIn, cand) << " allSharp=" << allSharp(node, inRail, tmpBidiOut, true) << "\n";
512  if (!cand->isBidiRail() && isStraight(node, bidiIn, cand)
513  && cand->getLaneSpreadFunction() == LANESPREAD_CENTER
514  && allSharp(node, inRail, tmpBidiOut, true)) {
515  NBEdge* e2 = addBidiEdge(nb, cand);
516  if (e2 != nullptr) {
517  added += 1 + extendBidiEdges(nb, cand->getToNode(), cand);
518  }
519  }
520  }
521  for (NBEdge* cand : inRail) {
522  //std::cout << " extendBidiEdges n=" << node->getID() << " bidiOut=" << bidiOut->getID() << " cand=" << cand->getID() << " isStraight=" << isStraight(node, cand, bidiOut) << " allSharp=" << allSharp(node, outRail, tmpBidiIn, true) << "\n";
523  if (!cand->isBidiRail() && isStraight(node, cand, bidiOut)
524  && cand->getLaneSpreadFunction() == LANESPREAD_CENTER
525  && allSharp(node, outRail, tmpBidiIn, true)) {
526  NBEdge* e2 = addBidiEdge(nb, cand);
527  if (e2 != nullptr) {
528  added += 1 + extendBidiEdges(nb, cand->getFromNode(), e2);
529  }
530  }
531  }
532  return added;
533 }
534 
535 
536 void
538  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
539  // find reversible edge sequences between broken nodes
540  std::vector<EdgeVector> seqsToReverse;
541  for (NBNode* n : brokenNodes) {
542  EdgeVector inRail, outRail;
543  getRailEdges(n, inRail, outRail);
544  for (NBEdge* start : outRail) {
545  EdgeVector tmp;
546  tmp.push_back(start);
547  // only reverse edges where the node would be unbroken afterwards
548  if (!allBroken(n, start, inRail, outRail)
549  || (inRail.size() == 1 && outRail.size() == 1)) {
550 #ifdef DEBUG_SEQSTOREVERSE
551  if (n->getID() == DEBUGNODEID) {
552  std::cout << " abort at start n=" << n->getID() << " (not all broken)\n";
553  }
554 #endif
555  continue;
556  }
557  //std::cout << " get sequences from " << start->getID() << "\n";
558  bool forward = true;
559  EdgeVector seq;
560  while (forward) {
561  seq.push_back(start);
562  //std::cout << " seq=" << toString(seq) << "\n";
563  NBNode* n2 = start->getToNode();
564  EdgeVector inRail2, outRail2;
565  getRailEdges(n2, inRail2, outRail2);
566  if (brokenNodes.count(n2) != 0) {
567  EdgeVector tmp2;
568  tmp2.push_back(start);
569  if (allBroken(n2, start, outRail2, inRail2)) {
570  seqsToReverse.push_back(seq);
571  } else {
572 #ifdef DEBUG_SEQSTOREVERSE
573  if (n->getID() == DEBUGNODEID) {
574  std::cout << " abort at n2=" << n2->getID() << " (not all broken)\n";
575  }
576 #endif
577  }
578  forward = false;
579  } else {
580  if (outRail2.size() == 0) {
581  // stop at network border
582  forward = false;
583 #ifdef DEBUG_SEQSTOREVERSE
584  if (n->getID() == DEBUGNODEID) {
585  std::cout << " abort at n2=" << n2->getID() << " (border)\n";
586  }
587 #endif
588  } else if (outRail2.size() > 1 || inRail2.size() > 1) {
589  // stop at switch
590  forward = false;
591 #ifdef DEBUG_SEQSTOREVERSE
592  if (n->getID() == DEBUGNODEID) {
593  std::cout << " abort at n2=" << n2->getID() << " (switch)\n";
594  }
595 #endif
596  } else {
597  start = outRail2.front();
598  }
599  }
600  }
601  }
602  }
603  // sort by sequence length
604  if (seqsToReverse.size() > 0) {
605  WRITE_MESSAGE("Found " + toString(seqsToReverse.size()) + " reversible edge sequences between broken rail nodes");
606  }
607  std::sort(seqsToReverse.begin(), seqsToReverse.end(),
608  [](const EdgeVector & a, const EdgeVector & b) {
609  return a.size() < b.size();
610  });
611  int numReversed = 0;
612  std::set<NBNode*> affectedEndpoints;
613  std::set<std::string> reversedIDs;
614  std::map<int, int> seqLengths;
615  for (EdgeVector& seq : seqsToReverse) {
616  NBNode* seqStart = seq.front()->getFromNode();
617  NBNode* seqEnd = seq.back()->getToNode();
618  // avoid reversing sequenes on both sides of a broken node
619  if (affectedEndpoints.count(seqStart) == 0
620  && affectedEndpoints.count(seqEnd) == 0) {
621  affectedEndpoints.insert(seqStart);
622  affectedEndpoints.insert(seqEnd);
623  //WRITE_MESSAGE(" reversed seq=" + toString(seq));
624  for (NBEdge* e : seq) {
625  e->reinitNodes(e->getToNode(), e->getFromNode());
626  e->setGeometry(e->getGeometry().reverse());
627  reversedIDs.insert(e->getID());
628  }
629  seqLengths[(int)seq.size()]++;
630  numReversed++;
631  }
632  }
633  if (numReversed > 0) {
634  WRITE_MESSAGE("Reversed " + toString(numReversed) + " sequences (count by length: " + joinToString(seqLengths, " ", ":") + ")");
635  for (auto& item : nb.getPTStopCont().getStops()) {
636  if (reversedIDs.count(item.second->getEdgeId())) {
637  item.second->findLaneAndComputeBusStopExtent(nb.getEdgeCont());
638  }
639  }
640  }
641 }
642 
643 
644 void
646  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
647  std::set<NBNode*> railNodes = getRailNodes(nb);
648  // find buffer stops and ensure that thay are connect to the network in both directions
649  int numBufferStops = 0;
650  int numAddedBidiTotal = 0;
651  for (NBNode* node : railNodes) {
652  if (StringUtils::toBool(node->getParameter("buffer_stop", "false"))) {
653  if (node->getEdges().size() != 1) {
654  WRITE_WARNING("Ignoring buffer stop junction '" + node->getID() + "' with " + toString(node->getEdges().size()) + " edges\n");
655  continue;
656  }
657  int numAddedBidi = 0;
658  numBufferStops++;
659  NBEdge* prev = nullptr;
660  NBEdge* prev2 = nullptr;
661  EdgeVector inRail, outRail;
662  getRailEdges(node, inRail, outRail);
663  bool addAway = true; // add new edges away from buffer stop
664  while (prev == nullptr || (inRail.size() + outRail.size()) == 3) {
665  NBEdge* e = nullptr;
666  if (prev == nullptr) {
667  assert(node->getEdges().size() == 1);
668  e = node->getEdges().front();
669  addAway = node == e->getToNode();
670  } else {
671  if (addAway) {
672  // XXX if node is broken we need to switch direction
673  assert(inRail.size() == 2);
674  e = inRail.front() == prev2 ? inRail.back() : inRail.front();
675  } else {
676  // XXX if node is broken we need to switch direction
677  assert(outRail.size() == 2);
678  e = outRail.front() == prev2 ? outRail.back() : outRail.front();
679  }
680  }
682  NBNode* e2From = nullptr;
683  NBNode* e2To = nullptr;
684  if (addAway) {
685  e2From = node;
686  e2To = e->getFromNode();
687  node = e2To;
688  } else {
689  e2From = e->getToNode();
690  e2To = node;
691  node = e2From;
692  }
693  NBEdge* e2 = addBidiEdge(nb, e);
694  if (e2 == nullptr) {
695  break;
696  }
697  prev = e;
698  prev2 = e2;
699  numAddedBidi++;
700  numAddedBidiTotal++;
701  inRail.clear();
702  outRail.clear();
703  getRailEdges(node, inRail, outRail);
704  }
705  //if (numAddedBidi > 0) {
706  // WRITE_MESSAGE(" added " + toString(numAddedBidi) + " edges between buffer stop junction '" + bufferStop->getID() + "' and junction '" + node->getID() + "'");
707  //}
708  }
709  }
710  if (numAddedBidiTotal > 0) {
711  WRITE_MESSAGE("Added " + toString(numAddedBidiTotal) + " edges to connect " + toString(numBufferStops) + " buffer stops in both directions.");
712  }
713 }
714 
715 NBEdge*
717  EdgeVector inRail, outRail;
718  getRailEdges(n, inRail, outRail);
719  if (inRail.size() == 2 && outRail.size() == 1 && isStraight(n, inRail.front(), inRail.back())) {
720  if (isStraight(n, inRail.front(), outRail.front())) {
721  return inRail.front();
722  } else if (isStraight(n, inRail.back(), outRail.front())) {
723  return inRail.back();
724  }
725  }
726  if (inRail.size() == 1 && outRail.size() == 2 && isStraight(n, outRail.front(), outRail.back())) {
727  if (isStraight(n, outRail.front(), inRail.front())) {
728  return outRail.front();
729  } else if (isStraight(n, outRail.back(), inRail.front())) {
730  return outRail.back();
731  }
732  }
733  return nullptr;
734 }
735 
736 
737 void
739  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
740  std::map<int, int> seqLengths;
741  int numAdded = 0;
742  int numSeqs = 0;
743  for (NBNode* n : brokenNodes) {
744  NBEdge* edge = isBidiSwitch(n);
745  if (edge != nullptr) {
746  std::vector<NBNode*> nodeSeq;
747  EdgeVector edgeSeq;
748  NBNode* prev = n;
749  nodeSeq.push_back(prev);
750  edgeSeq.push_back(edge);
751  bool forward = true;
752  //std::cout << "Looking for potential bidi-edge sequence starting at junction '" << n->getID() << "' with edge '" + edge->getID() << "'\n";
753  // find a suitable end point for adding bidi edges
754  while (forward) {
755  NBNode* next = edge->getFromNode() == prev ? edge->getToNode() : edge->getFromNode();
756  EdgeVector allRail;
757  getRailEdges(next, allRail, allRail);
758  if (allRail.size() == 2 && isStraight(next, allRail.front(), allRail.back())) {
759  prev = next;
760  edge = allRail.front() == edge ? allRail.back() : allRail.front();
761  nodeSeq.push_back(prev);
762  edgeSeq.push_back(edge);
763  } else {
764  forward = false;
765  EdgeVector inRail2, outRail2;
766  getRailEdges(next, inRail2, outRail2);
767  if (isBidiSwitch(next) == edge) {
768  // suitable switch found as endpoint, add reverse edges
769  //WRITE_MESSAGE("Adding " + toString(edgeSeq.size())
770  // + " bidi-edges between switches junction '" + n->getID() + "' and junction '" + next->getID() + "'");
771  for (NBEdge* e : edgeSeq) {
772  addBidiEdge(nb, e);
773  }
774  seqLengths[(int)edgeSeq.size()]++;
775  numSeqs++;
776  numAdded += (int)edgeSeq.size();
777  } else {
778  //std::cout << " sequence ended at junction " << next->getID()
779  // << " in=" << inRail2.size()
780  // << " out=" << outRail2.size()
781  // << " bidiSwitch=" << Named::getIDSecure(isBidiSwitch(next))
782  // << "\n";
783  }
784 
785  }
786  }
787 
788  }
789  }
790  if (seqLengths.size() > 0) {
791  WRITE_MESSAGE("Added " + toString(numAdded) + " bidi-edges between " + toString(numSeqs) + " pairs of railway switches (count by length: " + joinToString(seqLengths, " ", ":") + ")");
792  }
793 }
794 
795 
796 void
798  // generate bidirectional routing graph
799  NBEdgeCont& ec = nb.getEdgeCont();
800  std::vector<Track*> tracks;
801  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
802  tracks.push_back(new Track(edge));
803  }
804  const int numEdges = (int)tracks.size();
805  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
806  tracks.push_back(new Track(edge, (int)tracks.size(), edge->getID() + "_reverse"));
807  }
808  // add special tracks for starting end ending in both directions
809  std::map<NBEdge*, std::pair<Track*, Track*> > stopTracks;
810  for (NBEdge* edge : nb.getEdgeCont().getAllEdges()) {
811  if ((edge->getPermissions() & SVC_RAIL_CLASSES) != 0) {
812  Track* start = new Track(edge, (int)tracks.size(), edge->getID() + "_start");
813  tracks.push_back(start);
814  Track* end = new Track(edge, (int)tracks.size(), edge->getID() + "_end");
815  tracks.push_back(end);
816  stopTracks[edge] = std::make_pair(start, end);
817  }
818  }
819  // set successors based on angle (connections are not yet built)
820  for (NBNode* node : getRailNodes(nb)) {
821  EdgeVector railEdges;
822  getRailEdges(node, railEdges, railEdges);
823  for (NBEdge* e1 : railEdges) {
824  for (NBEdge* e2 : railEdges) {
825  if (e1 != e2 && isStraight(node, e1, e2)) {
826  int i = e1->getNumericalID();
827  int i2 = e2->getNumericalID();
828  if (e1->getToNode() == node) {
829  if (e2->getFromNode() == node) {
830  // case 1) plain forward connection
831  tracks[i]->addSuccessor(tracks[i2]);
832  // reverse edge (numerical id incremented by numEdges)
833  tracks[i2 + numEdges]->addSuccessor(tracks[i + numEdges]);
834  } else {
835  // case 2) both edges pointing towards each ohter
836  tracks[i]->addSuccessor(tracks[i2 + numEdges]);
837  tracks[i2]->addSuccessor(tracks[i + numEdges]);
838  }
839  } else {
840  if (e2->getFromNode() == node) {
841  // case 3) both edges pointing away from each other
842  tracks[i + numEdges]->addSuccessor(tracks[i2]);
843  tracks[i2 + numEdges]->addSuccessor(tracks[i]);
844  } else {
845  // already handled via case 1)
846  }
847  }
848 
849  }
850  }
851  }
852  }
853  // define start and end successors
854  for (auto& item : stopTracks) {
855  const int index = item.first->getNumericalID();
856  // start
857  item.second.first->addSuccessor(tracks[index]);
858  item.second.first->addSuccessor(tracks[index + numEdges]);
859  // end
860  tracks[index]->addSuccessor(item.second.second);
861  tracks[index + numEdges]->addSuccessor(item.second.second);
862  }
863  // DEBUG
864  /*
865  for (Track* t : tracks) {
866  std::cout << "track " << t->getID() << " e=" << t->edge->getID() << " i=" << t->getNumericalID() << " succ:\n";
867  for (Track* s : t->getSuccessors(SVC_IGNORING)) {
868  std::cout << " succ=" << s->getID() << "\n";
869  }
870  }
871  */
872 
875  tracks, true, &NBRailwayTopologyAnalyzer::getTravelTimeStatic, nullptr, true);
876 
877  int added = 0;
878  int numDisconnected = 0;
879  std::set<NBEdge*> addBidiStops;
880  std::set<NBEdge*> addBidiEdges;
881  std::set<std::pair<NBPTStop*, NBPTStop*> > visited;
882  for (const auto& item : nb.getPTLineCont().getLines()) {
883  NBPTLine* line = item.second;
884  std::vector<NBPTStop*> stops = line->getStops();
885  if (stops.size() < 2) {
886  continue;
887  }
888  for (auto it = stops.begin(); it + 1 != stops.end(); ++it) {
889  std::pair<NBPTStop*, NBPTStop*> trip(*it, *(it + 1));
890  if (visited.count(trip) != 0) {
891  continue;
892  } else {
893  visited.insert(trip);
894  }
895  NBEdge* fromEdge = ec.getByID((*it)->getEdgeId());
896  NBEdge* toEdge = ec.getByID((*(it + 1))->getEdgeId());
897  if (fromEdge == nullptr || toEdge == nullptr) {
898  continue;
899  }
900  if (stopTracks.count(fromEdge) == 0
901  || stopTracks.count(toEdge) == 0) {
902  continue;
903  }
904  NBVehicle veh(line->getRef(), (SUMOVehicleClass)(fromEdge->getPermissions() & SVC_RAIL_CLASSES));
905  std::vector<const Track*> route;
906  router->compute(stopTracks[fromEdge].first, stopTracks[toEdge].second, &veh, 0, route);
907  //if (fromEdge->getID() == "356053025#1" && toEdge->getID() == "23256161") {
908  // std::cout << "DEBUG: route=" << toString(route) << "\n";
909  //}
910  if (route.size() > 0) {
911  assert(route.size() > 2);
912  for (int i = 1; i < (int)route.size() - 1; ++i) {
913  if (route[i]->getNumericalID() >= numEdges) {
914  NBEdge* edge = route[i]->edge;
915  if (addBidiEdges.count(edge) == 0) {
916  if (!edge->isBidiRail(true)) {
917  bool isStop = i == 1 || i == (int)route.size() - 2;
918  if (edge->getLaneSpreadFunction() == LANESPREAD_CENTER) {
919  addBidiEdges.insert(edge);
920  if (isStop) {
921  addBidiStops.insert(edge);
922  }
923  } else {
924  if (isStop) {
925  WRITE_WARNING("Stop on edge " + fromEdge->getID() + " can only be reached in reverse but edge has the wrong spreadType");
926  }
927  }
928  }
929  }
930  }
931  }
932  } else {
933  WRITE_WARNING("No connection found between stops on edge '" + fromEdge->getID() + "' and edge '" + toEdge->getID() + "'");
934  numDisconnected++;
935  }
936  }
937  }
938  for (NBEdge* edge : addBidiEdges) {
939  if (!edge->isBidiRail()) {
940  NBEdge* e2 = addBidiEdge(nb, edge);
941  //std::cout << " add bidiEdge for stop at edge " << edge->getID() << "\n";
942  if (e2 != nullptr) {
943  added++;
944  added += extendBidiEdges(nb, edge->getToNode(), edge);
945  added += extendBidiEdges(nb, edge->getFromNode(), e2);
946  }
947  }
948  }
949 
950  if (addBidiEdges.size() > 0 || numDisconnected > 0) {
951  WRITE_MESSAGE("Added " + toString(addBidiStops.size()) + " bidi-edges for public transport stops and a total of "
952  + toString(added) + " bidi-edges to ensure connectivity of stops ("
953  + toString(numDisconnected) + " stops remain disconnected)");
954  }
955 
956  // clean up
957  for (Track* t : tracks) {
958  delete t;
959  }
960  delete router;
961 }
962 
963 
964 void
966  int added = 0;
967  std::set<NBNode*> brokenNodes = getBrokenRailNodes(nb);
968  for (const auto& e : nb.getEdgeCont()) {
969  if (!isRailway(e.second->getPermissions())) {
970  continue;
971  }
972  NBNode* const from = e.second->getFromNode();
973  NBNode* const to = e.second->getToNode();
974  if (brokenNodes.count(from) == 0 && brokenNodes.count(to) == 0) {
975  continue;
976  }
977  EdgeVector inRailFrom, outRailFrom, inRailTo, outRailTo;
978  getRailEdges(from, inRailFrom, outRailFrom);
979  getRailEdges(to, inRailTo, outRailTo);
980  bool haveReverse = false;
981  for (const NBEdge* cand : outRailTo) {
982  if (cand->getToNode() == from) {
983  haveReverse = true;
984  break;
985  }
986  }
987  if (haveReverse) {
988  continue;
989  }
990  bool haveStraightFrom = false;
991  for (const NBEdge* fromStraightCand : outRailFrom) {
992  if (fromStraightCand != e.second && isStraight(from, fromStraightCand, e.second)) {
993  haveStraightFrom = true;
994  break;
995  }
996  }
997  if (!haveStraightFrom) {
998  continue;
999  }
1000  for (const NBEdge* toStraightCand : inRailTo) {
1001  if (toStraightCand != e.second && isStraight(to, toStraightCand, e.second)) {
1002  NBEdge* e2 = addBidiEdge(nb, e.second);
1003  //std::cout << " add bidiEdge for straight connectivity at edge " << e.second->getID() << " fromBroken=" << brokenNodes.count(from) << " toBroken=" << brokenNodes.count(to) << "\n";
1004  if (e2 != nullptr) {
1005  added++;
1006  added += extendBidiEdges(nb, to, e.second);
1007  added += extendBidiEdges(nb, from, e2);
1008  }
1009  break;
1010  }
1011  }
1012  }
1013  if (added > 0) {
1014  WRITE_MESSAGE("Added " + toString(added) + " bidi-edges to ensure connectivity of straight tracks.");
1015  }
1016 }
1017 
1018 
1019 void
1023 }
1024 
1025 
1026 double
1027 NBRailwayTopologyAnalyzer::getTravelTimeStatic(const Track* const track, const NBVehicle* const veh, double time) {
1028  return NBEdge::getTravelTimeStatic(track->edge, veh, time);
1029 }
1030 
1031 /****************************************************************************/
1032 
LaneSpreadFunction getLaneSpreadFunction() const
Returns how this edge&#39;s lanes&#39; lateral offset is computed.
Definition: NBEdge.h:762
bool gDebugFlag1
global utility flags for debugging
Definition: StdDefs.cpp:33
void invalidateConnections(bool reallowSetting=false)
invalidate current connections of edge
Definition: NBEdge.cpp:1363
#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...
const std::map< std::string, NBPTLine * > & getLines() const
Definition: NBPTLineCont.h:39
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:86
bool isBidiRail(bool ignoreSpread=false) const
whether this edge is part of a bidirectional railway
Definition: NBEdge.cpp:683
NBPTStopCont & getPTStopCont()
Returns a reference to the pt stop container.
Definition: NBNetBuilder.h:177
NBEdge * getTurnDestination(bool possibleDestination=false) const
Definition: NBEdge.cpp:3116
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:182
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:77
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:239
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:264
static bool toBool(const std::string &sData)
converts a string into the bool value described by it by calling the char-type converter ...
const std::string & getRef() const
get line reference (not unique)
Definition: NBPTLine.h:61
void invalidateIncomingConnections()
invalidate incoming connections
Definition: NBNode.cpp:1665
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:48
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:151
static void getRailEdges(const NBNode *node, EdgeVector &inEdges, EdgeVector &outEdges)
filter out rail edges among all edges of a the given node
const std::string & getID() const
Definition: NBEdge.h:1364
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
#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:1863
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:3441
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:680
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:259
Instance responsible for building networks.
Definition: NBNetBuilder.h:110
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:35
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:1335
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)
std::vector< NBPTStop * > getStops()
Definition: NBPTLine.cpp:41
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:479
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:877
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:240
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:486
std::string joinToString(const std::vector< T > &v, const T_BETWEEN &between, std::streamsize accuracy=gPrecision)
Definition: ToString.h:247
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.