graph design suggestions

Posted on 2006-05-14
Last Modified: 2013-12-03

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

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.

    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
    LVL 5

    Assisted Solution

    For finding the number of nodes, you'll have to traverse the graph.   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

    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.
    LVL 45

    Expert Comment

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

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


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Better Security Awareness With Threat Intelligence

    See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

    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  To view more iPhone tutorials, visit 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.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

    761 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now