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

  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 239
  • Last Modified:

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

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

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

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.
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

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

You might find this helpful too
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.
Thunder_screamAuthor 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.


Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

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