graph< N, E > Class Template Reference

#include <DetectorDescription/Core/interface/adjgraph.h>

List of all members.

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 &)

const_adj_iterator begin () const

adj_iterator begin ()

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 (const N &) const

edge_range edges (const N &)

const_edge_range edges (index_type nodeIndex) const

edge_range edges (index_type nodeIndex)

const_adj_iterator end () const

adj_iterator end ()

const_iterator end_iter () const

void findRoots (edge_list &) const

graph ()

void invert (graph &g) const

const N & nodeData (const const_adj_iterator &) const

const N & nodeData (index_type) const

const N & nodeData (const edge_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

~graph ()

Private Attributes

adj_list adjl_

edge_store edges_

edge_list emptyEdges_

indexer_type indexer_

node_list nodes_

Classes

class const_iterator

struct value_type

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.

00147 : edges_(1)  { }

template<class N, class E>

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

Definition at line 148 of file adjgraph.h.

00148 { }

Member Function Documentation

template<class N, class E>

void graph< N, E >::addEdge	(	const N &	from,
		const N &	to,
		const E &	edge
	)			`[inline]`

Definition at line 265 of file adjgraph.h.

References graph< N, E >::addNode(), graph< N, E >::adjl_, and graph< N, E >::edges_.

Referenced by DDpos(), graph_combine(), graph< N, E >::invert(), SaxToDom::startElement(), and SaxToDom2::startElement().

00266 {
00267   index_type iFrom = addNode(from);
00268   index_type iTo   = addNode(to);
00269   
00270   adjl_[iFrom].push_back(edge_type(iTo,edges_.size()));
00271   edges_.push_back(edge);
00272 }

template<class N, class E>

graph< N, E >::index_type graph< N, E >::addNode ( const N & node ) [inline]

Definition at line 233 of file adjgraph.h.

References graph< N, E >::adjl_, graph< N, E >::indexer_, graph< N, E >::nodes_, and HLT_VtxMuL3::result.

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

00234 {
00235   index_type idx = indexer_.size() ; //  +1;
00236   std::pair<indexer_iterator,bool> result 
00237     = indexer_.insert(typename indexer_type::value_type(node,idx));
00238   
00239   if ( result.second ) { // new index!
00240     nodes_.push_back(node);
00241     adjl_.push_back(edge_list());
00242   }  
00243   else {
00244     idx = result.first->second;
00245   }
00246   return idx;
00247 }

template<class N, class E>

const_adj_iterator graph< N, E >::begin ( ) const [inline]

Definition at line 199 of file adjgraph.h.

00199 { return adjl_.begin(); }

template<class N, class E>

adj_iterator graph< N, E >::begin ( ) [inline]

Definition at line 198 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), WriteOneGeometryFromXML::beginJob(), DDG4Builder::BuildGeometry(), GraphPath< N, E >::calcPaths(), DDCompactView::clear(), ddstats(), and graph< N, E >::findRoots().

