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-2014 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 
71 
73  clear();
74 }
75 
76 
77 // ----------- Insertion/removal/retrieval of nodes
78 bool
79 NBNodeCont::insert(const std::string& id, const Position& position,
80  NBDistrict* district) {
81  NodeCont::iterator i = myNodes.find(id);
82  if (i != myNodes.end()) {
83  return false;
84  }
85  NBNode* node = new NBNode(id, position, district);
86  myNodes[id] = node;
87  const float pos[2] = {(float)position.x(), (float)position.y()};
88  myRTree.Insert(pos, pos, node);
89  return true;
90 }
91 
92 
94 NBNodeCont::insert(const std::string& id) {
95  std::pair<SUMOReal, SUMOReal> ret(-1.0, -1.0);
96  NodeCont::iterator i = myNodes.find(id);
97  if (i != myNodes.end()) {
98  return (*i).second->getPosition();
99  } else {
100  NBNode* node = new NBNode(id, Position(-1.0, -1.0));
101  myNodes[id] = node;
102  const float pos[2] = {(float) - 1, (float) - 1};
103  myRTree.Insert(pos, pos, node);
104  }
105  return Position(-1, -1);
106 }
107 
108 
109 bool
111  std::string id = node->getID();
112  NodeCont::iterator i = myNodes.find(id);
113  if (i != myNodes.end()) {
114  return false;
115  }
116  myNodes[id] = node;
117  const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
118  myRTree.Insert(pos, pos, node);
119  return true;
120 }
121 
122 
123 NBNode*
124 NBNodeCont::retrieve(const std::string& id) const {
125  NodeCont::const_iterator i = myNodes.find(id);
126  if (i == myNodes.end()) {
127  return 0;
128  }
129  return (*i).second;
130 }
131 
132 
133 NBNode*
134 NBNodeCont::retrieve(const Position& position, const SUMOReal offset) const {
135  const SUMOReal extOffset = offset + POSITION_EPS;
136  const float cmin[2] = {(float)(position.x() - extOffset), (float)(position.y() - extOffset)};
137  const float cmax[2] = {(float)(position.x() + extOffset), (float)(position.y() + extOffset)};
138  std::set<std::string> into;
139  Named::StoringVisitor sv(into);
140  myRTree.Search(cmin, cmax, sv);
141  for (std::set<std::string>::const_iterator i = into.begin(); i != into.end(); i++) {
142  NBNode* const node = myNodes.find(*i)->second;
143  if (fabs(node->getPosition().x() - position.x()) <= offset
144  &&
145  fabs(node->getPosition().y() - position.y()) <= offset) {
146  return node;
147  }
148  }
149  return 0;
150 }
151 
152 
153 bool
155  if (extract(node)) {
156  delete node;
157  return true;
158  } else {
159  return false;
160  }
161 }
162 
163 
164 bool
165 NBNodeCont::extract(NBNode* node, bool remember) {
166  NodeCont::iterator i = myNodes.find(node->getID());
167  if (i == myNodes.end()) {
168  return false;
169  }
170  myNodes.erase(i);
171  const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
172  myRTree.Remove(pos, pos, node);
173  node->removeTrafficLights();
174  if (remember) {
175  myExtractedNodes.insert(node);
176  }
177  return true;
178 }
179 
180 
181 // ----------- Adapting the input
182 void
184  unsigned int no = 0;
185  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
186  no += (*i).second->removeSelfLoops(dc, ec, tc);
187  }
188  if (no != 0) {
189  WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
190  }
191 }
192 
193 
194 void
196  // magic values
197  SUMOReal distanceThreshold = 7; // don't merge edges further apart
198  SUMOReal lengthThreshold = 0.05; // don't merge edges with higher relative length-difference
199 
200  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
201  // count the edges to other nodes outgoing from the current node
202  std::map<NBNode*, EdgeVector> connectionCount;
203  const EdgeVector& outgoing = (*i).second->getOutgoingEdges();
204  for (EdgeVector::const_iterator j = outgoing.begin(); j != outgoing.end(); j++) {
205  NBEdge* e = (*j);
206  NBNode* connected = e->getToNode();
207  if (connectionCount.find(connected) == connectionCount.end()) {
208  connectionCount[connected] = EdgeVector();
209  }
210  connectionCount[connected].push_back(e);
211  }
212  // check whether more than a single edge connect another node and join them
213  std::map<NBNode*, EdgeVector>::iterator k;
214  for (k = connectionCount.begin(); k != connectionCount.end(); k++) {
215  // possibly we do not have anything to join...
216  if ((*k).second.size() < 2) {
217  continue;
218  }
219  // for the edges that seem to be a single street,
220  // check whether the geometry is similar
221  const EdgeVector& ev = (*k).second;
222  const NBEdge* const first = ev.front();
223  EdgeVector::const_iterator jci; // join candidate iterator
224  for (jci = ev.begin() + 1; jci != ev.end(); ++jci) {
225  const SUMOReal relativeLengthDifference = fabs(first->getLoadedLength() - (*jci)->getLoadedLength()) / first->getLoadedLength();
226  if ((!first->isNearEnough2BeJoined2(*jci, distanceThreshold)) ||
227  (relativeLengthDifference > lengthThreshold) ||
228  (first->getSpeed() != (*jci)->getSpeed())
229  // @todo check vclass
230  ) {
231  break;
232  }
233  }
234  // @bug If there are 3 edges of which 2 can be joined, no joining will
235  // take place with the current implementation
236  if (jci == ev.end()) {
237  ec.joinSameNodeConnectingEdges(dc, tlc, ev);
238  }
239  }
240  }
241 }
242 
243 
244 void
246  UNUSED_PARAMETER(tc);
247  // Warn of isolated edges, i.e. a single edge with no connection to another edge
248  int edgeCounter = 0;
249  const std::vector<std::string>& edgeNames = ec.getAllNames();
250  for (std::vector<std::string>::const_iterator it = edgeNames.begin(); it != edgeNames.end(); ++it) {
251  // Test whether this node starts at a dead end, i.e. it has only one adjacent node
252  // to which an edge exists and from which an edge may come.
253  NBEdge* e = ec.retrieve(*it);
254  if (e == 0) {
255  continue;
256  }
257  NBNode* from = e->getFromNode();
258  const EdgeVector& outgoingEdges = from->getOutgoingEdges();
259  if (outgoingEdges.size() != 1) {
260  // At this node, several edges or no edge start; so, this node is no dead end.
261  continue;
262  }
263  const EdgeVector& incomingEdges = from->getIncomingEdges();
264  if (incomingEdges.size() > 1) {
265  // At this node, several edges end; so, this node is no dead end.
266  continue;
267  } else if (incomingEdges.size() == 1) {
268  NBNode* fromNodeOfIncomingEdge = incomingEdges[0]->getFromNode();
269  NBNode* toNodeOfOutgoingEdge = outgoingEdges[0]->getToNode();
270  if (fromNodeOfIncomingEdge != toNodeOfOutgoingEdge) {
271  // At this node, an edge ends which is not the inverse direction of
272  // the starting node.
273  continue;
274  }
275  }
276  // Now we know that the edge e starts a dead end.
277  // Next we test if the dead end is isolated, i.e. does not lead to a junction
278  bool hasJunction = false;
279  EdgeVector road;
280  NBEdge* eOld = 0;
281  NBNode* to;
282  std::set<NBNode*> adjacentNodes;
283  do {
284  road.push_back(e);
285  eOld = e;
286  from = e->getFromNode();
287  to = e->getToNode();
288  const EdgeVector& outgoingEdgesOfToNode = to->getOutgoingEdges();
289  const EdgeVector& incomingEdgesOfToNode = to->getIncomingEdges();
290  adjacentNodes.clear();
291  for (EdgeVector::const_iterator itOfOutgoings = outgoingEdgesOfToNode.begin(); itOfOutgoings != outgoingEdgesOfToNode.end(); ++itOfOutgoings) {
292  if ((*itOfOutgoings)->getToNode() != from // The back path
293  && (*itOfOutgoings)->getToNode() != to // A loop / dummy edge
294  ) {
295  e = *itOfOutgoings; // Probably the next edge
296  }
297  adjacentNodes.insert((*itOfOutgoings)->getToNode());
298  }
299  for (EdgeVector::const_iterator itOfIncomings = incomingEdgesOfToNode.begin(); itOfIncomings != incomingEdgesOfToNode.end(); ++itOfIncomings) {
300  adjacentNodes.insert((*itOfIncomings)->getFromNode());
301  }
302  adjacentNodes.erase(to); // Omit loops
303  if (adjacentNodes.size() > 2) {
304  hasJunction = true;
305  }
306  } while (!hasJunction && eOld != e);
307  if (!hasJunction) {
308  edgeCounter += int(road.size());
309  std::string warningString = "Removed a road without junctions: ";
310  for (EdgeVector::iterator roadIt = road.begin(); roadIt != road.end(); ++roadIt) {
311  if (roadIt == road.begin()) {
312  warningString += (*roadIt)->getID();
313  } else {
314  warningString += ", " + (*roadIt)->getID();
315  }
316 
317  NBNode* fromNode = (*roadIt)->getFromNode();
318  NBNode* toNode = (*roadIt)->getToNode();
319  ec.erase(dc, *roadIt);
320  if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
321  // Node is empty; can be removed
322  erase(fromNode);
323  }
324  if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
325  // Node is empty; can be removed
326  erase(toNode);
327  }
328  }
329  WRITE_WARNING(warningString);
330  }
331  }
332  if (edgeCounter > 0 && !OptionsCont::getOptions().getBool("remove-edges.isolated")) {
333  WRITE_WARNING("Detected isolated roads. Use the option --remove-edges.isolated to get a list of all affected edges.");
334  }
335 }
336 
337 
338 unsigned int
341  bool removeGeometryNodes) {
342  unsigned int no = 0;
343  std::vector<NBNode*> toRemove;
344  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
345  NBNode* current = (*i).second;
346  bool remove = false;
347  std::vector<std::pair<NBEdge*, NBEdge*> > toJoin;
348  // check for completely empty nodes
349  if (current->getOutgoingEdges().size() == 0 && current->getIncomingEdges().size() == 0) {
350  // remove if empty
351  remove = true;
352  }
353  // check for nodes which are only geometry nodes
354  if (removeGeometryNodes) {
355  if ((current->getOutgoingEdges().size() == 1 && current->getIncomingEdges().size() == 1)
356  ||
357  (current->getOutgoingEdges().size() == 2 && current->getIncomingEdges().size() == 2)) {
358  // ok, one in, one out or two in, two out
359  // -> ask the node whether to join
360  remove = current->checkIsRemovable();
361  if (remove) {
362  toJoin = current->getEdgesToJoin();
363  }
364  }
365  }
366  // remove the node and join the geometries when wished
367  if (!remove) {
368  continue;
369  }
370  for (std::vector<std::pair<NBEdge*, NBEdge*> >::iterator j = toJoin.begin(); j != toJoin.end(); j++) {
371  NBEdge* begin = (*j).first;
372  NBEdge* continuation = (*j).second;
373  begin->append(continuation);
374  continuation->getToNode()->replaceIncoming(continuation, begin, 0);
375  tlc.replaceRemoved(continuation, -1, begin, -1);
376  je.appended(begin->getID(), continuation->getID());
377  ec.erase(dc, continuation);
378  }
379  toRemove.push_back(current);
380  no++;
381  }
382  // erase all
383  for (std::vector<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
384  erase(*j);
385  }
386  return no;
387 }
388 
389 
390 // ----------- (Helper) methods for joining nodes
391 void
393  std::set<NBNode*> visited;
394  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
395  std::vector<NBNode*> toProc;
396  if (visited.find((*i).second) != visited.end()) {
397  continue;
398  }
399  toProc.push_back((*i).second);
400  std::set<NBNode*> c;
401  while (!toProc.empty()) {
402  NBNode* n = toProc.back();
403  toProc.pop_back();
404  if (visited.find(n) != visited.end()) {
405  continue;
406  }
407  c.insert(n);
408  visited.insert(n);
409  const EdgeVector& edges = n->getEdges();
410  for (EdgeVector::const_iterator j = edges.begin(); j != edges.end(); ++j) {
411  NBEdge* e = *j;
412  NBNode* s = 0;
413  if (n->hasIncoming(e)) {
414  s = e->getFromNode();
415  } else {
416  s = e->getToNode();
417  }
418  if (visited.find(s) != visited.end()) {
419  continue;
420  }
421  if (e->getLoadedLength() < maxDist) {
422  toProc.push_back(s);
423  }
424  }
425  }
426  if (c.size() < 2) {
427  continue;
428  }
429  into.push_back(c);
430  }
431 }
432 
433 
434 void
435 NBNodeCont::addJoinExclusion(const std::vector<std::string>& ids, bool check) {
436  for (std::vector<std::string>::const_iterator it = ids.begin(); it != ids.end(); it++) {
437  // error handling has to take place here since joinExclusions could be
438  // loaded from multiple files / command line
439  if (myJoined.count(*it) > 0) {
440  WRITE_WARNING("Ignoring join exclusion for node '" + *it + "' since it already occured in a list of nodes to be joined");
441  } else if (check && retrieve(*it) == 0) {
442  WRITE_WARNING("Ignoring join exclusion for unknown node '" + *it + "'");
443  } else {
444  myJoinExclusions.insert(*it);
445  }
446  }
447 }
448 
449 
450 void
451 NBNodeCont::addCluster2Join(std::set<std::string> cluster) {
452  // error handling has to take place here since joins could be loaded from multiple files
453  for (std::set<std::string>::const_iterator it = cluster.begin(); it != cluster.end(); it++) {
454  if (myJoinExclusions.count(*it) > 0) {
455  WRITE_WARNING("Ignoring join-cluster because node '" + *it + "' was already excluded from joining");
456  return;
457  } else if (myJoined.count(*it) > 0) {
458  WRITE_WARNING("Ignoring join-cluster because node '" + *it + "' already occured in another join-cluster");
459  return;
460  } else {
461  myJoined.insert(*it);
462  }
463  }
464  myClusters2Join.push_back(cluster);
465 }
466 
467 
468 unsigned int
470  NodeClusters clusters;
471  for (std::vector<std::set<std::string> >::iterator it = myClusters2Join.begin(); it != myClusters2Join.end(); it++) {
472  // verify loaded cluster
473  std::set<NBNode*> cluster;
474  for (std::set<std::string>::iterator it_id = it->begin(); it_id != it->end(); it_id++) {
475  NBNode* node = retrieve(*it_id);
476  if (node == 0) {
477  WRITE_WARNING("Ignoring unknown node '" + *it_id + "' while joining");
478  } else {
479  cluster.insert(node);
480  }
481  }
482  if (cluster.size() > 1) {
483  clusters.push_back(cluster);
484  }
485  }
486  joinNodeClusters(clusters, dc, ec, tlc);
487  myClusters2Join.clear(); // make save for recompute
488  return (int)clusters.size();
489 }
490 
491 
492 unsigned int
494  NodeClusters cands;
495  NodeClusters clusters;
496  generateNodeClusters(maxDist, cands);
497  for (NodeClusters::iterator i = cands.begin(); i != cands.end(); ++i) {
498  std::set<NBNode*> cluster = (*i);
499  // remove join exclusions
500  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end();) {
501  std::set<NBNode*>::iterator check = j;
502  ++j;
503  if (myJoinExclusions.count((*check)->getID()) > 0) {
504  cluster.erase(check);
505  }
506  }
507  // iteratively remove the fringe
508  bool pruneFringe = true;
509  while (pruneFringe) {
510  pruneFringe = false;
511  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end();) {
512  std::set<NBNode*>::iterator check = j;
513  NBNode* n = *check;
514  ++j;
515  // remove geometry-like nodes at fringe of the cluster
516  // (they have 1 neighbor in the cluster and at most 1 neighbor outside the cluster)
517  std::set<NBNode*> neighbors;
518  std::set<NBNode*> clusterNeigbors;
519  for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
520  NBNode* neighbor = (*it_edge)->getToNode();
521  if (cluster.count(neighbor) == 0) {
522  neighbors.insert(neighbor);
523  } else {
524  clusterNeigbors.insert(neighbor);
525  }
526  }
527  for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
528  NBNode* neighbor = (*it_edge)->getFromNode();
529  if (cluster.count(neighbor) == 0) {
530  neighbors.insert(neighbor);
531  } else {
532  clusterNeigbors.insert(neighbor);
533  }
534  }
535  if (neighbors.size() <= 1 && clusterNeigbors.size() == 1) {
536  cluster.erase(check);
537  pruneFringe = true; // other nodes could belong to the fringe now
538  }
539  }
540  }
541  // exclude the fromNode of a long edge if the toNode is in the cluster (and they were both added via an alternative path).
542  std::set<NBNode*> toRemove;
543  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end(); ++j) {
544  NBNode* n = *j;
545  const EdgeVector& edges = n->getOutgoingEdges();
546  for (EdgeVector::const_iterator it_edge = edges.begin(); it_edge != edges.end(); ++it_edge) {
547  NBEdge* edge = *it_edge;
548  if (cluster.count(edge->getToNode()) != 0 && edge->getLoadedLength() > maxDist) {
549  //std::cout << "long edge " << edge->getID() << " (" << edge->getLoadedLength() << ", max=" << maxDist << ")\n";
550  toRemove.insert(n);
551  toRemove.insert(edge->getToNode());
552  }
553  }
554  }
555  for (std::set<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
556  cluster.erase(*j);
557  }
558  if (cluster.size() > 1) {
559  // check for clusters which are to complex and probably won't work very well
560  // we count the incoming edges of the final junction
561  std::set<NBEdge*> finalIncoming;
562  std::set<NBEdge*> finalOutgoing;
563  std::vector<std::string> nodeIDs;
564  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
565  nodeIDs.push_back((*j)->getID());
566  for (EdgeVector::const_iterator it_edge = (*j)->getIncomingEdges().begin(); it_edge != (*j)->getIncomingEdges().end(); ++it_edge) {
567  NBEdge* edge = *it_edge;
568  if (cluster.count(edge->getFromNode()) == 0) {
569  // incoming edge, does not originate in the cluster
570  finalIncoming.insert(edge);
571  }
572  }
573  for (EdgeVector::const_iterator it_edge = (*j)->getOutgoingEdges().begin(); it_edge != (*j)->getOutgoingEdges().end(); ++it_edge) {
574  NBEdge* edge = *it_edge;
575  if (cluster.count(edge->getToNode()) == 0) {
576  // outgoing edge, does not end in the cluster
577  finalOutgoing.insert(edge);
578  }
579  }
580 
581  }
582  if (finalIncoming.size() > 4) {
583  std::sort(nodeIDs.begin(), nodeIDs.end());
584  WRITE_WARNING("Not joining junctions " + joinToStringSorting(nodeIDs, ',') + " because the cluster is too complex (" + toString(finalIncoming.size()) + " incoming edges)");
585  } else {
586  // check for incoming parallel edges
587  const SUMOReal PARALLEL_INCOMING_THRESHOLD = 10.0;
588  bool foundParallel = false;
589  for (std::set<NBEdge*>::const_iterator j = finalIncoming.begin(); j != finalIncoming.end() && !foundParallel; ++j) {
590  for (std::set<NBEdge*>::const_iterator k = finalIncoming.begin(); k != finalIncoming.end() && !foundParallel; ++k) {
591  if ((*j) != (*k) && fabs((*j)->getAngleAtNode((*j)->getToNode()) - (*k)->getAngleAtNode((*k)->getToNode())) < PARALLEL_INCOMING_THRESHOLD) {
592  std::vector<std::string> parallelEdgeIDs;
593  parallelEdgeIDs.push_back((*j)->getID());
594  parallelEdgeIDs.push_back((*k)->getID());
595  std::sort(parallelEdgeIDs.begin(), parallelEdgeIDs.end());
596  WRITE_WARNING("Not joining junctions " + joinToStringSorting(nodeIDs, ',') + " because the cluster is too complex (parallel incoming "
597  + joinToString(parallelEdgeIDs, ',') + ")");
598  foundParallel = true;
599  }
600  }
601  }
602  // check for outgoing parallel edges
603  for (std::set<NBEdge*>::const_iterator j = finalOutgoing.begin(); j != finalOutgoing.end() && !foundParallel; ++j) {
604  for (std::set<NBEdge*>::const_iterator k = finalOutgoing.begin(); k != finalOutgoing.end() && !foundParallel; ++k) {
605  if ((*j) != (*k) && fabs((*j)->getAngleAtNode((*j)->getFromNode()) - (*k)->getAngleAtNode((*k)->getFromNode())) < PARALLEL_INCOMING_THRESHOLD) {
606  std::vector<std::string> parallelEdgeIDs;
607  parallelEdgeIDs.push_back((*j)->getID());
608  parallelEdgeIDs.push_back((*k)->getID());
609  std::sort(parallelEdgeIDs.begin(), parallelEdgeIDs.end());
610  WRITE_WARNING("Not joining junctions " + joinToStringSorting(nodeIDs, ',') + " because the cluster is too complex (parallel outgoing "
611  + joinToStringSorting(parallelEdgeIDs, ',') + ")");
612  foundParallel = true;
613  }
614  }
615  }
616  if (!foundParallel && cluster.size() > 1) {
617  // compute all connected components of this cluster
618  // (may be more than 1 if intermediate nodes were removed)
619  NodeClusters components;
620  for (std::set<NBNode*>::iterator j = cluster.begin(); j != cluster.end(); ++j) {
621  // merge all connected components into newComp
622  std::set<NBNode*> newComp;
623  NBNode* current = *j;
624  //std::cout << "checking connectivity for " << current->getID() << "\n";
625  newComp.insert(current);
626  for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end();) {
627  NodeClusters::iterator check = it_comp;
628  //std::cout << " connected with " << toString(*check) << "?\n";
629  bool connected = false;
630  for (std::set<NBNode*>::iterator k = (*check).begin(); k != (*check).end(); ++k) {
631  if (current->getConnectionTo(*k) != 0 || (*k)->getConnectionTo(current) != 0) {
632  //std::cout << "joining with connected component " << toString(*check) << "\n";
633  newComp.insert((*check).begin(), (*check).end());
634  it_comp = components.erase(check);
635  connected = true;
636  break;
637  }
638  }
639  if (!connected) {
640  it_comp++;
641  }
642  }
643  //std::cout << "adding new component " << toString(newComp) << "\n";
644  components.push_back(newComp);
645  }
646  for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end(); ++it_comp) {
647  if ((*it_comp).size() > 1) {
648  //std::cout << "adding cluster " << toString(*it_comp) << "\n";
649  clusters.push_back(*it_comp);
650  }
651  }
652  }
653  }
654  }
655  }
656  joinNodeClusters(clusters, dc, ec, tlc);
657  return (int)clusters.size();
658 }
659 
660 
661 void
664  for (NodeClusters::iterator i = clusters.begin(); i != clusters.end(); ++i) {
665  std::set<NBNode*> cluster = *i;
666  assert(cluster.size() > 1);
667  Position pos;
668  bool setTL;
669  std::string id;
670  TrafficLightType type;
671  analyzeCluster(cluster, id, pos, setTL, type);
672  if (!insert(id, pos)) {
673  // should not fail
674  WRITE_WARNING("Could not join junctions " + id);
675  continue;
676  }
677  NBNode* newNode = retrieve(id);
678  if (setTL) {
679  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, newNode, 0, type);
680  if (!tlc.insert(tlDef)) {
681  // actually, nothing should fail here
682  delete tlDef;
683  throw ProcessError("Could not allocate tls '" + id + "'.");
684  }
685  }
686  // collect edges
687  std::set<NBEdge*> allEdges;
688  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
689  const EdgeVector& edges = (*j)->getEdges();
690  allEdges.insert(edges.begin(), edges.end());
691  }
692 
693  // remap and remove edges which are completely within the new intersection
694  for (std::set<NBEdge*>::iterator j = allEdges.begin(); j != allEdges.end();) {
695  NBEdge* e = (*j);
696  NBNode* from = e->getFromNode();
697  NBNode* to = e->getToNode();
698  if (cluster.count(from) > 0 && cluster.count(to) > 0) {
699  for (std::set<NBEdge*>::iterator l = allEdges.begin(); l != allEdges.end(); ++l) {
700  if (e != *l) {
701  (*l)->replaceInConnections(e, e->getConnections());
702  }
703  }
704  ec.erase(dc, e);
705  allEdges.erase(j++); // erase does not invalidate the other iterators
706  } else {
707  ++j;
708  }
709  }
710 
711  // remap edges which are incoming / outgoing
712  for (std::set<NBEdge*>::iterator j = allEdges.begin(); j != allEdges.end(); ++j) {
713  NBEdge* e = (*j);
714  std::vector<NBEdge::Connection> conns = e->getConnections();
715  const bool outgoing = cluster.count(e->getFromNode()) > 0;
716  NBNode* from = outgoing ? newNode : e->getFromNode();
717  NBNode* to = outgoing ? e->getToNode() : newNode;
718  e->reinitNodes(from, to);
719  // re-add connections which previously existed and may still valid.
720  // connections to removed edges will be ignored
721  for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
722  e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::L2L_USER, false, (*k).mayDefinitelyPass);
723  }
724  }
725  // remove original nodes
726  registerJoinedCluster(cluster);
727  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
728  erase(*j);
729  }
730  }
731 }
732 
733 
734 void
735 NBNodeCont::registerJoinedCluster(const std::set<NBNode*>& cluster) {
736  std::set<std::string> ids;
737  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); j++) {
738  ids.insert((*j)->getID());
739  }
740  myJoinedClusters.push_back(ids);
741 }
742 
743 
744 void
745 NBNodeCont::analyzeCluster(std::set<NBNode*> cluster, std::string& id, Position& pos,
746  bool& hasTLS, TrafficLightType& type) {
747  id = "cluster";
748  hasTLS = false;
749  std::vector<std::string> member_ids;
750  bool ambiguousType = false;
751  for (std::set<NBNode*>::const_iterator j = cluster.begin(); j != cluster.end(); j++) {
752  member_ids.push_back((*j)->getID());
753  pos.add((*j)->getPosition());
754  // add a traffic light if any of the cluster members was controlled
755  if ((*j)->isTLControlled()) {
756  if (!hasTLS) {
757  // init type
758  type = (*(*j)->getControllingTLS().begin())->getType();
759  } else if (type != (*(*j)->getControllingTLS().begin())->getType()) {
760  ambiguousType = true;
761  }
762  hasTLS = true;
763  }
764  }
765  pos.mul(1.0 / cluster.size());
766  // need to sort the member names to make the output deterministic
767  sort(member_ids.begin(), member_ids.end());
768  for (std::vector<std::string>::iterator j = member_ids.begin(); j != member_ids.end(); j++) {
769  id = id + "_" + (*j);
770  }
771  if (ambiguousType) {
772  type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
773  WRITE_WARNING("Ambiguous traffic light type for node cluster '" + id + "' set to '" + toString(type) + "'");
774  }
775 }
776 
777 
778 // ----------- (Helper) methods for guessing/computing traffic lights
779 bool
780 NBNodeCont::shouldBeTLSControlled(const std::set<NBNode*>& c) const {
781  unsigned int noIncoming = 0;
782  unsigned int noOutgoing = 0;
783  bool tooFast = false;
784  SUMOReal f = 0;
785  std::set<NBEdge*> seen;
786  for (std::set<NBNode*>::const_iterator j = c.begin(); j != c.end(); ++j) {
787  const EdgeVector& edges = (*j)->getEdges();
788  for (EdgeVector::const_iterator k = edges.begin(); k != edges.end(); ++k) {
789  if (c.find((*k)->getFromNode()) != c.end() && c.find((*k)->getToNode()) != c.end()) {
790  continue;
791  }
792  if ((*j)->hasIncoming(*k)) {
793  ++noIncoming;
794  f += (SUMOReal)(*k)->getNumLanes() * (*k)->getLaneSpeed(0);
795  } else {
796  ++noOutgoing;
797  }
798  if ((*k)->getLaneSpeed(0) * 3.6 > 79) {
799  tooFast = true;
800  }
801  }
802  }
803  return !tooFast && f >= 150. / 3.6 && c.size() != 0;
804 }
805 
806 
807 void
809  // build list of definitely not tls-controlled junctions
810  std::vector<NBNode*> ncontrolled;
811  if (oc.isSet("tls.unset")) {
812  std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
813  for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
814  NBNode* n = NBNodeCont::retrieve(*i);
815  if (n == 0) {
816  throw ProcessError(" The node '" + *i + "' to set as not-controlled is not known.");
817  }
818  std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
819  for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
820  (*j)->removeNode(n);
821  }
822  n->removeTrafficLights();
823  ncontrolled.push_back(n);
824  }
825  }
826 
828  // loop#1 checking whether the node shall be tls controlled,
829  // because it is assigned to a district
830  if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
831  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
832  NBNode* cur = (*i).second;
833  if (cur->isNearDistrict() && find(ncontrolled.begin(), ncontrolled.end(), cur) == ncontrolled.end()) {
834  setAsTLControlled(cur, tlc, type);
835  }
836  }
837  }
838 
839  // figure out which nodes mark the locations of TLS signals
840  // This assumes nodes are already joined
841  if (oc.exists("tls.guess-signals") && oc.getBool("tls.guess-signals")) {
842  // prepare candidate edges
843  const SUMOReal signalDist = oc.getFloat("tls.guess-signals.dist");
844  for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
845  NBNode* node = (*i).second;
846  if (node->isTLControlled() && node->geometryLike()) {
847  const EdgeVector& outgoing = node->getOutgoingEdges();
848  for (EdgeVector::const_iterator it_o = outgoing.begin(); it_o != outgoing.end(); ++it_o) {
849  (*it_o)->setSignalOffset((*it_o)->getLength());
850  }
851  }
852  }
853  // check which nodes should be controlled
854  for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
855  NBNode* node = i->second;
856  const EdgeVector& incoming = node->getIncomingEdges();
857  if (!node->isTLControlled() && incoming.size() > 1 && !node->geometryLike()) {
858  std::vector<NBNode*> signals;
859  bool isTLS = true;
860  for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
861  const NBEdge* inEdge = *it_i;
862  if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET || inEdge->getSignalOffset() > signalDist) {
863  isTLS = false;
864  break;
865  }
866  if (inEdge->getSignalOffset() == inEdge->getLength()) {
867  signals.push_back(inEdge->getFromNode());
868  }
869  }
870  if (isTLS) {
871  for (std::vector<NBNode*>::iterator j = signals.begin(); j != signals.end(); ++j) {
872  std::set<NBTrafficLightDefinition*> tls = (*j)->getControllingTLS();
873  (*j)->removeTrafficLights();
874  for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
875  tlc.removeFully((*j)->getID());
876  }
877  }
878  NBTrafficLightDefinition* tlDef = new NBOwnTLDef("GS_" + node->getID(), node, 0, TLTYPE_STATIC);
879  // @todo patch endOffset for all incoming lanes according to the signal positions
880  if (!tlc.insert(tlDef)) {
881  // actually, nothing should fail here
882  WRITE_WARNING("Could not build joined tls '" + node->getID() + "'.");
883  delete tlDef;
884  return;
885  }
886  }
887  }
888  }
889  }
890 
891  // maybe no tls shall be guessed
892  if (!oc.getBool("tls.guess")) {
893  return;
894  }
895 
896  // guess joined tls first, if wished
897  if (oc.getBool("tls.join")) {
898  // get node clusters
899  std::vector<std::set<NBNode*> > cands;
900  generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
901  // check these candidates (clusters) whether they should be controlled by a tls
902  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end();) {
903  std::set<NBNode*>& c = (*i);
904  // regard only junctions which are not yet controlled and are not
905  // forbidden to be controlled
906  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end();) {
907  if ((*j)->isTLControlled() || find(ncontrolled.begin(), ncontrolled.end(), *j) != ncontrolled.end()) {
908  c.erase(j++);
909  } else {
910  ++j;
911  }
912  }
913  // check whether the cluster should be controlled
914  if (!shouldBeTLSControlled(c)) {
915  i = cands.erase(i);
916  } else {
917  ++i;
918  }
919  }
920  // cands now only contain sets of junctions that shall be joined into being tls-controlled
921  unsigned int index = 0;
922  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end(); ++i) {
923  std::vector<NBNode*> nodes;
924  for (std::set<NBNode*>::iterator j = (*i).begin(); j != (*i).end(); j++) {
925  nodes.push_back(*j);
926  }
927  std::string id = "joinedG_" + toString(index++);
928  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
929  if (!tlc.insert(tlDef)) {
930  // actually, nothing should fail here
931  WRITE_WARNING("Could not build guessed, joined tls");
932  delete tlDef;
933  return;
934  }
935  }
936  }
937 
938  // guess tls
939  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
940  NBNode* cur = (*i).second;
941  // do nothing if already is tl-controlled
942  if (cur->isTLControlled()) {
943  continue;
944  }
945  // do nothing if in the list of explicit non-controlled junctions
946  if (find(ncontrolled.begin(), ncontrolled.end(), cur) != ncontrolled.end()) {
947  continue;
948  }
949  std::set<NBNode*> c;
950  c.insert(cur);
951  if (!shouldBeTLSControlled(c) || cur->getIncomingEdges().size() < 3) {
952  continue;
953  }
954  setAsTLControlled((*i).second, tlc, type);
955  }
956 }
957 
958 
959 void
961  std::vector<std::set<NBNode*> > cands;
962  generateNodeClusters(maxdist, cands);
963  unsigned int index = 0;
964  for (std::vector<std::set<NBNode*> >::iterator i = cands.begin(); i != cands.end(); ++i) {
965  std::set<NBNode*>& c = (*i);
966  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end();) {
967  if (!(*j)->isTLControlled()) {
968  c.erase(j++);
969  } else {
970  ++j;
971  }
972  }
973  if (c.size() < 2) {
974  continue;
975  }
976  // figure out type of the joined TLS
977  Position dummyPos;
978  bool dummySetTL;
979  std::string dummyId;
980  TrafficLightType type;
981  analyzeCluster(c, dummyId, dummyPos, dummySetTL, type);
982  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end(); ++j) {
983  std::set<NBTrafficLightDefinition*> tls = (*j)->getControllingTLS();
984  (*j)->removeTrafficLights();
985  for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
986  tlc.removeFully((*j)->getID());
987  }
988  }
989  std::string id = "joinedS_" + toString(index++);
990  std::vector<NBNode*> nodes;
991  for (std::set<NBNode*>::iterator j = c.begin(); j != c.end(); j++) {
992  nodes.push_back(*j);
993  }
994  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
995  if (!tlc.insert(tlDef)) {
996  // actually, nothing should fail here
997  WRITE_WARNING("Could not build a joined tls.");
998  delete tlDef;
999  return;
1000  }
1001  }
1002 }
1003 
1004 
1005 void
1007  TrafficLightType type, std::string id) {
1008  if (id == "") {
1009  id = node->getID();
1010  }
1011  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
1012  if (!tlc.insert(tlDef)) {
1013  // actually, nothing should fail here
1014  WRITE_WARNING("Building a tl-logic for node '" + id + "' twice is not possible.");
1015  delete tlDef;
1016  return;
1017  }
1018 }
1019 
1020 
1021 // -----------
1022 void
1023 NBNodeCont::computeLanes2Lanes(const bool buildCrossingsAndWalkingAreas) {
1024  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1025  (*i).second->computeLanes2Lanes(buildCrossingsAndWalkingAreas);
1026  }
1027 }
1028 
1029 
1030 // computes the "wheel" of incoming and outgoing edges for every node
1031 void
1033  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1034  (*i).second->computeLogic(ec, oc);
1035  }
1036 }
1037 
1038 
1039 void
1041  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1042  delete((*i).second);
1043  }
1044  myNodes.clear();
1045  for (std::set<NBNode*>::iterator i = myExtractedNodes.begin(); i != myExtractedNodes.end(); i++) {
1046  delete(*i);
1047  }
1048  myExtractedNodes.clear();
1049 }
1050 
1051 
1052 std::string
1054  // !!! not guaranteed to be free
1055  std::string ret = "SUMOGenerated" + toString<int>(size());
1056  assert(retrieve(ret) == 0);
1057  return ret;
1058 }
1059 
1060 
1061 void
1062 NBNodeCont::computeNodeShapes(bool leftHand, SUMOReal mismatchThreshold) {
1063  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1064  (*i).second->computeNodeShape(leftHand, mismatchThreshold);
1065  }
1066 }
1067 
1068 
1069 void
1071  int numUnregulatedJunctions = 0;
1072  int numDeadEndJunctions = 0;
1073  int numPriorityJunctions = 0;
1074  int numRightBeforeLeftJunctions = 0;
1075  int numAllWayStopJunctions = 0;
1076  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1077  switch ((*i).second->getType()) {
1078  case NODETYPE_NOJUNCTION:
1080  ++numUnregulatedJunctions;
1081  break;
1082  case NODETYPE_DEAD_END:
1083  ++numDeadEndJunctions;
1084  break;
1085  case NODETYPE_PRIORITY:
1088  ++numPriorityJunctions;
1089  break;
1091  ++numRightBeforeLeftJunctions;
1092  break;
1093  case NODETYPE_ALLWAY_STOP:
1094  ++numAllWayStopJunctions;
1095  break;
1096  case NODETYPE_DISTRICT:
1097  ++numRightBeforeLeftJunctions;
1098  break;
1099  case NODETYPE_UNKNOWN:
1100  break;
1101  default:
1102  break;
1103  }
1104  }
1105  WRITE_MESSAGE(" Node type statistics:");
1106  WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
1107  if (numDeadEndJunctions > 0) {
1108  WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
1109  }
1110  WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
1111  WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
1112  if (numAllWayStopJunctions > 0) {
1113  WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
1114  }
1115 }
1116 
1117 
1118 std::vector<std::string>
1120  std::vector<std::string> ret;
1121  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1122  ret.push_back((*i).first);
1123  }
1124  return ret;
1125 }
1126 
1127 
1128 void
1129 NBNodeCont::rename(NBNode* node, const std::string& newID) {
1130  if (myNodes.count(newID) != 0) {
1131  throw ProcessError("Attempt to rename node using existing id '" + newID + "'");
1132  }
1133  myNodes.erase(node->getID());
1134  node->setID(newID);
1135  myNodes[newID] = node;
1136 }
1137 
1138 
1139 void
1140 NBNodeCont::discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike, bool guessSignals) {
1141  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1142  NBNode* node = i->second;
1143  if (!geometryLike || node->geometryLike()) {
1144  // make a copy of tldefs
1145  const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
1146  if (guessSignals && node->isTLControlled() && node->geometryLike()) {
1147  // record signal location
1148  const EdgeVector& outgoing = node->getOutgoingEdges();
1149  for (EdgeVector::const_iterator it_o = outgoing.begin(); it_o != outgoing.end(); ++it_o) {
1150  (*it_o)->setSignalOffset((*it_o)->getLength());
1151  }
1152  }
1153  for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
1154  NBTrafficLightDefinition* tlDef = *it;
1155  node->removeTrafficLight(tlDef);
1156  tlc.extract(tlDef);
1157  }
1158  node->reinit(node->getPosition(), NODETYPE_UNKNOWN);
1159  }
1160  }
1161 }
1162 
1163 /****************************************************************************/
1164