|
|
|
#include <DetectorDescription/Core/interface/graph_path.h>
Public Types | |
| typedef std::vector< pair< N, N > > | chain_type |
| typedef set< std::vector< N > > | paths_set |
| typedef std::map< segment_type, set< segment_type > > | paths_type |
| typedef std::vector < std::vector< segment_type > > | result_type |
| typedef pair< N, N > | segment_type |
Public Member Functions | |
| void | calcPaths (const graph< N, E > &g, const N &root) |
| creates a lookup-table of starting-points of pathes between nodes n A and B A->B: A->X, A->Y, B->B (B->B denotes a direct connectino between A and B, A->X means that B can be reached from X directly while X can be reached from A) the lookup-table is stored in a std::map< pair<n,n>, set< pair<n,n> > (could be a multistd::map. | |
| void | findSegments (const N &n, set< segment_type > &result) |
| bool | fromTo (const N &from, const N &to, std::vector< std::vector< N > > &result) const |
| GraphPath (const graph< N, E > &g, const N &root) | |
| bool | paths2 (const segment_type &ft, result_type &result) const |
| |
| void | stream (std::ostream &) |
| void | update (segment_type &s, result_type &r, int pos) const |
| ~GraphPath () | |
Public Attributes | |
| paths_type | paths_ |
Definition at line 13 of file graph_path.h.
| typedef std::vector< pair<N,N> > GraphPath< N, E >::chain_type |
Definition at line 20 of file graph_path.h.
Definition at line 19 of file graph_path.h.
| typedef std::map< segment_type, set< segment_type > > GraphPath< N, E >::paths_type |
Definition at line 18 of file graph_path.h.
| typedef std::vector<std::vector<segment_type> > GraphPath< N, E >::result_type |
Definition at line 21 of file graph_path.h.
| typedef pair<N,N> GraphPath< N, E >::segment_type |
Definition at line 16 of file graph_path.h.
| GraphPath< N, E >::GraphPath | ( | const graph< N, E > & | g, | |
| const N & | root | |||
| ) | [inline] |
| void GraphPath< N, E >::calcPaths | ( | const graph< N, E > & | g, | |
| const N & | n | |||
| ) | [inline] |
creates a lookup-table of starting-points of pathes between nodes n A and B A->B: A->X, A->Y, B->B (B->B denotes a direct connectino between A and B, A->X means that B can be reached from X directly while X can be reached from A) the lookup-table is stored in a std::map< pair<n,n>, set< pair<n,n> > (could be a multistd::map.
.)
Definition at line 216 of file graph_path.h.
References graph< N, E >::begin(), GraphPath< N, E >::findSegments(), getDQMSummary::key, GraphPath< N, E >::paths_, and pyDBSRunClass::temp.
Referenced by GraphPath< N, E >::GraphPath().
00217 { 00218 // find n(ode) in g(raph) and all its children (get rid of the 00219 // multiconnections ... 00220 //set< pair<N,E> > nodes; 00221 pair<bool,graph<N,E>::neighbour_range> childRange = g.nodes(n); 00222 if (!childRange.first) 00223 return; 00224 00225 set<N> children; 00226 typename set< pair<N,E> >::const_iterator nit = childRange.second.first; 00227 for(; nit!=childRange.second.second; ++nit) 00228 children.insert(nit->first); 00229 00230 // iterate over children and .. 00231 typename set<N>::iterator cit = children.begin(); 00232 for(; cit!=children.end(); ++cit) { 00233 segment_type key = segment_type(n,*cit); // create new direct path-segment 00234 segment_type direct = segment_type(*cit,*cit); 00235 set< segment_type > temp; 00236 temp.insert(direct); // add direct connection as first member of set, 00237 // but not as <A,B> but as <B,B> to mark a direct connection 00238 //if(n != *cit) { 00239 paths_.insert(std::make_pair(key,temp)); 00240 findSegments(n,temp); // look for previous segments leading to n 00241 typename set< segment_type >::iterator sit = temp.begin(); 00242 for (; sit!=temp.end(); ++sit) { // iterator over already linked segments 00243 if (sit->first != key.second) // don't insert <B,B> as key! 00244 paths_[segment_type(sit->first,key.second)].insert(*sit); 00245 } 00246 //} 00247 //calcPath(g,*cit); 00248 } 00249 for(cit=children.begin();cit!=children.end();++cit) { 00250 //if (n != * cit) 00251 calcPaths(g,*cit); 00252 } 00253 }
| void GraphPath< N, E >::findSegments | ( | const N & | n, | |
| set< segment_type > & | result | |||
| ) | [inline] |
Definition at line 257 of file graph_path.h.
References GraphPath< N, E >::paths_.
Referenced by GraphPath< N, E >::calcPaths().
00258 { 00259 typename paths_type::iterator pit = paths_.begin(); 00260 for (; pit!=paths_.end(); ++pit) { 00261 if (pit->first.second == n) 00262 result.insert(pit->first); 00263 } 00264 }
| bool GraphPath< N, E >::fromTo | ( | const N & | from, | |
| const N & | to, | |||
| std::vector< std::vector< N > > & | result | |||
| ) | const [inline] |
Definition at line 94 of file graph_path.h.
References first, N, GraphPath< N, E >::paths2(), HLT_VtxMuL3::result, target, and v.
00095 { 00096 result_type tres; 00097 bool rslt=false; 00098 if (paths2(segment_type(from,to),tres)) { 00099 typename result_type::iterator rit = tres.begin(); // iterator over std::vector< std::vector<seg_t> > 00100 for (; rit!=tres.end(); ++rit) { 00101 N & target = (*rit)[0].second; 00102 typename std::vector<segment_type>::reverse_iterator pit = rit->rbegin(); 00103 typename std::vector<segment_type>::reverse_iterator pend = rit->rend(); 00104 --pend; 00105 std::vector<N> v(1,(*rit)[0].first); // <A,X> -> <A> 00106 //std::cout << pit->first << '-'; 00107 ++pit; 00108 for(; pit!=pend; ++pit) { 00109 v.push_back(pit->second); 00110 //std::cout << pit->second << '-'; 00111 } 00112 //std::cout << target << std::endl; 00113 v.push_back(target); 00114 result.push_back(v); 00115 } 00116 00117 rslt=true; 00118 } 00119 00120 return rslt; 00121 }
| bool GraphPath< N, E >::paths2 | ( | const segment_type & | ft, | |
| result_type & | result | |||
| ) | const [inline] |
Definition at line 125 of file graph_path.h.
References i, GraphPath< N, E >::paths_, GraphPath< N, E >::update(), and v.
Referenced by GraphPath< N, E >::fromTo().
00126 { 00127 typename paths_type::const_iterator git = paths_.find(ft); 00128 if (git==paths_.end()) { 00129 result.clear(); 00130 return false; 00131 } 00132 00133 std::vector<segment_type> v; 00134 v.push_back(git->first); 00135 result.push_back(v); // starting point; the set will be enlarged & the std::vectors inside 00136 // get pushed_back as new path-segments appear ... 00137 00138 // find a possible direct-connetion: 00139 //set<segment_type>::iterator direct_it = 00140 00141 bool goOn(true); 00142 00143 while(goOn) { 00144 //FIXME: use size_type whenever possible .. 00145 int u = result.size(); 00146 int i; 00147 int cntdwn=u; 00148 for (i=0; i<u; ++i) { 00149 segment_type & upd_seg = result[i].back(); 00150 if (upd_seg.first!=upd_seg.second) // only update result if not <X,X> !! 00151 update(upd_seg,result,i); // adds new paths .. 00152 else 00153 --cntdwn; 00154 } 00155 goOn = bool(cntdwn); 00156 00157 //std::cout << "0.--: cntdwn=" << cntdwn << std::endl; 00158 /* PRINT THE RESULT 00159 result_type::iterator rit = result.begin(); 00160 for(; rit!=result.end(); ++rit) { 00161 std::vector<segment_type>::iterator pit = rit->begin(); 00162 for(; pit!=rit->end(); ++pit) { 00163 std::cout << "[" << pit->first << "," << pit->second << "] "; 00164 } 00165 std::cout << std::endl; 00166 } 00167 std::cout << "===========" << std::endl; 00168 */ 00169 } 00170 return true; 00171 }
Definition at line 267 of file graph_path.h.
References lat::endl(), it, and GraphPath< N, E >::paths_.
00268 { 00269 typename paths_type::iterator it = paths_.begin(); 00270 for(; it!=paths_.end(); ++it) { 00271 os << "[" << it->first.first << "->" << it->first.second << "] : "; 00272 typename set<segment_type>::iterator sit = it->second.begin(); 00273 os << "< "; 00274 for(; sit!=it->second.end();++sit) { 00275 os << " [" << sit->first << "->" << sit->second << "] "; 00276 } 00277 os << " >" << std::endl; 00278 00279 } 00280 }
| void GraphPath< N, E >::update | ( | segment_type & | s, | |
| result_type & | r, | |||
| int | pos | |||
| ) | const [inline] |
Definition at line 175 of file graph_path.h.
References TestMuL1L2Filter_cff::cerr, lat::endl(), cmsRelvalreport::exit, GraphPath< N, E >::paths_, and v.
Referenced by GraphPath< N, E >::paths2().
00176 { 00177 // s ... segment, which is used to find its children 00178 // result ... std::vector of path-std::vectors 00179 // u ... path in result which is currently under observation, s is it's 'back' 00180 const set<segment_type> & segs = paths_.find(s)->second; 00181 typename set<segment_type>::const_iterator segit = segs.begin(); 00182 00183 if (segs.size()==0) { 00184 cerr << "you should never get here: GraphPath::update(...)" << std::endl; 00185 exit(1); 00186 } 00187 /* 00188 std::cout << "1. s=" << s.first << " " << s.second 00189 << " aseg=" << segit->first << " " << segit->second << std::endl; 00190 */ 00191 std::vector<segment_type> temp_pth = result[u]; 00192 ++segit; 00193 for (; segit!=segs.end(); ++segit) { // create new pathes (whenever a the path-tree is branching) 00194 std::vector<segment_type> v = temp_pth; 00195 v.push_back(*segit); 00196 result.push_back(v); 00197 } 00198 temp_pth.push_back(*segs.begin()); // just append the first new segment to the existing one (also, when no branch!) 00199 result[u]=temp_pth; 00200 }
| paths_type GraphPath< N, E >::paths_ |
Definition at line 38 of file graph_path.h.
Referenced by GraphPath< N, E >::calcPaths(), GraphPath< N, E >::findSegments(), GraphPath< N, E >::paths2(), GraphPath< N, E >::stream(), and GraphPath< N, E >::update().
1.5.4