Solved

# graph design suggestions

Posted on 2006-05-14
237 Views

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

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

Cheers!
0
Question by:Thunder_scream

LVL 16

Expert Comment

Hi Thunder_scream,

Your design is fine, its generally called a tree. What do you want to do with it (apart from count the nodes which would be better done while it is being built)? That is generally the driving force for most structures.

Paul
0

LVL 2

Author Comment

I know that for a binary tree the complexity is O(log n) would that be the case here as well? what would my limitations be (I'm so used to program with java/C# that I cant think like this anymore). The purpose of this graph is to learn more about c and what i can do..more or less. I'm probably going to work in a mobile phone company and knowing specifics of C graphics and graph representation would be useful. However this question only focuses on the graph representation. So please give me some constructive arguments of pros and cons of this design
0

LVL 5

Assisted Solution

For finding the number of nodes, you'll have to traverse the graph.

http://en.wikipedia.org/wiki/Breadth-first_search   this is a traversing algorithm, you have details regarding complexity on that page.
http://en.wikipedia.org/wiki/Depth-first_search

Or, you can keep track of the number of nodes you've allocated ;)

I recommend you to get Cormen's book on algorithms, it's the best around http://en.wikipedia.org/wiki/Introduction_to_Algorithms

And about this approach with dynamically allocating the nodes... perhaps if you tell us what do you want to accomplish, we might suggest a better way. In my opinion, this would be useful if you have lots of data to store inside the node.
0

LVL 45

Expert Comment

Last 10 Grades Given        B B A C C B C A B C

You might find this helpful too
http://www.experts-exchange.com/help.jsp#hi73
0

LVL 1

Accepted Solution

I found following  problems in your design
1. How will you put any cost on arcs.
2. For un-directed graphs You need to maintain 2 pointers for each arc.

Alternative design---
--------------------------
Use two types of nodes, one to represent  node other to represent arc.
Use a link list that contains  all node of the garph.
Each node of the above  link list maintains aother link list of all outing going arcs from that  node.
Arc Node will maintain a pointer to the node where this arc is ingoing
This design will remove first problem.
0

LVL 2

Author Comment

I was reading the previous link given by Dragon_Krome. However I came up with a question. What should i do when new nodes are inserted in the desigen given above. (Tree structure I suppose)

I'm not looking to accomplish anything specific yet with my design, just want to freshen up my knowledge.

Cheers!
0

## Featured Post

### Suggested Solutions

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.