mcb::spvecgf2 Class Reference

#include <spvecgf2.h>

List of all members.

---

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:

Dimitris Michail

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
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

---

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()

void mcb::spvecgf2::clear (   )  [inline]

Clear the set.

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.

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.

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()

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.

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().

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  )  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().

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().

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= (  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.

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

Assign current vector to be .

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.

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.

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.

---