Data structure for storing graphs/networks. More...

Inheritance diagram for Graph< link_type >:

Collaboration diagram for Graph< link_type >:

Public Types
using	graph_iterator = graph_utils::graph_iterator< link_type >

using	sparse_graph_iterator = graph_utils::sparse_graph_iterator< link_type >

using	row_graph_iterator = graph_utils::row_graph_iterator< link_type >

using	col_graph_iterator = graph_utils::col_graph_iterator< link_type >

using	const_full_row_iterator = graph_utils::const_full_row_iterator< link_type >

using	full_row_iterator = graph_utils::full_row_iterator< link_type >

using	const_sparse_row_iterator = graph_utils::const_sparse_row_iterator< link_type >

using	sparse_row_iterator = graph_utils::sparse_row_iterator< link_type >

using	const_full_col_iterator = graph_utils::const_full_col_iterator< link_type >

using	full_col_iterator = graph_utils::full_col_iterator< link_type >

using	const_sparse_col_iterator = graph_utils::const_sparse_col_iterator< link_type >

using	sparse_col_iterator = graph_utils::sparse_col_iterator< link_type >

using	const_row_begin_iterator = graph_utils::const_row_begin_iterator< link_type >

using	row_begin_iterator = graph_utils::row_begin_iterator< link_type >

using	const_col_begin_iterator = graph_utils::const_col_begin_iterator< link_type >

using	col_begin_iterator = graph_utils::col_begin_iterator< link_type >

Public Types inherited from Typeless_Graph
enum class	edge_types : char { dbool , dint , duint , dfloat , dstring , vbool , vint , vuint , vfloat , vstring , mbool , mint , muint , mfloat , mstring , unknown }
	Set of all edge types a Graph can have.

Public Member Functions
virtual	~Graph ()

virtual link_type &	at (unsigned int row, unsigned int col)=0
	Gets a reference to the specified link value. More...

void	at (unsigned int row, unsigned int col, const link_type &data)
	Takes a values and either sets the entry to that value or removes the entry if the submitted value is equal to the default value. More...

virtual const link_type &	examine (unsigned int row, unsigned int col) const =0
	Gets a constant reference to the specified element. More...

virtual void	clear (const link_type &data) noexcept=0
	Set all elements equal to the submitted value. More...

template<typename Callable >
void	examine_all_links (Callable lambda)
	For each link in the graph, the lambda or function pointer is called on the value of that link.

template<typename Callable >
void	apply_operation (Callable lambda)
	Applies a function pointer or lamda expression to all links in the Graph. More...

template<typename Callable >
void	apply_row_operation (unsigned int row_index, Callable lambda)
	Applies a function pointer or lamda expression to all links in the Graph's row. More...

template<typename Callable >
void	apply_col_operation (unsigned int col_index, Callable lambda)
	Applies a function pointer or lamda expression to all links in the Graph's column. More...

void	add_delta (unsigned int row, unsigned int col, const link_type &data)
	Adds a queued modification to the specified element. More...

void	push_deltas (void)
	Applies all queued modifications created by the add_delta function. More...

void	get_data_state (std::ostream &out) const
	Sends each row in a comma seperated format to the output stream, with a std::endl between each row. More...

virtual link_type &	at (row_graph_iterator &it)=0
	Gets a reference to link value the iterator points to. More...

virtual link_type &	at (col_graph_iterator &it)=0
	Gets a reference to link value the iterator points to. See Graph::at(row_graph_iterator& it).

void	at (row_graph_iterator &it, const link_type &data)
	Takes a values and either sets the entry to that value or removes the entry if the submitted value is equal to the default value. More...

void	at (col_graph_iterator &it, const link_type &data)
	See Graph::at(row_graph_iterator&, const link_type&)

virtual full_row_iterator	full_row_begin (unsigned int row_index)=0
	Returns an iterator pointing to column index 0 of the specified row. More...

virtual const_full_row_iterator	full_row_begin (unsigned int row_index) const =0
	Returns an iterator pointing to column index 0 of the specified row. More...

const_full_row_iterator	full_row_cbegin (unsigned int row_index) const
	Function is identical to the const full_row_begin .

virtual sparse_row_iterator	sparse_row_begin (unsigned int row_index, const link_type &skip_data)=0
	Returns an iterator pointing to the first column index that shouldn't be skipped in the specified row. More...

virtual const_sparse_row_iterator	sparse_row_begin (unsigned int row_index, const link_type &skip_data) const =0
	Returns an iterator pointing to the first column index that shouldn't be skipped in the specified row. More...

const_sparse_row_iterator	sparse_row_cbegin (unsigned int row_index, const link_type &skip_data) const
	Function is identical to the const sparse_row_begin .

virtual row_begin_iterator	begin_rows (void) noexcept=0
	Returns an iterator pointing to the first row. More...

virtual const_row_begin_iterator	begin_rows (void) const noexcept=0
	Returns an iterator pointing to the first row. More...

const_row_begin_iterator	cbegin_rows (void) const noexcept
	Function is identical to the const begin_rows .

virtual row_begin_iterator	get_row (unsigned int row_index)=0
	Returns an iterator pointing to the specified row. More...

virtual const_row_begin_iterator	get_row (unsigned int row_index) const =0
	Returns an iterator pointing to the specified row. More...

row_begin_iterator	operator[] (unsigned int row_index)

const_row_begin_iterator	operator[] (unsigned int row_index) const

const_row_begin_iterator	cget_row (unsigned int row_index) const
	Function is identical to the const get_row .

const typeless_graph_iterator	row_end (unsigned int row_index) const
	Returns the end iterator for the specified row. More...

const typeless_graph_iterator	end_rows (void) const noexcept
	Returns an iterator pointing to the after the last row. More...

void	set_row (unsigned int row_index, const link_type &value)

virtual full_col_iterator	full_col_begin (unsigned int col_index)=0
	Returns an iterator pointing to row index 0 of the specified column. More...

virtual const_full_col_iterator	full_col_begin (unsigned int col_index) const =0
	Returns an iterator pointing to row index 0 of the specified column. More...

const_full_col_iterator	full_col_cbegin (unsigned int col_index) const
	Function is identical to the const full_col_begin .

virtual sparse_col_iterator	sparse_col_begin (unsigned int col_index, const link_type &skip_data)=0
	Returns an iterator pointing to the first row index that shouldn't be skipped in the specified column. More...

virtual const_sparse_col_iterator	sparse_col_begin (unsigned int col_index, const link_type &skip_data) const =0
	Returns an iterator pointing to the first row index that shouldn't be skipped in the specified column. More...

const_sparse_col_iterator	sparse_col_cbegin (unsigned int col_index, const link_type &skip_data) const
	Function is identical to the const sparse_col_begin .

virtual col_begin_iterator	begin_cols (void) noexcept=0
	Returns an iterator pointing to the first column. More...

virtual const_col_begin_iterator	begin_cols (void) const noexcept=0
	Returns an iterator pointing to the first row. More...

const_col_begin_iterator	cbegin_cols (void) const noexcept
	Function is identical to the const begin_cols .

virtual col_begin_iterator	get_col (unsigned int col_index)=0
	Returns an iterator pointing to the specified column. More...

virtual const_col_begin_iterator	get_col (unsigned int col_index) const =0
	Returns an iterator pointing to the specified column. More...

const_col_begin_iterator	cget_col (unsigned int col_index) const
	Function is identical to the const get_col .

void	set_col (unsigned int col_index, const link_type &value)

const typeless_graph_iterator	col_end (unsigned int col_index) const
	Returns the end iterator for the specified column. More...

const typeless_graph_iterator	end_cols (void) const noexcept
	Returns an iterator pointing to the after the last column. More...

std::vector< link_type >	get_dense_row (unsigned int row_index) const
	Returns the link values of a row as a vector.

std::vector< link_type >	get_dense_col (unsigned int col_index) const
	Returns the link values of a column as a vector.

std::map< unsigned int, link_type >	get_sparse_row (unsigned int row_index, const link_type &skip_value) const
	Returns the link values of a row as a map.

std::map< unsigned int, link_type >	get_sparse_col (unsigned int col_index, const link_type &skip_value) const
	Returns the link values of a column as a map.

Transpose< link_type >	T (void)
	Returns the Transpose wrapper class for this Graph.

const Transpose< link_type >	T (void) const
	Returns the const Transpose wrapper class for this Graph.

template<typename input >
Graph< link_type > &	operator= (const Temporary_Graph< input > &other)
	Sets all links in the Graph to have the same values of the links of the Temporary_Graph

template<typename other >
Graph< link_type > &	operator+= (const other &val)
	Adds the submitted value to all links.

template<typename other >
Graph< link_type > &	operator-= (const other &val)
	Subtracts the submitted value from all links.

template<typename other >
Graph< link_type > &	*operator=** (const other &val)
	Muliplies all links by the submitted value.

template<typename other >
Graph< link_type > &	operator/= (const other &val)
	Divides all links by the submitted value.

template<class output = decltype(link_type() + link_type())>
output	row_sum (unsigned int row_index) const
	Adds up all values in a row together. More...

template<class output = decltype(link_type() + link_type())>
output	col_sum (unsigned int col_index) const
	Adds up all values in a column together. More...

virtual void	push_deltas (void)=0
	Virtual function that allows the deltas in a Graph to be pushed without needing to convert the Typeless_Graph into its child type. More...

virtual void	get_data_state (std::ostream &out) const =0
	For each link in the graph, the lambda or function pointer is called on the value of that link. More...

Public Attributes
const link_type	def_val
	The default value a entry will have if that entry is not stored in memory.

Public Attributes inherited from Typeless_Graph
const Nodeset *const	source_nodeset
	The nodeset in which each node corresponds to a row in the data structure.

const Nodeset *const	target_nodeset
	The nodeset in which each node corresponds to a column in the data structure.

const Nodeset *const	slice_nodeset
	The nodeset in which each node corresponds to a slice in the data structure.

const std::string	name
	The name of the network.

const unsigned int	row_size
	The number of rows in the data structure. Equalivilent to the size of the source nodeset.

const unsigned int	col_size
	The number of columns in the data structure. Equalivilent to the size of the target nodeset.

const edge_types	edge_type
	The edge's data type. Set by #dynet::get_type_name.

const bool	col_dense

const bool	row_dense
	True if the row representation is dense, false if the representation is sparse.

Detailed Description

template<typename link_type>
class Graph< link_type >

Data structure for storing graphs/networks.

Graphs/networks connect one node to another node using links/edges. In the case of 3d graphs, these edges can themselves be another dimension. Three dimensions are currently supported; source, target, and slice, with the last being used exclusively in 3d graphs. Edge types currently supported are bool, int, unsigned int, float, and string.

The source and target dimensions can be sparse or dense. This class has been constructed such that the source and target densities do not impact behaviour, only cpu and memory usage. From a developer's point of view, it is best to assume both dimensions are sparse as there is no complexity penalty if the dimensions are dense. The slice dimension density must match that requested by a model. When using a 3d graph with a slice dimension, a data type of vector<T> or map<unsigned int, T> is used for dense or sparse representation, respectively. The edge_type identifier in the parent class Typeless_Graph both indicates slice dimension density, and the data type used. By checking edge_type, conversion from 2d to 3d graphs is avoided as is conversion between two different data types such as float and string. The string used to define edge_type can be found using the function dynet::get_type_name.

The Graph structure itself is a collection of entries, which are not synonymous with links. When a link is examined using a soft examine, the entry's value is returned if the entry exists, otherwise the default value is returned. In a hard examine, an entry is allocated and the default value copied into it before returning the entry's value. Thus there can exist many links, with no entries with the correct default value. In a dense representation, every possible entry is allocated and default value is copied into each entry. In a sparse representation, entries are only allocated during a hard examine. Setting an entry with a hard examine to equal the default value is not recommended. While in a dense representation there is no consequence, excessive cpu and memory usage is wasted allocating a new entry.

Graphs can only be constructed or deconstructed by the GraphManager.

Member Typedef Documentation

◆ col_graph_iterator

template<typename link_type >

using Graph< link_type >::col_graph_iterator = graph_utils::col_graph_iterator<link_type>

summary>

◆ const_col_begin_iterator

template<typename link_type >

using Graph< link_type >::const_col_begin_iterator = graph_utils::const_col_begin_iterator<link_type>

summary>

◆ const_full_col_iterator

template<typename link_type >

using Graph< link_type >::const_full_col_iterator = graph_utils::const_full_col_iterator<link_type>

summary>

◆ const_full_row_iterator

template<typename link_type >

using Graph< link_type >::const_full_row_iterator = graph_utils::const_full_row_iterator<link_type>

summary>

◆ const_row_begin_iterator

template<typename link_type >

using Graph< link_type >::const_row_begin_iterator = graph_utils::const_row_begin_iterator<link_type>

summary>

◆ const_sparse_col_iterator

template<typename link_type >

using Graph< link_type >::const_sparse_col_iterator = graph_utils::const_sparse_col_iterator<link_type>

summary>

◆ const_sparse_row_iterator

template<typename link_type >

using Graph< link_type >::const_sparse_row_iterator = graph_utils::const_sparse_row_iterator<link_type>

summary>

◆ full_col_iterator

template<typename link_type >

using Graph< link_type >::full_col_iterator = graph_utils::full_col_iterator<link_type>

summary>

◆ full_row_iterator

template<typename link_type >

using Graph< link_type >::full_row_iterator = graph_utils::full_row_iterator<link_type>

summary>

◆ graph_iterator

template<typename link_type >

using Graph< link_type >::graph_iterator = graph_utils::graph_iterator<link_type>

summary>

◆ row_begin_iterator

template<typename link_type >

using Graph< link_type >::row_begin_iterator = graph_utils::row_begin_iterator<link_type>

summary>

◆ row_graph_iterator

template<typename link_type >

using Graph< link_type >::row_graph_iterator = graph_utils::row_graph_iterator<link_type>

summary>

◆ sparse_col_iterator

template<typename link_type >

using Graph< link_type >::sparse_col_iterator = graph_utils::sparse_col_iterator<link_type>

summary>

◆ sparse_graph_iterator

template<typename link_type >

using Graph< link_type >::sparse_graph_iterator = graph_utils::sparse_graph_iterator<link_type>

summary>

◆ sparse_row_iterator

template<typename link_type >

using Graph< link_type >::sparse_row_iterator = graph_utils::sparse_row_iterator<link_type>

summary>

Constructor & Destructor Documentation

◆ ~Graph()

template<typename link_type >

virtual Graph< link_type >::~Graph ( )

inlinevirtual

summary>

Member Function Documentation

◆ add_delta()

template<typename link_type >

void Graph< link_type >::add_delta	(	unsigned int	row,
		unsigned int	col,
		const link_type &	data
	)

Adds a queued modification to the specified element.

The queued modification is not applied until push_deltas is called. At that time, the element is replaced with the specified data.

Parameters

row	Row index of the desired element.
col	Column index of the desired element.
data	Column index of the desired element.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->add_delta(0, 0, 1);
 
    std::cout << "row 0 before pushing deltas:";
    for (Graph<int>::full_row_iterator it = mygraph->full_row_begin(0); it != mygraph->row_end(0); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
 
    mygraph->push_deltas();
    
    std::cout << "row 0 after pushing deltas:";
    for (Graph<int>::full_row_iterator it = mygraph->full_row_begin(0); it != mygraph->row_end(0); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 0 before pushing deltas: 0 1 4 2

row 0 after pushing deltas: 1 1 4 2

Complexity

Constant.

Iterator validity

No changes.

Exception Safety

An assertion is raised if either row or col is out of bounds of the source and target nodeset, respectively.

Here is the caller graph for this function:

◆ apply_col_operation()

template<typename link_type >

template<typename Callable >

void Graph< link_type >::apply_col_operation	(	unsigned int	col_index,
		Callable	lambda
	)

inline

Applies a function pointer or lamda expression to all links in the Graph's column.

The function pointer or lamda expression should take as an agrument Graph<link_type>::full_col_iterator and return a value convertable to link_type.

◆ apply_operation()

template<typename link_type >

template<typename Callable >

void Graph< link_type >::apply_operation ( Callable lambda )

inline

Applies a function pointer or lamda expression to all links in the Graph.

The function pointer or lamda expression should take as an agrument Graph<link_type>::full_row_iterator and return a value convertable to link_type.

Here is the call graph for this function:

◆ apply_row_operation()

template<typename link_type >

template<typename Callable >

void Graph< link_type >::apply_row_operation	(	unsigned int	row_index,
		Callable	lambda
	)

inline

Applies a function pointer or lamda expression to all links in the Graph's row.

The function pointer or lamda expression should take as an agrument Graph<link_type>::full_row_iterator and return a value convertable to link_type.

◆ at() [1/4]

template<typename link_type >

virtual link_type & Graph< link_type >::at ( row_graph_iterator & it )

pure virtual

Gets a reference to link value the iterator points to.

A hard examine is done for the entry in which if there is not a physical entry present, an entry is added at that element and the default value is copied into it.

While the col_begin_iterator does inheriet from row_graph_iterator, using it as a parameter causes undefined behavior.

Parameters

it	Iterator that determines which element is accessed.

Returns: A reference to the element the iterator points to.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        mygraph->at(it) = it.col();
    }
 
    std::cout << "row 1:";
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 0 1 2 3

Complexity

Constant.

Iterator validity

The submitted iterator will always remain valid. Other iterators iterating over the same row or column may no longer be valid.

Exception Safety

An assertion is raised if typeless_graph_iterator::index is equal to typeless_graph_iterator::max.

◆ at() [2/4]

template<typename link_type >

void Graph< link_type >::at	(	row_graph_iterator &	it,
		const link_type &	data
	)

Takes a values and either sets the entry to that value or removes the entry if the submitted value is equal to the default value.

If the submitted value does not equal the default value, a hard examine is done for the entry in which if there is not a physical entry present, an entry is added and the submitted value is coppied into that entry. If the submitted value does equal the default value, that entry is erased if it exists.

While the col_begin_iterator does inheriet from row_graph_iterator, using it as a parameter causes undefined behavior.

Parameters

it	Iterator that determines which element is accessed.
data	Data to be inserted in that element.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        mygraph->at(it, it.col());
    }
 
    std::cout << "row 1:";
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 0 1 2 3

Complexity

Constant.

Iterator validity

The submitted iterator will always remain valid. Other iterators iterating over the same row or column may no longer be valid.

Exception Safety

An assertion is raised if typeless_graph_iterator::index is equal to typeless_graph_iterator::max.

◆ at() [3/4]

template<typename link_type >

virtual link_type & Graph< link_type >::at	(	unsigned int	row,
		unsigned int	col
	)

pure virtual

Gets a reference to the specified link value.

A hard examine is done for the entry in which if there is not a physical entry present, an entry is added at that location and the default value is copied into it.

Parameters

row	Row index of the desired element.
col	Column index of the desired element.

Returns: A reference to the desired element.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,1) = 4;
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    std::cout << "row 1:";
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 1 4 9 3

Complexity

If both source and target dimension are dense, constant. If a dimension is sparse, a binary search is used to locate the correct row and/or column, which individual takes O(log n) based on the number of real rows/columns.

Iterator validity

If an entry was not inserted at the specified element, all iterators remain valid. Otherwise depending on user defined dimension density, iterators before or at the entry may not be valid.

Exception Safety

An assertion is raised if either row or col is out of bounds of the source and target nodeset, respectively.

Here is the caller graph for this function:

◆ at() [4/4]

template<typename link_type >

void Graph< link_type >::at	(	unsigned int	row,
		unsigned int	col,
		const link_type &	data
	)

Takes a values and either sets the entry to that value or removes the entry if the submitted value is equal to the default value.

If the submitted value does not equal the default value, a hard examine is done for the entry in which if there is not a physical entry present, an entry is added and the submitted value is coppied into that entry. If the submitted value does equal the default value, that entry is erased if it exists.

Parameters

row	Row index of the desired element.
col	Column index of the desired element.
data	Data to be inserted in that element.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1, 1, 4);
    mygraph->at(1, 2, 9);
    mygraph->at(1, 0, 0);
 
    std::cout << "row 1:";
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 0 4 9 0

Complexity

If both source and target dimension are dense, constant. If a dimension is sparse, a binary search is used to locate the correct row and/or column, which individually takes O(log n) based on the number of real rows/columns.

Iterator validity

If an entry was not inserted at the specified element, all iterators remain valid. Otherwise depending on user defined dimension density, iterators before or at the entry may not be valid.

Exception Safety

An assertion is raised if either row or col is out of bounds of the source and target nodeset, respectively.

◆ begin_cols() [1/2]

template<typename link_type >

virtual const_col_begin_iterator Graph< link_type >::begin_cols ( void ) const

pure virtualnoexcept

Returns an iterator pointing to the first row.

Example

