math::Graph< N, E > Class Template Reference

#include <Graph.h>

Classes
class	const_iterator
struct	value_type

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

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...
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)
auto	size () const -> adj_list::size_type
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 math::Graph< N, E >

Definition at line 13 of file Graph.h.

Member Typedef Documentation

adj_iterator

template<class N, class E>

using math::Graph< N, E >::adj_iterator = adj_list::iterator

Definition at line 104 of file Graph.h.

adj_list

template<class N, class E>

using math::Graph< N, E >::adj_list = std::vector<edge_list>

Definition at line 21 of file Graph.h.

const_adj_iterator

template<class N, class E>

using math::Graph< N, E >::const_adj_iterator = adj_list::const_iterator

Definition at line 105 of file Graph.h.

const_edge_iterator

template<class N, class E>

using math::Graph< N, E >::const_edge_iterator = edge_list::const_iterator

Definition at line 114 of file Graph.h.

const_edge_range

template<class N, class E>

using math::Graph< N, E >::const_edge_range = std::pair<const_edge_iterator, const_edge_iterator>

Definition at line 116 of file Graph.h.

const_indexer_iterator

template<class N, class E>

using math::Graph< N, E >::const_indexer_iterator = typename indexer_type::const_iterator

Definition at line 110 of file Graph.h.

edge_iterator

template<class N, class E>

using math::Graph< N, E >::edge_iterator = edge_list::iterator

Definition at line 113 of file Graph.h.

edge_list

template<class N, class E>

using math::Graph< N, E >::edge_list = std::vector<edge_type>

Definition at line 19 of file Graph.h.

edge_range

template<class N, class E>

using math::Graph< N, E >::edge_range = std::pair<edge_iterator, edge_iterator>

Definition at line 115 of file Graph.h.

edge_store

template<class N, class E>

using math::Graph< N, E >::edge_store = std::vector<E>

Definition at line 101 of file Graph.h.

edge_type

template<class N, class E>

using math::Graph< N, E >::edge_type = std::pair<index_type, index_type>

Definition at line 17 of file Graph.h.

index_result

template<class N, class E>

using math::Graph< N, E >::index_result = std::pair<index_type, bool>

Definition at line 117 of file Graph.h.

index_type

template<class N, class E>

using math::Graph< N, E >::index_type = std::vector<double>::size_type

Definition at line 15 of file Graph.h.

indexer_iterator

template<class N, class E>

using math::Graph< N, E >::indexer_iterator = typename indexer_type::iterator

Definition at line 109 of file Graph.h.

indexer_type

template<class N, class E>

using math::Graph< N, E >::indexer_type = std::map<N, index_type>

Definition at line 108 of file Graph.h.

node_list

template<class N, class E>

using math::Graph< N, E >::node_list = std::vector<N>

Definition at line 100 of file Graph.h.

Constructor & Destructor Documentation

Graph()

template<class N, class E>

math::Graph< N, E >::Graph ( )

inline

Definition at line 121 of file Graph.h.

: edges_(1) {}

~Graph()

template<class N, class E>

math::Graph< N, E >::~Graph ( )

inline

Definition at line 122 of file Graph.h.

{}

Member Function Documentation

addEdge()

template<class N, class E>

void math::Graph< N, E >::addEdge	(	const N &	from,
		const N &	to,
		const E &	edge
	)

Definition at line 231 of file Graph.h.

Referenced by DDCompactViewImpl::position().

                                                                     {
    index_type iFrom = addNode(from);
    index_type iTo = addNode(to);

    adjl_[iFrom].emplace_back(edge_type(iTo, edges_.size()));
    edges_.emplace_back(edge);
  }

addNode()

template<class N, class E >

Graph< N, E >::index_type math::Graph< N, E >::addNode

(

const N &

node

)

Definition at line 205 of file Graph.h.

                                                                   {
    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_.emplace_back(node);
      adjl_.emplace_back(edge_list());
    } else {
      idx = result.first->second;
    }
    return idx;
  }

begin() [1/2]

template<class N, class E>

adj_iterator math::Graph< N, E >::begin ( void  )

inline

Definition at line 172 of file Graph.h.

Referenced by TinyDomTest::allNodes(), TinyDomTest2::allNodes(), and GeometryInfoDump::dumpInfo().

{ return adjl_.begin(); }

begin() [2/2]

template<class N, class E>

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

inline

Definition at line 173 of file Graph.h.

{ return adjl_.begin(); }

begin_iter()

template<class N, class E>

const_iterator math::Graph< N, E >::begin_iter ( ) const

inline

Definition at line 165 of file Graph.h.

{ return const_iterator(*this); }

clear()

template<class N , class E >

void math::Graph< N, E >::clear

(

void

)

it clear everything!

Definition at line 338 of file Graph.h.

Referenced by BeautifulSoup.Tag::setString().

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

edge_size()

template<class N, class E>

size_t math::Graph< N, E >::edge_size ( ) const

inline

Definition at line 169 of file Graph.h.

{ return edges_.size(); }

edgeData()

template<class N, class E>

const E& math::Graph< N, E >::edgeData ( index_type  i ) const

inline

Definition at line 158 of file Graph.h.

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

{ return edges_[i]; }

edges() [1/4]

template<class N , class E >

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

inline

Definition at line 240 of file Graph.h.

Referenced by DDCompactViewImpl::~DDCompactViewImpl().

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

edges() [2/4]

template<class N , class E >

Graph< N, E >::const_edge_range math::Graph< N, E >::edges ( index_type  nodeIndex ) const

