S

#### sschnug

i'm trying to implement a solver for a problem called hitting-set (np-

complete). My first simple version of a tree search (parameterized

algorithm) should be generic. It should work without knowing the data

structure used for saving the instance.

An instance of the problem is described with a collection C of subsets

of size three (maxsize=3) of a finite set S and a parameter k. The

solver should determine a subset S' smaller than S with |S<k|, so that

S' contains at least one element from each subset C.

Now my idea for storing the instance:

- There is a class Vertexpointer which stores pointers to sets, where

the vertex is present. Using a generic container.

template<class T>

class VERTEXPOINTER{

int size;

T container;

};

- There is also the same Pointercontainer with Edges

- The class EDGE stores the pointers and the sets

template<class T>

class EDGE : public EDGEPOINTER<T>{

int size;

int vertices[3];

EDGEPOINTER<T> pointers;

};

- The class EDGES stores all EDGE's (EDGE's are splitted in 3 Groups)

template<class T>

class EDGES{

int size;

int sizeOne;

int sizeTwo;

int sizeThree;

T degreeOne;

T degreeTwo;

T degreeThree;

};

-Then there is the HYPERGRAPH which stores everything

template<class T>

class HYPERGRAPH : VERTICES<T>, EDGES<T>{

VERTICES<T> vertices;

EDGES<T> edges;

};

That was my first attempt of defining generic classes for later

implementing algorithms.

Now i want to implement a tree search. But i'm unable to get the

needed Iterators. I thought that every container has a iterator and

therefore i can pick this one in my algorithm.

But maybe i need all the iterators (many many) as parameters to my

algorithm?

My questions?

- is it possible to work with the above definitions?

- could it be more generic? (i already designed the pointercontainer

in each element (edge, vector))

- how do i use this definitions in algorithms WITHOUT defining the

real types (i want to chose the containertypes at the end)