SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NBRequest.cpp
Go to the documentation of this file.
1 /****************************************************************************/
10 // This class computes the logic of a junction
11 /****************************************************************************/
12 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
13 // Copyright (C) 2001-2013 DLR (http://www.dlr.de/) and contributors
14 /****************************************************************************/
15 //
16 // This file is part of SUMO.
17 // SUMO is free software: you can redistribute it and/or modify
18 // it under the terms of the GNU General Public License as published by
19 // the Free Software Foundation, either version 3 of the License, or
20 // (at your option) any later version.
21 //
22 /****************************************************************************/
23 
24 
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #ifdef _MSC_VER
29 #include <windows_config.h>
30 #else
31 #include <config.h>
32 #endif
33 
34 #include <string>
35 #include <vector>
36 #include <set>
37 #include <algorithm>
38 #include <bitset>
39 #include <sstream>
40 #include <map>
41 #include <cassert>
43 #include <utils/common/ToString.h>
46 #include "NBEdge.h"
47 #include "NBContHelper.h"
48 #include "NBTrafficLightLogic.h"
50 #include "NBNode.h"
51 #include "NBRequest.h"
52 
53 #ifdef CHECK_MEMORY_LEAKS
54 #include <foreign/nvwa/debug_new.h>
55 #endif // CHECK_MEMORY_LEAKS
56 
57 
58 // ===========================================================================
59 // static member variables
60 // ===========================================================================
61 size_t NBRequest::myGoodBuilds = 0;
62 size_t NBRequest::myNotBuild = 0;
63 
64 
65 // ===========================================================================
66 // method definitions
67 // ===========================================================================
69  NBNode* junction,
70  const EdgeVector& all,
71  const EdgeVector& incoming,
72  const EdgeVector& outgoing,
73  const NBConnectionProhibits& loadedProhibits)
74  : myJunction(junction),
75  myAll(all), myIncoming(incoming), myOutgoing(outgoing) {
76  size_t variations = myIncoming.size() * myOutgoing.size();
77  // build maps with information which forbidding connection were
78  // computed and what's in there
79  myForbids.reserve(variations);
80  myDone.reserve(variations);
81  for (size_t i = 0; i < variations; i++) {
82  myForbids.push_back(LinkInfoCont(variations, false));
83  myDone.push_back(LinkInfoCont(variations, false));
84  }
85  // insert loaded prohibits
86  for (NBConnectionProhibits::const_iterator j = loadedProhibits.begin(); j != loadedProhibits.end(); j++) {
87  NBConnection prohibited = (*j).first;
88  bool ok1 = prohibited.check(ec);
89  if (find(myIncoming.begin(), myIncoming.end(), prohibited.getFrom()) == myIncoming.end()) {
90  ok1 = false;
91  }
92  if (find(myOutgoing.begin(), myOutgoing.end(), prohibited.getTo()) == myOutgoing.end()) {
93  ok1 = false;
94  }
95  int idx1 = 0;
96  if (ok1) {
97  idx1 = getIndex(prohibited.getFrom(), prohibited.getTo());
98  if (idx1 < 0) {
99  ok1 = false;
100  }
101  }
102  const NBConnectionVector& prohibiting = (*j).second;
103  for (NBConnectionVector::const_iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
104  NBConnection sprohibiting = *k;
105  bool ok2 = sprohibiting.check(ec);
106  if (find(myIncoming.begin(), myIncoming.end(), sprohibiting.getFrom()) == myIncoming.end()) {
107  ok2 = false;
108  }
109  if (find(myOutgoing.begin(), myOutgoing.end(), sprohibiting.getTo()) == myOutgoing.end()) {
110  ok2 = false;
111  }
112  if (ok1 && ok2) {
113  int idx2 = getIndex(sprohibiting.getFrom(), sprohibiting.getTo());
114  if (idx2 < 0) {
115  ok2 = false;
116  } else {
117  myForbids[idx2][idx1] = true;
118  myDone[idx2][idx1] = true;
119  myDone[idx1][idx2] = true;
120  myGoodBuilds++;
121  }
122  } else {
123  std::string pfID = prohibited.getFrom() != 0 ? prohibited.getFrom()->getID() : "UNKNOWN";
124  std::string ptID = prohibited.getTo() != 0 ? prohibited.getTo()->getID() : "UNKNOWN";
125  std::string bfID = sprohibiting.getFrom() != 0 ? sprohibiting.getFrom()->getID() : "UNKNOWN";
126  std::string btID = sprohibiting.getTo() != 0 ? sprohibiting.getTo()->getID() : "UNKNOWN";
127  WRITE_WARNING("could not prohibit " + pfID + "->" + ptID + " by " + bfID + "->" + btID);
128  myNotBuild++;
129  }
130  }
131  }
132  // ok, check whether someone has prohibited two links vice versa
133  // (this happens also in some Vissim-networks, when edges are joined)
134  size_t no = myIncoming.size() * myOutgoing.size();
135  for (size_t s1 = 0; s1 < no; s1++) {
136  for (size_t s2 = s1 + 1; s2 < no; s2++) {
137  // not set, yet
138  if (!myDone[s1][s2]) {
139  continue;
140  }
141  // check whether both prohibit vice versa
142  if (myForbids[s1][s2] && myForbids[s2][s1]) {
143  // mark unset - let our algorithm fix it later
144  myDone[s1][s2] = false;
145  myDone[s2][s1] = false;
146  }
147  }
148  }
149 }
150 
151 
153 
154 
155 void
157  EdgeVector::const_iterator i, j;
158  for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
159  for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
160  computeRightOutgoingLinkCrossings(leftHanded, *i, *j);
161  computeLeftOutgoingLinkCrossings(leftHanded, *i, *j);
162  }
163  }
164  // reset signalised/non-signalised dependencies
165  resetSignalised();
166  // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
168 }
169 
170 
171 void
173  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
174  while (*pfrom != to) {
176  if ((*pfrom)->getToNode() == myJunction) {
177  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
178  while (*pto != from) {
179  if (!((*pto)->getToNode() == myJunction)) {
180  setBlocking(leftHanded, from, to, *pfrom, *pto);
181  }
183  }
184  }
185  }
186 }
187 
188 
189 void
191  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
192  while (*pfrom != to) {
193  NBContHelper::nextCW(myAll, pfrom);
194  if ((*pfrom)->getToNode() == myJunction) {
195  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
196  while (*pto != from) {
197  if (!((*pto)->getToNode() == myJunction)) {
198  setBlocking(leftHanded, from, to, *pfrom, *pto);
199  }
201  }
202  }
203  }
204 }
205 
206 
207 void
208 NBRequest::setBlocking(bool leftHanded,
209  NBEdge* from1, NBEdge* to1,
210  NBEdge* from2, NBEdge* to2) {
211  // check whether one of the links has a dead end
212  if (to1 == 0 || to2 == 0) {
213  return;
214  }
215  // get the indices of both links
216  int idx1 = getIndex(from1, to1);
217  int idx2 = getIndex(from2, to2);
218  if (idx1 < 0 || idx2 < 0) {
219  return; // !!! error output? did not happend, yet
220  }
221  // check whether the link crossing has already been checked
222  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
223  if (myDone[idx1][idx2]) {
224  return;
225  }
226  // mark the crossings as done
227  myDone[idx1][idx2] = true;
228  myDone[idx2][idx1] = true;
229  // check if one of the links is a turn; this link is always not priorised
230  // true for right-before-left and priority
231  if (from1->isTurningDirectionAt(myJunction, to1)) {
232  myForbids[idx2][idx1] = true;
233  return;
234  }
235  if (from2->isTurningDirectionAt(myJunction, to2)) {
236  myForbids[idx1][idx2] = true;
237  return;
238  }
239 
240  // check the priorities if required by node type
242  int from1p = from1->getJunctionPriority(myJunction);
243  int from2p = from2->getJunctionPriority(myJunction);
244  // check if one of the connections is higher priorised when incoming into
245  // the junction, the connection road will yield
246  if (from1p > from2p) {
247  myForbids[idx1][idx2] = true;
248  return;
249  }
250  if (from2p > from1p) {
251  myForbids[idx2][idx1] = true;
252  return;
253  }
254  }
255 
256  // check whether one of the connections is higher priorised on
257  // the outgoing edge when both roads are high priorised
258  // the connection with the lower priorised outgoing edge will lead
259  // should be valid for priority junctions only
260  /*
261  if (from1p > 0 && from2p > 0) {
262  assert(myJunction->getType() != NODETYPE_RIGHT_BEFORE_LEFT);
263  int to1p = to1->getJunctionPriority(myJunction);
264  int to2p = to2->getJunctionPriority(myJunction);
265  if (to1p > to2p) {
266  myForbids[idx1][idx2] = true;
267  return;
268  }
269  if (to2p > to1p) {
270  myForbids[idx2][idx1] = true;
271  return;
272  }
273  }
274  */
275 
276  // compute the yielding due to the right-before-left rule
277  // get the position of the incoming lanes in the junction-wheel
278  EdgeVector::const_iterator c1 = find(myAll.begin(), myAll.end(), from1);
280  // go through next edges clockwise...
281  while (*c1 != from1 && *c1 != from2) {
282  if (*c1 == to2) {
283  // if we encounter to2 the second one prohibits the first
284  if (!leftHanded) {
285  myForbids[idx2][idx1] = true;
286  } else {
287  myForbids[idx1][idx2] = true;
288  }
289  return;
290  }
292  }
293  // get the position of the incoming lanes in the junction-wheel
294  EdgeVector::const_iterator c2 = find(myAll.begin(), myAll.end(), from2);
296  // go through next edges clockwise...
297  while (*c2 != from2 && *c2 != from1) {
298  if (*c2 == to1) {
299  // if we encounter to1 the second one prohibits the first
300  if (!leftHanded) {
301  myForbids[idx1][idx2] = true;
302  } else {
303  myForbids[idx2][idx1] = true;
304  }
305  return;
306  }
308  }
309 }
310 
311 
312 size_t
314  EdgeVector::const_iterator p = find(myAll.begin(), myAll.end(), from);
315  size_t ret = 0;
316  do {
317  ret++;
318  if (p == myAll.begin()) {
319  p = myAll.end();
320  }
321  p--;
322  } while (*p != to);
323  return ret;
324 }
325 
326 
327 void
328 NBRequest::writeLogic(std::string /* key */, OutputDevice& into) const {
329  int pos = 0;
330  EdgeVector::const_iterator i;
331  for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
332  unsigned int noLanes = (*i)->getNumLanes();
333  for (unsigned int k = 0; k < noLanes; k++) {
334  pos = writeLaneResponse(into, *i, k, pos);
335  }
336  }
337 }
338 
339 
340 void
342  // go through possible prohibitions
343  for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
344  unsigned int noLanesEdge1 = (*i11)->getNumLanes();
345  for (unsigned int j1 = 0; j1 < noLanesEdge1; j1++) {
346  std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
347  for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
348  int idx1 = getIndex((*i11), (*i12).toEdge);
349  if (idx1 < 0) {
350  continue;
351  }
352  // go through possibly prohibited
353  for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
354  unsigned int noLanesEdge2 = (*i21)->getNumLanes();
355  for (unsigned int j2 = 0; j2 < noLanesEdge2; j2++) {
356  std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
357  for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
358  int idx2 = getIndex((*i21), (*i22).toEdge);
359  if (idx2 < 0) {
360  continue;
361  }
362  // check
363  // same incoming connections do not prohibit each other
364  if ((*i11) == (*i21)) {
365  myForbids[idx1][idx2] = false;
366  myForbids[idx2][idx1] = false;
367  continue;
368  }
369  // check other
370  // if both are non-signalised or both are signalised
371  if (((*i12).tlID == "" && (*i22).tlID == "")
372  ||
373  ((*i12).tlID != "" && (*i22).tlID != "")) {
374  // do nothing
375  continue;
376  }
377  // supposing, we don not have to
378  // brake if we are no foes
379  if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
380  continue;
381  }
382  // otherwise:
383  // the non-signalised must break
384  if ((*i12).tlID != "") {
385  myForbids[idx1][idx2] = true;
386  myForbids[idx2][idx1] = false;
387  } else {
388  myForbids[idx1][idx2] = false;
389  myForbids[idx2][idx1] = true;
390  }
391  }
392  }
393  }
394  }
395  }
396  }
397 }
398 
399 
400 std::pair<unsigned int, unsigned int>
402  unsigned int noLanes = 0;
403  unsigned int noLinks = 0;
404  for (EdgeVector::const_iterator i = myIncoming.begin();
405  i != myIncoming.end(); i++) {
406  unsigned int noLanesEdge = (*i)->getNumLanes();
407  for (unsigned int j = 0; j < noLanesEdge; j++) {
408  unsigned int numConnections = (unsigned int)(*i)->getConnectionsFromLane(j).size();
409  noLinks += numConnections;
410  if (numConnections > 0) {
411  noLanes++;
412  }
413  }
414  }
415  return std::make_pair(noLanes, noLinks);
416 }
417 
418 
419 bool
420 NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
421  const NBEdge* const from2, const NBEdge* const to2) const {
422  // unconnected edges do not forbid other edges
423  if (to1 == 0 || to2 == 0) {
424  return false;
425  }
426  // get the indices
427  int idx1 = getIndex(from1, to1);
428  int idx2 = getIndex(from2, to2);
429  if (idx1 < 0 || idx2 < 0) {
430  return false; // sure? (The connection does not exist within this junction)
431  }
432  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
433  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
434  return myForbids[idx1][idx2] || myForbids[idx2][idx1];
435 }
436 
437 
438 bool
439 NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
440  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
441  bool regardNonSignalisedLowerPriority) const {
442  // unconnected edges do not forbid other edges
443  if (possProhibitorTo == 0 || possProhibitedTo == 0) {
444  return false;
445  }
446  // get the indices
447  int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
448  int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
449  if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
450  return false; // sure? (The connection does not exist within this junction)
451  }
452  assert((size_t) possProhibitorIdx < myIncoming.size()*myOutgoing.size());
453  assert((size_t) possProhibitedIdx < myIncoming.size()*myOutgoing.size());
454  // check simple right-of-way-rules
455  if (!regardNonSignalisedLowerPriority) {
456  return myForbids[possProhibitorIdx][possProhibitedIdx];
457  }
458  // if its not forbidden, report
459  if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
460  return false;
461  }
462  // do not forbid a signalised stream by a non-signalised
463  if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
464  return false;
465  }
466  return true;
467 }
468 
469 
470 int
472  int fromLane, int pos) const {
473  std::vector<NBEdge::Connection> connected = from->getConnectionsFromLane(fromLane);
474  for (std::vector<NBEdge::Connection>::iterator j = connected.begin(); j != connected.end(); j++) {
476  od.writeAttr(SUMO_ATTR_INDEX, pos++);
477  od.writeAttr(SUMO_ATTR_RESPONSE, getResponseString(from, (*j).toEdge, fromLane, (*j).mayDefinitelyPass));
478  od.writeAttr(SUMO_ATTR_FOES, getFoesString(from, (*j).toEdge));
479  if (!OptionsCont::getOptions().getBool("no-internal-links")) {
480  od.writeAttr(SUMO_ATTR_CONT, j->haveVia);
481  }
482  od.closeTag();
483  }
484  return pos;
485 }
486 
487 
488 std::string
489 NBRequest::getResponseString(const NBEdge* const from, const NBEdge* const to,
490  int fromLane, bool mayDefinitelyPass) const {
491  int idx = 0;
492  if (to != 0) {
493  idx = getIndex(from, to);
494  }
495  std::string result;
496  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
497  //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
498  unsigned int noLanes = (*i)->getNumLanes();
499  for (int j = noLanes; j-- > 0;) {
500  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
501  int size = (int) connected.size();
502  for (int k = size; k-- > 0;) {
503  if (mayDefinitelyPass) {
504  result += '0';
505  } else if (to == 0) {
506  // should wait if no further connection!?
507  result += '1';
508  } else if ((*i) == from && fromLane == j) {
509  // do not prohibit a connection by others from same lane
510  result += '0';
511  } else {
512  assert(k < (int) connected.size());
513  assert((size_t) idx < myIncoming.size()*myOutgoing.size());
514  assert(connected[k].toEdge == 0 || (size_t) getIndex(*i, connected[k].toEdge) < myIncoming.size()*myOutgoing.size());
515  // check whether the connection is prohibited by another one
516  if (connected[k].toEdge != 0 && myForbids[getIndex(*i, connected[k].toEdge)][idx]) {
517  result += '1';
518  continue;
519  }
520  result += '0';
521  }
522  }
523  }
524  }
525  return result;
526 }
527 
528 
529 std::string
531  // remember the case when the lane is a "dead end" in the meaning that
532  // vehicles must choose another lane to move over the following
533  // junction
534  // !!! move to forbidden
535  std::string result;
536  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin();
537  i != myIncoming.rend(); i++) {
538 
539  unsigned int noLanes = (*i)->getNumLanes();
540  for (unsigned int j = noLanes; j-- > 0;) {
541  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
542  int size = (int) connected.size();
543  for (int k = size; k-- > 0;) {
544  if (to == 0) {
545  result += '0';
546  } else {
547 // if (foes(from, to, (*i), connected[k].edge) && !isInnerEnd) {
548  if (foes(from, to, (*i), connected[k].toEdge)) {
549  result += '1';
550  } else {
551  result += '0';
552  }
553  }
554  }
555  }
556  }
557  return result;
558 }
559 
560 
561 int
562 NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
563  EdgeVector::const_iterator fp = find(myIncoming.begin(), myIncoming.end(), from);
564  EdgeVector::const_iterator tp = find(myOutgoing.begin(), myOutgoing.end(), to);
565  if (fp == myIncoming.end() || tp == myOutgoing.end()) {
566  return -1;
567  }
568  // compute the index
569  return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
570 }
571 
572 
573 std::ostream&
574 operator<<(std::ostream& os, const NBRequest& r) {
575  size_t variations = r.myIncoming.size() * r.myOutgoing.size();
576  for (size_t i = 0; i < variations; i++) {
577  os << i << ' ';
578  for (size_t j = 0; j < variations; j++) {
579  if (r.myForbids[i][j]) {
580  os << '1';
581  } else {
582  os << '0';
583  }
584  }
585  os << std::endl;
586  }
587  os << std::endl;
588  return os;
589 }
590 
591 
592 bool
593 NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to) const {
594  // vehicles which do not have a following lane must always decelerate to the end
595  if (to == 0) {
596  return true;
597  }
598  // get the indices
599  int idx2 = getIndex(from, to);
600  if (idx2 == -1) {
601  return false;
602  }
603  // go through all (existing) connections;
604  // check whether any of these forbids the one to determine
605  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
606  for (size_t idx1 = 0; idx1 < myIncoming.size()*myOutgoing.size(); idx1++) {
607  //assert(myDone[idx1][idx2]);
608  if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
609  return true;
610  }
611  }
612  return false;
613 }
614 
615 
616 bool
617 NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
618  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
619  // get the indices
620  int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
621  int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
622  return (myForbids[idx2][idx1]);
623 }
624 
625 
626 void
628  // check if any errors occured on build the link prohibitions
629  if (myNotBuild != 0) {
630  WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
631  }
632 }
633 
634 
635 void
637  // map from edge to number of incoming connections
638  std::map<NBEdge*, size_t> incomingCount; // initialized to 0
639  // map from edge to indices of approached lanes
640  std::map<NBEdge*, std::set<int> > approachedLanes;
641  // map from edge to list of incoming edges
642  std::map<NBEdge*, EdgeVector> incomingEdges;
643  for (EdgeVector::const_iterator it_e = myIncoming.begin(); it_e != myIncoming.end(); it_e++) {
644  const std::vector<NBEdge::Connection> connections = (*it_e)->getConnections();
645  for (std::vector<NBEdge::Connection>::const_iterator it_c = connections.begin(); it_c != connections.end(); ++it_c) {
646  incomingCount[it_c->toEdge]++;
647  approachedLanes[it_c->toEdge].insert(it_c->toLane);
648  incomingEdges[it_c->toEdge].push_back(*it_e);
649  }
650  }
651  for (std::map<NBEdge*, size_t>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
652  NBEdge* to = it->first;
653  // we cannot test against to->getNumLanes() since not all lanes may be used
654  if (approachedLanes[to].size() >= it->second) {
655  EdgeVector& incoming = incomingEdges[to];
656  // make these connections mutually unconflicting
657  for (EdgeVector::iterator it_e1 = incoming.begin(); it_e1 != incoming.end(); ++it_e1) {
658  for (EdgeVector::iterator it_e2 = incoming.begin(); it_e2 != incoming.end(); ++it_e2) {
659  myForbids[getIndex(*it_e1, to)][getIndex(*it_e2, to)] = false;
660  }
661  }
662  }
663  }
664 }
665 
666 /****************************************************************************/
667