Implementing weird kind of graph in C++

M

mike3

Hi.

I've got this problem. I'm trying to implement a funny kind of "graph"
composed of "beads" which are strung together to form "strings" that
are in turn attached at beads to form the full "graphs". I've got
something like this:

---
class BeadString;

struct Connection {
int dstBeadIdx;
BeadString *dstString;
};

class Bead {
private:
// ...
std::vector<Connection> connections; // connections from this
bead to
// other beads
public:
// ...
void addConnection(int, BeadString *); // Adds a connection to
other beads
// ...
};

class BeadString {
private:
std::vector<Bead> beads;
std::string label;
public:
// ...
BeadString(int, std::string);
// ...
};

class Web {
private:
std::vector<BeadString> strings;
std::string label;
// ...
public:
// ...
void addBeadString(int, std::string);
};

// ...

void Bead::addConnection(int dstBeadIdx, BeadString *dstString)
{
// ...
}

// ...

BeadString::BeadString(int numBeads, std::string label_)
: beads(numBeads),
label(label_)
{
// Connect the beads together.
if(numBeads > 1)
{
beads[0].addConnection(1, this); // add a connection to the next
// bead on the string

for(int i(1);i<numBeads-1;++i)
{
beads.addConnection(i+1, this);
beads.addConnection(i-1, this);
}

beads[numBeads-1].addConnection(numBeads-2, this);
}
}

// ...

void Web::addBeadString(int numBeads, std::string label)
{
// Make a new bead string.
BeadString bs(numBeads, label);

// Add it to the list.
beads.push_back(bs); // FAIL! We try to construct a copy of bead
string bs,
// but the connections between beads in the
bead
// string break since the pointers involved
point to
// bead string bs, not the copy!
}

// ...
---

Now I know that we could resolve this by using, say, a list of
pointers to bead strings instead of actual bead strings, and so avoid
the need to make copies of bs, or have a custom copy constructor that
roots through the connections in each bead (perhaps using special
connection accessors on the beads). But is it possible this signals a
fault with the design itself? If so, what would be a better one?
Remember: each bead needs to know what it's connected to. It just
"seems" off, somehow. But I could be wrong.
 
J

Jorgen Grahn

Hi.

I've got this problem. I'm trying to implement a funny kind of "graph"
composed of "beads" which are strung together to form "strings" that
are in turn attached at beads to form the full "graphs". I've got
something like this:
Click to expand...

I haven't read the code, but please read up on data structures and try
to use standard terminology. For example, is there some difference
between the concept of a bead and a node? What's a string and a web?
Is there a reason you put quotes around the word "graph" -- do you
mean to say it's not a graph after all?

/Jorgen
 
M

mike3

I haven't read the code, but please read up on data structures and try
to use standard terminology. For example, is there some difference
between the concept of a bead and a node? What's a string and a web?
Is there a reason you put quotes around the word "graph" -- do you
mean to say it's not a graph after all?
Click to expand...

Yeah, that's why I said it's "weird". Yes, I'm familiar with the
standard
terminology. In this "new" terminology, the beads are like nodes,
which
are then connected together in linear "strings", but the strings are
connected at beads to form webs.

An illustration (use fixed font to view):

b-b-b-b-b-b-b-b-b-b-b-b (String 1)
|
b
| (String 2)
b
|
b-b-b-b-b-b-b-b-b-b-b-b (String 3)

(Three strings with many beads)

Now I suppose one can consider this as just a special case of a
regular graph, with the "b" being nodes and the "-"/"|" as edges,
but I want to store information on the bead, string, and web
levels as opposed to the node (bead), _edge_, and web (graph)
levels, if you get what I mean, and perhaps also the connection
level (which would be the edges, i.e. the "-"/"|"s). The difference
is then really the existence of the string level.
 
J

Jorgen Grahn

Yeah, that's why I said it's "weird". Yes, I'm familiar with the
standard
terminology. In this "new" terminology, the beads are like nodes,
which
are then connected together in linear "strings", but the strings are
connected at beads to form webs.

An illustration (use fixed font to view):

b-b-b-b-b-b-b-b-b-b-b-b (String 1)
|
b
| (String 2)
b
|
b-b-b-b-b-b-b-b-b-b-b-b (String 3)

(Three strings with many beads)

Now I suppose one can consider this as just a special case of a
regular graph, with the "b" being nodes and the "-"/"|" as edges,
but I want to store information on the bead, string, and web
levels as opposed to the node (bead), _edge_, and web (graph)
levels, if you get what I mean, and perhaps also the connection
level (which would be the edges, i.e. the "-"/"|"s). The difference
is then really the existence of the string level.
Click to expand...

Excellent description!

I suppose you don't allow cycles in the graph?

I know to little about graphs (and am too sleepy) but perhaps with the
information above in mind someone else can revisit your code.
Perhaps it's also important what you want to do with the graph, apart
from just representing it.

/Jorgen
 
M

MiB

I would recommend you to stick to established basics, and then add the
extra icing.

For example, you could chose a general graph representation
(substructure), e.g. adjacency matrix, or adjacency lists. Add a
superstructure like your "string" concept on top of that.

There may be also some ambiguity in your model. In your example a
clear cut correspondence of beads to strings is suggested. However,
alternate versions of the same substructure exist, like this:

a-a-a-a-a-a-b-b-b-b-b-b
|
a
|
a
|
c-c-c-c-c-a-a-a-a-a-a-a

I replaced the original b's to illustrate how a different set up of
"strings" map to the same "bead" interconnections. You should
carefully consider if this is OK for the problem you are trying to
solve.

best,

MiB.
 
M

mike3

I would recommend you to stick to established basics, and then add the
extra icing.

For example, you could chose a general graph representation
(substructure), e.g. adjacency matrix, or adjacency lists. Add a
superstructure like your "string" concept on top of that.
Click to expand...

So instead of the current model, go and use one where, e.g. the beads
are linked directly together instead of linking strings, and then
perhaps have some field in each bead that says what string it is part
of,
or something like that?
There may be also some ambiguity in your model. In your example a
clear cut correspondence of beads to strings is suggested. However,
alternate versions of the same substructure exist, like this:

a-a-a-a-a-a-b-b-b-b-b-b
          |
          a
          |
          a
          |
c-c-c-c-c-a-a-a-a-a-a-a

I replaced the original b's to illustrate how a different set up of
"strings" map to the same "bead" interconnections. You should
carefully consider if this is OK for the problem you are trying to
solve.
Click to expand...

Yes, that'd be OK. Then you have 4 strings now (or 3 if the "a"s in
the
downbar are part of the same string). Which could mean different
associated
information for them, etc.
 
M

MiB

On 13 Dez. said:
So instead of the current model, go and use one where, e.g. the beads
are linked directly together instead of linking strings, and then
perhaps have some field in each bead that says what string it is part
of,
or something like that?
Click to expand...

Yes, this looks like a more promising approach to me.

I would like to add, though, a graph structure implemented as node
objects linked by pointers is intuitive because it corresponds so
nicely to what you would draw on paper. However, it is not very well
suited for solving many graph related problems.

While you can traverse the linked graph easily, finding specific nodes
or edges is cumbersome without extra book keeping. Any change to the
graph, like adding/removing nodes or edges, must be reflected in the
book keeping records as well as in the linked structure, destroying
any advantage you may have hoped to gain by the pointers. The boost
graph library recommended by Jeff Flinn in this thread offers more
benign graph representations. As an added plus, it is well-tested code
that lets you focus on the specifics of your problem at hand without
getting hampered by low-level details.

MiB.
 
M

mike3

Yes, this looks like a more promising approach to me.

I would like to add, though, a graph structure implemented as node
objects linked by pointers is intuitive because it corresponds so
nicely to what you would draw on paper. However, it is not very well
suited for solving many graph related problems.

While you can traverse the linked graph easily, finding specific nodes
or edges is cumbersome without extra book keeping.
Click to expand...

Which is something I'd have to do in the application I'm thinking of.
Any change to the
graph, like adding/removing nodes or edges, must be reflected in the
book keeping records as well as in the linked structure, destroying
any advantage you may have hoped to gain by the pointers. The boost
graph library recommended by Jeff Flinn in this thread offers more
benign graph representations. As an added plus, it is well-tested code
that lets you focus on the specifics of your problem at hand without
getting hampered by low-level details.

MiB.
Click to expand...

So then I guess what I should do is have a regular graph class
(perhaps
use the one from Boost) and then make a special "string manager" or
something
that provides the "string" functionality I'm looking for? E.g.:

---
class Graph {
...
};

struct String {
... (just data to define a string, probably a list of node
indices or similar) ...
};

class Web {
private:
Graph graph;
std::vector<String> webStrings;
...
public:
...
addString( <params> );
removeString( <index> );
...
};
---

?

Or string could be a separate class, but that could mean it could be
used
outside a web, in which case there seem to be problems: if you could
use it
on any old accessible graph, then if you go through the graph's add/
delete
node functions (as opposed to the string's), there'd be no guarantees
the
string would still work afterwards. Is that OK? It would seem that to
alleviate
it you'd need more intimate connections between the graph & string
object.
And that's where my troubles appear -- how to do that in a non-"messy"
fashion. What to do? Just use the approach above? Does that "miss" a
layer
of abstraction since string is not its own class and all its stuff is
handled
by Web, and so be bug-inducing?
 
M

MiB

On Dec 13 said:
So then I guess what I should do is have a regular graph class (perhaps
use the one from Boost) and then make a special "string manager" or something
that provides the "string" functionality I'm looking for? E.g.: [..]
Or string could be a separate class, but that could mean it could be used
outside a web, in which case there seem to be problems: if you could use it
on any old accessible graph, then if you go through the graph's add/ delete
node functions (as opposed to the string's), there'd be no guarantees
the string would still work afterwards. Is that OK? It would seem that to
alleviate it you'd need more intimate connections between the graph & string
object.
And that's where my troubles appear -- how to do that in a non-"messy"
fashion. What to do? Just use the approach above? Does that "miss" a layer
of abstraction since string is not its own class and all its stuff is handled
by Web, and so be bug-inducing?
Click to expand...

Notice, you are now at a completely different level of thinking about
your original problem. At first you mixed details of the
implementation, like pointers, into your considerations. Now you focus
on caring about how your classes should interact, i.e. the design
level. I consider this a progress.

In your prototype code you always consider constructing handlers, or
adding members that have class types defined externally to the class
you are setting up. Maybe it could help to review your design not to
consist of classes that manages / contains objects of other classes
exclusively. Instead, use class inheritance where appropriate.

The thing I do most of the time is asking myself, (1) should new class
A *be* a special case of existing class B, or (2) should class A
*have* one or more instances of class B. For the first case, I choose
inheritance, for the latter case members. This simple test is not a
dogma, many times you can do things the other way around just as well
or even better. I tend to get working programs by this approach, so it
can't be all bad.

In your problem, my stomach feeling tells me class Web is a special
case of a general graph. Therefore I believe its a good idea to derive
Web from one of the boost classes and provide its interface to the
public. This gives you the added benefit of all graph algorithms
available from boost immediately working with your class at no extra
cost. Overload any of the methods that need to do stuff special to
your Web class. This should take care of your worries about somebody
calling methods of your base class interface.

"String" is a different issue. A Web *has* strings, so here a book
keeping helper class may be a good approach. If you do not like to
export it outside of Web, just make it an embedded private class.
Maybe you should choose a better name because 'string' has a different
notion for other people that may add confusion.

So a very crunched (no proper C++ !) set up might be:

class Web : public boost::somegraphclass {
private:
class String { ... }; // describes one string in a web
std::vector<String> mystrings; // or other container, the strings
in *this* web
void BookKeepingMethod1();
void BookKeepingMethod2(); // also can wrap these in a handler
class

public:
void MyWebAlgorithm(); // your specialized public interface.
};

best,

MiB.
 
M

mike3

On Dec 13, 9:52 pm, mike3 <[email protected]> wrote:
Click to expand...
Notice, you are now at a completely different level of thinking about
your original problem. At first you mixed details of the
implementation, like pointers, into your considerations. Now you focus
on caring about how your classes should interact, i.e. the design
level. I consider this a progress.

In your prototype code you always consider constructing handlers, or
adding members that have class types defined externally to the class
you are setting up. Maybe it could help to review your design not to
consist of classes that manages / contains objects of other classes
exclusively. Instead, use class inheritance where appropriate.

The thing I do most of the time is asking myself, (1) should new class
A *be* a special case of existing class B, or (2) should class A
*have* one or more instances of class B. For the first case, I choose
inheritance, for the latter case members. This simple test is not a
dogma, many times you can do things the other way around just as well
or even better. I tend to get working programs by this approach, so it
can't be all bad.

In your problem, my stomach feeling tells me class Web is a special
case of a general graph. Therefore I believe its a good idea to derive
Web from one of the boost classes and provide its interface to the
public. This gives you the added benefit of all graph algorithms
available from boost immediately working with your class at no extra
cost. Overload any of the methods that need to do stuff special to
your Web class. This should take care of your worries about somebody
calling methods of your base class interface.

"String" is a different issue. A Web *has* strings, so here a book
keeping helper class may be a good approach. If you do not like to
export it outside of Web, just make it an embedded private class.
Maybe you should choose a better name because 'string' has a different
notion for other people that may add confusion.

So a very crunched (no proper C++ !) set up might be:

class Web : public boost::somegraphclass {
private:
   class String { ... }; // describes one string in a web
   std::vector<String> mystrings; // or other container, the strings
in *this* web
   void BookKeepingMethod1();
   void BookKeepingMethod2(); // also can wrap these in a handler
class

public:
   void MyWebAlgorithm(); // your specialized public interface.

};

best,

 MiB.
Click to expand...

Hmm. However, what if in the Web, we need to get in to the Strings to
change something in them? Like, for example, I want to remove a vertex
from the graph (a "Bead" from before). We could:

1. ground out the base's vertex-routines and demand only string work
(i.e. make them throw or something like that)

but that doesn't seem "good",

2. make string all-public to Web, so that Web can get in and change
its data as needed so as to reflect the changes in the graph (e.g.
if there's pointers (or descriptors as in "boost") to the vertices
comprising the string there, the remove may invalidate them, thus
we need to dive into the string's data to make the necessary
changes
so it stays valid)

but that doesn't seem "good" either. See where my troubles are? What
to
do with this?
 
M

mike3

On Dec 13 said:
I would like to add, though, a graph structure implemented as node
objects linked by pointers is intuitive because it corresponds so
nicely to what you would draw on paper. However, it is not very well
suited for solving many graph related problems.

While you can traverse the linked graph easily, finding specific nodes
or edges is cumbersome without extra book keeping. Any change to the
graph, like adding/removing nodes or edges, must be reflected in the
book keeping records as well as in the linked structure, destroying
any advantage you may have hoped to gain by the pointers. The boost
graph library recommended by Jeff Flinn in this thread offers more
benign graph representations. As an added plus, it is well-tested code
that lets you focus on the specifics of your problem at hand without
getting hampered by low-level details.
Click to expand...

I'm curious about this bit. I thought "adjacency list" was a well-
accepted
kind of graph data structure, and in there you have pointers + book
keeping
("master" list of pointers & pointers in each node). Also, for the
application
I am thinking of, speed is not a concern.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Attempting to implement "weird" kind of graph 4
Weird Behavior with Rays in C and OpenGL 4
Implementing Many Stacks in the Same Program 1
Graph of quadratic function with CanvasRenderingContext2D 2
Character operations in C++ 2
C# MVC Razor page form 0
C# problem 1
How to multiply two matrices of size in using inline assembly in C++ 3

Members online

Total: 74 (members: 2, guests: 72)
Robots: 378

Forum statistics

Threads
473,982
Messages
2,570,189
Members
46,734
Latest member
manin

Latest Threads

Top