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-2012 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 }
167 
168 
169 void
171  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
172  while (*pfrom != to) {
174  if ((*pfrom)->getToNode() == myJunction) {
175  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
176  while (*pto != from) {
177  if (!((*pto)->getToNode() == myJunction)) {
178  setBlocking(leftHanded, from, to, *pfrom, *pto);
179  }
181  }
182  }
183  }
184 }
185 
186 
187 void
189  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
190  while (*pfrom != to) {
191  NBContHelper::nextCW(myAll, pfrom);
192  if ((*pfrom)->getToNode() == myJunction) {
193  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
194  while (*pto != from) {
195  if (!((*pto)->getToNode() == myJunction)) {
196  setBlocking(leftHanded, from, to, *pfrom, *pto);
197  }
199  }
200  }
201  }
202 }
203 
204 
205 void
206 NBRequest::setBlocking(bool leftHanded,
207  NBEdge* from1, NBEdge* to1,
208  NBEdge* from2, NBEdge* to2) {
209  // check whether one of the links has a dead end
210  if (to1 == 0 || to2 == 0) {
211  return;
212  }
213  // get the indices of both links
214  int idx1 = getIndex(from1, to1);
215  int idx2 = getIndex(from2, to2);
216  if (idx1 < 0 || idx2 < 0) {
217  return; // !!! error output? did not happend, yet
218  }
219  // check whether the link crossing has already been checked
220  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
221  if (myDone[idx1][idx2]) {
222  return;
223  }
224  // mark the crossings as done
225  myDone[idx1][idx2] = true;
226  myDone[idx2][idx1] = true;
227  // check if one of the links is a turn; this link is always not priorised
228  // true for right-before-left and priority
229  if (from1->isTurningDirectionAt(myJunction, to1)) {
230  myForbids[idx2][idx1] = true;
231  return;
232  }
233  if (from2->isTurningDirectionAt(myJunction, to2)) {
234  myForbids[idx1][idx2] = true;
235  return;
236  }
237 
238  // check the priorities
239  int from1p = from1->getJunctionPriority(myJunction);
240  int from2p = from2->getJunctionPriority(myJunction);
241  // check if one of the connections is higher priorised when incoming into
242  // the junction, the connection road will yield
243  // should be valid for priority junctions only
244  if (from1p > from2p) {
246  myForbids[idx1][idx2] = true;
247  return;
248  }
249  if (from2p > from1p) {
251  myForbids[idx2][idx1] = true;
252  return;
253  }
254 
255  // check whether one of the connections is higher priorised on
256  // the outgoing edge when both roads are high priorised
257  // the connection with the lower priorised outgoing edge will lead
258  // should be valid for priority junctions only
259  /*
260  if (from1p > 0 && from2p > 0) {
261  assert(myJunction->getType() != NODETYPE_RIGHT_BEFORE_LEFT);
262  int to1p = to1->getJunctionPriority(myJunction);
263  int to2p = to2->getJunctionPriority(myJunction);
264  if (to1p > to2p) {
265  myForbids[idx1][idx2] = true;
266  return;
267  }
268  if (to2p > to1p) {
269  myForbids[idx2][idx1] = true;
270  return;
271  }
272  }
273  */
274 
275  // compute the yielding due to the right-before-left rule
276  // get the position of the incoming lanes in the junction-wheel
277  EdgeVector::const_iterator c1 = find(myAll.begin(), myAll.end(), from1);
279  // go through next edges clockwise...
280  while (*c1 != from1 && *c1 != from2) {
281  if (*c1 == to2) {
282  // if we encounter to2 the second one prohibits the first
283  if (!leftHanded) {
284  myForbids[idx2][idx1] = true;
285  } else {
286  myForbids[idx1][idx2] = true;
287  }
288  return;
289  }
290  NBContHelper::nextCW(myAll, c1);
291  }
292  // get the position of the incoming lanes in the junction-wheel
293  EdgeVector::const_iterator c2 = find(myAll.begin(), myAll.end(), from2);
294  NBContHelper::nextCW(myAll, c2);
295  // go through next edges clockwise...
296  while (*c2 != from2 && *c2 != from1) {
297  if (*c2 == to1) {
298  // if we encounter to1 the second one prohibits the first
299  if (!leftHanded) {
300  myForbids[idx1][idx2] = true;
301  } else {
302  myForbids[idx2][idx1] = true;
303  }
304  return;
305  }
306  NBContHelper::nextCW(myAll, c2);
307  }
308 }
309 
310 
311 size_t
313  EdgeVector::const_iterator p = find(myAll.begin(), myAll.end(), from);
314  size_t ret = 0;
315  while (true) {
316  ret++;
317  if (p == myAll.begin()) {
318  p = myAll.end();
319  }
320  p--;
321  if ((*p) == to) {
322  return ret;
323  }
324  }
325 }
326 
327 
328 void
329 NBRequest::writeLogic(std::string key, OutputDevice& into) const {
330  int pos = 0;
331  EdgeVector::const_iterator i;
332  for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
333  unsigned int noLanes = (*i)->getNumLanes();
334  for (unsigned int k = 0; k < noLanes; k++) {
335  pos = writeLaneResponse(into, *i, k, pos);
336  }
337  }
338 }
339 
340 
341 void
343  // go through possible prohibitions
344  for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
345  unsigned int noLanesEdge1 = (*i11)->getNumLanes();
346  for (unsigned int j1 = 0; j1 < noLanesEdge1; j1++) {
347  std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
348  for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
349  int idx1 = getIndex((*i11), (*i12).toEdge);
350  if (idx1 < 0) {
351  continue;
352  }
353  // go through possibly prohibited
354  for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
355  unsigned int noLanesEdge2 = (*i21)->getNumLanes();
356  for (unsigned int j2 = 0; j2 < noLanesEdge2; j2++) {
357  std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
358  for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
359  int idx2 = getIndex((*i21), (*i22).toEdge);
360  if (idx2 < 0) {
361  continue;
362  }
363  // check
364  // same incoming connections do not prohibit each other
365  if ((*i11) == (*i21)) {
366  myForbids[idx1][idx2] = false;
367  myForbids[idx2][idx1] = false;
368  continue;
369  }
370  // check other
371  // if both are non-signalised or both are signalised
372  if (((*i12).tlID == "" && (*i22).tlID == "")
373  ||
374  ((*i12).tlID != "" && (*i22).tlID != "")) {
375  // do nothing
376  continue;
377  }
378  // supposing, we don not have to
379  // brake if we are no foes
380  if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
381  continue;
382  }
383  // otherwise:
384  // the non-signalised must break
385  if ((*i12).tlID != "") {
386  myForbids[idx1][idx2] = true;
387  myForbids[idx2][idx1] = false;
388  } else {
389  myForbids[idx1][idx2] = false;
390  myForbids[idx2][idx1] = true;
391  }
392  }
393  }
394  }
395  }
396  }
397  }
398 }
399 
400 
401 std::pair<unsigned int, unsigned int>
403  unsigned int noLanes = 0;
404  unsigned int noLinks = 0;
405  for (EdgeVector::const_iterator i = myIncoming.begin();
406  i != myIncoming.end(); i++) {
407  unsigned int noLanesEdge = (*i)->getNumLanes();
408  for (unsigned int j = 0; j < noLanesEdge; j++) {
409  unsigned int numConnections = (unsigned int)(*i)->getConnectionsFromLane(j).size();
410  noLinks += numConnections;
411  if (numConnections > 0) {
412  noLanes++;
413  }
414  }
415  }
416  return std::make_pair(noLanes, noLinks);
417 }
418 
419 
420 bool
421 NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
422  const NBEdge* const from2, const NBEdge* const to2) const {
423  // unconnected edges do not forbid other edges
424  if (to1 == 0 || to2 == 0) {
425  return false;
426  }
427  // get the indices
428  int idx1 = getIndex(from1, to1);
429  int idx2 = getIndex(from2, to2);
430  if (idx1 < 0 || idx2 < 0) {
431  return false; // sure? (The connection does not exist within this junction)
432  }
433  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
434  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
435  return myForbids[idx1][idx2] || myForbids[idx2][idx1];
436 }
437 
438 
439 bool
440 NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
441  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
442  bool regardNonSignalisedLowerPriority) const {
443  // unconnected edges do not forbid other edges
444  if (possProhibitorTo == 0 || possProhibitedTo == 0) {
445  return false;
446  }
447  // get the indices
448  int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
449  int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
450  if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
451  return false; // sure? (The connection does not exist within this junction)
452  }
453  assert((size_t) possProhibitorIdx < myIncoming.size()*myOutgoing.size());
454  assert((size_t) possProhibitedIdx < myIncoming.size()*myOutgoing.size());
455  // check simple right-of-way-rules
456  if (!regardNonSignalisedLowerPriority) {
457  return myForbids[possProhibitorIdx][possProhibitedIdx];
458  }
459  // if its not forbidden, report
460  if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
461  return false;
462  }
463  // do not forbid a signalised stream by a non-signalised
464  if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
465  return false;
466  }
467  return true;
468 }
469 
470 
471 int
473  int fromLane, int pos) const {
474  std::vector<NBEdge::Connection> connected = from->getConnectionsFromLane(fromLane);
475  for (std::vector<NBEdge::Connection>::iterator j = connected.begin(); j != connected.end(); j++) {
477  od.writeAttr(SUMO_ATTR_INDEX, pos++);
478  od.writeAttr(SUMO_ATTR_RESPONSE, getResponseString(from, (*j).toEdge, fromLane, (*j).mayDefinitelyPass));
479  od.writeAttr(SUMO_ATTR_FOES, getFoesString(from, (*j).toEdge));
480  if (!OptionsCont::getOptions().getBool("no-internal-links")) {
481  if ((*j).haveVia) {
482  od.writeAttr(SUMO_ATTR_CONT, 1);
483  } else {
484  od.writeAttr(SUMO_ATTR_CONT, 0);
485  }
486  }
487  od.closeTag(true);
488  }
489  return pos;
490 }
491 
492 
493 std::string
494 NBRequest::getResponseString(const NBEdge* const from, const NBEdge* const to,
495  int fromLane, bool mayDefinitelyPass) const {
496  int idx = 0;
497  if (to != 0) {
498  idx = getIndex(from, to);
499  }
500  std::string result;
501  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
502  //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
503  unsigned int noLanes = (*i)->getNumLanes();
504  for (int j = noLanes; j-- > 0;) {
505  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
506  int size = (int) connected.size();
507  for (int k = size; k-- > 0;) {
508  if (mayDefinitelyPass) {
509  result += '0';
510  } else if (to == 0) {
511  // should wait if no further connection!?
512  result += '1';
513  } else if ((*i) == from && fromLane == j) {
514  // do not prohibit a connection by others from same lane
515  result += '0';
516  } else {
517  assert(k < (int) connected.size());
518  assert((size_t) idx < myIncoming.size()*myOutgoing.size());
519  assert(connected[k].toEdge == 0 || (size_t) getIndex(*i, connected[k].toEdge) < myIncoming.size()*myOutgoing.size());
520  // check whether the connection is prohibited by another one
521  if (connected[k].toEdge != 0 && myForbids[getIndex(*i, connected[k].toEdge)][idx]) {
522  result += '1';
523  continue;
524  }
525  result += '0';
526  }
527  }
528  }
529  }
530  return result;
531 }
532 
533 
534 std::string
536  // remember the case when the lane is a "dead end" in the meaning that
537  // vehicles must choose another lane to move over the following
538  // junction
539  int idx = 0;
540  if (to != 0) {
541  idx = getIndex(from, to);
542  }
543  // !!! move to forbidden
544  std::string result;
545  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin();
546  i != myIncoming.rend(); i++) {
547 
548  unsigned int noLanes = (*i)->getNumLanes();
549  for (unsigned int j = noLanes; j-- > 0;) {
550  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
551  int size = (int) connected.size();
552  for (int k = size; k-- > 0;) {
553  if (to == 0) {
554  result += '0';
555  } else {
556 // if (foes(from, to, (*i), connected[k].edge) && !isInnerEnd) {
557  if (foes(from, to, (*i), connected[k].toEdge)) {
558  result += '1';
559  } else {
560  result += '0';
561  }
562  }
563  }
564  }
565  }
566  return result;
567 }
568 
569 
570 int
571 NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
572  EdgeVector::const_iterator fp = find(myIncoming.begin(), myIncoming.end(), from);
573  EdgeVector::const_iterator tp = find(myOutgoing.begin(), myOutgoing.end(), to);
574  if (fp == myIncoming.end() || tp == myOutgoing.end()) {
575  return -1;
576  }
577  // compute the index
578  return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
579 }
580 
581 
582 std::ostream&
583 operator<<(std::ostream& os, const NBRequest& r) {
584  size_t variations = r.myIncoming.size() * r.myOutgoing.size();
585  for (size_t i = 0; i < variations; i++) {
586  os << i << ' ';
587  for (size_t j = 0; j < variations; j++) {
588  if (r.myForbids[i][j]) {
589  os << '1';
590  } else {
591  os << '0';
592  }
593  }
594  os << std::endl;
595  }
596  os << std::endl;
597  return os;
598 }
599 
600 
601 bool
602 NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to) const {
603  // vehicles which do not have a following lane must always decelerate to the end
604  if (to == 0) {
605  return true;
606  }
607  // get the indices
608  int idx2 = getIndex(from, to);
609  if (idx2 == -1) {
610  return false;
611  }
612  // go through all (existing) connections;
613  // check whether any of these forbids the one to determine
614  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
615  for (size_t idx1 = 0; idx1 < myIncoming.size()*myOutgoing.size(); idx1++) {
616  //assert(myDone[idx1][idx2]);
617  if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
618  return true;
619  }
620  }
621  return false;
622 }
623 
624 
625 bool
626 NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
627  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
628  // get the indices
629  int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
630  int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
631  return (myForbids[idx2][idx1]);
632 }
633 
634 
635 void
637  // check if any errors occured on build the link prohibitions
638  if (myNotBuild != 0) {
639  WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
640  }
641 }
642 
643 
644 
645 /****************************************************************************/
646