inline

Definition at line 246 of file Graph.h.

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

edges() [3/4]

template<class N, class E >

Graph< N, E >::edge_range math::Graph< N, E >::edges ( const N &  node )

inline

Definition at line 252 of file Graph.h.

                                                                 {
    index_result idxResult = nodeIndex(node);
    edge_range result(emptyEdges_.begin(), emptyEdges_.end());
    if (idxResult.second) {
      result = edges(idxResult.first);
    }
    return result;
  }

edges() [4/4]

template<class N, class E >

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

inline

Definition at line 262 of file Graph.h.

                                                                             {
    index_result idxResult = nodeIndex(node);
    const_edge_range result(emptyEdges_.begin(), emptyEdges_.end());
    if (idxResult.second) {
      result = edges(idxResult.first);
    }
    return result;
  }

end() [1/2]

template<class N, class E>

adj_iterator math::Graph< N, E >::end ( void  )

inline

Definition at line 174 of file Graph.h.

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

{ return adjl_.end(); }

end() [2/2]

template<class N, class E>

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

inline

Definition at line 175 of file Graph.h.

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

{ return adjl_.end(); }

end_iter()

template<class N, class E>

const_iterator math::Graph< N, E >::end_iter ( ) const

inline

Definition at line 167 of file Graph.h.

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

findRoots()

template<class N , class E >

void math::Graph< N, E >::findRoots

(

edge_list &

result

)

const

Definition at line 287 of file Graph.h.

                                                     {
    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;
      for (auto const &el_it : el) {
        rootCandidate[el_it.first] = false;
      }
    }
    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]) {
        result.emplace_back(edge_type(v_sz, 0));
      }
    }
  }

invert()

template<class N , class E >

void math::Graph< N, E >::invert

(

Graph< N, E > &

g

)

const

Definition at line 346 of file Graph.h.

                                               {
    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));
      }
    }
  }

nodeData() [1/3]

template<class N , class E >

const N & math::Graph< N, E >::nodeData ( const edge_type &  edge ) const

inline

Definition at line 272 of file Graph.h.

Referenced by TinyDomTest::allNodes(), TinyDomTest2::allNodes(), math::Graph< N, E >::const_iterator::value_type::from(), and math::Graph< N, E >::const_iterator::value_type::to().

                                                            {
    return nodes_[edge.first];
  }

nodeData() [2/3]

template<class N , class E >

const N & math::Graph< N, E >::nodeData ( index_type  i ) const

inline

Definition at line 277 of file Graph.h.

                                                   {
    return nodes_[i];
  }

nodeData() [3/3]

template<class N , class E >

const N & math::Graph< N, E >::nodeData ( const const_adj_iterator &  it ) const

inline

Definition at line 282 of file Graph.h.

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

nodeIndex()

template<class N, class E >

Graph< N, E >::index_result math::Graph< N, E >::nodeIndex ( const N &  node ) const

inline

Definition at line 219 of file Graph.h.

                                                                             {
    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);
  }

replace()

template<class N, class E >

bool math::Graph< N, E >::replace	(	const N &	oldNode,
		const N &	newNode
	)

Definition at line 310 of file Graph.h.

                                                              {
    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;
  }

replaceEdge()

template<class N , class E>

bool math::Graph< N, E >::replaceEdge	(	const E &	ldEdge,
		const E &	newEdge
	)

Definition at line 323 of file Graph.h.

                                                                  {
    typename edge_store::size_type it = 0;
    typename edge_store::size_type ed = edges_.size();
    bool result = false;
    for (; it < ed; ++it) {
      if (edges_[it] == oldEdge) {
        result = true;
        edges_[it] = newEdge;
        break;
      }
    }
    return result;
  }

size()

template<class N, class E>

auto math::Graph< N, E >::size ( void  ) const -> adj_list::size_type

inline

Definition at line 176 of file Graph.h.

Referenced by ntupleDataFormat._Collection::__iter__(), ntupleDataFormat._Collection::__len__(), TinyDomTest2::allNodes(), and DDCompactViewImpl::~DDCompactViewImpl().

{ return adjl_.size(); }

swap()

template<class N, class E>

void math::Graph< N, E >::swap

(

Graph< N, E > &

g

)

Definition at line 363 of file Graph.h.

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

adjl_

template<class N, class E>

adj_list math::Graph< N, E >::adjl_

private

Definition at line 189 of file Graph.h.

Referenced by math::Graph< Node2, AnotherDummy2 >::begin(), math::Graph< N, E >::const_iterator::value_type::edge(), math::Graph< Node2, AnotherDummy2 >::end(), math::Graph< Node2, AnotherDummy2 >::end_iter(), math::Graph< Node2, AnotherDummy2 >::size(), and math::Graph< N, E >::const_iterator::value_type::to().

edges_

template<class N, class E>

edge_store math::Graph< N, E >::edges_

private

Definition at line 195 of file Graph.h.

Referenced by math::Graph< Node2, AnotherDummy2 >::edge_size(), and math::Graph< Node2, AnotherDummy2 >::edgeData().

emptyEdges_

template<class N, class E>

edge_list math::Graph< N, E >::emptyEdges_

private

Definition at line 201 of file Graph.h.

indexer_

template<class N, class E>

indexer_type math::Graph< N, E >::indexer_

private

Definition at line 198 of file Graph.h.

nodes_

template<class N, class E>

node_list math::Graph< N, E >::nodes_

private

Definition at line 192 of file Graph.h.