SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NBNodeCont.cpp
Go to the documentation of this file.
1 /****************************************************************************/
13 // Container for nodes during the netbuilding process
14 /****************************************************************************/
15 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
16 // Copyright (C) 2001-2013 DLR (http://www.dlr.de/) and contributors
17 /****************************************************************************/
18 //
19 // This file is part of SUMO.
20 // SUMO is free software: you can redistribute it and/or modify
21 // it under the terms of the GNU General Public License as published by
22 // the Free Software Foundation, either version 3 of the License, or
23 // (at your option) any later version.
24 //
25 /****************************************************************************/
26 
27 
28 // ===========================================================================
29 // included modules
30 // ===========================================================================
31 #ifdef _MSC_VER
32 #include <windows_config.h>
33 #else
34 #include <config.h>
35 #endif
36 
37 #include <string>
38 #include <map>
39 #include <algorithm>
40 #include <cmath>
42 #include <utils/geom/Boundary.h>
43 #include <utils/geom/GeomHelper.h>
47 #include <utils/common/StdDefs.h>
48 #include <utils/common/ToString.h>
52 #include "NBDistrict.h"
53 #include "NBEdgeCont.h"
55 #include "NBJoinedEdgesMap.h"
56 #include "NBOwnTLDef.h"
57 #include "NBNodeCont.h"
58 
59 #ifdef CHECK_MEMORY_LEAKS
60 #include <foreign/nvwa/debug_new.h>
61 #endif // CHECK_MEMORY_LEAKS
62 
63 
64 // ===========================================================================
65 // method definitions
66 // ===========================================================================
68  : myInternalID(1) {}
69 
70 
72  clear();
73 }
74 
75 
76 // ----------- Insertion/removal/retrieval of nodes
77 bool
78 NBNodeCont::insert(const std::string& id, const Position& position,
79  NBDistrict* district) {
80  NodeCont::iterator i = myNodes.find(id);
81  if (i != myNodes.end()) {
82  return false;
83  }
84  NBNode* node = new NBNode(id, position, district);
85  myNodes[id] = node;
86  return true;
87 }
88 
89 
90 bool
91 NBNodeCont::insert(const std::string& id, const Position& position) {
92  NodeCont::iterator i = myNodes.find(id);
93  if (i != myNodes.end()) {
94  return false;
95  }
96  NBNode* node = new NBNode(id, position);
97  myNodes[id] = node;
98  return true;
99 }
100 
101 
102 Position
103 NBNodeCont::insert(const std::string& id) {
104  std::pair<SUMOReal, SUMOReal> ret(-1.0, -1.0);
105  NodeCont::iterator i = myNodes.find(id);
106  if (i != myNodes.end()) {
107  return (*i).second->getPosition();
108  } else {
109  NBNode* node = new NBNode(id, Position(-1.0, -1.0));
110  myNodes[id] = node;
111  }
112  return Position(-1, -1);
113 }
114 
115 
116 bool
118  std::string id = node->getID();
119  NodeCont::iterator i = myNodes.find(id);
120  if (i != myNodes.end()) {
121  return false;
122  }
123  myNodes[id] = node;
124  return true;
125 }
126 
127 
128 NBNode*
129 NBNodeCont::retrieve(const std::string& id) const {
130  NodeCont::const_iterator i = myNodes.find(id);
131  if (i == myNodes.end()) {
132  return 0;
133  }
134  return (*i).second;
135 }
136 
137 
138 NBNode*
139 NBNodeCont::retrieve(const Position& position, SUMOReal offset) const {
140  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
141  NBNode* node = (*i).second;
142  if (fabs(node->getPosition().x() - position.x()) < offset
143  &&
144  fabs(node->getPosition().y() - position.y()) < offset) {
145  return node;
146  }
147  }
148  return 0;
149 }
150 
151 
152 bool
154  if (extract(node)) {
155  delete node;
156  return true;
157  } else {
158  return false;
159  }
160 }
161 
162 
163 bool
164 NBNodeCont::extract(NBNode* node, bool remember) {
165  NodeCont::iterator i = myNodes.find(node->getID());
166  if (i == myNodes.end()) {
167  return false;
168  }
169  myNodes.erase(i);
170  node->removeTrafficLights();
171  if (remember) {
172  myExtractedNodes.insert(node);
173  }
174  return true;
175 }
176 
177 
178 // ----------- Adapting the input
179 void
181  unsigned int no = 0;
182  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
183  no += (*i).second->removeSelfLoops(dc, ec, tc);
184  }
185  if (no != 0) {
186  WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
187  }
188 }
189 
190 
191 void
193  // magic values
194  SUMOReal distanceThreshold = 7; // don't merge edges further apart
195  SUMOReal lengthThreshold = 0.05; // don't merge edges with higher relative length-difference
196 
197  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
198  // count the edges to other nodes outgoing from the current node
199  std::map<NBNode*, EdgeVector> connectionCount;
200  const EdgeVector& outgoing = (*i).second->getOutgoingEdges();
201  for (EdgeVector::const_iterator j = outgoing.begin(); j != outgoing.end(); j++) {
202  NBEdge* e = (*j);
203  NBNode* connected = e->getToNode();
204  if (connectionCount.find(connected) == connectionCount.end()) {
205  connectionCount[connected] = EdgeVector();
206  }
207  connectionCount[connected].push_back(e);
208  }
209  // check whether more than a single edge connect another node and join them
210  std::map<NBNode*, EdgeVector>::iterator k;
211  for (k = connectionCount.begin(); k != connectionCount.end(); k++) {
212  // possibly we do not have anything to join...
213  if ((*k).second.size() < 2) {
214  continue;
215  }
216  // for the edges that seem to be a single street,
217  // check whether the geometry is similar
218  const EdgeVector& ev = (*k).second;
219  const NBEdge* const first = ev.front();
220  EdgeVector::const_iterator jci; // join candidate iterator
221  for (jci = ev.begin() + 1; jci != ev.end(); ++jci) {
222  const SUMOReal relativeLengthDifference = fabs(first->getLoadedLength() - (*jci)->getLoadedLength()) / first->getLoadedLength();
223  if ((!first->isNearEnough2BeJoined2(*jci, distanceThreshold)) ||
224  (relativeLengthDifference > lengthThreshold) ||
225  (first->getSpeed() != (*jci)->getSpeed())
226  // @todo check vclass
227  ) {
228  break;
229  }
230  }
231  // @bug If there are 3 edges of which 2 can be joined, no joining will
232  // take place with the current implementation
233  if (jci == ev.end()) {
234  ec.joinSameNodeConnectingEdges(dc, tlc, ev);
235  }
236  }
237  }
238 }
239 
240 
241 void
243  UNUSED_PARAMETER(tc);
244  // Warn of isolated edges, i.e. a single edge with no connection to another edge
245  int edgeCounter = 0;
246  const std::vector<std::string>& edgeNames = ec.getAllNames();
247  for (std::vector<std::string>::const_iterator it = edgeNames.begin(); it != edgeNames.end(); ++it) {
248  // Test whether this node starts at a dead end, i.e. it has only one adjacent node
249  // to which an edge exists and from which an edge may come.
250  NBEdge* e = ec.retrieve(*it);
251  if (e == 0) {
252  continue;
253  }
254  NBNode* from = e->getFromNode();
255  const EdgeVector& outgoingEdges = from->getOutgoingEdges();
256  if (outgoingEdges.size() != 1) {
257  // At this node, several edges or no edge start; so, this node is no dead end.
258  continue;
259  }
260  const EdgeVector& incomingEdges = from->getIncomingEdges();
261  if (incomingEdges.size() > 1) {
262  // At this node, several edges end; so, this node is no dead end.
263  continue;
264  } else if (incomingEdges.size() == 1) {
265  NBNode* fromNodeOfIncomingEdge = incomingEdges[0]->getFromNode();
266  NBNode* toNodeOfOutgoingEdge = outgoingEdges[0]->getToNode();
267  if (fromNodeOfIncomingEdge != toNodeOfOutgoingEdge) {
268  // At this node, an edge ends which is not the inverse direction of
269  // the starting node.
270  continue;
271  }
272  }
273  // Now we know that the edge e starts a dead end.
274  // Next we test if the dead end is isolated, i.e. does not lead to a junction
275  bool hasJunction = false;
276  EdgeVector road;
277  NBEdge* eOld = 0;
278  NBNode* to;
279  std::set<NBNode*> adjacentNodes;
280  do {
281  road.push_back(e);
282  eOld = e;
283  from = e->getFromNode();
284  to = e->getToNode();
285  const EdgeVector& outgoingEdgesOfToNode = to->getOutgoingEdges();
286  const EdgeVector& incomingEdgesOfToNode = to->getIncomingEdges();
287  adjacentNodes.clear();
288  for (EdgeVector::const_iterator itOfOutgoings = outgoingEdgesOfToNode.begin(); itOfOutgoings != outgoingEdgesOfToNode.end(); ++itOfOutgoings) {
289  if ((*itOfOutgoings)->getToNode() != from // The back path
290  && (*itOfOutgoings)->getToNode() != to // A loop / dummy edge
291  ) {
292  e = *itOfOutgoings; // Probably the next edge
293  }
294  adjacentNodes.insert((*itOfOutgoings)->getToNode());
295  }
296  for (EdgeVector::const_iterator itOfIncomings = incomingEdgesOfToNode.begin(); itOfIncomings != incomingEdgesOfToNode.end(); ++itOfIncomings) {
297  adjacentNodes.insert((*itOfIncomings)->getFromNode());
298  }
299  adjacentNodes.erase(to); // Omit loops
300  if (adjacentNodes.size() > 2) {
301  hasJunction = true;
302  }
303  } while (!hasJunction && eOld != e);
304  if (!hasJunction) {
305  edgeCounter += int(road.size());
306  std::string warningString = "Removed a road without junctions: ";
307  for (EdgeVector::iterator roadIt = road.begin(); roadIt != road.end(); ++roadIt) {
308  if (roadIt == road.begin()) {
309  warningString += (*roadIt)->getID();
310  } else {
311  warningString += ", " + (*roadIt)->getID();
312  }
313 
314  NBNode* fromNode = (*roadIt)->getFromNode();
315  NBNode* toNode = (*roadIt)->getToNode();
316  ec.erase(dc, *roadIt);
317  if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
318  // Node is empty; can be removed
319  erase(fromNode);
320  }
321  if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
322  // Node is empty; can be removed
323  erase(toNode);
324  }
325  }
326  WRITE_WARNING(warningString);
327  }
328  }
329  if (edgeCounter > 0 && !OptionsCont::getOptions().getBool("remove-edges.isolated")) {
330  WRITE_WARNING("Detected isolated roads. Use the option --remove-edges.isolated to get a list of all affected edges.");
331  }
332 }
333 
334 
335 unsigned int
338  bool removeGeometryNodes) {
339  unsigned int no = 0;
340  std::vector<NBNode*> toRemove;
341  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
342  NBNode* current = (*i).second;
343  bool remove = false;
344  std::vector<std::pair<NBEdge*, NBEdge*> > toJoin;
345  // check for completely empty nodes
346  if (current->getOutgoingEdges().size() == 0 && current->getIncomingEdges().size() == 0) {
347  // remove if empty
348  remove = true;
349  }
350  // check for nodes which are only geometry nodes
351  if (removeGeometryNodes) {
352  if ((current->getOutgoingEdges().size() == 1 && current->getIncomingEdges().size() == 1)
353  ||
354  (current->getOutgoingEdges().size() == 2 && current->getIncomingEdges().size() == 2)) {
355  // ok, one in, one out or two in, two out
356  // -> ask the node whether to join
357  remove = current->checkIsRemovable();
358  if (remove) {
359  toJoin = current->getEdgesToJoin();
360  }
361  }
362  }
363  // remove the node and join the geometries when wished
364  if (!remove) {
365  continue;
366  }
367  for (std::vector<std::pair<NBEdge*, NBEdge*> >::iterator j = toJoin.begin(); j != toJoin.end(); j++) {
368  NBEdge* begin = (*j).first;
369  NBEdge* continuation = (*j).second;
370  begin->append(continuation);
371  continuation->getToNode()->replaceIncoming(continuation, begin, 0);
372  tlc.replaceRemoved(continuation, -1, begin, -1);
373  je.appended(begin->getID(), continuation->getID());
374  ec.erase(dc, continuation);
375  }
376  toRemove.push_back(current);
377  no++;
378  }
379  // erase all
380  for (std::vector<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
381  erase(*j);
382  }
383  return no;
384 }
385 
386 
387 // ----------- (Helper) methods for joining nodes
388 void
390  std::set<NBNode*> visited;
391  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
392  std::vector<NBNode*> toProc;
393  if (visited.find((*i).second) != visited.end()) {
394  continue;
395  }
396  toProc.push_back((*i).second);
397  std::set<NBNode*> c;
398  while (!toProc.empty()) {
399  NBNode* n = toProc.back();
400  toProc.pop_back();
401  if (visited.find(n) != visited.end()) {
402  continue;
403  }
404  c.insert(n);
405  visited.insert(n);
406  const EdgeVector& edges = n->getEdges();
407  for (EdgeVector::const_iterator j = edges.begin(); j != edges.end(); ++j) {
408  NBEdge* e = *j;
409  NBNode* s = 0;
410  if (n->hasIncoming(e)) {
411  s = e->getFromNode();
412  } else {
413  s = e->getToNode();
414  }
415  if (visited.find(s) != visited.end()) {
416  continue;
417  }
418  if (e->getLoadedLength() < maxDist) {
419  toProc.push_back(s);
420  }
421  }
422  }
423  if (c.size() < 2) {
424  continue;
425  }
426  into.push_back(c);
427  }
428 }
429 
430 
431 void
432 NBNodeCont::addJoinExclusion(const std::vector<std::string>& ids, bool check) {
433  for (std::vector<std::string>::const_iterator it = ids.begin(); it != ids.end(); it++) {
434  // error handling has to take place here since joinExclusions could be
435  // loaded from multiple files / command line
436  if (myJoined.count(*it) > 0) {
437  WRITE_WARNING("Ignoring join exclusion for node '" + *it + "' since it already occured in a list of nodes to be joined");
438  } else if (check && retrieve(*it) == 0) {
439  WRITE_WARNING("Ignoring join exclusion for unknown node '" + *it + "'");
440  } else {
441  myJoinExclusions.insert(*it);
442  }
443  }
444 }
445 
446 
447 void
448 NBNodeCont::addCluster2Join(std::set<std::string> cluster) {
449  // error handling has to take place here since joins could be loaded from multiple files
450  for (std::set<std::string>::const_iterator it = cluster.begin(); it != cluster.end(); it++) {
451  if (myJoinExclusions.count(*it) > 0) {
452  WRITE_WARNING("Ignoring join-cluster because node '" + *it + "' was already excluded from joining");
453  return;
454  } else if (myJoined.count(*it) > 0) {
455  WRITE_WARNING("Ignoring join-cluster because node '" + *it + "' already occured in another join-cluster");
456  return;
457  } else {
458  myJoined.insert(*it);
459  }
460  }
461  myClusters2Join.push_back(cluster);
462 }
463 
464 
465 unsigned int
467  NodeClusters clusters;
468  for (std::vector<std::set<std::string> >::iterator it = myClusters2Join.begin(); it != myClusters2Join.end(); it++) {
469  // verify loaded cluster
470  std::set<NBNode*> cluster;
471  for (std::set<std::string>::iterator it_id = it->begin(); it_id != it->end(); it_id++) {
472  NBNode* node = retrieve(*it_id);
473  if (node == 0) {
474  WRITE_WARNING("Ignoring unknown node '" + *it_id + "' while joining");
475  } else {
476  cluster.insert(node);
477  }
478  }
479  if (cluster.size() > 1) {
480  clusters.push_back(cluster);
481  }
482  }
483  joinNodeClusters(clusters, dc, ec, tlc);
484  myClusters2Join.clear(); // make save for recompute
485  return (int)clusters.size();
486 }
487 
488 
489 unsigned int
491  NodeClusters cands;
492  NodeClusters clusters;
493  generateNodeClusters(maxdist, cands);
494  for (NodeClusters::iterator i = cands.begin(); i != cands.end(); ++i) {
495  std::set<NBNode*> cluster = (*i);
496  // remove join exclusions
497  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end();) {
498  std::set<NBNode*>::iterator check = j;
499  ++j;
500  if (myJoinExclusions.count((*check)->getID()) > 0) {
501  cluster.erase(check);
502  }
503  }
504  // iteratively remove the fringe
505  bool pruneFringe = true;
506  while (pruneFringe) {
507  pruneFringe = false;
508  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end();) {
509  std::set<NBNode*>::iterator check = j;
510  NBNode* n = *check;
511  ++j;
512  // remove nodes with degree <= 2 at fringe of the cluster (at least one edge leads to a non-cluster node)
513  if (
514  (n->getIncomingEdges().size() <= 1 && n->getOutgoingEdges().size() <= 1) &&
515  ((n->getIncomingEdges().size() == 0 ||
516  (n->getIncomingEdges().size() == 1 && cluster.count(n->getIncomingEdges()[0]->getFromNode()) == 0)) ||
517  (n->getOutgoingEdges().size() == 0 ||
518  (n->getOutgoingEdges().size() == 1 && cluster.count(n->getOutgoingEdges()[0]->getToNode()) == 0)))
519  ) {
520  cluster.erase(check);
521  pruneFringe = true; // other nodes could belong to the fringe now
522  }
523  }
524  }
525  if (cluster.size() > 1) {
526  // check for clusters which are to complex and probably won't work very well
527  // we count the incoming edges of the final junction
528  std::set<NBEdge*> finalIncoming;
529  std::vector<std::string> nodeIDs;
530  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
531  nodeIDs.push_back((*j)->getID());
532  const EdgeVector& edges = (*j)->getIncomingEdges();
533  for (EdgeVector::const_iterator it_edge = edges.begin(); it_edge != edges.end(); ++it_edge) {
534  NBEdge* edge = *it_edge;
535  if (cluster.count(edge->getFromNode()) == 0) {
536  // incoming edge, does not originate in the cluster
537  finalIncoming.insert(edge);
538  }
539  }
540 
541  }
542  if (finalIncoming.size() > 4) {
543  std::sort(nodeIDs.begin(), nodeIDs.end());
544  WRITE_WARNING("Not joining junctions " + joinToString(nodeIDs, ',') + " because the cluster is too complex");
545  } else {
546  clusters.push_back(cluster);
547  }
548  }
549  }
550  joinNodeClusters(clusters, dc, ec, tlc);
551  return (int)clusters.size();
552 }
553 
554 
555 void
558  for (NodeClusters::iterator i = clusters.begin(); i != clusters.end(); ++i) {
559  std::set<NBNode*> cluster = *i;
560  assert(cluster.size() > 1);
561  Position pos;
562  bool setTL;
563  std::string id;
564  TrafficLightType type;
565  analyzeCluster(cluster, id, pos, setTL, type);
566  if (!insert(id, pos)) {
567  // should not fail
568  WRITE_WARNING("Could not join junctions " + id);
569  continue;
570  }
571  NBNode* newNode = retrieve(id);
572  if (setTL) {
573  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, newNode, 0, type);
574  if (!tlc.insert(tlDef)) {
575  // actually, nothing should fail here
576  delete tlDef;
577  throw ProcessError("Could not allocate tls '" + id + "'.");
578  }
579  }
580  // collect edges
581  std::set<NBEdge*> allEdges;
582  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
583  const EdgeVector& edges = (*j)->getEdges();
584  allEdges.insert(edges.begin(), edges.end());
585  }
586 
587  // remap and remove edges which are completely within the new intersection
588  for (std::set<NBEdge*>::iterator j = allEdges.begin(); j != allEdges.end();) {
589  NBEdge* e = (*j);
590  NBNode* from = e->getFromNode();
591  NBNode* to = e->getToNode();
592  if (cluster.count(from) > 0 && cluster.count(to) > 0) {
593  for (std::set<NBEdge*>::iterator l = allEdges.begin(); l != allEdges.end(); ++l) {
594  if (e != *l) {
595  (*l)->replaceInConnections(e, e->getConnections());
596  }
597  }
598  ec.erase(dc, e);
599  allEdges.erase(j++); // erase does not invalidate the other iterators
600  } else {
601  ++j;
602  }
603  }
604 
605  // remap edges which are incoming / outgoing
606  for (std::set<NBEdge*>::iterator j = allEdges.begin(); j != allEdges.end(); ++j) {
607  NBEdge* e = (*j);
608  std::vector<NBEdge::Connection> conns = e->getConnections();
609  const bool outgoing = cluster.count(e->getFromNode()) > 0;
610  NBNode* from = outgoing ? newNode : e->getFromNode();
611  NBNode* to = outgoing ? e->getToNode() : newNode;
612  e->reinitNodes(from, to);
613  // re-add connections which previously existed and may still valid.
614  // connections to removed edges will be ignored
615  for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
616  e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::L2L_USER, false, (*k).mayDefinitelyPass);
617  }
618  }
619  // remove original nodes
620  registerJoinedCluster(cluster);
621  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
622  erase(*j);
623  }
624  }
625 }
626 
627 
628 void
629 NBNodeCont::registerJoinedCluster(const std::set<NBNode*>& cluster) {
630  std::set<std::string> ids;
631  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); j++) {
632  ids.insert((*j)->getID());
633  }
634  myJoinedClusters.push_back(ids);
635 }
636 
637 
638 void
639 NBNodeCont::analyzeCluster(std::set<NBNode*> cluster, std::string& id, Position& pos,
640  bool& hasTLS, TrafficLightType& type) {
641  id = "cluster";
642  hasTLS = false;
643  std::vector<std::string> member_ids;
644  bool ambiguousType = false;
645  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); j++) {
646  member_ids.push_back((*j)->getID());
647  pos.add((*j)->getPosition());
648  // add a traffic light if any of the cluster members was controlled
649  if ((*j)->isTLControlled()) {
650  if (!hasTLS) {
651  // init type
652  type = (*(*j)->getControllingTLS().begin())->getType();
653  } else if (type != (*(*j)->getControllingTLS().begin())->getType()) {
654  ambiguousType = true;
655  }
656  hasTLS = true;
657  }
658  }
659  pos.mul(1.0 / cluster.size());
660  // need to sort the member names to make the output deterministic
661  sort(member_ids.begin(), member_ids.end());
662  for (std::vector<std::string>::iterator j = member_ids.begin(); j != member_ids.end(); j++) {
663  id = id + "_" + (*j);
664  }
665  if (ambiguousType) {
666  type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
667  WRITE_WARNING("Ambiguous traffic light type for node cluster '" + id + "' set to '" + toString(type) + "'");
668  }
669 }
670 
671 
672 // ----------- (Helper) methods for guessing/computing traffic lights
673 bool
674 NBNodeCont::shouldBeTLSControlled(const std::set<NBNode*>& c) const {
675  unsigned int noIncoming = 0;
676  unsigned int noOutgoing = 0;
677  bool tooFast = false;
678  SUMOReal f = 0;
679  std::set<NBEdge*> seen;
680  for (std::set<NBNode*>::const_iterator j = c.begin(); j != c.end(); ++j) {
681  const EdgeVector& edges = (*j)->getEdges();
682  for (EdgeVector::const_iterator k = edges.begin(); k != edges.end(); ++k) {
683  if (c.find((*k)->getFromNode()) != c.end() && c.find((*k)->getToNode()) != c.end()) {
684  continue;
685  }
686  if ((*j)->hasIncoming(*k)) {
687  ++noIncoming;
688  f += (SUMOReal)(*k)->getNumLanes() * (*k)->getLaneSpeed(0);
689  } else {
690  ++noOutgoing;
691  }
692  if ((*k)->getLaneSpeed(0) * 3.6 > 79) {
693  tooFast = true;
694  }
695  }
696  }
697  return !tooFast && f >= 150. / 3.6 && c.size() != 0;
698 }
699 
700 
701 void
703  // build list of definitely not tls-controlled junctions
704  std::vector<NBNode*> ncontrolled;
705  if (oc.isSet("tls.unset")) {
706  std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
707  for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
708  NBNode* n = NBNodeCont::retrieve(*i);
709  if (n == 0) {
710  throw ProcessError(" The node '" + *i + "' to set as not-controlled is not known.");
711  }
712  std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
713  for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
714  (*j)->removeNode(n);
715  }
716  n->removeTrafficLights();
717  ncontrolled.push_back(n);
718  }
719  }
720 
722  // loop#1 checking whether the node shall be tls controlled,
723  // because it is assigned to a district
724  if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
725  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
726  NBNode* cur = (*i).second;
727  if (cur->isNearDistrict() && find(ncontrolled.begin(), ncontrolled.end(), cur) == ncontrolled.end()) {
728  setAsTLControlled(cur, tlc, type);
729  }
730  }
731  }
732 
733  // maybe no tls shall be guessed
734  if (!oc.getBool("tls.guess")) {
735  return;
736  }
737 
738  // guess joined tls first, if wished
739  if (oc.getBool("tls.join")) {
740  // get node clusters
741  std::vector<std::set<NBNode*> > cands;
742  generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
743  // check these candidates (clusters) whether they should be controlled by a tls
744  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end();) {
745  std::set<NBNode*>& c = (*i);
746  // regard only junctions which are not yet controlled and are not
747  // forbidden to be controlled
748  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end();) {
749  if ((*j)->isTLControlled() || find(ncontrolled.begin(), ncontrolled.end(), *j) != ncontrolled.end()) {
750  c.erase(j++);
751  } else {
752  ++j;
753  }
754  }
755  // check whether the cluster should be controlled
756  if (!shouldBeTLSControlled(c)) {
757  i = cands.erase(i);
758  } else {
759  ++i;
760  }
761  }
762  // cands now only contain sets of junctions that shall be joined into being tls-controlled
763  unsigned int index = 0;
764  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end(); ++i) {
765  std::vector<NBNode*> nodes;
766  for (std::set<NBNode*>::iterator j = (*i).begin(); j != (*i).end(); j++) {
767  nodes.push_back(*j);
768  }
769  std::string id = "joinedG_" + toString(index++);
770  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
771  if (!tlc.insert(tlDef)) {
772  // actually, nothing should fail here
773  WRITE_WARNING("Could not build guessed, joined tls");
774  delete tlDef;
775  return;
776  }
777  }
778  }
779 
780  // guess tls
781  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
782  NBNode* cur = (*i).second;
783  // do nothing if already is tl-controlled
784  if (cur->isTLControlled()) {
785  continue;
786  }
787  // do nothing if in the list of explicit non-controlled junctions
788  if (find(ncontrolled.begin(), ncontrolled.end(), cur) != ncontrolled.end()) {
789  continue;
790  }
791  std::set<NBNode*> c;
792  c.insert(cur);
793  if (!shouldBeTLSControlled(c) || cur->getIncomingEdges().size() < 3) {
794  continue;
795  }
796  setAsTLControlled((*i).second, tlc, type);
797  }
798 }
799 
800 
801 void
803  std::vector<std::set<NBNode*> > cands;
804  generateNodeClusters(maxdist, cands);
805  unsigned int index = 0;
806  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end(); ++i) {
807  std::set<NBNode*>& c = (*i);
808  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end();) {
809  if (!(*j)->isTLControlled()) {
810  c.erase(j++);
811  } else {
812  ++j;
813  }
814  }
815  if (c.size() < 2) {
816  continue;
817  }
818  // figure out type of the joined TLS
819  Position dummyPos;
820  bool dummySetTL;
821  std::string dummyId;
822  TrafficLightType type;
823  analyzeCluster(c, dummyId, dummyPos, dummySetTL, type);
824  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end(); ++j) {
825  std::set<NBTrafficLightDefinition*> tls = (*j)->getControllingTLS();
826  (*j)->removeTrafficLights();
827  for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
828  tlc.removeFully((*j)->getID());
829  }
830  }
831  std::string id = "joinedS_" + toString(index++);
832  std::vector<NBNode*> nodes;
833  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end(); j++) {
834  nodes.push_back(*j);
835  }
836  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
837  if (!tlc.insert(tlDef)) {
838  // actually, nothing should fail here
839  WRITE_WARNING("Could not build a joined tls.");
840  delete tlDef;
841  return;
842  }
843  }
844 }
845 
846 
847 void
849  TrafficLightType type, std::string id) {
850  if (id == "") {
851  id = node->getID();
852  }
853  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
854  if (!tlc.insert(tlDef)) {
855  // actually, nothing should fail here
856  WRITE_WARNING("Building a tl-logic for node '" + id + "' twice is not possible.");
857  delete tlDef;
858  return;
859  }
860 }
861 
862 
863 // -----------
864 void
866  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
867  (*i).second->computeLanes2Lanes();
868  }
869 }
870 
871 
872 // computes the "wheel" of incoming and outgoing edges for every node
873 void
875  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
876  (*i).second->computeLogic(ec, oc);
877  }
878 }
879 
880 
881 void
883  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
884  delete((*i).second);
885  }
886  myNodes.clear();
887  for (std::set<NBNode*>::iterator i = myExtractedNodes.begin(); i != myExtractedNodes.end(); i++) {
888  delete(*i);
889  }
890  myExtractedNodes.clear();
891 }
892 
893 
894 std::string
896  // !!! not guaranteed to be free
897  std::string ret = "SUMOGenerated" + toString<int>(size());
898  assert(retrieve(ret) == 0);
899  return ret;
900 }
901 
902 
903 void
905  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
906  (*i).second->computeNodeShape(leftHand);
907  }
908 }
909 
910 
911 void
913  int numUnregulatedJunctions = 0;
914  int numDeadEndJunctions = 0;
915  int numPriorityJunctions = 0;
916  int numRightBeforeLeftJunctions = 0;
917  int numAllWayStopJunctions = 0;
918  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
919  switch ((*i).second->getType()) {
920  case NODETYPE_NOJUNCTION:
922  ++numUnregulatedJunctions;
923  break;
924  case NODETYPE_DEAD_END:
925  ++numDeadEndJunctions;
926  break;
927  case NODETYPE_PRIORITY:
930  ++numPriorityJunctions;
931  break;
933  ++numRightBeforeLeftJunctions;
934  break;
936  ++numAllWayStopJunctions;
937  break;
938  case NODETYPE_DISTRICT:
939  ++numRightBeforeLeftJunctions;
940  break;
941  case NODETYPE_UNKNOWN:
942  break;
943  default:
944  break;
945  }
946  }
947  WRITE_MESSAGE(" Node type statistics:");
948  WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
949  if (numDeadEndJunctions > 0) {
950  WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
951  }
952  WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
953  WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
954  if (numAllWayStopJunctions > 0) {
955  WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
956  }
957 }
958 
959 
960 std::vector<std::string>
962  std::vector<std::string> ret;
963  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
964  ret.push_back((*i).first);
965  }
966  return ret;
967 }
968 
969 
970 void
971 NBNodeCont::rename(NBNode* node, const std::string& newID) {
972  if (myNodes.count(newID) != 0) {
973  throw ProcessError("Attempt to rename node using existing id '" + newID + "'");
974  }
975  myNodes.erase(node->getID());
976  node->setID(newID);
977  myNodes[newID] = node;
978 }
979 
980 
981 void
983  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
984  NBNode* node = i->second;
985  if (!geometryLike || node->geometryLike()) {
986  // make a copy of tldefs
987  const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
988  for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
989  NBTrafficLightDefinition* tlDef = *it;
990  node->removeTrafficLight(tlDef);
991  tlc.extract(tlDef);
992  }
993  node->reinit(node->getPosition(), NODETYPE_UNKNOWN);
994  }
995  }
996 }
997 
998 /****************************************************************************/
999 
std::string getFreeID()
Definition: NBNodeCont.cpp:895
std::set< std::string > myJoinExclusions
Definition: NBNodeCont.h:385
NodeCont myNodes
The map of names to nodes.
Definition: NBNodeCont.h:379
void joinSimilarEdges(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins edges connecting the same nodes.
Definition: NBNodeCont.cpp:192
void replaceIncoming(NBEdge *which, NBEdge *by, unsigned int laneOff)
Replaces occurences of the first edge within the list of incoming by the second Connections are remap...
Definition: NBNode.cpp:797
std::vector< std::string > getStringVector(const std::string &name) const
Returns the list of string-vector-value of the named option (only for Option_String) ...
const EdgeVector & getIncomingEdges() const
Returns this node&#39;s incoming edges.
Definition: NBNode.h:177
void removeSelfLoops(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tc)
Removes self-loop edges (edges where the source and the destination node are the same) ...
Definition: NBNodeCont.cpp:180
bool insert(const std::string &id, const Position &position, NBDistrict *district)
Inserts a node into the map.
Definition: NBNodeCont.cpp:78
std::vector< std::string > getAllNames() const
Returns all ids of known edges.
Definition: NBEdgeCont.cpp:500
void addJoinExclusion(const std::vector< std::string > &ids, bool check=false)
Definition: NBNodeCont.cpp:432
void add(const Position &pos)
Adds the given position to this one.
Definition: Position.h:119
unsigned int removeUnwishedNodes(NBDistrictCont &dc, NBEdgeCont &ec, NBJoinedEdgesMap &je, NBTrafficLightLogicCont &tlc, bool removeGeometryNodes)
Removes &quot;unwished&quot; nodes.
Definition: NBNodeCont.cpp:336
A container for traffic light definitions and built programs.
void reinit(const Position &position, SumoXMLNodeType type, bool updateEdgeGeometries=false)
Resets initial values.
Definition: NBNode.cpp:223
bool isTLControlled() const
Returns whether this node is controlled by any tls.
Definition: NBNode.h:228
std::vector< std::set< std::string > > myJoinedClusters
Definition: NBNodeCont.h:390
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
The representation of a single edge during network building.
Definition: NBEdge.h:71
void reinitNodes(NBNode *from, NBNode *to)
Resets nodes but keeps all other values the same (used when joining)
Definition: NBEdge.cpp:278
A container for districts.
The base class for traffic light logic definitions.
bool addLane2LaneConnection(unsigned int fromLane, NBEdge *dest, unsigned int toLane, Lane2LaneInfoType type, bool mayUseSameDestination=false, bool mayDefinitelyPass=false)
Adds a connection between the specified this edge&#39;s lane and an approached one.
Definition: NBEdge.cpp:613
unsigned int joinJunctions(SUMOReal maxdist, NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins junctions that are very close together.
Definition: NBNodeCont.cpp:490
void guessTLs(OptionsCont &oc, NBTrafficLightLogicCont &tlc)
Guesses which junctions or junction clusters shall be controlled by tls.
Definition: NBNodeCont.cpp:702
SUMOReal getFloat(const std::string &name) const
Returns the SUMOReal-value of the named option (only for Option_Float)
bool checkIsRemovable() const
Definition: NBNode.cpp:1257
void removeTrafficLight(NBTrafficLightDefinition *tlDef)
Removes the given traffic light from this node.
Definition: NBNode.cpp:266
void extract(NBTrafficLightDefinition *definition)
Extracts a traffic light definition from myDefinitions but keeps it in myExtracted for eventual * del...
bool hasIncoming(const NBEdge *const e) const
Returns whether the given edge ends at this node.
Definition: NBNode.cpp:904
SUMOReal x() const
Returns the x-position.
Definition: Position.h:63
#define UNUSED_PARAMETER(x)
Definition: StdDefs.h:36
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:196
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:67
void computeLogics(const NBEdgeCont &ec, OptionsCont &oc)
build the list of outgoing edges and lanes
Definition: NBNodeCont.cpp:874
void generateNodeClusters(SUMOReal maxDist, NodeClusters &into) const
Builds node clusters.
Definition: NBNodeCont.cpp:389
A class representing a single district.
Definition: NBDistrict.h:72
const EdgeVector & getOutgoingEdges() const
Returns this node&#39;s outgoing edges.
Definition: NBNode.h:185
SUMOReal getLoadedLength() const
Returns the length was set explicitly or the computed length if it wasn&#39;t set.
Definition: NBEdge.h:406
const std::string & getID() const
Returns the id.
Definition: Named.h:60
unsigned int size() const
Returns the number of known nodes.
Definition: NBNodeCont.h:282
const Position & getPosition() const
Returns the position of this node.
Definition: NBNode.h:165
const std::set< NBTrafficLightDefinition * > & getControllingTLS() const
Returns the traffic lights that were assigned to this node.
Definition: NBNode.h:242
void computeLanes2Lanes()
divides the incoming lanes on outgoing lanes
Definition: NBNodeCont.cpp:865
~NBNodeCont()
Destructor.
Definition: NBNodeCont.cpp:71
void joinTLS(NBTrafficLightLogicCont &tlc, SUMOReal maxdist)
Builds clusters of tls-controlled junctions and joins the control if possible.
Definition: NBNodeCont.cpp:802
static StringBijection< TrafficLightType > TrafficLightTypes
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:46
NBNodeCont()
Constructor.
Definition: NBNodeCont.cpp:67
unsigned int joinLoadedClusters(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins loaded junction clusters (see NIXMLNodesHandler)
Definition: NBNodeCont.cpp:466
bool geometryLike() const
whether this is structurally similar to a geometry node
Definition: NBNode.cpp:1412
void removeTrafficLights()
Removes all references to traffic lights that control this tls.
Definition: NBNode.cpp:273
const EdgeVector & getEdges() const
Returns all edges which participate in this node.
Definition: NBNode.h:193
Storage for edges, including some functionality operating on multiple edges.
Definition: NBEdgeCont.h:66
void joinNodeClusters(NodeClusters clusters, NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Definition: NBNodeCont.cpp:556
std::set< NBNode * > myExtractedNodes
The extracted nodes which are kept for reference.
Definition: NBNodeCont.h:382
std::vector< std::string > getAllNames() const
get all node names
Definition: NBNodeCont.cpp:961
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:51
The connection was given by the user.
Definition: NBEdge.h:114
bool shouldBeTLSControlled(const std::set< NBNode * > &c) const
Returns whethe the given node cluster should be controlled by a tls.
Definition: NBNodeCont.cpp:674
void rename(NBNode *node, const std::string &newID)
Renames the node. Throws exception if newID already exists.
Definition: NBNodeCont.cpp:971
std::vector< std::pair< NBEdge *, NBEdge * > > getEdgesToJoin() const
Definition: NBNode.cpp:1314
void joinSameNodeConnectingEdges(NBDistrictCont &dc, NBTrafficLightLogicCont &tlc, EdgeVector edges)
Joins the given edges because they connect the same nodes.
Definition: NBEdgeCont.cpp:630
void setAsTLControlled(NBNode *node, NBTrafficLightLogicCont &tlc, TrafficLightType type, std::string id="")
Sets the given node as being controlled by a tls.
Definition: NBNodeCont.cpp:848
T get(const std::string &str)
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:362
bool isNearDistrict() const
Definition: NBNode.cpp:1355
void setID(const std::string &newID)
resets the id
Definition: Named.h:68
NBEdge * retrieve(const std::string &id, bool retrieveExtracted=false) const
Returns the edge that has the given id.
Definition: NBEdgeCont.cpp:251
void addCluster2Join(std::set< std::string > cluster)
add ids of nodes which shall be joined into a single node
Definition: NBNodeCont.cpp:448
A structure storing information about which edges were joined.
std::vector< NBEdge * > EdgeVector
Definition: NBCont.h:38
void analyzeCluster(std::set< NBNode * > cluster, std::string &id, Position &pos, bool &hasTLS, TrafficLightType &type)
Definition: NBNodeCont.cpp:639
void removeIsolatedRoads(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tc)
Removes sequences of edges that are not connected with a junction. Simple roads without junctions som...
Definition: NBNodeCont.cpp:242
std::set< std::string > myJoined
ids found in loaded join clusters used for error checking
Definition: NBNodeCont.h:393
SUMOReal y() const
Returns the y-position.
Definition: Position.h:68
A storage for options typed value containers)
Definition: OptionsCont.h:108
std::vector< std::set< NBNode * > > NodeClusters
Definition of a node cluster container.
Definition: NBNodeCont.h:339
void erase(NBDistrictCont &dc, NBEdge *edge)
Removes the given edge from the container (deleting it)
Definition: NBEdgeCont.cpp:363
void clear()
Definition: NBNodeCont.cpp:882
void computeNodeShapes(bool leftHand)
Definition: NBNodeCont.cpp:904
void mul(SUMOReal val)
Multiplies both positions with the given value.
Definition: Position.h:99
void append(NBEdge *continuation)
Definition: NBEdge.cpp:1831
std::vector< std::set< std::string > > myClusters2Join
Definition: NBNodeCont.h:388
Represents a single node (junction) during network building.
Definition: NBNode.h:74
bool removeFully(const std::string id)
Removes a logic definition (and all programs) from the dictionary.
std::string joinToString(const std::vector< T > &v, const T_BETWEEN &between, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:142
bool insert(NBTrafficLightDefinition *logic, bool forceInsert=false)
Adds a logic definition to the dictionary.
#define SUMOReal
Definition: config.h:215
bool isNearEnough2BeJoined2(NBEdge *e, SUMOReal threshold) const
Definition: NBEdge.cpp:1882
NBNode * retrieve(const std::string &id) const
Returns the node with the given name.
Definition: NBNodeCont.cpp:129
SUMOReal getSpeed() const
Returns the speed allowed on this edge.
Definition: NBEdge.h:422
void printBuiltNodesStatistics() const
Prints statistics about built nodes.
Definition: NBNodeCont.cpp:912
void replaceRemoved(NBEdge *removed, int removedLane, NBEdge *by, int byLane)
Replaces occurences of the removed edge/lane in all definitions by the given edge.
void discardTrafficLights(NBTrafficLightLogicCont &tlc, bool geometryLike)
Definition: NBNodeCont.cpp:982
A traffic light logics which must be computed (only nodes/edges are given)
Definition: NBOwnTLDef.h:54
void appended(const std::string &to, const std::string &what)
Informs the map that two edges have been joined.
bool extract(NBNode *node, bool remember=false)
Removes the given node but does not delete it.
Definition: NBNodeCont.cpp:164
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:197
bool erase(NBNode *node)
Removes the given node, deleting it.
Definition: NBNodeCont.cpp:153
const std::vector< Connection > & getConnections() const
Returns the connections.
Definition: NBEdge.h:724
std::map< std::string, NBNode * >::const_iterator begin() const
Returns the pointer to the begin of the stored nodes.
Definition: NBNodeCont.h:141
bool exists(const std::string &name) const
Returns the information whether the named option is known.
TrafficLightType
bool isSet(const std::string &name, bool failOnNonExistant=true) const
Returns the information whether the named option is set.
void registerJoinedCluster(const std::set< NBNode * > &cluster)
gets all joined clusters (see doc for myClusters2Join)
Definition: NBNodeCont.cpp:629
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:354