Problem with Generic Algorithms (Template Design)

[sschnug]

Hi,
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)

 

[sschnug]

i accidentally clicked send without finishing my post :-/

So this is my first attempt of my algorithm (partial code)

template<class T>
bool simpleSearchTree(HYPERGRAPH<T> graph, int k){

if(graph.vertices.size < k){
return false;
}
else if(graph.edges.size == 0){
return true;
}
else if(k==0){
return false;
}
else{
if(graph.edges.sizeThree != 0){

Then i need acces to the container elements. Therefore i need
iterators. Something like typename graph.edges.degreeThree::iterator
it; doesn't work. How i get access and the iterators?

Thanks for all the help. I know that my problem isn't really good
described. And theres a lack of knowledge about generic programming at
all. I read a bigger part of "Generic Programming and the STL" by
Matthew Austern and read about these iterator types like forward
iterator and bilateral but i can't use this knowledge. So i'm happy
about every comment

Thanks

maybe needed information: using gcc 4.3.x

 

[joecook]

I can't say I understand your question much at all, but I think you
are trying to run before you walk.. (There's nothing wrong with that))

You say:

template<class T>
class EDGE : public EDGEPOINTER<T>{
int size;
int vertices[3];
EDGEPOINTER<T> pointers;
};

What is an EDGE? (Btw, class names that are all CAPS are HARDER TO
READ)
It looks like an EDGE _is a_ EDGEPOINTER<T> (by inheritance) but it
also contains an EDGEPOINTER<T>

This doesn't make sense to me exactly. I'm also confused by what 'T'
may be. In this class, it seems it may be something like "float", but
the EDGEPOINTER class seems to think it should be something like
"vector<float>" (the variable is named 'container')

I have the same question on your HYPERGRAPH class, except that is
using private inheritance instead of public, but the intent is not
clearer..

You most likely do _not_ have to pass iterators around in what you are
trying to do. If you have stored a 'T' which happens to be something
where T::iterator is defined, (STL container), then you can access it
that way.

Joe C

 

[sschnug]

ok i recognized that this class inheritance wasn't really logical. for
my small projects i never used classes at all in c++.

template<class T>
class EDGE : public EDGEPOINTER<T>{
int size;
int vertices[3];
EDGEPOINTER<T> pointers;

};

that was my attempt to define an EDGE with size, vertices array and a
generic container holding pointers. Because this is generic too, i
thought i have to define it with an extra template like i did. And
then using inheritance.
How would you implement the EDGE class which doesn't have a generic
type inside except of a type EDGEPOINTER which holds a generic
container? Is inheritance necessary?
I think my code means that EDGE inherit from EDGEPOINTER and therefore
has already a container EDGEPOINTER in itself? So EDGEPOINTER<T>
pointers; should be complete useless.

So i'm trying to understand how i implement structures/classes which
holds thing, that can itself generic.

 

[sschnug]

New attempt of using generic classes in other classes with template
parameters.

VertexPointer and EdgePointer form the bottom layer. These are used in
the next Layer. Vertex and Edge. These both are used int Vertices and
Edges which form togeter the class Hypergraph.

template<class T>
class VertexPointer{
int size;
T container;
};

template<class T>
class EdgePointer{
int size;
T container;
};

template<typename T>
class Vertex{
int number;
T pointers;
};

template<typename T>
class Edge{
int size;
int vertices[3];
T pointers;
};

template<typename T>
class Vertices{
int size;
T container;
};

template<typename T>
class Edges{
int size;
int sizeOne;
int sizeTwo;
int sizeThree;
T degreeOne;
T degreeTwo;
T degreeThree;
};

template<typename T, typename U>
class Hypergraph{
T vertices;
U edges;
};

After these definitions, i try to implement an algorithm which works
with them:

template<class T>
bool simpleSearchTree(T graph, int k){

if(graph.vertices.size < k){
return false;
}
else if(graph.edges.size == 0){
return true;
}
else if(k==0){
return false;
}
else{
if(graph.edges.sizeThree != 0){
typename graph.edges.degreeThree::iterator it; //ERROR

How do i get the iterator of the container degreeThree which is part
of Edges, which is part of Hypergraph?
And is the definition above appropriate for my simple nested data
stucture? Will it work?

Thanks for help

 

[Kai-Uwe Bux]

New attempt of using generic classes in other classes with template
parameters.
template<class T>
class VertexPointer{
        int size;
        T container;
};

template<class T>
class EdgePointer{
        int size;
        T container;
};

template<typename T>
class Vertex{
        int number;
        T pointers;
};

template<typename T>
class Edge{
        int size;
        int vertices[3];
        T pointers;
};

template<typename T>
class Vertices{
        int size;
        T container;
};

template<typename T>
class Edges{
        int size;
        int sizeOne;
        int sizeTwo;
        int sizeThree;
        T degreeOne;
        T degreeTwo;
        T degreeThree;
};

template<typename T, typename U>
class Hypergraph{
        T vertices;
        U edges;
};

After these definitions, i try to implement an algorithm which works
with them:
template<class T>
bool simpleSearchTree(T graph, int k){

        if(graph.vertices.size < k){
                return false;
        }
        else if(graph.edges.size == 0){
                return true;
        }
        else if(k==0){
                return false;
        }
        else{
                if(graph.edges.sizeThree != 0){
                        typename graph.edges.degreeThree::iterator
                        it;       //ERROR

The type is a member of the class, not of the object. The object does not
give you any means to obtain the iterator type. You would want

typename T::EdgeType::degreeThreeType::iterator it;

but you did not typedef the template parameters, whence this information is
not available.

How do i get the iterator of the container degreeThree which is part
of Edges, which is part of Hypergraph?

Have typedefs that allow you to get at the template parameters, e.g.,


template<typename T>
class Edges{
int size;
int sizeOne;
int sizeTwo;
int sizeThree;
T degreeOne;
T degreeTwo;
T degreeThree;

public:

typedef T template_parameter;

};

And is the definition above appropriate for my simple nested data
stucture? Will it work?

Probably it isn't appropriate: it looks like using templates for no reason.
Maybe, you should start with a clear definition of the client interface and
worry about implementing the algorithm later.

Whether it will work, I don't know. With enough determination, anything can
be made to work.



Best

Kai-Uwe Bux

 

[sschnug]

Thanks for your reply. I added typedefs to every class which is part
of my hypergraph.
After instantiating my stuctures, i'm able to access the iterators
with the described way. Now i'm able to switch the data structures of
my classes between list, vector, set at one place in my code like i
wanted. Thanks for the help.
Now i have to play around and try to implement complete algorithms
with speciallizations and more.

Best Regards
Sascha

 

[sschnug]

One more question:

After the following definitions:

template<class T>
class VertexPointer{
public:
int size;
T container;
typedef T vertexPointerType;
};

template<class T>
class EdgePointer{
public:
int size;
T container;
typedef T edgePointerType;
};

template<class T>
class Vertex{
public:
int number;
T pointers;
typedef T vertexType;
};

template<class T>
class Edge{
public:
int size;
int vertices[3];
T pointers;
typedef T edgeType;
};

template<class T>
class Vertices{
public:
int size;
T container;
typedef T verticesType;
};

template<class T>
class Edges{
public:
int size;
int sizeOne;
int sizeTwo;
int sizeThree;
T degreeOne;
T degreeTwo;
T degreeThree;

typedef T edgesType;
};

i try to instantiate the Templates with my stl data structures as
parameters like this:

typedef EdgePointer<std::list<int> > graphEdgePointer;
typedef VertexPointer<std::list<int> > graphVertexPointer;
typedef Edge<std::list<graphEdgePointer> > graphEdge;
typedef Vertex<std::list<graphVertexPointer> > graphVertex;
typedef Edges<std::list<graphEdge> > graphEdges;
typedef Vertices<std::list<graphVertex> > graphVertices;

and merge all together in Hypergraph:

class Hypergraph{
public:
graphEdges edges;
graphVertices vertices;
};

This works (compiles and i get access to the class elements and
iterators).

My question:
- EdgePointer and VertexPointer are now lists of integers, but i want
them to be a list of Vertex' and list of Edge. But how do i
instantiate that. I think i will need some sort of forward declaring.
I tried the following but it didn't worked:

//forward declaring
template <class T>
class Vertex;

template <class T>
class Edge;

typedef EdgePointer<std::list<Vertex> > graphEdgePointer;
typedef VertexPointer<std::list<Edge> > graphVertexPointer;
[...]

compiler is arguing that he wants a type, but got Vertex. But Vertex
is my desired type. typename as hint didn't work either.

Any recommendations?

Thanks for help

 

[Kai-Uwe Bux]

One more question:

After the following definitions:

template<class T>
class VertexPointer{
public:
int size;
T container;
typedef T vertexPointerType;
};

template<class T>
class EdgePointer{
public:
int size;
T container;
typedef T edgePointerType;
};

template<class T>
class Vertex{
public:
int number;
T pointers;
typedef T vertexType;
};

template<class T>
class Edge{
public:
int size;
int vertices[3];
T pointers;
typedef T edgeType;
};

template<class T>
class Vertices{
public:
int size;
T container;
typedef T verticesType;
};

template<class T>
class Edges{
public:
int size;
int sizeOne;
int sizeTwo;
int sizeThree;
T degreeOne;
T degreeTwo;
T degreeThree;

typedef T edgesType;
};

i try to instantiate the Templates with my stl data structures as
parameters like this:

typedef EdgePointer<std::list<int> > graphEdgePointer;
typedef VertexPointer<std::list<int> > graphVertexPointer;
typedef Edge<std::list<graphEdgePointer> > graphEdge;
typedef Vertex<std::list<graphVertexPointer> > graphVertex;
typedef Edges<std::list<graphEdge> > graphEdges;
typedef Vertices<std::list<graphVertex> > graphVertices;

and merge all together in Hypergraph:

class Hypergraph{
public:
graphEdges edges;
graphVertices vertices;
};

This works (compiles and i get access to the class elements and
iterators).

My question:
- EdgePointer and VertexPointer are now lists of integers, but i want
them to be a list of Vertex' and list of Edge. But how do i
instantiate that. I think i will need some sort of forward declaring.
I tried the following but it didn't worked:

//forward declaring
template <class T>
class Vertex;

template <class T>
class Edge;

typedef EdgePointer<std::list<Vertex> > graphEdgePointer;
typedef VertexPointer<std::list<Edge> > graphVertexPointer;
[...]

compiler is arguing that he wants a type, but got Vertex. But Vertex
is my desired type. typename as hint didn't work either.

[snip]

That cannot work since Vertex is not a class, but a template. In particular,
Vertex is not a type. Vertex<some_type> is a type.

Before you try something more complicated to actually feed types, be advised
that STL containers need their value_type template arguments to be
_complete_ types. Otherwise, you get undefined behavior (and it is up to
the implementation whether to issue a diagnostic or not).


Best

Kai-Uwe Bux