GraphPath< N, E > Class Template Reference

#include <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)
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_

Detailed Description

template<class N, class E>
class GraphPath< N, E >

Definition at line 13 of file graph_path.h.

Member Typedef Documentation

template<class N , class E >

typedef std::vector< pair<N,N> > GraphPath< N, E >::chain_type

Definition at line 20 of file graph_path.h.

template<class N , class E >

typedef set< std::vector<N> > GraphPath< N, E >::paths_set

Definition at line 19 of file graph_path.h.

template<class N , class E >

typedef std::map< segment_type, set< segment_type > > GraphPath< N, E >::paths_type

Definition at line 18 of file graph_path.h.

template<class N , class E >

typedef std::vector<std::vector<segment_type> > GraphPath< N, E >::result_type

Definition at line 21 of file graph_path.h.

template<class N , class E >

typedef pair<N,N> GraphPath< N, E >::segment_type

Definition at line 16 of file graph_path.h.

Constructor & Destructor Documentation

template<class N , class E >

GraphPath< N, E >::GraphPath	(	const graph< N, E > &	g,
		const N &	root
	)

Definition at line 204 of file graph_path.h.

References GraphPath< N, E >::calcPaths().

{
   calcPaths(g,root);
}

template<class N , class E >

GraphPath< N, E >::~GraphPath ( )

inline

Definition at line 23 of file graph_path.h.

References GraphPath< N, E >::calcPaths(), GraphPath< N, E >::findSegments(), GraphPath< N, E >::fromTo(), g, N, gen::n, GraphPath< N, E >::paths2(), alignCSCRings::r, mps_fire::result, alignCSCRings::s, GraphPath< N, E >::stream(), and GraphPath< N, E >::update().

{}

Member Function Documentation

template<class N , class E >

void GraphPath< N, E >::calcPaths	(	const graph< N, E > &	g,
		const N &	n
	)

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 class-composition::children, GraphPath< N, E >::findSegments(), crabWrapper::key, GraphPath< N, E >::paths_, and groupFilesInBlocks::temp.

Referenced by GraphPath< N, E >::GraphPath(), and GraphPath< N, E >::~GraphPath().

{
   // find n(ode) in g(raph) and all its children (get rid of the
   // multiconnections ...
   //set< pair<N,E> > nodes;
   pair<bool,graph<N,E>::neighbour_range> childRange = g.nodes(n);
   if (!childRange.first) 
     return;
   
   set<N> children;
   typename set< pair<N,E> >::const_iterator nit = childRange.second.first;
   for(; nit!=childRange.second.second; ++nit)
     children.insert(nit->first);
   
   // iterate over children and ..
   typename set<N>::iterator cit = children.begin();
   for(; cit!=children.end(); ++cit) {
     segment_type key = segment_type(n,*cit); // create new direct path-segment
     segment_type direct = segment_type(*cit,*cit);
     set< segment_type > temp;
     temp.insert(direct); // add direct connection as first member of set,
                          // but not as <A,B> but as <B,B> to mark a direct connection
     //if(n != *cit) {            
       paths_.insert(std::make_pair(key,temp));
       findSegments(n,temp); // look for previous segments leading to n
       typename set< segment_type >::iterator sit = temp.begin();
       for (; sit!=temp.end(); ++sit) { // iterator over already linked segments
         if (sit->first != key.second) // don't insert <B,B> as key!
           paths_[segment_type(sit->first,key.second)].insert(*sit);
       }
     //} 
     //calcPath(g,*cit);        
   }
   for(cit=children.begin();cit!=children.end();++cit) {
     //if (n != * cit)
       calcPaths(g,*cit);  
   }  
}

template<class N , class E >

void GraphPath< N, E >::findSegments	(	const N &	n,
		set< segment_type > &	result
	)

Definition at line 257 of file graph_path.h.

References GraphPath< N, E >::paths_.

Referenced by GraphPath< N, E >::calcPaths(), and GraphPath< N, E >::~GraphPath().

