graph< N, E > Class Template Reference

#include <adjgraph.h>

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! More...
void	dump_graph (void) const
size_t	edge_size () const
const E &	edgeData (index_type i) const
edge_range	edges (index_type nodeIndex)
const_edge_range	edges (index_type nodeIndex) const
edge_range	edges (const N &)
const_edge_range	edges (const N &) const
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 (index_type) const
const N &	nodeData (const const_adj_iterator &) 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 12 of file adjgraph.h.

Member Typedef Documentation

template<class N, class E>

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

Definition at line 124 of file adjgraph.h.

template<class N, class E>

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

Definition at line 21 of file adjgraph.h.

template<class N, class E>

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

Definition at line 125 of file adjgraph.h.

template<class N, class E>

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

Definition at line 136 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 140 of file adjgraph.h.

template<class N, class E>

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

Definition at line 131 of file adjgraph.h.

template<class N, class E>

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

Definition at line 134 of file adjgraph.h.

template<class N, class E>

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

Definition at line 19 of file adjgraph.h.

template<class N, class E>

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

Definition at line 138 of file adjgraph.h.

template<class N, class E>

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

Definition at line 121 of file adjgraph.h.

template<class N, class E>

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

Definition at line 17 of file adjgraph.h.

template<class N, class E>

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

Definition at line 142 of file adjgraph.h.

template<class N, class E>

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

Definition at line 15 of file adjgraph.h.

template<class N, class E>

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

Definition at line 130 of file adjgraph.h.

template<class N, class E>

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

Definition at line 129 of file adjgraph.h.

template<class N, class E>

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

Definition at line 120 of file adjgraph.h.

Constructor & Destructor Documentation

template<class N, class E>

graph< N, E >::graph ( )

inline

Definition at line 146 of file adjgraph.h.

: edges_(1)  { }

template<class N, class E>

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

inline

Definition at line 147 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 266 of file adjgraph.h.

Referenced by 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 234 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 197 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), TinyDomTest2::allNodes(), DDG4Builder::BuildGeometry(), GraphPath< N, E >::calcPaths(), ddstats(), GeometryInfoDump::dumpInfo(), and DDCompareCPV::operator()().

{ return adjl_.begin(); } 

template<class N, class E>

const_adj_iterator graph< N, E >::begin ( void  ) const

inline

Definition at line 198 of file adjgraph.h.

{ return adjl_.begin(); }

template<class N, class E>

const_iterator graph< N, E >::begin_iter ( ) const

inline

Definition at line 190 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 401 of file adjgraph.h.

Referenced by Vispa.Views.WidgetView.WidgetView::closeEvent(), Vispa.Views.BoxDecayView.BoxDecayView::closeEvent(), Vispa.Share.FindAlgorithm.FindAlgorithm::findUsingFindDialog(), Vispa.Views.LineDecayView.LineDecayView::setDataObjects(), Vispa.Views.WidgetView.WidgetView::setDataObjects(), Vispa.Views.TreeView.TreeView::updateContent(), Vispa.Views.TableView.TableView::updateContent(), Vispa.Views.BoxDecayView.BoxDecayView::updateContent(), and Vispa.Views.PropertyView.PropertyView::updateContent().

{
  adjl_.clear();
  nodes_.clear();
  edges_.clear();
  indexer_.clear();
}

template<class N , class E >

void graph< N, E >::dump_graph

(

void

)

const

Definition at line 410 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 194 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 183 of file adjgraph.h.

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

{ return edges_[i]; }

template<class N , class E >

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

inline

Definition at line 277 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 285 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 293 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 >

graph< N, E >::const_edge_range graph< N, E >::edges ( const N &  node ) const

inline

Definition at line 305 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>

adj_iterator graph< N, E >::end ( void  )

inline

Definition at line 199 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), TinyDomTest2::allNodes(), Types.LuminosityBlockRange::cppID(), Types.EventRange::cppID(), ddstats(), and DDCompareCPV::operator()().

{ return adjl_.end(); }

template<class N, class E>

const_adj_iterator graph< N, E >::end ( void  ) const

inline

Definition at line 200 of file adjgraph.h.

Referenced by Types.LuminosityBlockRange::cppID(), and Types.EventRange::cppID().

{ return adjl_.end(); }

template<class N, class E>

const_iterator graph< N, E >::end_iter ( ) const

inline

Definition at line 192 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 337 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 424 of file adjgraph.h.

References graph< N, E >::addEdge(), and alignCSCRings::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 317 of file adjgraph.h.

Referenced by TinyDomTest::allNodes(), TinyDomTest2::allNodes(), DDCheckAll(), DDCheckConnect(), graph< N, E >::const_iterator::value_type::from(), graph_combine(), hierarchy(), DDErrorDetection::lp_cpv(), DDCompareCPV::operator()(), 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 324 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 331 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 252 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 367 of file adjgraph.h.

Referenced by graph_combine().

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

References query::result.

{
  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 201 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 442 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 215 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 221 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 227 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 224 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 218 of file adjgraph.h.

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