Depends::DAG

Depends::DAG< ValueType > Class Template Reference

A DAG carries its name very well: it means day in dutch and most dependencies are tracked at daytime. More...

#include <Depends/DAG.h>

List of all members.

Public Types

typedef ValueType value_type
typedef ValueType key_type
typedef ValueType & reference
typedef const ValueType & const_reference
typedef ValueType * pointer
typedef const ValueType * const_pointer
typedef unsigned long score_type
typedef Details::Node< ValueType,
score_type > 		node_type
typedef std::vector< node_type * > nodes_type
typedef Details::Iterator<
ValueType, const ValueType &,
const ValueType *, score_type,
typename nodes_type::iterator > 		iterator
typedef Details::Iterator<
ValueType, const ValueType &,
const ValueType *, score_type,
typename nodes_type::iterator > 		const_iterator
typedef Details::ReverseIterator<
ValueType, const ValueType &,
const ValueType *, score_type,
typename nodes_type::reverse_iterator > 		reverse_iterator
typedef Details::ReverseIterator<
ValueType, const ValueType &,
const ValueType *, score_type,
typename nodes_type::reverse_iterator > 		const_reverse_iterator
typedef std::vector< node_type
>::difference_type 		difference_type
typedef std::vector< node_type
>::size_type 		size_type
typedef Details::CircularReferenceException circular_reference_exception
 This exception is thrown in case a new link creates a circular reference.

Public Member Functions

 DAG ()
 DefaultConstructible.
 DAG (const DAG &d)
 CopyConstructible.
template<typename InputIterator>
 DAG (InputIterator first, InputIterator last)
 This constructor does not create any links and, for most intents and purposes, creates a simple vector-like container from the values in the given range.
DAG & operator= (const DAG &d)
 Assignable.
 ~DAG ()
iterator begin ()
 Get a bidirectional iterator to the beginning of the container.
const_iterator begin () const
 Get a bidirectional const iterator to the beginning of the container.
reverse_iterator rbegin ()
 Get a bidirectional reverse iterator to the end of the container.
const_reverse_iterator rbegin () const
 Get a bidirectional reverse const iterator to the end of the container.
iterator end ()
 Get a bidirectional iterator to one-past-the-end of the container.
const_iterator end () const
 Get a bidirectional const iterator to one-past-the-end of the container.
reverse_iterator rend ()
 Get a bidirectional reverse iterator to beginning of the container.
const_reverse_iterator rend () const
 Get a bidirectional reverse const iterator to beginning of the container.
size_type size () const
 get the size of the container
size_type max_size () const
 get the maximal size of the container (here for compatbility purposes only)
bool empty () const
 check whether the container is empty
void swap (DAG &d)
 swap the contents of this container with another one of the same type
bool operator== (const DAG &d) const
 Equality Comparable.
bool operator!= (const DAG &d) const
 Equality Comparable.
bool operator< (const DAG &d) const
 LessThan Comparable.
bool operator> (const DAG &d) const
 GreaterThan Comparable.
bool operator<= (const DAG &d) const
 LessThanOrEqual Comparable.
bool operator>= (const DAG &d) const
 GreaterThanOrEqual Comparable.
std::pair< iterator, bool > insert (const value_type &val)
 Insert a value in the container.
template<typename InputIterator>
void insert (InputIterator first, InputIterator last)
 Insert a range of values into the container, skipping anything that would be a duplicate.
void link (iterator source, iterator target)
 Link two values (nodes) at the give locations.
void link (iterator source, value_type target)
 Link a node at a given location with a given value.
void link (value_type source, iterator target)
 Link a node at with a given value to a node at a given location.
void link (value_type source, value_type target)
 link two values together
bool linked (iterator source, iterator target) const
 check whether the source and target nodes are linked
bool linked (iterator source, value_type target) const
 check whether the source and target nodes are linked
bool linked (value_type source, iterator target) const
 check whether the source and target nodes are linked
bool linked (value_type source, value_type target) const
 check whether the source and target nodes are linked
bool unlink (iterator source, iterator target)
 unlink source from target if they are linked
bool unlink (iterator source, value_type target)
 unlink source from target if they are linked
bool unlink (value_type source, iterator target)
 unlink source from target if they are linked
bool unlink (value_type source, value_type target)
 unlink source from target if they are linked
iterator erase (iterator where)
 erase the node at the given iterator, unlinking it from the DAG
iterator erase (iterator begin, iterator end)
 erase the values in the given range.
void clear ()
 Clear the DAG of all its contents.

Detailed Description

template<class ValueType>
class Depends::DAG< ValueType >

A DAG carries its name very well: it means day in dutch and most dependencies are tracked at daytime.

Such feeble attempts at humor aside, a DAG is, in deed, a collection of directed edges between nodes (or vertices, if you prefer) which, by definition, is acyclic. This means that if there exists a path (of edges) that goes from node A to node B, there shall not be a path that goes from node B to node A.

This particular DAG is a Reversible Container and a Unique Associative Container that just happens to sort its contents according to the links established between each of their values. The "normal" way to use this would therefore be to populate the DAG, and establish links between the values, using one of the link functions.

As an example of use, there are two test cases that may be of interest: First, a vector and a dag are both populated with integers ranging from 0 to 99, inclusive. 

void test1(void)
{
        Depends::DAG<int> dag;
        std::vector<int> v;
        
        for (int i = 0; i < 10/*0*/; ++i)
        {
                dag.insert(i);
                v.push_back(i);
        }
then, the vector is shuffled and links are created in the dag. As this carries on, more and more of those links will not be made as they would result in circular references. 
        for (int c = 0; c < 5; c++)
        {
                std::random_shuffle(v.begin(), v.end());
                for (std::vector<int>::const_iterator i = v.begin(); i + 1 != v.end(); ++i)
                {
                        try
                        {
                                std::cerr << "Setting a link between " << *i << " and " << *(i + 1) << ": ";
                                dag.link(*i, *(i + 1));
                                std::cerr << "OK" << std::endl;
                        }
                        catch (const Depends::DAG<int>::circular_reference_exception &)
                        {
                                // ignore circular references in this test
                                std::cerr << "Failed" << std::endl;
                        }
                }
        }
We then copy the contents of the DAG to std::cout, separating each entry with a space. 
        std::copy(dag.begin(), dag.end(), std::ostream_iterator<int>(std::cout, " "));
The output is sorted in order of "score", putting the node with the least dependencies pointing to it first. This means that that particular node is the one on which nothing depends.

The way this ordering is done is pretty simple: once a link is established in the DAG, a score (which starts at 1) is propagated through the DAG, adding the score of each source node to every one of its targets. As this is a recursive process, the final target node gets the highest score, which means it ends up at the end of the (serialized) DAG.

A second example would be a second test case in which we specifically check that a circular reference is detected. We first populate the DAG with ten values 

void test2(void)
{
        Depends::DAG<int> dag;
        std::vector<int> v;
        
        for (int i = 0; i < 10; i++)
                dag.insert(i);
and then link the values 1 through 4 together, linking 1 to 2, 2 to 3 and 3 to 4 
        for (int i = 1; i < 4; ++i)
                dag.link(i, i + 1);
Finally, we try to link 4 back to 2, which should create a circular reference and therefore throw an exception 
        
        bool detected(false);
        try
        {
                dag.link(4, 2);
        }
        catch (const Depends::DAG<int>::circular_reference_exception &)
        {
                std::cerr << "Circular reference detected" << std::endl;
                detected = true;
        }
The test-case should therefore, in test2, output "Circular reference detected"

Parameters:
ValueType the type of whatever the DAG should be decorated with
Todo:
provide a way to specify the allocator to use
Todo:
provide a way to provide a predicate to use to compare values

Definition at line 126 of file DAG.h.

Constructor & Destructor Documentation

template<class ValueType>
template<typename InputIterator>
Depends::DAG< ValueType >::DAG ( InputIterator  first,
InputIterator  last 
) [inline]

This constructor does not create any links and, for most intents and purposes, creates a simple vector-like container from the values in the given range.

Parameters:
first first iterator in the range to copy
last one-past-the-end

Definition at line 189 of file DAG.h.

Member Function Documentation

template<class ValueType>
std::pair<iterator, bool> Depends::DAG< ValueType >::insert ( const value_type &  val  )  [inline]

Insert a value in the container.

This does not create any links, but simply prepares a value to be linked with another one by inserting it in the container.

Returns:
a pair containing an iterator where the value was inserted and a boolean indicating that it was inserted. These two are set to end and false, resp. if the value was not inserted (which should only happen if the value is already in the container).

Definition at line 278 of file DAG.h.

Referenced by Depends::DAG< std::iterator_traits< iterator >::pointer >::DAG(), and Depends::DAG< std::iterator_traits< iterator >::pointer >::insert().

template<class ValueType>
template<typename InputIterator>
void Depends::DAG< ValueType >::insert ( InputIterator  first,
InputIterator  last 
) [inline]

Insert a range of values into the container, skipping anything that would be a duplicate.

Parameters:
first the first iterator in the range
last the last iterator in the range, which is expected to point one-past-the-end

Definition at line 293 of file DAG.h.

template<class ValueType>
void Depends::DAG< ValueType >::link ( iterator  source,
iterator  target 
) [inline]

Link two values (nodes) at the give locations.

Precondition:
neither source nor target must be the end iterator

both source and target must be valid iterators of this container

Parameters:
source the source node to link
target the node to link to
Exceptions:
circular_reference_exception if the link would create a circular reference

Definition at line 305 of file DAG.h.

Referenced by Depends::DAG< std::iterator_traits< iterator >::pointer >::link().

template<class ValueType>
void Depends::DAG< ValueType >::link ( iterator  source,
value_type  target 
) [inline]

Link a node at a given location with a given value.

Precondition:
the value must already be in the container

target must not be the end iterator and must be a valid iterator of this container

Parameters:
source the iterator at which the source value (node) can be found
target the value to link to
Exceptions:
circular_reference_exception if the link would create a circular reference

Definition at line 326 of file DAG.h.

template<class ValueType>
void Depends::DAG< ValueType >::link ( value_type  source,
iterator  target 
) [inline]

Link a node at with a given value to a node at a given location.

Precondition:
the value must already be in the container

source must not be the end iterator and must be a valid iterator of this container

Parameters:
source the value to link from
target the iterator at the location to link to
Exceptions:
circular_reference_exception if the link would create a circular reference

Definition at line 341 of file DAG.h.

template<class ValueType>
void Depends::DAG< ValueType >::link ( value_type  source,
value_type  target 
) [inline]

link two values together

Precondition:
both values must already be in the container
Parameters:
source the value of the node to link from
target the value of the node to link to
Exceptions:
circular_reference_exception of the link would create a circular reference

Definition at line 355 of file DAG.h.

template<class ValueType>
iterator Depends::DAG< ValueType >::erase ( iterator  where  )  [inline]

erase the node at the given iterator, unlinking it from the DAG

Precondition:
the iterator must be a valid iterator within this container and must not be end
Parameters:
where the iterator indicating the value to delete from the container.

Definition at line 465 of file DAG.h.

Referenced by Depends::DAG< std::iterator_traits< iterator >::pointer >::clear().

template<class ValueType>
iterator Depends::DAG< ValueType >::erase ( iterator  begin,
iterator  end 
) [inline]

erase the values in the given range.

Precondition:
both begin and end must be valid iterators in this container

end must be reachable by incrementing from begin

Parameters:
begin iterator pointing to the first value to delete from the container
end iterator pointing one-past-the-end of the range to delete

Definition at line 482 of file DAG.h.

The documentation for this class was generated from the following file:
Generated on Sat Aug 11 11:56:05 2007 for Depends by  doxygen 1.5.1