00198 { 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().

00191 { return const_iterator(*this); }

template<class N, class E>

void graph< N, E >::clear ( void ) [inline]

it clear everything!

Definition at line 400 of file adjgraph.h.

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

00401 {
00402   adjl_.clear();
00403   nodes_.clear();
00404   edges_.clear();
00405   indexer_.clear();
00406 }

template<class N, class E>

void graph< N, E >::dump_graph ( ) const [inline]

Definition at line 409 of file adjgraph.h.

00410 {
00411   //  std::cout << adjl_ << std::endl;
00412 /*
00413    std::cout << "Nodes and their indices:" << std::endl;
00414    typename indexer_type::const_iterator it = indexer_.begin();
00415    for (; it != indexer_.end(); ++it) {
00416       std::cout << ' ' << it->first << ' ' << it->second << std::endl;
00417    }
00418 */   
00419 }

template<class N, class E>

size_t graph< N, E >::edge_size ( ) const [inline]

Definition at line 195 of file adjgraph.h.

00195 { 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(), WriteOneGeometryFromXML::beginJob(), DDG4Builder::BuildGeometry(), DDCompactView::clear(), DDCheckPD(), graph< N, E >::const_iterator::value_type::edge(), graph< N, E >::invert(), and DDCompactViewImpl::~DDCompactViewImpl().

00184 { 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 304 of file adjgraph.h.

References graph< N, E >::edges(), graph< N, E >::emptyEdges_, graph< N, E >::nodeIndex(), and HLT_VtxMuL3::result.

00305 {
00306   index_result idxResult = nodeIndex(node);
00307   const_edge_range result(emptyEdges_.begin(),emptyEdges_.end());
00308   if (idxResult.second) {
00309     result = edges(idxResult.first);
00310   }   
00311   return result;
00312 }

template<class N, class E>

graph< N, E >::edge_range graph< N, E >::edges ( const N & node ) [inline]

Definition at line 292 of file adjgraph.h.

References graph< N, E >::edges(), graph< N, E >::emptyEdges_, graph< N, E >::nodeIndex(), and HLT_VtxMuL3::result.

00293 {
00294   index_result idxResult = nodeIndex(node);
00295   edge_range result(emptyEdges_.begin(),emptyEdges_.end());
00296   if (idxResult.second) {
00297     result = edges(idxResult.first);
00298   }   
00299   return result;
00300 }

template<class N, class E>

graph< N, E >::const_edge_range graph< N, E >::edges ( index_type nodeIndex ) const [inline]

Definition at line 284 of file adjgraph.h.

References graph< N, E >::adjl_, and graph< N, E >::edges().

00285 {
00286    const edge_list & edges = adjl_[nodeIndex];
00287    return const_edge_range(edges.begin(), edges.end());
00288 }

template<class N, class E>

graph< N, E >::edge_range graph< N, E >::edges ( index_type nodeIndex ) [inline]

Definition at line 276 of file adjgraph.h.

References graph< N, E >::adjl_.

Referenced by DDCheckAll(), graph< N, E >::edges(), hierarchy(), DDErrorDetection::lp_cpv(), and DDCompactViewImpl::~DDCompactViewImpl().

00277 {
00278    edge_list & edges = adjl_[nodeIndex];
00279    return edge_range(edges.begin(), edges.end());
00280 }

template<class N, class E>

const_adj_iterator graph< N, E >::end ( ) const [inline]

Definition at line 201 of file adjgraph.h.

00201 { return adjl_.end(); }

template<class N, class E>

adj_iterator graph< N, E >::end ( ) [inline]

Definition at line 200 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), WriteOneGeometryFromXML::beginJob(), DDG4Builder::BuildGeometry(), DDCompactView::clear(), ddstats(), and graph< N, E >::findRoots().

00200 { 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().

00193 { return const_iterator(*this, adjl_.size(),0); }

template<class N, class E>

void graph< N, E >::findRoots ( edge_list & result ) const [inline]

Definition at line 336 of file adjgraph.h.

References graph< N, E >::begin(), graph< N, E >::end(), it, and graph< N, E >::size().

00337 {
00338    result.clear();
00339       
00340    const_adj_iterator it = begin();   
00341    const_adj_iterator ed = end();
00342    std::vector<bool> rootCandidate(size(), true);
00343   
00344    for (; it != ed; ++it) {
00345       const edge_list & el = *it;
00346       typename edge_list::const_iterator el_it = el.begin();
00347       typename edge_list::const_iterator el_ed = el.end();
00348       for (; el_it != el_ed; ++el_it) {
00349          rootCandidate[el_it->first]=false; 
00350           //el_rt = el_it; // stop at the first encountered candidate!
00351           //std::cout << "graphwalker: found a root candidate = " << g.nodeData(el_rt->first) << std::endl;
00352           //break; 
00353       }
00354    }
00355    std::vector<bool>::size_type v_sz = 0;
00356    std::vector<bool>::size_type v_ed = rootCandidate.size();
00357    for (; v_sz < v_ed; ++v_sz) {
00358      if (rootCandidate[v_sz]) {
00359        //std::cout << "found = " << g.nodeData(v_sz) << std::endl;
00360        result.push_back(edge_type(v_sz,0));    
00361      }
00362    }  
00363 }

template<class N, class E>

void graph< N, E >::invert ( graph< N, E > & g ) const [inline]

Definition at line 423 of file adjgraph.h.

References graph< N, E >::addEdge(), graph< N, E >::adjl_, e, graph< N, E >::edgeData(), it, and graph< N, E >::nodeData().

00424 {
00425     adj_list::size_type it = 0;
00426     adj_list::size_type ed = adjl_.size();
00427     // loop over adjacency-list of this graph
00428     for (; it < ed; ++it) {
00429       const edge_list & el = adjl_[it];
00430       edge_list::size_type eit = 0;
00431       edge_list::size_type eed = el.size();
00432       // loop over edges of current node
00433       for (; eit < eed; ++eit) {
00434          const edge_type & e = el[eit];
00435          g.addEdge(nodeData(e.first), nodeData(it), edgeData(e.second));
00436       } 
00437     } 
00438 }

template<class N, class E>

const N & graph< N, E >::nodeData ( const const_adj_iterator & it ) const [inline]

Definition at line 330 of file adjgraph.h.

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

00331 {
00332   return nodes_[it-adjl_.begin()];
00333 }

template<class N, class E>

const N & graph< N, E >::nodeData ( index_type i ) const [inline]

Definition at line 323 of file adjgraph.h.

References graph< N, E >::nodes_.

00324 {
00325   return nodes_[i];
00326 }

template<class N, class E>

const N & graph< N, E >::nodeData ( const edge_type & edge ) const [inline]

Definition at line 316 of file adjgraph.h.

References graph< N, E >::nodes_.

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

00317 {
00318   return nodes_[edge.first];
00319 }

template<class N, class E>

graph< N, E >::index_result graph< N, E >::nodeIndex ( const N & node ) const [inline]

Definition at line 251 of file adjgraph.h.

References graph< N, E >::indexer_, and HLT_VtxMuL3::result.

Referenced by graph< N, E >::edges(), and DDErrorDetection::lp_cpv().

00252 {
00253   typename indexer_type::const_iterator result = indexer_.find(node);
00254   index_type idx = 0;
00255   bool flag = false;
00256   if (result != indexer_.end()) {
00257     flag = true;
00258     idx = result->second;
00259   }
00260   return index_result(idx, flag);
00261 }

template<class N, class E>

bool graph< N, E >::replace	(	const N &	oldNode,
		const N &	newNode
	)			`[inline]`

Definition at line 366 of file adjgraph.h.

References graph< N, E >::indexer_, it, and graph< N, E >::nodes_.

Referenced by graph_combine().

00367 {
00368    typename indexer_type::iterator it = indexer_.find(oldNode);
00369    if (it != indexer_.end()) {
00370      index_type oldIndex = it->second;
00371      nodes_[oldIndex]=newNode;
00372      indexer_[newNode]=oldIndex;
00373      indexer_.erase(it);
00374    }  
00375    else throw(oldNode);
00376    return true;   
00377 }

template<class N, class E>

bool graph< N, E >::replaceEdge	(	const E &	ldEdge,
		const E &	newEdge
	)			`[inline]`

Definition at line 380 of file adjgraph.h.

References graph< N, E >::edges_, it, and HLT_VtxMuL3::result.

00381 {
00382   typename edge_store::size_type it = 0;
00383   typename edge_store::size_type ed = edges_.size();
00384   bool result = false;
00385   //std::cout << "newedge=" << newEdge << std::endl;
00386   for (; it < ed; ++it) {
00387     //std::cout << "edge=" << edges_[it] << " ";
00388     if ( edges_[it] == oldEdge ) {
00389       //std::cout << "FOUND!" << std::endl;
00390       result = true;
00391       edges_[it] = newEdge;
00392       break;
00393     }
00394   }
00395   //std::cout << std::endl;
00396   return result;
00397 }

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 DDCheckAll(), DDCheckConnect(), graph< N, E >::findRoots(), graph< N, E >::const_iterator::operator++(), DDStreamer::pos_read(), and DDCompactViewImpl::~DDCompactViewImpl().

00202 { return adjl_.size(); }

Member Data Documentation

template<class N, class E>

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

Definition at line 214 of file adjgraph.h.

template<class N, class E>

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

Definition at line 220 of file adjgraph.h.

Referenced by graph< N, E >::addEdge(), graph< N, E >::clear(), graph< ReferenceCountingPointer, ReferenceCountingPointer >::edge_size(), graph< ReferenceCountingPointer, ReferenceCountingPointer >::edgeData(), and graph< N, E >::replaceEdge().

template<class N, class E>

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

Definition at line 226 of file adjgraph.h.

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

template<class N, class E>

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

Definition at line 223 of file adjgraph.h.

Referenced by graph< N, E >::addNode(), graph< N, E >::clear(), graph< N, E >::nodeIndex(), and graph< N, E >::replace().

template<class N, class E>

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

Definition at line 217 of file adjgraph.h.

Referenced by graph< N, E >::addNode(), graph< N, E >::clear(), graph< N, E >::nodeData(), and graph< N, E >::replace().

The documentation for this class was generated from the following file:

DetectorDescription/Core/interface/adjgraph.h

Generated on Tue Jun 9 18:21:52 2009 for CMSSW by

1.5.4


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 &)
const_adj_iterator	begin () const
adj_iterator	begin ()
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 (const N &) const
edge_range	edges (const N &)
const_edge_range	edges (index_type nodeIndex) const
edge_range	edges (index_type nodeIndex)
const_adj_iterator	end () const
adj_iterator	end ()
const_iterator	end_iter () const
void	findRoots (edge_list &) const
	graph ()
void	invert (graph &g) const
const N &	nodeData (const const_adj_iterator &) const
const N &	nodeData (index_type) const
const N &	nodeData (const edge_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
	~graph ()
Private Attributes
adj_list	adjl_
edge_store	edges_
edge_list	emptyEdges_
indexer_type	indexer_
node_list	nodes_
Classes
class	const_iterator
struct	value_type

graph< N, E > Class Template Reference

Public Types

Public Member Functions

Private Attributes

Classes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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