Hi! I deleted my previous post because terms were all wrong and I guess nobody didn''t understand anything about it. Or did even nobody read it. So what I want to do is implement an efficient, flexible data structure to represent graph. Quite a lot demands I think but I wan''t to make it as good as possible. I would like to start from the basics. So what is the general idea when you implement a graph? Floru

Disclaimer:
This is how *I* would go about implementing a graph system for line graphs.

First, a graph consists of an X-axis and a Y-axis. Both the X and Y Axis contains; Minimum, Maximum, Size and Scaling factor.

Second, a graph consists of 1 or more series. Each series represents the values of the points to place for each Category (ie: plotting ages of family members from multiple families a series would represent each family).

IE: Jumpster's Family: {10,20,13,3}; // Series 1
Jumpster's Friend: {32,12,30,2}; // Series 2

        class Axis{  int Size;        // Size in Pixels this axis will take.  int Minimum;     // Minimum value of Axis in Graph  int Maximum;     // Maximum value of Axis in Graph  float Scalar;    // Scalar value (distance between labels).                   // IE: Y-Axis = 0 to 100 -> Scalar 10 would                   // give labels of 0,10,20...100  virtual int ComputePoint( int value ) = 0;  virtual void DrawLabels() = 0;}class XAxis : public Axis{  // Draws the Labels of the XAxis values...  virtual void DrawLabels();  // Returns the X-Pixel coord to place the mark...  virtual int ComputePoint(int value);}class YAxis : public Axis{  // Draws the Labels of the YAxis values...  virtual void DrawLabels();  // Returns the Y-Pixel coord to place the mark...  virtual int ComputePoint(int value);}class Series{  int Values[10]; // Holds 10-values...}class Graph {  Axis* X;  Axis* Y;  Series* Lines[10]; // Can have up to 10-series...  char* iMarks[10] = "0123456789";  // Cycles through each series and plots the graph accordingly.  PlotGraph()  {    X->DrawLabels();    Y->DrawLabels();    for (int i=0; i<10; i++)    {      if (Lines<i>)      {         Series* series = Lines<i>;         for (int j=0; j<10; j++)         {           int x = X->ComputePoint(series[j]);           int y = Y->ComputePoint(series[j]);           // Plot the point at x,y...           PlotPoint(x,y,iMarks[i]); // Left for you to define...         }      }      else break;  // No more series - we're done...    }  };  Graph(int Height, int Width)  {    X = new XAxis();    X->Size = Width;    Y = new YAxis();    Y->Size = Height;  }  ~Graph() { delete X; delete Y; delete [] Series; }}        

Anyway, I think you get the idea. Hope this helps.

Regards,
Jumpster



Edited by - Jumpster on November 7, 2000 11:24:23 AM

I''m a little confused, Floru; there are two kinds of graphs that you could be talking about. One is a graph like for plotting (i.e. an "Excel Spreadsheet Graph"), which Jumpster covered. Then there''s the computer science Graph structure, which is a set of data in multiple linked lists (often the list links are shown visually as going across and up and down the data set, hence the term "graph"). Which were you asking about?

Sorry about the confusion. What I mean is the computer science Graph structure.

Sorry Jumpster, about making you to do such a big job.

Stoffel could you please explain a little bit more specific?

Thanks
Floru

hey Floru, my senior project team is implementing this type of graph structure. our advisor gave us some documents on an existing graphing utility.

maybe we can help eachother out.

i can scan the necessities for datatypes and methods and put it on my site or something, for you to see.

i''d like to know, how are you going to go about implementing the graphing app?

we''re debating between c++, java, opengl, etc.

see, swing is nice for the GUI, but opengl is nice in c++ (standardized and fast) i''d like to hear on what type of stuff you were gonna choose for yours.

a2k

Well, Floru, I just looked up Graph Algorithms in ye olde "Data Structures and Algorithm Analysis in C" text (Weiss). There's about 50 pages on graphs. It all depends on how you want to define paths between nodes, etc., but it looks like the generalized way to go is an adjacency list:
For each vertex, keep a list of all adjacent vertices. This allows you to keep cyclic or acyclic graphs, graphs with two-way, one-way, or a mixture of connections.

A way to implement it would be to have a container (map, list, hash table, whatever) of structures, one for each node in your graph. The structure would contain:
- a reference to this node itself
- a container of all nodes which can be reached directly from this node

So if I had a square-shaped graph, with two-way connections:

A - B|   |C - D 

I could represent it by an adjacency list like the following:
A (B C)
B (A D)
C (A D)
D (B C)

The first column is the entry in the node container, and the entries in parenthesis represent the container of adjacent nodes.

Hope this helps.

Edited by - Stoffel on November 7, 2000 4:11:57 PM

Oh well. I didn''t see the other post so I had no idea.

Regards,
Jumpster

Consider a graph data structure and a tree data structure, which is
very common (e.g. binary trees, etc.):

A tree has a root node and then has children nodes spread out from it.

A graph has no roots, and has no children. Instead, it has neighbors.
One neighbor is connected to another neighbor and another, and etc.

Look up A* algorithm on the web for things that use graph structures.

Pratical uses for searching algorithms like these are maps on the web.
Enter a starting and ending location, and it will map the shortest
route to your destination.

Or how about using for it chess AI. Find the quickest route to defeat
your foe. Many uses.

Ok, this is mostly food for thougt, but think simple here.
You can represent the graph using a linked list with linked lists. ACK! now that did sound a bit wired now didn''t it ?

ok say you have:

A--B--C
| / |
D/----/

whooo doesnt my ascii just rox
You have one list to keep track of the nodes i.e
A, B, C,...
Then A have a list containing all the nodes that it has a connection with in this case A''s list contains B D, B''s list contains C D, and C''s list contains B D. he.
Adding a new point to it is as easy as saying I want a point ''n''
insert it in the first list as a new node. And say I want it to be connected to for example A and update A and n''s lists to reflect that they link each other. The reason to have the data in multiple places is that that way you can have both bidirectional access as well as you can limit it to be oneway.

Hope that helps

The standard template library is another option.