[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 239

# graph design suggestions

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
Thunder_scream
2 Solutions

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

Author Commented:
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

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

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

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

Author Commented:
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

Tackle projects and never again get stuck behind a technical roadblock.