A sparse vector with elements in GF2. More...

#include <spvecgf2.h>

Public Member Functions

	spvecgf2 ()

	spvecgf2 (const spvecgf2 &a)

	~spvecgf2 ()


spvecgf2 &	operator= (const spvecgf2 &i)

spvecgf2 &	operator= (const int &i)

spvecgf2 &	operator= (d_int_set &i)

spvecgf2	operator- () const

int	operator* (const spvecgf2 &a) const

spvecgf2	operator+ (const spvecgf2 &a) const

void	add (const spvecgf2 &a)

spvecgf2	operator% (const spvecgf2 &a) const

d_int_set	operator% (const d_int_set &a) const

spvecgf2	intersect (const spvecgf2 &a) const

spvecgf2 &	operator+= (const spvecgf2 &a)

spvecgf2 &	operator-= (const spvecgf2 &a)

spvecgf2 &	operator%= (const spvecgf2 &a)

void	swap (spvecgf2 &a)


d_int_set	to_d_int_set () const

list< int >	to_list () const


void	clear ()

void	print (std::ostream &o) const

void	append (int index)

void	insert (int index)

int	pop ()

void	sort ()

bool	empty () const

int	size () const

list_item	first () const

list_item	last () const

list_item	succ (list_item it) const

list_item	pred (list_item it) const

int	index (list_item it) const

int	inf (list_item it) const

Detailed Description

A sparse vector with elements in GF2.

An object of this class represents a cycle of an undirected graph. It behaves as a sparse matrix of values in GF(2).

This class is implemented internally by double linked lists. The internal representation is a list of integers representing the indexes where the vector has a one. The indexes are stored in increasing order. Operations append and insert take constant time but do not ensure the correct ordering of the elements. See sort() for reconstructing this ordering.

Most binary operations take time proportional to the number of elements in the list by assumming that the indexes are stored in increasing order. Size, empty, clear and the iterators' methods take constant time. Swap also takes constant time.

Such an object can be accessed in exactly the same manner that a list of LEDA is accessed. Each one in the sparse vector corresponds in a list_item in a list. Thus, the following is valid:

mcb::spvecgf2 v;
int i;
leda::list_item li = v.first();
while( li != NULL ) { 
    i = v.index( li );
    // do something with i
    li = v.succ( li );
}

LEDA's forall macro works for this objects. It can be used in the following way:

mcb::spvecgf2 v;
int i;
forall(i,v) { 
    // do something with i
}

Date: 2005

Author: Dimitrios Michail

Constructor & Destructor Documentation

mcb::spvecgf2::spvecgf2 ( )

Default constructor.

mcb::spvecgf2::spvecgf2 ( const spvecgf2 & a )

Copy constructor.

mcb::spvecgf2::~spvecgf2 ( )

Destructor

Member Function Documentation

void mcb::spvecgf2::add ( const spvecgf2 & a )

Add a vector to the current vector.

Parameters

a	The vector to add.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

void mcb::spvecgf2::append ( int index )

Append an entry, without checking for proper order.

Parameters

index An integer representing that the sparse vector has a one at that position. Indexing should start from zero.

Remarks: The internal representation of this object is an ordered list of integers. This function however makes no attempt to ensure such an ordering, it only appends the new entry into the list. Use wisely.

See also: sort()

Referenced by clear().

void mcb::spvecgf2::clear ( )

inline

Clear the set.

References append(), index(), insert(), and print().

bool mcb::spvecgf2::empty ( ) const

inline

Check if empty.

Returns: True if empty, false otherwise.

list_item mcb::spvecgf2::first ( ) const

inline

Returns the first item of the sparse vector. Each item represents a position where the sparse vector has a one.

Returns: Returns the first item of the vector. This item is a list_item of LEDA's list representation. NULL is returned if the vector contains no elements.

int mcb::spvecgf2::index ( list_item it ) const

inline

Get the index of an item. Each item represents a one in the sparse vector.

Parameters

it The item.

Returns: The position of this one in the sparse vector.

Referenced by clear().

int mcb::spvecgf2::inf ( list_item it ) const

inline

Get the index of an item. Each item represents a one in the sparse vector.

Parameters

it The item.

Returns: The position of this one in the sparse vector.

References mcb::operator<<(), and mcb::operator>>().

void mcb::spvecgf2::insert ( int index )

Append an entry, without checking for proper order.

Parameters

index An integer representing that the sparse vector has a one at that position. Indexing should start from zero.

Remarks: The internal representation of this object is an ordered list of integers. This function however makes no attempt to ensure such an ordering, it only appends the new entry into the list. Use wisely.

See also: sort()