{
   typename paths_type::iterator pit = paths_.begin();
   for (; pit!=paths_.end(); ++pit) {
     if (pit->first.second == n)
       result.insert(pit->first);
   }    
}

template<class N , class E >

bool GraphPath< N, E >::fromTo	(	const N &	from,
		const N &	to,
		std::vector< std::vector< N > > &	result
	)		const

Definition at line 94 of file graph_path.h.

References plotBeamSpotDB::first, N, GraphPath< N, E >::paths2(), mps_fire::result, edmPickEvents::target, and findQualityFiles::v.

Referenced by GraphPath< N, E >::~GraphPath().

{
   result_type tres;
   bool rslt=false;
   if (paths2(segment_type(from,to),tres)) {
     typename result_type::iterator rit = tres.begin(); // iterator over std::vector< std::vector<seg_t> >
     for (; rit!=tres.end(); ++rit) {
       N & target = (*rit)[0].second;
       typename std::vector<segment_type>::reverse_iterator pit = rit->rbegin();
       typename std::vector<segment_type>::reverse_iterator pend = rit->rend(); 
       --pend;
       std::vector<N> v(1,(*rit)[0].first); // <A,X> -> <A>
       //std::cout << pit->first << '-';
       ++pit;
       for(; pit!=pend; ++pit) {
         v.push_back(pit->second);
     //std::cout << pit->second << '-';
       }     
       //std::cout << target << std::endl;
       v.push_back(target);
       result.push_back(v);  
     }

     rslt=true;
   }
   
   return rslt;
}

template<class N , class E >

bool GraphPath< N, E >::paths2	(	const segment_type &	ft,
		result_type &	result
	)		const

• false, if no (directed!) path between fromTo.first and fromTo.second, p = empty set
• true, if (directed!) paths exist between fromTo.first an fromTo.second, p = set of pathnodes

Definition at line 125 of file graph_path.h.

References i, GraphPath< N, E >::paths_, GraphPath< N, E >::update(), and findQualityFiles::v.

Referenced by GraphPath< N, E >::fromTo(), and GraphPath< N, E >::~GraphPath().

{
  typename paths_type::const_iterator git = paths_.find(ft);
  if (git==paths_.end()) {
    result.clear();
    return false;
  }
  
  std::vector<segment_type> v;
  v.push_back(git->first);
  result.push_back(v); // starting point; the set will be enlarged & the std::vectors inside
                    // get pushed_back as new path-segments appear ...
  
  // find a possible direct-connetion:
  //set<segment_type>::iterator direct_it = 
  
  bool goOn(true);
  
  while(goOn) {
    //FIXME: use size_type whenever possible ..
    int u = result.size();
    int i;
    int cntdwn=u;
    for (i=0; i<u; ++i) {
      segment_type & upd_seg = result[i].back();
      if (upd_seg.first!=upd_seg.second) // only update result if not <X,X> !!
        update(upd_seg,result,i); // adds new paths ..
      else
        --cntdwn;
    }
    goOn = bool(cntdwn);
    
    //std::cout << "0.--: cntdwn=" << cntdwn << std::endl;
    /* PRINT THE RESULT
    result_type::iterator rit = result.begin();
    for(; rit!=result.end(); ++rit) {
      std::vector<segment_type>::iterator pit = rit->begin();
      for(; pit!=rit->end(); ++pit) {
        std::cout << "[" << pit->first << "," << pit->second << "] ";
      }
      std::cout << std::endl;
    }  
    std::cout << "===========" << std::endl;
    */
  }    
  return true;
} 

template<class N , class E >

void GraphPath< N, E >::stream

(

std::ostream &

os

)

Definition at line 267 of file graph_path.h.

References GraphPath< N, E >::paths_.

Referenced by GraphPath< N, E >::~GraphPath().

{
  typename paths_type::iterator it = paths_.begin();
  for(; it!=paths_.end(); ++it) {
    os << "[" << it->first.first << "->" << it->first.second << "] : ";
    typename set<segment_type>::iterator sit = it->second.begin();
    os << "< ";
    for(; sit!=it->second.end();++sit) {
      os << " [" << sit->first << "->" << sit->second << "] ";
    }  
    os << " >" << std::endl;  
    
  }
}

