Solved

Adding Graphs

Posted on 1999-01-20
8
250 Views
Last Modified: 2010-04-02
I have a struct declared like this:

struct Graphs
{
  double x[100];
  double y[100];
       .
       .
       .
};

Graphs graph[10];
Graphs TotalGraph;

What I want to do now is to Add the 10 graphs to give me the sum in TotalGraph. The problem is however that not all the x-values are the same (but they are ordered from low to high), so you can not simply add the corresponding y-values. At the moment I put all the values in a large array, sort them using qsort, and then use the difference between two subsequent y-values to determine the total y-value at each discrete x-value. Although this works well enough, it's not fast enough.

Any ideas?
0
Comment
Question by:willemnel
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
8 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1184644
>>The problem is however that not all the x-values are the same (but
>>they are ordered from low to high), so you can not simply add
>>the corresponding y-values
???  What is your add algorithm?  Isn't it just add up all the x's to get a total x and add up all the y's to get a total y?
0
 
LVL 1

Author Comment

by:willemnel
ID: 1184645
No. The x-values represent discrete points on the x axis (something like a time axis) that are not the same for all the graphs.

Suppose that the following are (x,y) points on the first graph:

(0,0) (1,2) (3,3) (5,6) (9,4)

and these are (x,y) points on the second graph:

(0,0) (2,3) (3,5) (7,7)

then the TotalGraph will look something like this:

(0,0) (1,2) (2,5) (3,8) (5,11) (7,12) (9,9)

Is this is not clear, I can try to draw a picture and e-mail it
0
 
LVL 22

Accepted Solution

by:
nietod earned 50 total points
ID: 1184646
No problem.  You need to use two indexes.  One is an index into the source graph (the one you are adding on) and the other is the index into the destination graph (the total).
Both indexes start at 0.  Inside a loop compare the two x values that are indexed.  If they are the same, add the y's and increment BOTH indexes.  If the two x's are different.  Don't add and increment the ONLY index associated with the smaller x value.  The loop terminates when either index value goes past the last allowed index (when it is > 99).

Any questions?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:willemnel
ID: 1184647
Yes. I can see how this will work with 2 graphs, but what about 10 or 20? (That's the amount of graphs (varying) I have to use to update the total)  It'll help a lot if you can give some code to illustrate
0
 
LVL 22

Expert Comment

by:nietod
ID: 1184648
I forgot one point.  (maybe I didn't think of it). if a point in the source is not in the destination, then it must be added to the destination.  That is, it would be inserted into the destination's series of points.  Then to make this work you start the total out as a graph that has no points. You add the first one onto it (this should make it a copy of the first one) then you add the 2nd one onto it, then the third and so on.

The function would be like

Add(Graph &D,const Graph &S)
{
   int Di = 0
   int Si = 0;

   while (Si < S.Points)
   {
       if (Di < D.Points)
      {
         double Dx = D.x[Di];
         double Sx = S.x[Si];

         if (Dx == Sx)  // If 2 points have same X.
         {
             D.y[Di] += S.y[Si]; // Add points.
            ++Di;
            ++Si;
         }
         else if (Dx < Sx)  // If destination x is less than source,
         {
             ++Di // Skip this point in the dest.
         }
         else
        {
            // insert S's point Si into D.
            ++Di;
            ++Si;
         }
      }
     else
     {
            // insert S's point Si into D.
            ++Si;
      }
   }
}


I hope that helps.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1184649
Did this help?
0
 
LVL 2

Expert Comment

by:VEngineer
ID: 1184650
Despite all these textbooks representing a graph as a matrix, I think the representation is poor and inflexible (as you are trying to perform a simple task of combining the edges in two graphs).

Although it is slightly more complex than the matrix rep or the adjacency list representation, this is how I like to do my graphs (in pseudocode for now):

class Node {
public:
   Node(string id);  // constructs a node with a name
   string name();    // returns the node name
private:
   string identifier;
}

class Edge {
public:
   Edge(Node *a, Node *b);  // creates an edge from a to b
   string first();  // returns the name of the first node (x)
   string second(); // returns the name of the second node (y)
private:
   Node *x;
   Node *y;
}

class Graph {
public:
   Graph();
   void add_node(string id);
   void add_edge(string a, string b);
   // and so on
private:
   set<Node*> node_set;
   set<Edge*> edge_set;
   map <string, Node*> node_names;
}

void Graph::add_node(string id) {
   Node* new_node = new Node(id);
   node_set.insert(new_node);
   node_names[id] = new_node;
}

void Graph::add_edge(string a, string b)
   Node *first_node = node_names[a];
   Node *second_node = node_names[b];
   Edge *new_edge = new Edge(first_node, second_node);
   edge_set.insert(new_edge);
}

void Graph::combine(Graph g) {
   // all we have to do is do a union on the node and edge sets
}

---

Anyways, this representation follows closer to a mathematical definition of a graph G(V, E) where V is a set of nodes and E is a set of edges.

Let me know if you are interested in more details.




0
 
LVL 1

Author Comment

by:willemnel
ID: 1184651
Thanks for your input VEngineer. I'll accept Nietod's answer, but I like your idea. I'll have a look at it, and if I have any other questions, I'll let you know.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

626 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