Referenced by clear().

spvecgf2 mcb::spvecgf2::intersect ( const spvecgf2 & a ) const

Compute the intersection of this vector and a.

Parameters

a	A sparse vector.

Returns: The intersection of the current object and a.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

list_item mcb::spvecgf2::last ( ) const

inline

Returns the last item of the sparse vector. Each item represents a position where the sparse vector has a one.

Returns: Returns the last item of the vector. This item is a list_item of LEDA's list representation. NULL is returned if the vector contains no elements.

spvecgf2 mcb::spvecgf2::operator% ( const spvecgf2 & a ) const

Operator to compute the symmetric difference of this sparse vector and of a.

Parameters

a	A sparse vector.

Returns: The symmetric difference as a new sparse vector.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

d_int_set mcb::spvecgf2::operator% ( const d_int_set & a ) const

Operator to compute the symmetric difference of this sparse vector and of a LEDA dynamic integer set.

Parameters

a	A dynamic integer set.

Returns: The symmetric difference as a new dynamic integer set.

spvecgf2& mcb::spvecgf2::operator%= ( const spvecgf2 & a )

Assign to the current vector the symmetric difference of the current vector an vector a.

Parameters

a	An input sparse vector.

Returns: The current vector after the symmetric difference operation.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

int mcb::spvecgf2::operator* ( const spvecgf2 & a ) const

Compute inner product.

Parameters

a	Input vector a.

Returns: The inner product of this object and a.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

spvecgf2 mcb::spvecgf2::operator+ ( const spvecgf2 & a ) const

Operator to add the current vector with another vector.

Parameters

a	The second vector to add.

Returns: A new vector representing the sum.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

spvecgf2& mcb::spvecgf2::operator+= ( const spvecgf2 & a )

Add a vector to the current vector.

Parameters

a	The vector to add.

Returns: The current vector after the addition.

Precondition: Assumes a sorted representation. See insert(), append() and sort().

spvecgf2 mcb::spvecgf2::operator- ( ) const

Negate the current vector.

Returns: A new object representing the current vector negated.

spvecgf2& mcb::spvecgf2::operator-= ( const spvecgf2 & a )

Add a vector to the current vector.

Parameters

a	The vector to add.

Returns: The current vector after the addition.

Remarks: Subtracting and addition is the same in GF(2).

Precondition: Assumes a sorted representation. See insert(), append() and sort().

spvecgf2& mcb::spvecgf2::operator= ( const spvecgf2 & i )

Assign a vector to another vector.

Parameters

i	The vector to assign from.

Returns: The current vector after the assignment.

spvecgf2& mcb::spvecgf2::operator= ( const int & i )

Assign current vector to be $e_i$ .

spvecgf2& mcb::spvecgf2::operator= ( d_int_set & i )

Assignment operator for a leda::d_int_set.

Parameters

i	A compressed integer set of LEDA.

Returns: The currect sparse vector.

int mcb::spvecgf2::pop ( )

inline

Delete the first entry of the sparse vector and return its index.

Returns: The index of the first entry which was deleted.

Precondition: The sparse array should not be empty.

list_item mcb::spvecgf2::pred ( list_item it ) const

inline

Get the predecessor of an item. Each item represents a position where the sparse vector has a one.

Returns: The predecessor of an item, NULL if sparse vector is empty.

Precondition: it is an item of the current object.

void mcb::spvecgf2::print ( std::ostream & o ) const

Print a sparse vector to a stream.

Parameters

o	The stream to print to.

Referenced by clear().

int mcb::spvecgf2::size ( ) const

inline

Get size of sparse vector.

Returns: The size of the sparse vector.

void mcb::spvecgf2::sort ( )

inline

Sort the internal representation of the sparse vector. This operation ensures that a correct representation after its call. Should not be necessary unless insert or append were called in wrong order. Note that this function does not make sure the entries are unique.

list_item mcb::spvecgf2::succ ( list_item it ) const

inline

Get the successor of an item. Each item represents a position where the sparse vector has a one.

Returns: The successor of an item, NULL if sparse vector is empty.

Precondition: it is an item of the current object.

void mcb::spvecgf2::swap ( spvecgf2 & a )

Swap two sparse vectors.

Parameters

a	A sparse vector to swap with the current object.

Remarks: This is a constant time operation.

d_int_set mcb::spvecgf2::to_d_int_set ( ) const

Transform the sparse vector to a LEDA dynamic integer set.

Returns: A dynamic integer set.

list<int> mcb::spvecgf2::to_list ( ) const

inline

Transform the sparse vector to a list of integers.

Returns: A LEDA list of integers.

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation