Attempting to implement "weird" kind of graph

Discussion in 'C++' started by mike3, Jan 25, 2012.

  1. mike3

    mike3 Guest

    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/3efe9372c1e83eb0/033938a519c276f9?hl=en&lnk=gst&q=%22class+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, Jan 25, 2012
    #1
    1. Advertising

  2. mike3

    mike3 Guest

    On Jan 24, 7:21 pm, mike3 <> wrote:
    > 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?
     
    mike3, Jan 31, 2012
    #2
    1. Advertising

  3. mike3 <> writes:

    > On Jan 24, 7:21 pm, mike3 <> wrote:


    >> 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


    <snip large text>

    > 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.

    --
    Ben.
     
    Ben Bacarisse, Jan 31, 2012
    #3
  4. mike3

    mike3 Guest

    On Jan 31, 5:47 am, Ben Bacarisse <> wrote:
    > mike3 <> writes:
    > > On Jan 24, 7:21 pm, mike3 <> wrote:
    > >> 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

    >
    > <snip large text>
    >
    > > 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.
    >


    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, Jan 31, 2012
    #4
  5. mike3

    mike3 Guest

    On Feb 5, 4:53 am, "Chris Uppal" <-
    THIS.org> wrote:
    > mike3 wrote:
    > > I've been attempting to write a program in C++ that implements the
    > > “weird kind of graph”

    >
    > 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.

    >     -- chris
    >
    > P.S.  My "pretty lame" comment is not intended as a troll for the readers on
    > c.l.c++ -- which I have only just noticed that this is cross-posted to --but
    > is the sincere, and relevant, opionon of a reader of the language-agnostic
    > group comp.programming.
     
    mike3, Feb 7, 2012
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. George Sakkis
    Replies:
    1
    Views:
    477
    Szabolcs Nagy
    Jan 29, 2007
  2. Dr Ann Huxtable

    Missing Graph.h and (Graph.lib) woes - any help

    Dr Ann Huxtable, Dec 21, 2004, in forum: C Programming
    Replies:
    6
    Views:
    673
    Dr Ann Huxtable
    Dec 21, 2004
  3. Jef Driesen
    Replies:
    3
    Views:
    2,619
    mlimber
    Jan 24, 2006
  4. mike3
    Replies:
    11
    Views:
    465
    mike3
    Dec 16, 2011
  5. Emilio Mayorga
    Replies:
    6
    Views:
    380
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page