Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Implementing weird kind of graph in C++

Reply
Thread Tools

Implementing weird kind of graph in C++

 
 
mike3
Guest
Posts: n/a
 
      12-14-2011
On Dec 13, 5:36*pm, MiB <(E-Mail Removed)> wrote:
> On Dec 13, 9:52*pm, mike3 <(E-Mail Removed)> 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?
 
Reply With Quote
 
 
 
 
mike3
Guest
Posts: n/a
 
      12-16-2011
On Dec 13, 8:56*am, MiB <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Attempting to implement "weird" kind of graph mike3 C++ 4 02-07-2012 11:52 PM
[Boost.Graph] graph.vertices property creates new objects George Sakkis Python 1 01-29-2007 11:09 PM
Help with initialization of graph (Boost Graph Library) Jef Driesen C++ 3 01-24-2006 01:44 PM
Missing Graph.h and (Graph.lib) woes - any help Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments