Classes | Public Types | Public Member Functions | Friends | List of all members
alglib::graph::models::adj_list< vertex_t, edge_t > Class Template Reference

#include <adj_list.h>

Inheritance diagram for alglib::graph::models::adj_list< vertex_t, edge_t >:
alglib::graph::models::graph_model< vertex_t, edge_t >

Classes

class  const_eiterator
 

Public Types

typedef vertex_t vertex_type
 
typedef edge_t edge_type
 
typedef boost::transform_iterator< get_first< std::pair< vertex_t, alist_t > >, typename std::map< vertex_t, alist_t >::const_iterator > const_viterator
 Iterators. More...
 
typedef boost::transform_iterator< get_first< std::pair< vertex_t, edge_t > >, typename std::map< vertex_t, edge_t >::const_iterator > const_aviterator
 
typedef boost::transform_iterator< get_second< std::pair< vertex_t, edge_t > >, typename std::map< vertex_t, edge_t >::const_iterator > const_aeiterator
 

Public Member Functions

bool are_adj (const vertex_t &, const vertex_t &) const
 Returs true if the two given vertices are adjacent, otherwise false. More...
 
void add_vertex (const vertex_t &v)
 
void add_edge (const vertex_t &u, const vertex_t &v, const edge_t &a)
 
void add_edge (const edge_t &e)
 
void remove_vertex (const vertex_t &v)
 
void remove_edge (const vertex_t &u, const vertex_t &v)
 
int indeg (const vertex_t &v) const
 
int outdeg (const vertex_t &v) const
 
int num_vertices () const
 
int num_edges () const
 
const_viterator vbegin () const noexcept
 
const_viterator vend () const noexcept
 
const_eiterator ebegin () const noexcept
 
const_eiterator eend () const noexcept
 
const_aviterator avbegin (const vertex_t &u) const
 
const_aviterator avend (const vertex_t &u) const
 
const_aeiterator aebegin (const vertex_t &u) const
 
const_aeiterator aeend (const vertex_t &u) const
 

Friends

class const_iterator
 

Detailed Description

template<typename vertex_t, typename edge_t>
class alglib::graph::models::adj_list< vertex_t, edge_t >

A 'model' of a graph

Member Typedef Documentation

template<typename vertex_t, typename edge_t>
typedef boost::transform_iterator<get_second<std::pair<vertex_t, edge_t> >, typename std::map<vertex_t, edge_t>::const_iterator> alglib::graph::models::adj_list< vertex_t, edge_t >::const_aeiterator
template<typename vertex_t, typename edge_t>
typedef boost::transform_iterator<get_first<std::pair<vertex_t, edge_t> >, typename std::map<vertex_t, edge_t>::const_iterator> alglib::graph::models::adj_list< vertex_t, edge_t >::const_aviterator
template<typename vertex_t, typename edge_t>
typedef boost::transform_iterator<get_first<std::pair<vertex_t, alist_t> >, typename std::map<vertex_t, alist_t>::const_iterator> alglib::graph::models::adj_list< vertex_t, edge_t >::const_viterator

Iterators.

template<typename vertex_t, typename edge_t>
typedef edge_t alglib::graph::models::adj_list< vertex_t, edge_t >::edge_type
template<typename vertex_t, typename edge_t>
typedef vertex_t alglib::graph::models::adj_list< vertex_t, edge_t >::vertex_type

Member Function Documentation

template<typename vertex_t, typename edge_t>
void alglib::graph::models::adj_list< vertex_t, edge_t >::add_edge ( const vertex_t &  u,
const vertex_t &  v,
const edge_t &  a 
)
inlinevirtual

Add vertex u and v if they don't already exist. Then insert e into the adjacency list of u. Complexity Gurantee: O(lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

165  {
172  add_vertex(u);
173  add_vertex(v);
174 
175  alists[u][v] = e;
176 }
alglib::graph::models::adj_list::add_vertex
void add_vertex(const vertex_t &v)
Definition: adj_list.h:152
template<typename vertex_t, typename edge_t>
void alglib::graph::models::adj_list< vertex_t, edge_t >::add_edge ( const edge_t &  e)
inlinevirtual

Ensure that both e.from and e.to exist and then insert e into the adjacency list of e.from. Complexity Gurantee: O(lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

179  {
185  add_vertex(e.from);
186  add_vertex(e.to);
187 
188  alists[e.from][e.to] = e;
189 }
edge_t::from
long long from()
Definition: dijkstra.cpp:109
alglib::graph::models::adj_list::add_vertex
void add_vertex(const vertex_t &v)
Definition: adj_list.h:152
edge_t::to
long long to()
Definition: dijkstra.cpp:110
template<typename vertex_t, typename edge_t >
void alglib::graph::models::adj_list< vertex_t, edge_t >::add_vertex ( const vertex_t &  v)
inlinevirtual

If the vertex doesn't already exist, create a new entry in alists and initialize it with an empty alist. Complexity: O(lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

152  {
158  if(alists.find(v) == alists.end())
159  alists[v] = alist_t();
160 }
template<typename vertex_t, typename edge_t>
const_aeiterator alglib::graph::models::adj_list< vertex_t, edge_t >::aebegin ( const vertex_t &  u) const
inline
130  {
131  typename alists_t::const_iterator it;
132  if((it = alists.find(u)) == alists.end())
133  throw std::out_of_range("The vertex doesn't exist");
134  return boost::make_transform_iterator((it->second).cbegin(), get_aedge);
135  }
template<typename vertex_t, typename edge_t>
const_aeiterator alglib::graph::models::adj_list< vertex_t, edge_t >::aeend ( const vertex_t &  u) const
inline
137  {
138  typename alists_t::const_iterator it;
139  if((it = alists.find(u)) == alists.end())
140  throw std::out_of_range("The vertex doesn't exist");
141  return boost::make_transform_iterator((it->second).cend(), get_aedge);
142  }
template<typename vertex_t, typename edge_t >
bool alglib::graph::models::adj_list< vertex_t, edge_t >::are_adj ( const vertex_t &  u,
const vertex_t &  v 
) const
inlinevirtual

Returs true if the two given vertices are adjacent, otherwise false.

If v exists in the adjacency list of u, then return true, otherwise false. Complexity Gurantee: O(lg V + lg deg u)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

267  {
274  return alists.at(u).find(v) != alists.at(u).end();
275 }
template<typename vertex_t, typename edge_t>
const_aviterator alglib::graph::models::adj_list< vertex_t, edge_t >::avbegin ( const vertex_t &  u) const
inline
116  {
117  typename alists_t::const_iterator it;
118  if((it = alists.find(u)) == alists.end())
119  throw std::out_of_range("The vertex doesn't exist");
120  return boost::make_transform_iterator((it->second).cbegin(), get_avertex);
121  }
template<typename vertex_t, typename edge_t>
const_aviterator alglib::graph::models::adj_list< vertex_t, edge_t >::avend ( const vertex_t &  u) const
inline
123  {
124  typename alists_t::const_iterator it;
125  if((it = alists.find(u)) == alists.end())
126  throw std::out_of_range("The vertex doesn't exist");
127  return boost::make_transform_iterator((it->second).cend(), get_avertex);
128  }
template<typename vertex_t, typename edge_t>
const_eiterator alglib::graph::models::adj_list< vertex_t, edge_t >::ebegin ( ) const
inlinenoexcept
108  {
109  return const_eiterator(*this);
110  }
template<typename vertex_t, typename edge_t>
const_eiterator alglib::graph::models::adj_list< vertex_t, edge_t >::eend ( ) const
inlinenoexcept
111  {
112  const_eiterator it(*this);
113  it.vit = alists.end();
114  return it;
115  }
template<typename vertex_t, typename edge_t >
int alglib::graph::models::adj_list< vertex_t, edge_t >::indeg ( const vertex_t &  v) const
inlinevirtual

For each alist, if v exists in the alist, increment deg by 1. Complexity Gurantee: O(V lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

217  {
223  int deg = 0;
224 
225  for(auto& entry : alists) {
226  auto& alist = entry.second;
227  if(alist.find(v) != alist.end())
228  deg++;
229  }
230  return deg;
231 }
template<typename vertex_t , typename edge_t >
int alglib::graph::models::adj_list< vertex_t, edge_t >::num_edges ( ) const
inlinevirtual

Sum the sizes of all the alists. Complexity Gurantee: O(V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

252  {
258  int sum = 0;
259  for(auto& entry : alists)
260  sum += entry.second.size();
261  return sum;
262 }
template<typename vertex_t , typename edge_t >
int alglib::graph::models::adj_list< vertex_t, edge_t >::num_vertices ( ) const
inlinevirtual

Complexity Gurantee: O(1)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

243  {
248  return alists.size();
249 }
template<typename vertex_t, typename edge_t >
int alglib::graph::models::adj_list< vertex_t, edge_t >::outdeg ( const vertex_t &  v) const
inlinevirtual

Locate the alist of v and return its size. Complexity Gurantee: O(lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

234  {
239  return alists.at(v).size();
240 }
template<typename vertex_t, typename edge_t >
void alglib::graph::models::adj_list< vertex_t, edge_t >::remove_edge ( const vertex_t &  u,
const vertex_t &  v 
)
inlinevirtual

Remove v from the adjacency list of u. Complexity Gurantee: O(lg outdeg u)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

208  {
213  alists[u].erase(v);
214 }
template<typename vertex_t, typename edge_t >
void alglib::graph::models::adj_list< vertex_t, edge_t >::remove_vertex ( const vertex_t &  v)
inlinevirtual

Delete the adjacency list of v. Then, delete v from any other alist that contains it. Complexity Gurantee: O(V lg V)

Implements alglib::graph::models::graph_model< vertex_t, edge_t >.

192  {
199  alists.erase(v);
200 
201  for(auto& entry : alists) {
202  entry.second.erase(v);
203  }
204 }
template<typename vertex_t, typename edge_t>
const_viterator alglib::graph::models::adj_list< vertex_t, edge_t >::vbegin ( ) const
inlinenoexcept
102  {
103  return boost::make_transform_iterator(alists.cbegin(), get_vertex);
104  }
template<typename vertex_t, typename edge_t>
const_viterator alglib::graph::models::adj_list< vertex_t, edge_t >::vend ( ) const
inlinenoexcept
105  {
106  return boost::make_transform_iterator(alists.cend(), get_vertex);
107  }

Friends And Related Function Documentation

template<typename vertex_t, typename edge_t>
friend class const_iterator
friend
The documentation for this class was generated from the following file:
Generated on Sun Jun 14 2015 23:11:18 for alglib by   doxygen 1.8.9.1