[algogeeks] Re: Tree/Graph implementation

2012-06-02 Thread Gene 
You can look at adjacency lists as a way of compressing the rows of
the adjacency matrix. So you can choose instead to compress the
columns into lists. This is a reverse adjacency list. You can also
compress both dimensions by storing row,col - value mappings in a
map (hash table, tree, etc.)

There are other variations on adjacency lists.  The outer list can
be a linked list (single or double), array, or map from node id to
list of adjacent nodes. Same for the inner list, but add the
possiblity of maps where the key is the label on the edge.

Several graph data structures are used for computational geometry:
winged edge, half-edge, quad-edge, and vertex lists, for example.
These support certain query and edit operations in constant time
regardless of vertex degree.

The best choice depends on the operations that must be performed and
their relative frequency. In this choice you are often trading
constant factors of memory usage for speed.


On May 31, 2:06 pm, Mad Coder imamadco...@gmail.com wrote:
 @Gene: Can you tell some other ways of graph representation in case of
 sparse matrix as till now I consider adjacency list as the best method for
 the same.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Tree/Graph implementation

2012-05-29 Thread Gene 
I'm interested to see problems where tree implementation causes a
performance problem.  Example?

Choice of graph data structures is very problem-dependent. An
adjacency matrix will probably be fastest and simplest for dense
graphs.  For sparse ones there are many, many answers.

An efficient way to do n-ary trees (which are usually sparse graphs)
in C:

typedef struct node_s {
 // Use a fixed size array of NODE* if you know
 // the maximum number of children in advance.
 // Here we assume this isn't true.
 struct node_s **children;
 int n_children;
 ...
} NODE;

NODE *make_node(int max_children)
{
  // Allocate nodes in a single array if you know the max
  // number in advance.  Here we assume this isn't true.
  NODE *node = safe_malloc(sizeof *node);
  node-children = safe_malloc(max_children * sizeof *node-children);
  node-n_children = 0;
  return node;
}

void add_child(NODE *parent, NODE *child)
{
  parent-children[parent-n_children++] = child;
}

void walk

On May 29, 6:17 am, prakash y yprakash@gmail.com wrote:
 How to implement complex data structures like trees (with unknown no.of
 subtrees) and graphs efficiently in C/Java?
 I have implemented binary trees in Java as it always contains two nodes.
 But I don't know about graphs.
 I am not able to solve these problems in coding contests because of this.
 Can anyone please suggest me?

 Thanks in advance.
 ~Prakash.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Tree/Graph implementation

2012-05-29 Thread Ashish Goel 
Gene: why do you say that adjacency list is not a good solution for sparse
matrix? what other alternates are you looking at?

Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Tue, May 29, 2012 at 9:09 PM, Gene gene.ress...@gmail.com wrote:

 I'm interested to see problems where tree implementation causes a
 performance problem.  Example?

 Choice of graph data structures is very problem-dependent. An
 adjacency matrix will probably be fastest and simplest for dense
 graphs.  For sparse ones there are many, many answers.

 An efficient way to do n-ary trees (which are usually sparse graphs)
 in C:

 typedef struct node_s {
  // Use a fixed size array of NODE* if you know
  // the maximum number of children in advance.
  // Here we assume this isn't true.
  struct node_s **children;
  int n_children;
  ...
 } NODE;

 NODE *make_node(int max_children)
 {
  // Allocate nodes in a single array if you know the max
  // number in advance.  Here we assume this isn't true.
  NODE *node = safe_malloc(sizeof *node);
  node-children = safe_malloc(max_children * sizeof *node-children);
  node-n_children = 0;
  return node;
 }

 void add_child(NODE *parent, NODE *child)
 {
  parent-children[parent-n_children++] = child;
 }

 void walk

 On May 29, 6:17 am, prakash y yprakash@gmail.com wrote:
  How to implement complex data structures like trees (with unknown no.of
  subtrees) and graphs efficiently in C/Java?
  I have implemented binary trees in Java as it always contains two nodes.
  But I don't know about graphs.
  I am not able to solve these problems in coding contests because of this.
  Can anyone please suggest me?
 
  Thanks in advance.
  ~Prakash.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Tree/Graph implementation

2012-05-29 Thread saurabh singh 
^ A list representation 
consider a graph with 1 million nodes..and at a time only 2  nodes will be
connected...Compare the difference in the two representations...
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Tue, May 29, 2012 at 10:00 PM, Ashish Goel ashg...@gmail.com wrote:

 Gene: why do you say that adjacency list is not a good solution for sparse
 matrix? what other alternates are you looking at?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652



 On Tue, May 29, 2012 at 9:09 PM, Gene gene.ress...@gmail.com wrote:

 I'm interested to see problems where tree implementation causes a
 performance problem.  Example?

 Choice of graph data structures is very problem-dependent. An
 adjacency matrix will probably be fastest and simplest for dense
 graphs.  For sparse ones there are many, many answers.

 An efficient way to do n-ary trees (which are usually sparse graphs)
 in C:

 typedef struct node_s {
  // Use a fixed size array of NODE* if you know
  // the maximum number of children in advance.
  // Here we assume this isn't true.
  struct node_s **children;
  int n_children;
  ...
 } NODE;

 NODE *make_node(int max_children)
 {
  // Allocate nodes in a single array if you know the max
  // number in advance.  Here we assume this isn't true.
  NODE *node = safe_malloc(sizeof *node);
  node-children = safe_malloc(max_children * sizeof *node-children);
  node-n_children = 0;
  return node;
 }

 void add_child(NODE *parent, NODE *child)
 {
  parent-children[parent-n_children++] = child;
 }

 void walk

 On May 29, 6:17 am, prakash y yprakash@gmail.com wrote:
  How to implement complex data structures like trees (with unknown no.of
  subtrees) and graphs efficiently in C/Java?
  I have implemented binary trees in Java as it always contains two nodes.
  But I don't know about graphs.
  I am not able to solve these problems in coding contests because of
 this.
  Can anyone please suggest me?
 
  Thanks in advance.
  ~Prakash.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.