CMS 3D CMS Logo
Classes | Public Types | Public Member Functions | Private Attributes

graph< N, E > Class Template Reference

#include <adjgraph.h>

List of all members.

Classes

class  const_iterator
struct  value_type

Public Types

typedef adj_list::iterator adj_iterator
typedef std::vector< edge_list > adj_list
typedef adj_list::const_iterator const_adj_iterator
typedef edge_list::const_iterator const_edge_iterator
typedef std::pair
< const_edge_iterator,
const_edge_iterator > 		const_edge_range
typedef
indexer_type::const_iterator 		const_indexer_iterator
typedef edge_list::iterator edge_iterator
typedef std::vector< edge_type > edge_list
typedef std::pair
< edge_iterator, edge_iterator > 		edge_range
typedef std::vector< E > edge_store
typedef std::pair< index_type,
index_type > 		edge_type
typedef std::pair< index_type,
bool > 		index_result
typedef std::vector< double >
::size_type 		index_type
typedef indexer_type::iterator indexer_iterator
typedef std::map< N, index_type > indexer_type
typedef std::vector< N > node_list

Public Member Functions

void addEdge (const N &from, const N &to, const E &edge)
index_type addNode (const N &)
adj_iterator begin ()
const_adj_iterator begin () const
const_iterator begin_iter () const
void clear ()
 it clear everything!
void dump_graph () const
size_t edge_size () const
const E & edgeData (index_type i) const
const_edge_range edges (index_type nodeIndex) const
edge_range edges (const N &)
const_edge_range edges (const N &) const
edge_range edges (index_type nodeIndex)
adj_iterator end ()
const_adj_iterator end () const
const_iterator end_iter () const
void findRoots (edge_list &) const
 graph ()
void invert (graph &g) const
const N & nodeData (const edge_type &) const
const N & nodeData (const const_adj_iterator &) const
const N & nodeData (index_type) const
index_result nodeIndex (const N &) const
bool replace (const N &oldNode, const N &newNode)
bool replaceEdge (const E &ldEdge, const E &newEdge)
adj_list::size_type size () const
void swap (graph< N, E > &)
 ~graph ()

Private Attributes

adj_list adjl_
edge_store edges_
edge_list emptyEdges_
indexer_type indexer_
node_list nodes_

Detailed Description

template<class N, class E>
class graph< N, E >

Definition at line 15 of file adjgraph.h.

Member Typedef Documentation

template<class N, class E>
typedef adj_list::iterator graph< N, E >::adj_iterator

Definition at line 125 of file adjgraph.h.

template<class N, class E>
typedef std::vector<edge_list> graph< N, E >::adj_list

Definition at line 124 of file adjgraph.h.

template<class N, class E>
typedef adj_list::const_iterator graph< N, E >::const_adj_iterator

Definition at line 126 of file adjgraph.h.

template<class N, class E>
typedef edge_list::const_iterator graph< N, E >::const_edge_iterator

Definition at line 137 of file adjgraph.h.

template<class N, class E>
typedef std::pair<const_edge_iterator, const_edge_iterator> graph< N, E >::const_edge_range

Definition at line 141 of file adjgraph.h.

template<class N, class E>
typedef indexer_type::const_iterator graph< N, E >::const_indexer_iterator

Definition at line 132 of file adjgraph.h.

template<class N, class E>
typedef edge_list::iterator graph< N, E >::edge_iterator

Definition at line 135 of file adjgraph.h.

template<class N, class E>
typedef std::vector<edge_type> graph< N, E >::edge_list

Definition at line 121 of file adjgraph.h.

template<class N, class E>
typedef std::pair<edge_iterator,edge_iterator> graph< N, E >::edge_range

Definition at line 139 of file adjgraph.h.

template<class N, class E>
typedef std::vector<E> graph< N, E >::edge_store

Definition at line 118 of file adjgraph.h.

template<class N, class E>
typedef std::pair<index_type, index_type> graph< N, E >::edge_type

Definition at line 114 of file adjgraph.h.

template<class N, class E>
typedef std::pair<index_type, bool> graph< N, E >::index_result

Definition at line 143 of file adjgraph.h.

template<class N, class E>
typedef std::vector<double>::size_type graph< N, E >::index_type

Definition at line 111 of file adjgraph.h.

template<class N, class E>
typedef indexer_type::iterator graph< N, E >::indexer_iterator

Definition at line 131 of file adjgraph.h.

template<class N, class E>
typedef std::map<N, index_type> graph< N, E >::indexer_type

Definition at line 130 of file adjgraph.h.

template<class N, class E>
typedef std::vector<N> graph< N, E >::node_list

Definition at line 117 of file adjgraph.h.

Constructor & Destructor Documentation

template<class N, class E>
graph< N, E >::graph ( ) [inline]

Definition at line 147 of file adjgraph.h.

: edges_(1)  { }
template<class N, class E>
graph< N, E >::~graph ( ) [inline]

Definition at line 148 of file adjgraph.h.

{ }

Member Function Documentation

template<class N, class E>
void graph< N, E >::addEdge ( const N &  from,
const N &  to,
const E &  edge 
)

Definition at line 267 of file adjgraph.h.

Referenced by KinematicTree::addParticle(), graph_combine(), graph< N, E >::invert(), and DDCompactViewImpl::position().

{
  index_type iFrom = addNode(from);
  index_type iTo   = addNode(to);
  
  adjl_[iFrom].push_back(edge_type(iTo,edges_.size()));
  edges_.push_back(edge);
}
template<class N, class E >
graph< N, E >::index_type graph< N, E >::addNode ( const N &  node)

Definition at line 235 of file adjgraph.h.

References query::result.

{
  index_type idx = indexer_.size() ; //  +1;
  std::pair<indexer_iterator,bool> result 
    = indexer_.insert(typename indexer_type::value_type(node,idx));
  
  if ( result.second ) { // new index!
    nodes_.push_back(node);
    adjl_.push_back(edge_list());
  }  
  else {
    idx = result.first->second;
  }
  return idx;
}
template<class N, class E>
adj_iterator graph< N, E >::begin ( void  ) [inline]

Definition at line 198 of file adjgraph.h.

Referenced by TinyDomTest2::allNodes(), TinyDomTest::allNodes(), GraphPath< N, E >::calcPaths(), and ddstats().

{ return adjl_.begin(); }
template<class N, class E>
const_adj_iterator graph< N, E >::begin ( void  ) const [inline]

Definition at line 199 of file adjgraph.h.

{ return adjl_.begin(); }
template<class N, class E>
const_iterator graph< N, E >::begin_iter ( ) const [inline]

Definition at line 191 of file adjgraph.h.

Referenced by DDStreamer::pos_write().

{ return const_iterator(*this); }
template<class N , class E >
void graph< N, E >::clear ( void  )

it clear everything!

Definition at line 402 of file adjgraph.h.

{
  adjl_.clear();
  nodes_.clear();
  edges_.clear();
  indexer_.clear();
}
template<class N , class E >
void graph< N, E >::dump_graph ( ) const

Definition at line 411 of file adjgraph.h.

{
  //  std::cout << adjl_ << std::endl;
/*
   std::cout << "Nodes and their indices:" << std::endl;
   typename indexer_type::const_iterator it = indexer_.begin();
   for (; it != indexer_.end(); ++it) {
      std::cout << ' ' << it->first << ' ' << it->second << std::endl;
   }
*/   
}
template<class N, class E>
size_t graph< N, E >::edge_size ( ) const [inline]

Definition at line 195 of file adjgraph.h.

{ return edges_.size(); }
template<class N, class E>
const E& graph< N, E >::edgeData ( index_type  i) const [inline]

Definition at line 184 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), DDCheckPD(), graph< N, E >::const_iterator::value_type::edge(), and DDCompactViewImpl::~DDCompactViewImpl().

{ return edges_[i]; }
template<class N, class E >
graph< N, E >::const_edge_range graph< N, E >::edges ( const N &  node) const [inline]

Definition at line 306 of file adjgraph.h.

References prof2calltree::edges, and query::result.

{
  index_result idxResult = nodeIndex(node);
  const_edge_range result(emptyEdges_.begin(),emptyEdges_.end());
  if (idxResult.second) {
    result = edges(idxResult.first);
  }   
  return result;
}
template<class N , class E >
graph< N, E >::edge_range graph< N, E >::edges ( index_type  nodeIndex) [inline]

Definition at line 278 of file adjgraph.h.

References prof2calltree::edges.

Referenced by DDCheckAll(), hierarchy(), DDErrorDetection::lp_cpv(), and DDCompactViewImpl::~DDCompactViewImpl().

{
   edge_list & edges = adjl_[nodeIndex];
   return edge_range(edges.begin(), edges.end());
}
template<class N , class E >
graph< N, E >::const_edge_range graph< N, E >::edges ( index_type  nodeIndex) const [inline]

Definition at line 286 of file adjgraph.h.

References prof2calltree::edges.

{
   const edge_list & edges = adjl_[nodeIndex];
   return const_edge_range(edges.begin(), edges.end());
}
template<class N, class E >
graph< N, E >::edge_range graph< N, E >::edges ( const N &  node) [inline]

Definition at line 294 of file adjgraph.h.

References prof2calltree::edges, and query::result.

{
  index_result idxResult = nodeIndex(node);
  edge_range result(emptyEdges_.begin(),emptyEdges_.end());
  if (idxResult.second) {
    result = edges(idxResult.first);
  }   
  return result;
}
template<class N, class E>
adj_iterator graph< N, E >::end ( void  ) [inline]

Definition at line 200 of file adjgraph.h.

Referenced by TinyDomTest2::allNodes(), TinyDomTest::allNodes(), and ddstats().

{ return adjl_.end(); }
template<class N, class E>
const_adj_iterator graph< N, E >::end ( void  ) const [inline]

Definition at line 201 of file adjgraph.h.

{ return adjl_.end(); }
template<class N, class E>
const_iterator graph< N, E >::end_iter ( ) const [inline]

Definition at line 193 of file adjgraph.h.

Referenced by DDStreamer::pos_write().

{ return const_iterator(*this, adjl_.size(),0); }
template<class N , class E >
void graph< N, E >::findRoots ( edge_list &  result) const

Definition at line 338 of file adjgraph.h.

References begin, end, and findQualityFiles::size.

{
   result.clear();
      
   const_adj_iterator it = begin();   
   const_adj_iterator ed = end();
   std::vector<bool> rootCandidate(size(), true);
  
   for (; it != ed; ++it) {
      const edge_list & el = *it;
      typename edge_list::const_iterator el_it = el.begin();
      typename edge_list::const_iterator el_ed = el.end();
      for (; el_it != el_ed; ++el_it) {
         rootCandidate[el_it->first]=false; 
          //el_rt = el_it; // stop at the first encountered candidate!
          //std::cout << "graphwalker: found a root candidate = " << g.nodeData(el_rt->first) << std::endl;
          //break; 
      }
   }
   std::vector<bool>::size_type v_sz = 0;
   std::vector<bool>::size_type v_ed = rootCandidate.size();
   for (; v_sz < v_ed; ++v_sz) {
     if (rootCandidate[v_sz]) {
       //std::cout << "found = " << g.nodeData(v_sz) << std::endl;
       result.push_back(edge_type(v_sz,0));    
     }
   }  
}
template<class N , class E >
void graph< N, E >::invert ( graph< N, E > &  g) const

Definition at line 425 of file adjgraph.h.

References graph< N, E >::addEdge(), and ExpressReco_HICollisions_FallBack::e.

{
    adj_list::size_type it = 0;
    adj_list::size_type ed = adjl_.size();
    // loop over adjacency-list of this graph
    for (; it < ed; ++it) {
      const edge_list & el = adjl_[it];
      edge_list::size_type eit = 0;
      edge_list::size_type eed = el.size();
      // loop over edges of current node
      for (; eit < eed; ++eit) {
         const edge_type & e = el[eit];
         g.addEdge(nodeData(e.first), nodeData(it), edgeData(e.second));
      } 
    } 
}
template<class N , class E >
const N & graph< N, E >::nodeData ( const edge_type &  edge) const [inline]

Definition at line 318 of file adjgraph.h.

Referenced by TinyDomTest2::allNodes(), TinyDomTest::allNodes(), DDCheckAll(), DDCheckConnect(), graph< N, E >::const_iterator::value_type::from(), graph_combine(), hierarchy(), DDErrorDetection::lp_cpv(), and graph< N, E >::const_iterator::value_type::to().

{
  return nodes_[edge.first];
}
template<class N , class E >
const N & graph< N, E >::nodeData ( index_type  i) const [inline]

Definition at line 325 of file adjgraph.h.

References i.

{
  return nodes_[i];
}
template<class N , class E >
const N & graph< N, E >::nodeData ( const const_adj_iterator &  it) const [inline]

Definition at line 332 of file adjgraph.h.

{
  return nodes_[it-adjl_.begin()];
}
template<class N, class E >
graph< N, E >::index_result graph< N, E >::nodeIndex ( const N &  node) const [inline]

Definition at line 253 of file adjgraph.h.

References query::result.

Referenced by DDErrorDetection::lp_cpv().

{
  typename indexer_type::const_iterator result = indexer_.find(node);
  index_type idx = 0;
  bool flag = false;
  if (result != indexer_.end()) {
    flag = true;
    idx = result->second;
  }
  return index_result(idx, flag);
}
template<class N, class E >
bool graph< N, E >::replace ( const N &  oldNode,
const N &  newNode 
)

Definition at line 368 of file adjgraph.h.

Referenced by graph_combine(), and KinematicTree::replaceCurrentVertex().

{
   typename indexer_type::iterator it = indexer_.find(oldNode);
   if (it != indexer_.end()) {
     index_type oldIndex = it->second;
     nodes_[oldIndex]=newNode;
     indexer_[newNode]=oldIndex;
     indexer_.erase(it);
   }  
   else throw(oldNode);
   return true;   
}
template<class N , class E>
bool graph< N, E >::replaceEdge ( const E &  ldEdge,
const E &  newEdge 
)

Definition at line 382 of file adjgraph.h.

References query::result.

Referenced by KinematicTree::replaceCurrentParticle().

{
  typename edge_store::size_type it = 0;
  typename edge_store::size_type ed = edges_.size();
  bool result = false;
  //std::cout << "newedge=" << newEdge << std::endl;
  for (; it < ed; ++it) {
    //std::cout << "edge=" << edges_[it] << " ";
    if ( edges_[it] == oldEdge ) {
      //std::cout << "FOUND!" << std::endl;
      result = true;
      edges_[it] = newEdge;
      break;
    }
  }
  //std::cout << std::endl;
  return result;
}
template<class N, class E>
adj_list::size_type graph< N, E >::size ( void  ) const [inline]

Definition at line 202 of file adjgraph.h.

Referenced by TinyDomTest2::allNodes(), DDCheckAll(), DDCheckConnect(), graph< N, E >::const_iterator::operator++(), DDStreamer::pos_read(), and DDCompactViewImpl::~DDCompactViewImpl().

{ return adjl_.size(); }
template<class N, class E>
void graph< N, E >::swap ( graph< N, E > &  g)

Definition at line 443 of file adjgraph.h.

References graph< N, E >::adjl_, graph< N, E >::edges_, graph< N, E >::emptyEdges_, graph< N, E >::indexer_, and graph< N, E >::nodes_.

Referenced by DDCompactViewImpl::swap().

                                        { 
  adjl_.swap(g.adjl_);
  nodes_.swap(g.nodes_);
  edges_.swap(g.edges_);
  indexer_.swap(g.indexer_);
  emptyEdges_.swap(g.emptyEdges_);
}

Member Data Documentation

template<class N, class E>
adj_list graph< N, E >::adjl_ [private]

Definition at line 216 of file adjgraph.h.

Referenced by graph< Node2, AnotherDummy2 >::begin(), graph< N, E >::const_iterator::value_type::edge(), graph< Node2, AnotherDummy2 >::end(), graph< Node2, AnotherDummy2 >::end_iter(), graph< N, E >::const_iterator::operator++(), graph< Node2, AnotherDummy2 >::size(), graph< N, E >::swap(), and graph< N, E >::const_iterator::value_type::to().

template<class N, class E>
edge_store graph< N, E >::edges_ [private]

Definition at line 222 of file adjgraph.h.

Referenced by graph< Node2, AnotherDummy2 >::edge_size(), graph< Node2, AnotherDummy2 >::edgeData(), and graph< N, E >::swap().

template<class N, class E>
edge_list graph< N, E >::emptyEdges_ [private]

Definition at line 228 of file adjgraph.h.

Referenced by graph< N, E >::swap().

template<class N, class E>
indexer_type graph< N, E >::indexer_ [private]

Definition at line 225 of file adjgraph.h.

Referenced by graph< N, E >::swap().

template<class N, class E>
node_list graph< N, E >::nodes_ [private]

Definition at line 219 of file adjgraph.h.

Referenced by graph< N, E >::swap().

Generated for CMSSW Reference Manual by doxygen 1.7.3