LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-27-2010, 11:28 AM   #1
jamesbon
Member
 
Registered: Jun 2010
Posts: 147

Rep: Reputation: 9
how to define a structure node in graph in a c program


I wanted to implement a graph.By graph I mean to say that I am writing programs for BFS,DFS and other such stuff and want to see them in action.

For this I started writing a program.The first entry point is to define a graph.
I took a pen and paper and made a graph.
Now to be able to code this in C.I defined a structure but I am finding problem in defining this structure.
I looked into Google and came across incidence list and adjacency list representation
http://en.wikipedia.org/wiki/Incidence_list
after understanding that I am not able to understand how do I define my structure that would be a node in graph.

Here is what my graph looks like
Quote:
|-----------31
| |
| 2---4---6---8
| |
--- 5--13-------|
| 19
|---12---27-----|
| | |
----- |
28
This is the above graph the numbers would be what I will give as input but I am not able to understand how do I define a structure for the same.


27 is connected to 28
12 has an edge to itself
31 is connected to 6 and not 2 as you see in question
The formating of above graph in forum is not coming clearly so when I save in quotes/code tags the changes get lost.
Ok here is a pictorial representation


http://www.flickr.com/photos/55167530@N02/5119750360/
 
Old 10-27-2010, 06:05 PM   #2
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Bookworm (Fluxbox WM)
Posts: 1,391
Blog Entries: 54

Rep: Reputation: 360Reputation: 360Reputation: 360Reputation: 360
Quote:
I looked into Google and came across incidence list and adjacency list representation
I would suggest ignoring the "Incidence List" article in wikipedia, which complicates the data structure (my suspicion is that the article was added to promote the book that it references; edge oriented adjacency lists have been around since at least the 1970s).

However, it is worth reading the adjacency list and adjacency matrix articles.

The simplest representation is an array of pairs, where each pair structure contains the vertices of a single edge. This is effectively a list of edges. However, this representation is slow for many applications such as traversals, because it is hard to find the next vertices as you traverse the graph.

An adjacency matrix is a two dimensional array, which contains the connection between each pair of vertices. In other words, each index combination represents two vertices, and the value of the array is the edge cost; vertices that are not connected will have a dummy value at that point of the array (eg 0). An adjacency matrix is fast for some applications (though not for traversal). And for graphs where the number of edges is significantly less than the number of vertices squared, it wastes a lot of storage.

An adjacency list is an array of vertices, where each array entry has a list of other vertices adjacent to that vertex. It is an efficient way of storing all the data, and allows easy traversal of the graph, so it is a reasonable structure for your application.

Your example (undirected) graph:
Code:
|--------------31
|               |
|    2-----4----6-----8
|    |
|----5-----13---\
     |          19
    12-----27---/
           |
           28
For your example, the adjacency list would look like this:
Code:
2: 4, 5
4: 2, 6
5: 2, 12, 13, 31
6: 4, 8, 31
8: 6
12: 5, 27
13: 5, 19
19: 13, 27
27: 12, 19, 28
28: 27
31: 5, 6
and the adjacency matrix like this:
Code:
    2  4  5  6  8 12 13 19 27 28 31
 2     1  1
 4  1        1
 5  1              1  1           1
 6     1        1                 1
 8           1
12        1                 1
13        1              1
19                    1     1
27                 1     1     1
28                          1
31        1  1

Last edited by neonsignal; 10-27-2010 at 06:28 PM.
 
Old 10-28-2010, 04:32 AM   #3
jamesbon
Member
 
Registered: Jun 2010
Posts: 147

Original Poster
Rep: Reputation: 9
I know what an adjacency list is I also know the matrix thing.
I am asking for a data structure some like of struc node {};
thing what do I need to define this struct node as?
 
Old 10-28-2010, 05:05 AM   #4
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Bookworm (Fluxbox WM)
Posts: 1,391
Blog Entries: 54

Rep: Reputation: 360Reputation: 360Reputation: 360Reputation: 360
Quote:
Originally Posted by jamesbon View Post
I am asking for a data structure some like of struc node {}; thing what do I need to define this struct node as?
The main list will be an array of node structures.

The node structure will contain the list of adjacent nodes.

The simplest would be to number the nodes (ie, use integers to index them), which means that the adjacency list will be a list of integers. You could implement this as a pointer to integer (and use malloc to allocate the array of integers) along with a length value.

Or you could implement the list it as a linked list, and the structure would contain a pointer to the head of the list.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ graph / map data structure Galib Programming 3 10-17-2010 08:50 PM
Graph data structure generation options and parametrization hamtavs Programming 1 04-18-2008 03:44 PM
Why define function pointer in a structure? ArthurHuang Programming 4 08-24-2006 12:32 AM
Graph drawing program davholla Linux - General 1 11-21-2004 10:31 AM
Good Gui graph program in linux? tricky_linux Linux - Software 1 02-15-2004 08:54 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:37 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration