Attempting to implement "weird" kind of graph

[mike3]

Hi.

I've been attempting to write a program in C++ that implements the
“weird kind of graph” I discussed in this thread:

http://groups.google.com/group/comp...033938a519c276f9?hl=en&lnk=gst&q="class+Bead+{%22+%2Bmike3#033938a519c276f9

and am wondering if how I've done it is a good idea or not. I was
following on the idea to use a conventional graph to underlie it, with
the “strings” of nodes implemented on top. So what I did was the
following:

1. There is a class “Web” which contains the strings, and has members
that allow for the adding, removing, and accessing of the stored
strings. It also contains a graph, on top of which the strings are
laid.
2. The strings are represented in a private member class of Web, which
contains among other things a list of iterators pointing to the nodes
in the graph that make up the string, as well as the string's ID code,
which is used to tag the string and also to identify the nodes in the
graph.
3. When a new string object is constructed (happens inside Web), the
constructor adds nodes into the graph (passed as argument) for the
string, and each node contains the unique ID code as a tag. The ID
codes are also passed as an argument, and Web keeps track to make sure
no collisions occur. ID codes are passed by the user of Web, so that
strings can be accessed by indicating the ID code (as there are two
access options: index and ID code, with ID code slower than direct
access by string index due to lookup, but we don't expect there to be
a huge volume of strings on a Web anyways, and it is robust against
string deletions which is why it's included. And collisions are
prevented by seeing if the ID code is already used – if it is, then
it's rejected on new string creation.).
4. When a string is removed, the destructor for the string object
removes the nodes. After removing a string, then all the other strings
(which are kept in a list in the web) must be updated (via a special
member function) to reset their iterators since the iterators are
invalidated when nodes are removed from the graph.

My questions relate to those internal details: namely, is it a good
idea to implement this where the constructor for the string object
creates nodes in the graph and the destructor then deletes them? As
what if we need to make a copy of that string object? This would also
seem to create another problem, since if a copy is made then its nodes
will have the same ID code, and that will clash when we go to update
on node removal. Would it be OK to just say not to pass string objects
by value (as that's my concern insofar as making copies goes)?

Also, is there any way by which the update step could be eliminated,
apart from using a graph whose iterators do not invalidate when nodes
are removed or is that otherwise an inevitable requirement? That part
is not so essential since this is not a performance-critical piece of
code.

Finally, would it be a good idea to perhaps separate the ID code used
to identify the string from the one used to identify the nodes, and
generate the one to identify nodes internally to the string object by
some approach (like have some unique-identifier approach or something,
with, say, 64-bit super-long ID codes that will never get exhausted in
any feasible amount of time? (it'd take 7 months to exhaust it at a
rate of a trillion creations per second which will never happen in
this program – is it a good idea to count on that never happening?
Personally, I'd think so, but I just want to be sure.))? This would
seem to have the advantage of allowing the string class to mind its
own business, so the web doesn't have to babysit it and its node-
discrimination abilities.

These questions are because I'm not entirely sure what would be a
“Good Design” for this, although what I have does seem to _work_, it's
just that it “feels” messy somehow.

 

[mike3]

Hi.

I've been attempting to write a program in C++ that implements the
“weird kind of graph” I discussed in this thread:

http://groups.google.com/group/comp.lang.c++/browse_thread/thread/3ef...{%22+%2Bmike3#033938a519c276f9

and am wondering if how I've done it is a good idea or not. I was
following on the idea to use a conventional graph to underlie it, with
the “strings” of nodes implemented on top. So what I did was the
following:

1. There is a class “Web” which contains the strings, and has members
that allow for the adding, removing, and accessing of the stored
strings. It also contains a graph, on top of which the strings are
laid.
2. The strings are represented in a private member class of Web, which
contains among other things a list of iterators pointing to the nodes
in the graph that make up the string, as well as the string's ID code,
which is used to tag the string and also to identify the nodes in the
graph.
3. When a new string object is constructed (happens inside Web), the
constructor adds nodes into the graph (passed as argument) for the
string, and each node contains the unique ID code as a tag. The ID
codes are also passed as an argument, and Web keeps track to make sure
no collisions occur. ID codes are passed by the user of Web, so that
strings can be accessed by indicating the ID code (as there are two
access options: index and ID code, with ID code slower than direct
access by string index due to lookup, but we don't expect there to be
a huge volume of strings on a Web anyways, and it is robust against
string deletions which is why it's included. And collisions are
prevented by seeing if the ID code is already used – if it is, then
it's rejected on new string creation.).
4. When a string is removed, the destructor for the string object
removes the nodes. After removing a string, then all the other strings
(which are kept in a list in the web) must be updated (via a special
member function) to reset their iterators since the iterators are
invalidated when nodes are removed from the graph.

My questions relate to those internal details: namely, is it a good
idea to implement this where the constructor for the string object
creates nodes in the graph and the destructor then deletes them? As
what if we need to make a copy of that string object? This would also
seem to create another problem, since if a copy is made then its nodes
will have the same ID code, and that will clash when we go to update
on node removal. Would it be OK to just say not to pass string objects
by value (as that's my concern insofar as making copies goes)?

Also, is there any way by which the update step could be eliminated,
apart from using a graph whose iterators do not invalidate when nodes
are removed or is that otherwise an inevitable requirement? That part
is not so essential since this is not a performance-critical piece of
code.

Finally, would it be a good idea to perhaps separate the ID code used
to identify the string from the one used to identify the nodes, and
generate the one to identify nodes internally to the string object by
some approach (like have some unique-identifier approach or something,
with, say, 64-bit super-long ID codes that will never get exhausted in
any feasible amount of time? (it'd take 7 months to exhaust it at a
rate of a trillion creations per second which will never happen in
this program – is it a good idea to count on that never happening?
Personally, I'd think so, but I just want to be sure.))? This would
seem to have the advantage of allowing the string class to mind its
own business, so the web doesn't have to babysit it and its node-
discrimination abilities.

These questions are because I'm not entirely sure what would be a
“Good Design” for this, although what I have does seem to _work_, it's
just that it “feels” messy somehow.

Any responses?

 

[Ben Bacarisse]

Any responses?

Just speaking for myself... (a) I find Google's interface to Usenet so
tedious that I don't usually follow such links. (b) As a programmer, I
don't find algorithms and data structures explained in text easy to
follow -- I'd respond better to code snippets or pseudo-code. (c) data
structures have to evaluated against the algorithms you want to apply to
them and I did not get a sense of what you want to do with these weird
graphs.

These three factors let me with nothing to say.

 

[mike3]

Just speaking for myself... (a) I find Google's interface to Usenet so
tedious that I don't usually follow such links.  (b) As a programmer, I
don't find algorithms and data structures explained in text easy to
follow -- I'd respond better to code snippets or pseudo-code.  (c) data
structures have to evaluated against the algorithms you want to apply to
them and I did not get a sense of what you want to do with these weird
graphs.

These three factors let me with nothing to say.

OK, then, here goes. Hopefully I've made the issues and usage more
clear.

What I'm trying to represent is a "web of levels" for a game. To
visualize
this, you can use the following: consider a string of beads, each bead
linked to the next by a chain segment. These strings form what I call
the
"branches" of the web, with the individual beads being levels and the
chain segments being connections between levels. Now, these branches
can
be linked by chain segments themselves, and that forms the web. As can
be
seen, this is essentially a graph: beads are nodes, chain segments are
edges. (In my implementation, there are actually _two_ directed edges
in
a chain segment, to represent portals going one or the other way from
the
levels in question.) But there's the additional structure of the
branches
on top. Thus, "weird" kind of graph. And that's where my problem comes
in:
trying to figure out just how to implement that.

On the thread, it was suggested I use an ordinary graph type to
represent
it, and add the branch structure on top somehow. (One even suggested
to
take a graph type and make a derived class from it.) Makes sense,
since
it is a kind of graph, after all.

But that last bit is the rub: how to implement that branch structure.
I
did it as mentioned in the OP. Now, here's a code segment for the
class
definition I've got, if it'll help any, at the bottom. I can't give
the
full implementation as it's too long to put in a post. I suppose I
could
email you the code snippet if you want.

Now, the troubles (partially revised) (and I have to use text to give
explanations!):

1. I use a class "LevelBranch" to represent the branches, that stores
its nodes in a passed-to graph. Is this a good idea? After all, you
can
dink with the branch directly by dinking with the nodes in the graph
structure, without going through the branch's interface. Although,
LevelBranch is only used inside LevelWeb.

2. When such a branch object is created, the constructor adds new
nodes
in the graph and the destructor then deletes them. Is this the usual
way
this'd be done? To me, it makes sense, but the trouble here is this
thing
is an overlay on the graph, thus why I feel iffy: we could also
construct
the nodes outside, and then apply the branch as an overlay on top of
them.
Which one is better? The destroy- nodes-on-destructor thing is iffy
because we may try constructing copies of the branch object to pass by
value, and when temp copies get destroyed, trouble. Right now, I just
arbit
that you shouldn't pass it by value. Is that OK to make those kind of
arbitrary "user-must- understand" restrictions? Not that it matters
much,
since the way this is done now, the branch is a private buried
inside the LevelWeb.

3. And speaking of that last bit, I find myself duplicating certain
member
functions: e.g. there is a "retrieveMap" function in both LevelBranch
and
LevelWeb, and the one in LevelWeb calls the one in LevelBranch. Is
there a
way to eliminate that? I thought of a special "accessBranch" function
(which may mean we need to make LevelBranch public) that would return
a
reference to the branch in question, and then we can call
LevelBranch's
members right there, but that raises the possibility of someone doing
something like:

web.accessBranch(5) = LevelWeb::LevelBranch(<blah>);

BAD!

4. The way LevelBranch is implemented right now, as you can see, is
that
it contains a list of iterators to the nodes in the graph. The problem
is
that with this kind of graph, these iterators are rendered invalid by
deletion. Thus, when we destroy a LevelBranch, all the others on that
graph lose their iterators and those iterators need to be re-updated
again
by a special "recalibrate()" call. However, that means that wherever
we
get rid of LevelBranches, we'd better be sure to have access to ALL of
those on the graph so we can reset them. This isn't a problem, of
course,
in the level web implementation, because we do -- they're all there in
the
branch array. But the problem is this "feels" wrong, and I'm not sure
what
to do. The iterators are going to get invalidated, they are going to
HAVE
to be updated. Unless we should just switch to a different kind of
graph
implementation? E.g. like how if we used Boost's graph we could have a
graph that can use an std::list for its vertex list. This kills random
access to the nodes, though with a pre-stored grid of iterators, this
isn't really a problem here.

5. How to identify the nodes, so that the branch knows which nodes
belong to it upon recalibration. Currently, I have it so that when
a branch is created, the user specifies a branch ID code for that
branch.
These ID codes are meant to be user-specifiable since they're there
to easily tag branches for later access in an index-independent
fashion
(so they survive branch deletions while indices do not). Now, I'm
going to
have a mechanism that ensures these codes are unique (the web
remembers
which IDs have been used so it can ensure that new IDs don't clash),
though
that isn't implemented in the current snippet, as I'm still testing
the
thing, but I want to know if this approach is good before I finish it
out
or I should just pitch it. But that delegates the responsibility of
making
sure IDs are unique to the Web, yet it "feels" like it should be a
feature
of Branch. So, I wondered if I should use something else, like a
unique-ID
counter, inside Branch that specifies special "node ID" codes distinct
from
the user-passed branch IDs.

What should I do about these?

--- Code snippet ---
/* Level web, which stores a complete collection of levels
representing
* a single game location.
*/
class LevelWeb {
private:
/* Level element. This is used to form the nodes of the level web's
graph. */
class LevelElement {
private:
int branchID; /* ID code of branch this level
belongs
* to.
*/
int levelNumber; /* Level number of this level in
its
* associated branch.
*/
LevelGenerator *levelGenerator; /* Level generator used to
generate
* this level.
*/
bool isGenerated; /* Flag indicating whether this
level
* has been generated.
*/
std::string fileName; /* Filename of file to store map
in */
public:
LevelElement(); /* Default constructor */
LevelElement(int branchID_, int levelNumber_,
LevelGenerator *levelGenerator_,
std::string fileName_); /* Construct to specified parameters */
~LevelElement(); /* Destructor */
int getBranchID(); /* Get this level's branch ID
code */
int getLevelNumber(); /* Get this level's level number
*/
void setLevelNumber(int); /* Set this level's level number
*/
bool isLevelGenerated(); /* Returns whether this level has
been
* generated.
*/
LevelMap *retrieveMap(); /* Retrieve the level map.
Generates
* the map if it's not already generated
* or there's no map stored.
*/
CcmbsError saveMap(LevelMap &lm); /* Save a level map to the file
*/
};

/* Level connection data. This is stored in the graph's edges. */
struct LevelConnectionData {
PortalType portalType; /* Type of portal used for this
* connection.
*/

/* Constructors */
LevelConnectionData() : portalType(PORTAL_UPSTAIRS)
{}
LevelConnectionData(PortalType portalType_) :
portalType(portalType_)
{}
};

/* Graph data types */
typedef Graph<LevelElement, LevelConnectionData> WebGraph;
typedef Graph<LevelElement, LevelConnectionData>::NodeIterator
WebGraphNodeIterator;
typedef Graph<LevelElement, LevelConnectionData>::EdgeIterator
WebGraphEdgeIterator;

/* Level branch. The web is composed of branches, linked together in
* the underlying graph.
*/
class LevelBranch {
private:
int parentWebID; /* Parent web ID code */
int branchID; /* Branch ID code. Must be unique
* for each branch in the web.
* Used to identify the branch
* _and_ to tag the nodes in the
* graph.
*/
std::string branchAbbrev; /* Abbreviated description of
this
* branch.
*/
std::string branchDescriptionText; /* Text description of this
branch. */
WebGraph *parentGraph; /* Graph containing the nodes
comprising
* the branch.
*/
std::vector<WebGraphNodeIterator> nodes; /* Graph nodes containing
the
* levels in the branch.
*/
public:
LevelBranch(); /* Default constructor */
LevelBranch(int parentWebID_, int branchID_,
std::string branchAbbrev_,
std::string branchDescriptionText_,
WebGraph *parentGraph_,
LevelGenerator *levelGenerator,
PortalType fwdPortalType,
PortalType revPortalType,
std::size_t numLevels); /* Construct to specified parameters */
~LevelBranch(); /* Destructor */
int getBranchID(); /* Get branch ID */
std::size_t getNumLevels(); /* Get number of levels in this
branch */
std::string getAbbrev(); /* Get abbreviated description of
this
* branch
*/
std::string getDescriptionText(); /* Get branch description text
*/
bool isLevelGenerated(std::size_t which); /* Returns whether a
given level has
* been generated.
*/
LevelMap *retrieveMap(std::size_t which); /* Retrieve a level map
from the
* branch
*/
CcmbsError connectTo(LevelBranch &dstBranch,
PortalType portalType,
std::size_t srcLevelNum,
std::size_t dstLevelNum); /* Connect this branch one-way to
* another branch.
*/
void recalibrate(); /* Recalibrate this branch to the
* parent graph. Necessary after
* removing nodes from the parent
* graph (or any other operation that
* invalidates graph iterators).
*/
};

int webID; /* Web ID code */
std::string webAbbrev; /* Abbreviated description of
this web */
std::string webDescriptionText; /* Text description of this web.
*/
WebGraph graph; /* The underlying graph
containing all
* the level data.
*/
std::vector<LevelBranch *> branches; /* The level branches, which
are defined
* on the graph.
*/

/* Routines defined in levelmgmt.cpp */
std::size_t searchForBranch(int branchID); /* Private member:
searches for a
* level branch with a given ID code
* and returns its index (or -1 if
* no branch found)
*/
public:
/* Routines defined in levelmgmt.cpp */
LevelWeb(); /* Default constructor */
LevelWeb(int webID_,
std::string webAbbrev_,
std::string webDescriptionText_); /* Construct with
specified parameters */
~LevelWeb(); /* Destructor */
void addBranch(int branchID,
std::string branchAbbrev,
std::string branchDescriptionText,
LevelGenerator *levelGenerator,
PortalType fwdPortalType,
PortalType revPortalType,
std::size_t numLevels); /* Add a new level branch to this web. */
CcmbsError removeBranch(std::size_t branchIdx); /* Remove a level
branch from the
* web.
*/
CcmbsError removeBranchByID(int branchID); /* Remove a level branch
indicated by
* its ID code.
*/
CcmbsError connectBranches(std::size_t branchIdx1,
std::size_t branchIdx2,
std::size_t levelNum1,
std::size_t levelNum2,
PortalType fwdPortalType,
PortalType revPortalType); /* Connect two level
* branches
* together.
*/
CcmbsError connectBranchesByID(int branchID1, int branchID2,
std::size_t levelNum1,
std::size_t levelNum2,
PortalType fwdPortalType,
PortalType revPortalType); /* Connect two level
* branches,
* indicated by
* their ID codes.
*/
LevelMap *retrieveMap(std::size_t branchIdx, std::size_t levelNum); /
* Retrieve a level map. */
LevelMap *retrieveMapByID(int branchID, std::size_t levelNum); /*
Retrieve a level map
* with branch indicated by
* its ID code.
*/
};
---

 

[mike3]

Not too hopeful that this'll help, but here goes anyway...

I get the impression that you're all snarled-up in the mechanics of C++
programming, rather than thinking about the objects/roles/operations thatare
appropriate to your target domain.  If you start talking about "constructors",
"destructors", "iterators", before you've really decided what your objects are
going to /do/ then I think that's a bad sign -- you are thinking about how you
are going to represent something in a concrete (and pretty lame) language, C++,
before you've thought about /what/ you want to represent.

I haven't really followed the ins and outs of your discussion on this thread,
and in the original one of c.l.c++, but it seems to me that you have:

    A Graph (aka Web)

    which is made of Strings

    each of which is made of a sequence of Nodes.

    Strings connect to other Strings at a Node.

    Each node is part of exactly one String and has a well-defined position
(index) on that String.

    Each String has exactly two endpoints which are nodes on other Strings.

Well, a string doesn't need its endpoints to be on other strings. It
can
have "free-floating" ends. Strings can connect to other strings at
arbitrary
points, not just end-points.

Some questions:

    Can Strings be of zero length (ie no "internal" nodes, just the endpoints
which are on other Strings)?

No. There would then be no place to connect to another string.

    Do you need to associate data with the fact that one string terminates in
another one?

Not sure what you mean by this exactly, but no.

    Do you need to associate data with the fact that two "internal" nodes are
adjacent on their owining String?

Not anything other than the level numbers.

    If you delete a node which is the endpoint of a String, what happens to
that String.

It loses connection with whatever was connected to that point?

    More generally, do you need to modify the structure once it has been
created ?

Perhaps.

    Do you need "fast" graph-theoretic operations (mu guess would be no).

Fast accessing would be nice. But I don't think operations would
overall
be a huge performance issue because the graphs are not used in
anything
performance-critical.

    And so on and so on...

Regardless of the specific answers to the questions, there is a
straight-forward data-structure here (or if may become complicated if youhave
stringent performance constraints).  So my ultimate question is "why not
program it like that ?"  No "node ID's", no "node indexes" (unless yourdomain
needs them -- which I doubt).  Represent Graphs by instances of class Graph,
Strings by instances of class String (in some non-std namespace ;-), and Nodes
by instances of class Node...

As they say, the devil is in the details. All the "node IDs" and so
forth crop
up when considering things like the fact that the graph invalidates
its iterators.
It _looks_ straightforward, but when you realize that a delete will
screw the
iterators in the Strings, that the Strings use to point to their
constituent nodes,
then the problems start popping up.