Implementing weird kind of graph in C++

Discussion in 'C++' started by mike3, Dec 12, 2011.

  1. mike3

    mike3 Guest

    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.
    mike3, Dec 12, 2011
    #1
    1. Advertising

  2. mike3

    Jorgen Grahn Guest

    On Mon, 2011-12-12, mike3 wrote:
    > 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:


    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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Dec 13, 2011
    #2
    1. Advertising

  3. mike3

    mike3 Guest

    On Dec 12, 5:26 pm, Jorgen Grahn <> wrote:
    > On Mon, 2011-12-12, mike3 wrote:
    > > 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:

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


    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.

    > /Jorgen
    >
    > --
    >   // Jorgen Grahn <grahn@  Oo  o.   .     .
    > \X/     snipabacken.se>   O  o   .
    mike3, Dec 13, 2011
    #3
  4. mike3

    Jorgen Grahn Guest

    On Tue, 2011-12-13, mike3 wrote:
    > On Dec 12, 5:26 pm, Jorgen Grahn <> wrote:
    >> On Mon, 2011-12-12, mike3 wrote:
    >> > 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:

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

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


    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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Dec 13, 2011
    #4
  5. mike3

    MiB Guest

    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.
    MiB, Dec 13, 2011
    #5
  6. mike3

    mike3 Guest

    On Dec 12, 10:16 pm, MiB <> wrote:
    > 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.
    >


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


    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.
    mike3, Dec 13, 2011
    #6
  7. mike3

    Jeff Flinn Guest

    mike3 wrote:
    > On Dec 12, 10:16 pm, MiB <> wrote:
    >> 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.
    >>

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


    See the boost graph library at:
    http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/index.html.

    Jeff
    Jeff Flinn, Dec 13, 2011
    #7
  8. mike3

    MiB Guest

    On 13 Dez., 08:00, mike3 <> wrote:
    [..]
    > 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?


    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.
    MiB, Dec 13, 2011
    #8
  9. mike3

    mike3 Guest

    On Dec 13, 8:56 am, MiB <> wrote:
    > On 13 Dez., 08:00, mike3 <> wrote:
    > [..]
    >
    > > 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?

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


    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.


    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?
    mike3, Dec 13, 2011
    #9
  10. mike3

    MiB Guest

    On Dec 13, 9:52 pm, mike3 <> wrote:
    [..]
    > 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?


    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.
    MiB, Dec 14, 2011
    #10
  11. mike3

    mike3 Guest

    On Dec 13, 5:36 pm, MiB <> wrote:
    > On Dec 13, 9:52 pm, mike3 <> wrote:

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


    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?
    mike3, Dec 14, 2011
    #11
  12. mike3

    mike3 Guest

    On Dec 13, 8:56 am, MiB <> wrote:
    <snip>
    > 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.
    >


    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.
    mike3, Dec 16, 2011
    #12
    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:
    450
    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:
    650
    Dr Ann Huxtable
    Dec 21, 2004
  3. Jef Driesen
    Replies:
    3
    Views:
    2,543
    mlimber
    Jan 24, 2006
  4. mike3
    Replies:
    4
    Views:
    276
    mike3
    Feb 7, 2012
  5. Emilio Mayorga
    Replies:
    6
    Views:
    329
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page