Asp Forum - Problem with Generic Algorithms (Template Design

sschnug

12/7/2008 10:25:00 PM

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)

10 Answers

sschnug

12/7/2008 10:32:00 PM

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

joseph cook

12/7/2008 10:45:00 PM

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

12/7/2008 11:13:00 PM

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

12/8/2008 1:35:00 AM

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

12/8/2008 1:54:00 AM

sschnug wrote:

> 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

12/8/2008 2:23:00 PM

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

12/8/2008 7:52:00 PM

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

12/8/2008 10:17:00 PM

sschnug wrote:

> 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

A Moose in Love

4/6/2014 11:05:00 AM

On Saturday, April 5, 2014 12:33:33 PM UTC-4, The Revd wrote:
> On Sat, 5 Apr 2014 16:16:02 +0200, "Heinrich" <Heinrich@Ruhrgasnet.de>
>
> wrote:
>
>
>
> >is there any use of griks in today's society? I think not they are just a
>
> >waste of space and use too much oxygin
>
>
>
> Even niggers are of more use than Griks!

I can't use the 'n' word because it's illegal to do so in Canada. Or maybe not. Hell I don't know. Some black people are of the 'n' word, and some are not. Just like some white people are 'crackers' and some not. I worked beside the most obnoxious person you could ever meet. He was a person of the 'n' persuasion. I also worked with the most wonderful man you could meet. He was black.
I think it's legal to call people of grik culture names, although I do so in a joking manner. I could really give a shit one way or the other.
I've never eaten grik food. I don't know why. They come here, try and steal our women with their grik souvlaki and expect us to like it?
Back home in Italy, we used to have griks that would make yours look like an antique.
On a serious note though, they are sucking up to Germany for money. For that, they are crap. Germany this, and Germany that and Nazis this and that Oy Vey.

The Peeler

4/6/2014 11:27:00 AM

On Sun, 6 Apr 2014 04:04:51 -0700 (PDT), A Moose in Love in Love with Nazi
Scum wrote:

<FLUSH the disgusting Nazi-cock sucker's usual sick shit>

Keep your STENCH out of sci!

comp.lang.c++

Problem with Generic Algorithms (Template Design

sschnug

sschnug

joseph cook

sschnug

sschnug

Kai-Uwe Bux

sschnug

sschnug

Kai-Uwe Bux

A Moose in Love

The Peeler

x Login to ForumsZone