int main() {
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    const Graph<int>* const_mygraph = mygraph;
 
    for (auto cols = const_mygraph->begin_cols(); cols != const_mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(auto it = cols.begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 0: 0 1 0 4
col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions.

◆ begin_cols() [2/2]

template<typename link_type >

virtual col_begin_iterator Graph< link_type >::begin_cols ( void )

pure virtualnoexcept

Returns an iterator pointing to the first column.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::col_begin_iterator cols = mygraph->begin_cols(); cols != mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(Graph<int>::full_col_iterator it = cols.full_begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 0: 0 1 0 4
col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions

Here is the caller graph for this function:

◆ begin_rows() [1/2]

template<typename link_type >

virtual const_row_begin_iterator Graph< link_type >::begin_rows ( void ) const

pure virtualnoexcept

Returns an iterator pointing to the first row.

Example

int main() {
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    const Graph<int>* const_mygraph = mygraph;
 
    for (auto rows = const_mygraph->begin_rows(); rows != const_mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(auto it = rows.begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 0: 0 1 4 2
row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions.

◆ begin_rows() [2/2]

template<typename link_type >

virtual row_begin_iterator Graph< link_type >::begin_rows ( void )

pure virtualnoexcept

Returns an iterator pointing to the first row.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::row_begin_iterator rows = mygraph->begin_rows(); rows != mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(Graph<int>::full_row_iterator it = rows.full_begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 0: 0 1 4 2 
row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions

Here is the caller graph for this function:

◆ clear()

template<typename link_type >

virtual void Graph< link_type >::clear ( const link_type & data )

pure virtualnoexcept

Set all elements equal to the submitted value.

Parameters

data	Value that each element is set to.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->clear(2);
 
    std::cout << "row 0:" << std::endl;
    for (Graph<int>::full_row_iterator it = mygraph->full_row_begin(0); it != mygraph->row_end(0); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
    
}

Output:

row 0: 2 2 2 2

Complexity

Linear in number of elements in the graph.

Iterator validity

All iterators are invalidated unless both dimensions are dense.

Exception Safety

Strong Guarantee: This function never throws exceptions.

Here is the caller graph for this function:

◆ col_end()

template<typename link_type >

const typeless_graph_iterator Graph< link_type >::col_end ( unsigned int col_index ) const

Returns the end iterator for the specified column.

This iterator points to beyond the last piece of data and thus should not be dereferenced.

Parameters

col_index Column index the returned iterator points to.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::col_begin_iterator cols = mygraph->begin_cols(1); cols != mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(Graph<int>::full_col_iterator it = colss.full_begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

Here is the caller graph for this function:

◆ col_sum()

template<typename link_type >

template<class output = decltype(link_type() + link_type())>

output Graph< link_type >::col_sum ( unsigned int col_index ) const

inline

Adds up all values in a column together.

Return type is the same as the link_type except for bool in which the column sum returns an int.

◆ end_cols()

template<typename link_type >

const typeless_graph_iterator Graph< link_type >::end_cols ( void ) const

noexcept

Returns an iterator pointing to the after the last column.

Returns: A typeless_graph_iterator pointing element (col_size, 0).

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::col_begin_iterator cols = mygraph->begin_cols(1); cols != mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(Graph<int>::full_col_iterator it = cols.full_begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions.

Here is the caller graph for this function:

◆ end_rows()

template<typename link_type >

const typeless_graph_iterator Graph< link_type >::end_rows ( void ) const

noexcept

Returns an iterator pointing to the after the last row.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::row_begin_iterator rows = mygraph->begin_rows(1); rows != mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(Graph<int>::full_row_iterator it = rows.full_begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

Strong Guarantee: This function never throws exceptions.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ examine()

template<typename link_type >

virtual const link_type & Graph< link_type >::examine	(	unsigned int	row,
		unsigned int	col
	)		const

pure virtual

Gets a constant reference to the specified element.

A soft examine is done for the element in which if the element is not present, the default value is returned. The constant reference can not be modified as the default value is a constant in the case its returned.

Parameters

row	Row index of the desired element.
col	Column index of the desired element.

Returns: A constant reference to the desired element.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for(unsigned int i = 0; i < mygraph->row_size; i++) {
        std::cout << "row " << i << " col 0: " << mygraph->examine(i,0) << std::endl;
    }
}

Output:

row 0 col 0: 0
row 1 col 0: 1
row 2 col 0: 0
row 3 col 0: 4

Complexity

If both source and target dimension are dense, constant. If a dimension is sparse, a binary search is used to locate the correct row and/or column, which individual takes O(log n) based on the number of real rows/columns.

Iterator validity

No changes.

Exception Safety

An assertion is raised if either row or col is out of bounds of the source and target nodeset, respectively.

Here is the caller graph for this function:

◆ full_col_begin() [1/2]

template<typename link_type >

virtual const_full_col_iterator Graph< link_type >::full_col_begin ( unsigned int col_index ) const

pure virtual

Returns an iterator pointing to row index 0 of the specified column.

Parameters

col_index Column index the returned iterator points to.

Returns: An iterator pointing to the element (0, col_index).

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,1) = 4;
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    const Graph<int>* const_mygraph = mygraph;
 
    std::cout << "col 1:";
    for(Graph<int>::const_full_col_iterator it = const_mygraph->full_col_begin(1); it != const_mygraph->end_col(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

col 1: 1 4 0 5

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

◆ full_col_begin() [2/2]

template<typename link_type >

virtual full_col_iterator Graph< link_type >::full_col_begin ( unsigned int col_index )

pure virtual

Returns an iterator pointing to row index 0 of the specified column.

Parameters

col_index Column index the returned iterator points to.

Returns: An iterator pointing to the element (0, col_index).

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,1) = 4;
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    std::cout << "col 1:";
    for(Graph<int>::full_col_iterator it = mygraph->full_col_begin(1); it != mygraph->end_col(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

col 1: 1 4 0 5

Complexity

If the target dimension is dense, constant. Otherwise a binary search is used to find the beginning of a column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

Here is the caller graph for this function:

◆ full_row_begin() [1/2]

template<typename link_type >

virtual const_full_row_iterator Graph< link_type >::full_row_begin ( unsigned int row_index ) const

pure virtual

Returns an iterator pointing to column index 0 of the specified row.

Parameters

row_index Row index the returned iterator points to.

Returns: An iterator pointing to the element (row_index, 0).

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,1) = 4;
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    const Graph<int>* const_mygraph = mygraph;
 
    std::cout << "row 1:";
    for(Graph<int>::const_full_row_iterator it = const_mygraph->full_row_begin(1); it != const_mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 1 4 9 3

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

◆ full_row_begin() [2/2]

template<typename link_type >

virtual full_row_iterator Graph< link_type >::full_row_begin ( unsigned int row_index )

pure virtual

Returns an iterator pointing to column index 0 of the specified row.

Parameters

row_index Row index the returned iterator points to.

Returns: An iterator pointing to the element (row_index, 0).

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,1) = 4;
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    std::cout << "row 1:";
    for(Graph<int>::full_row_iterator it = mygraph->full_row_begin(1); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 1: 1 4 9 3

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

Here is the caller graph for this function:

◆ get_col() [1/2]

template<typename link_type >

virtual const_col_begin_iterator Graph< link_type >::get_col ( unsigned int col_index ) const

pure virtual

Returns an iterator pointing to the specified column.

Parameters

col_index Row index the returned iterator points to.

Returns: A graph_utils::const_col_begin_iterator pointing to the specified column in the data structure.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    const Graph<int>* const_mygraph = mygraph;
 
    for (Graph<int>::const_col_begin_iterator cols = const_mygraph->begin_cols(1); cols != const_mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(Graph<int>::const_full_col_iterator it = cols.full_begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant if the source dimension is dense. Otherwise a binary search is used to find the beginning of the column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

◆ get_col() [2/2]

template<typename link_type >

virtual col_begin_iterator Graph< link_type >::get_col ( unsigned int col_index )

pure virtual

Returns an iterator pointing to the specified column.

Parameters

col_index Column index the returned iterator points to.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::col_begin_iterator cols = mygraph->begin_cols(1); cols != mygraph->end_cols(); ++cols) {
 
        std::cout << "col " << cols.col() << ": ";
 
        for(Graph<int>::full_col_iterator it = cols.full_begin(); it != cols.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

col 1: 1 0 0 5
col 2: 4 0 2 3
col 3: 2 0 3 6

Complexity

Constant if the target dimension is dense. Otherwise a binary search is used to find the beginning of the column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the source nodeset.

Here is the caller graph for this function:

◆ get_data_state()

template<typename link_type >

void Graph< link_type >::get_data_state ( std::ostream & out ) const

virtual

Sends each row in a comma seperated format to the output stream, with a std::endl between each row.

Implements Typeless_Graph.

◆ get_row() [1/2]

template<typename link_type >

virtual const_row_begin_iterator Graph< link_type >::get_row ( unsigned int row_index ) const

pure virtual

Returns an iterator pointing to the specified row.

Parameters

row_index Row index the returned iterator points to.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    const Graph<int>* const_mygraph = mygraph;
 
    for (Graph<int>::const_row_begin_iterator rows = const_mygraph->begin_rows(1); rows != const_mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(Graph<int>::const_full_row_iterator it = rows.full_begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant if the source dimension is dense. Otherwise a binary search is used to find the beginning of the row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

◆ get_row() [2/2]

template<typename link_type >

virtual row_begin_iterator Graph< link_type >::get_row ( unsigned int row_index )

pure virtual

Returns an iterator pointing to the specified row.

Parameters

row_index Row index the returned iterator points to.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::row_begin_iterator rows = mygraph->begin_rows(1); rows != mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(Graph<int>::full_row_iterator it = rows.full_begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant if the source dimension is dense. Otherwise a binary search is used to find the beginning of the row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

Here is the caller graph for this function:

◆ push_deltas()

template<typename link_type >

void Graph< link_type >::push_deltas ( void )

virtual

Applies all queued modifications created by the add_delta function.

Modifications are applied starting with the first modification queued. If two modifications are queued for the same element, the most recent delta overwrites the older delta. If a modification would set an element to equal the default value, the element is instead removed. After all modifications have been made, the queue of deltas is cleared.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->add_delta(0, 0, 1);
    mygraph->push_deltas();
    
    std::cout << "row 0:";
    for (Graph<int>::full_row_iterator it = mygraph->full_row_begin(0); it != mygraph->row_end(0); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

row 0: 1 1 4 2

Complexity

Each modification requires an at(unsigned int, unsigned int, const link_type&) call which can be O(1) or O(log n) depending on dimension density. This call is done for every queued modification.

Iterator validity

If densities aren't sparse some iterators may be invalid based on set of deltas used

Exception Safety

Strong Guarantee: This function never throws exceptions.

Implements Typeless_Graph.

Here is the caller graph for this function:

◆ row_end()

template<typename link_type >

const typeless_graph_iterator Graph< link_type >::row_end ( unsigned int row_index ) const

Returns the end iterator for the specified row.

This iterator points to beyond the last piece of data and thus should not be dereferenced.

Parameters

row_index Row index the returned iterator points to.

Example

int main() {
 
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    for (Graph<int>::row_begin_iterator rows = mygraph->begin_rows(1); rows != mygraph->end_rows(); ++rows) {
 
        std::cout << "row " << rows.row() << ": ";
 
        for(Graph<int>::full_row_iterator it = rows.full_begin(); it != rows.end(); ++it) {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
}

Output:

row 1: 1 0 0 0
row 2: 0 0 2 3
row 3: 4 5 3 6

Complexity

Constant

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

Here is the caller graph for this function:

◆ row_sum()

template<typename link_type >

template<class output = decltype(link_type() + link_type())>

output Graph< link_type >::row_sum ( unsigned int row_index ) const

inline

Adds up all values in a row together.

Return type is the same as the link_type except for bool in which the row sum returns an int.

◆ sparse_col_begin() [1/2]

template<typename link_type >

virtual const_sparse_col_iterator Graph< link_type >::sparse_col_begin	(	unsigned int	col_index,
		const link_type &	skip_data
	)		const

pure virtual

Returns an iterator pointing to the first row index that shouldn't be skipped in the specified column.

Parameters

col_index	Column index the returned iterator points to.
skip_data	Element values the iterator will skip over.

Returns: An iterator pointing to the first row index whose value does not equal skip_data in the specified column.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    const Graph<int>* const_mygraph = mygraph;
 
    std::cout << "non-zero elements in col 1:";
    for(Graph<int>::const_sparse_col_iterator it = const_mygraph->sparse_col_begin(1, 0); it != const_mygraph->end_col(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

non-zero elements in col 1: 1 5

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

◆ sparse_col_begin() [2/2]

template<typename link_type >

virtual sparse_col_iterator Graph< link_type >::sparse_col_begin	(	unsigned int	col_index,
		const link_type &	skip_data
	)

pure virtual

Returns an iterator pointing to the first row index that shouldn't be skipped in the specified column.

Parameters

col_index	Column index the returned iterator points to.
skip_data	Element values the iterator will skip over.

Returns: An iterator pointing to the first row index whose value does not equal skip_data in the specified column.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    std::cout << "non-zero elements in col 1:";
    for(Graph<int>::sparse_col_iterator it = mygraph->sparse_col_begin(1, 0); it != mygraph->end_col(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

non-zero elements in col 1: 1 5

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a column.

Iterator validity

No changes.

Exception Safety

An assertion is raised if col_index is out of bounds of the target nodeset.

Here is the caller graph for this function:

◆ sparse_row_begin() [1/2]

template<typename link_type >

virtual const_sparse_row_iterator Graph< link_type >::sparse_row_begin	(	unsigned int	row_index,
		const link_type &	skip_data
	)		const

pure virtual

Returns an iterator pointing to the first column index that shouldn't be skipped in the specified row.

Parameters

row_index	Row index the returned iterator points to.
skip_data	Element values the iterator will skip over.

Returns: An iterator pointing to the first column index whose value does not equal skip_data in the specified row.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    const Graph<int>* const_mygraph = mygraph;
 
    std::cout << "non-zero elements in row 1:";
    for(Graph<int>::const_sparse_row_iterator it = const_mygraph->sparse_row_begin(1, 0); it != const_mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

non-zero elements in row 1: 1 9 3

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

◆ sparse_row_begin() [2/2]

template<typename link_type >

virtual sparse_row_iterator Graph< link_type >::sparse_row_begin	(	unsigned int	row_index,
		const link_type &	skip_data
	)

pure virtual

Returns an iterator pointing to the first column index that shouldn't be skipped in the specified row.

Parameters

row_index	Row index the returned iterator points to.
skip_data	Element values the iterator will skip over.

Returns: An iterator pointing to the first column index whose value does not equal skip_data in the specified row.

Example

int main()
{
    Graph<int>* mygraph;
 
    // Graph<int>* mygraph has been initialized with the following data
    // 0 1 4 2
    // 1 0 0 0
    // 0 0 2 3
    // 4 5 3 6
    // the default value for mygraph being zero.
    // each element with a zero does not have a data entry
 
    mygraph->at(1,2) = 9;
    mygraph->at(1,3) = 3;
 
    std::cout << "non-zero elements in row 1:";
    for(Graph<int>::sparse_row_iterator it = mygraph->sparse_row_begin(1, 0); it != mygraph->end_row(1); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
}

Output:

non-zero elements in row 1: 1 9 3

Complexity

If the source dimension is dense, constant. Otherwise a binary search is used to find the beginning of a row.

Iterator validity

No changes.

Exception Safety

An assertion is raised if row_index is out of bounds of the source nodeset.

Here is the caller graph for this function:

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ col_graph_iterator

◆ const_col_begin_iterator

◆ const_full_col_iterator

◆ const_full_row_iterator

◆ const_row_begin_iterator

◆ const_sparse_col_iterator

◆ const_sparse_row_iterator

◆ full_col_iterator

◆ full_row_iterator

◆ graph_iterator

◆ row_begin_iterator

◆ row_graph_iterator

◆ sparse_col_iterator

◆ sparse_graph_iterator

◆ sparse_row_iterator

Constructor & Destructor Documentation

◆ ~Graph()

Member Function Documentation

◆ add_delta()

◆ apply_col_operation()

◆ apply_operation()

◆ apply_row_operation()

◆ at() [1/4]

◆ at() [2/4]

◆ at() [3/4]

◆ at() [4/4]

◆ begin_cols() [1/2]

◆ begin_cols() [2/2]

◆ begin_rows() [1/2]

◆ begin_rows() [2/2]

◆ clear()

◆ col_end()

◆ col_sum()

◆ end_cols()

◆ end_rows()

◆ examine()

◆ full_col_begin() [1/2]

◆ full_col_begin() [2/2]

◆ full_row_begin() [1/2]

◆ full_row_begin() [2/2]

◆ get_col() [1/2]

◆ get_col() [2/2]

◆ get_data_state()

◆ get_row() [1/2]

◆ get_row() [2/2]

◆ push_deltas()

◆ row_end()

◆ row_sum()

◆ sparse_col_begin() [1/2]

◆ sparse_col_begin() [2/2]

◆ sparse_row_begin() [1/2]

◆ sparse_row_begin() [2/2]