template<class N , class E >

void GraphPath< N, E >::update	(	segment_type &	s,
		result_type &	r,
		int	pos
	)		const

Definition at line 175 of file graph_path.h.

References MessageLogger_cfi::cerr, cmsRelvalreport::exit, GraphPath< N, E >::paths_, and findQualityFiles::v.

Referenced by progressbar.ProgressBar::__next__(), MatrixUtil.Matrix::__setitem__(), MatrixUtil.Steps::__setitem__(), Vispa.Gui.VispaWidget.VispaWidget::autosize(), Vispa.Views.LineDecayView.LineDecayContainer::createObject(), Vispa.Views.LineDecayView.LineDecayContainer::deselectAllObjects(), Vispa.Gui.VispaWidgetOwner.VispaWidgetOwner::deselectAllWidgets(), Vispa.Gui.VispaWidget.VispaWidget::enableAutosizing(), dqm-mbProfile.Profile::finish(), progressbar.ProgressBar::finish(), Vispa.Gui.MenuWidget.MenuWidget::leaveEvent(), Vispa.Gui.VispaWidgetOwner.VispaWidgetOwner::mouseMoveEvent(), Vispa.Gui.MenuWidget.MenuWidget::mouseMoveEvent(), Vispa.Views.LineDecayView.LineDecayContainer::mouseMoveEvent(), Vispa.Gui.VispaWidgetOwner.VispaWidgetOwner::mouseReleaseEvent(), Vispa.Views.LineDecayView.LineDecayContainer::objectMoved(), MatrixUtil.Steps::overwrite(), GraphPath< N, E >::paths2(), Vispa.Views.LineDecayView.LineDecayContainer::removeObject(), Vispa.Gui.ConnectableWidget.ConnectableWidget::removePorts(), Vispa.Gui.FindDialog.FindDialog::reset(), Vispa.Gui.PortConnection.PointToPointConnection::select(), Vispa.Gui.VispaWidget.VispaWidget::select(), Vispa.Views.LineDecayView.LineDecayContainer::select(), Vispa.Gui.VispaWidget.VispaWidget::setText(), Vispa.Gui.VispaWidget.VispaWidget::setTitle(), Vispa.Gui.ZoomableWidget.ZoomableWidget::setZoom(), Vispa.Views.LineDecayView.LineDecayContainer::setZoom(), Vispa.Gui.PortConnection.PointToPointConnection::updateConnection(), and GraphPath< N, E >::~GraphPath().

{
   // s ...      segment, which is used to find its children
   // result ... std::vector of path-std::vectors
   // u ...      path in result which is currently under observation, s is it's 'back'
   const set<segment_type> & segs = paths_.find(s)->second;
   typename set<segment_type>::const_iterator segit = segs.begin();

   if (segs.size()==0)  {
     cerr << "you should never get here: GraphPath::update(...)" << std::endl;
     exit(1);
   }  
   /*
   std::cout << "1. s=" << s.first << " " << s.second 
        << " aseg=" << segit->first << " " << segit->second << std::endl;
   */
   std::vector<segment_type>  temp_pth = result[u];
   ++segit;
   for (; segit!=segs.end(); ++segit) { // create new pathes (whenever a the path-tree is branching)
     std::vector<segment_type> v = temp_pth;
     v.push_back(*segit);
     result.push_back(v);     
   }
   temp_pth.push_back(*segs.begin()); // just append the first new segment to the existing one (also, when no branch!)
   result[u]=temp_pth;
}

Member Data Documentation

template<class N , class E >

paths_type GraphPath< N, E >::paths_

Definition at line 38 of file graph_path.h.

Referenced by Config.Process::_insertPaths(), GraphPath< N, E >::calcPaths(), Config.Process::dumpConfig(), Config.Process::dumpPython(), GraphPath< N, E >::findSegments(), Config.Process::pathNames(), GraphPath< N, E >::paths2(), GraphPath< N, E >::stream(), and GraphPath< N, E >::update().