graph design suggestions
Posted on 2006-05-14
I have some thought in my mind regarding the design of a graph. I have yet not started coding it and would like some feedback on it. So consider the following, rather limited, design of a (directed) graph: nodes in the graph are instances of node objects, and arcs are pointers (of type node*) between the objects. Each node object holds a container of some sort (e.g. an array of type node**), which in turn stores the node’s outgoing arcs. There exists a special non-arc global pointer to the node created first, so as to provide a handle to the
Now I would like to know the pros and cons of this design, if a math guy could figure out the time complexity for finding the number of nodes in the graph, or do a through reasoning (just to see if this is a feasible solution). Forinstance what should I do when inserting new nodes...etc. Can someone think of an alternative representation that overcomes the problems with my design (which I'm sure to be plenty).