Adjacency Matrix and Linked lists

[DemonGal711]

Okay, I have to store an adjacency matrix for a graph problem I'm doing. Let's use this picture to explain it right now. Click here I figured, I'm use a linked list to store it where each node uses the struct

struct Node
{   char item;
    Node* vertex;
    Node* next; };

Where item would be either A, B, C, D; vertex would point to another list that said what each pointed to (i.e. In the node A, there would be a B and C in the vertex list), and the next would point to the next item.

The list that vertex pointed to would use this struct.

struct VNode
{    char item;
     int val;
     VNode* next; };

To put it into a visual sense, this is what my picture came out to be. Click here

When the program reads it, it should find the vertex it's in (say A), go into the vertex list, and look at the values there to figure out which is the lowest (hence why I designed it that way).

Now, I'm not sure if this is the best way to handle it or not, but I'm not told how many I'll need and I don't know vectors yet so this is what I'm trying.

My question is that am I gonna have to use two list classes to do that? My concern is when it hits the destructor that it's not going to deallocate the memory in the list that vertex points to. The two list idea should get rid of that (I think) but it seems like a lot to make two separate list classes just to run on program. Any suggestions?

[MattEvans]

You don't imply any memory management in the description of the problem: there's no necessity that the nodes/lists even be allocated with new, e.g.:

Node a, b;
a.next = &b;

You wouldn't want any automatic delete to occur in this case, since you never call new ( a and b will be correctly de-allocated when they leave scope). If you can get away with allocating everything you need up-front and then deleting it when its no longer needed (or by not calling new atall as above), then do it that way.

If you must assume that one object 'owns' another, and your sure that all objects are allocated with new, then have have node's destructor delete the node pointed to as 'next' and its own vertex list node, and have each vertex list node delete its 'next' vertex node on destruction. Then call delete on only the first node. That is assuming that any given VNode is only reachable from a single Node, is that a correct assumption?

but it seems like a lot to make two separate list classes just to run on program.

This is why we generally use std::list / std::vector / etc.

[StuXYZ]

First off. What do you want to do about multiple edges? The problem you have is that link-lists are very specialized graphs, in which they connected linearly as A-B-C-D.

So do define topographic graph in the sense of your diagram, you are going to have to add some additional linkage to the program.
There are many ways of doing this:

Maybe define an edge + a vertex. Not that each edge can only
connect two vertex.

struct Node;         // Pre-declare

struct Edge
{
   int cost;
   Node* A;
   Node* B;
};

struct Node
{
   int data;
   std::vector<Edge*> ConnectionList;   // this can be an array etc
};

Note that each vertex (node) can connect to any other node in multiple ways e.g. a simple two node graph A B , could have two routes from A-B and even a route A-A. hence Node A would have 3 edges. (and Node B would have 2).

Once you have separated Node from Edge, most things are relatively straightforward. However, the next "interesting" problem will come when you need to define a Loop class, (one which records a cyclic loop). or a Route class, but you don't need it for this problem.

So now make those two structures proper classes, add copy/assignment etc.
Produce a container for all of them and be come up with a simple plan to do memory management. That should be all you need for a while.

Finally, I use integer cost (for the edge) and integer value for the node. In normal graphs, this information can be much more sophisticated, so if you need to change it to something else.

[DemonGal711]

Okay, I hadn't looked at this for a while, but this is what I had come up with. I might try what StuXYZ said but I want to know if anyone can help with what I came up with.

I attempted to put a list within a list. Apparently the coding looks right but it just stops during the run time. And if I try to use the Print(); funtion, that makes the program close. Any help?

[MosaicFuneral]

And if I try to use the Print(); funtion, that makes the program close. Any help?

What Print() function?

[DemonGal711]

Nevermind, I had to switch a few things to get it to work out.