create a linked list of nodes

[Espresso]

Hi everyone!

I need to implement a linked list for representing a (planar) graph with the particularity that nodes can only be added and not removed. After implementing this list, I need also an adjacency list to get all the neighbors of a selected node. I also want to add and remove edges between two selected nodes.

I want to make a list of lists. So a list of nodes in which every node has a list of pointers to its adjacent nodes. I prefer to use the STL container List. Using the std::list

My input is the number of nodes. After I know how many node are in my Graph, I assign randomly a couple of neighbors to every node. Next I want to push this info (all the nodes and there connected neighbors) in an adjacency list.

Should I put my all my info first in an array and then in a adjacency list, OR is is possible to put this info directly in an adjacency list???

What is the best way to do this??

Hope someone can help me!

Greetz E

[kbw]

You're off to a good start. Your use of the list isn't incorrect per say. But there's more to your problem than lists.

Vertex looks ok, except you don't initialise the member variable startVertex.

I understand Vertexarray. But you may want to rethink it.
1. What does it represent? The description of your assignment doesn't mention Vertexarray. It's helpful if you define things in your program that represent concepts in the assignment.
2. Once you've decided what it is, you may realise that representing it with an array of 10000 Vertix(es) may not be optimal.

It may be useful to do it on paper first. That way you'll be clear on what the items and lists are and what to do with them. I realise this is all very vague, but I think you need to step back a bit.

[Espresso]

I can't make it work yet.

I think it's better to start with just a basic linked list of nodes without the properties (coordinates) of the vertices and then also implement a list of adjacency nodes.

I'm trying to make a list of lists. Like this example: http://www.pagebox.net/graph.html#toc3

There are a lot of examples on the net of adjacency list. But the most of them use selfmade structures like this:

struct Node;       // pre-delcare

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

struct Node
{
    int data;
    std::vector<Edge*> ConnectionList

};

When I use std::list from the Standard Template Library, I don't need these kind of structures right?? With the STL in C++ I can add and removing nodes, without the use of structures??

[Espresso]

Thanks kbw!

I just read your reaction. I think I don't need the vertexarray at all, but i didn't know how to get the vertices in the list...

I'm going to try something right now...I'll post it, when I'm finished.

Thanks for your support!
Gr. E

[Espresso]

Ok, I defined a startingvertex, but why is this necessary? Isn't the first element in the list, also the startingvertex?

Now, the list excists of only integers. Is it better to replace these integers, with my defined Vertex from the class Vertex??

like this:
list<int> node_list;
could be:
list<Vertex> node_list;

some integers in a list...??

[kbw]

I think we're agreed that you need a collection of vertices, but one way to think about it is as follows.

You're really interested in Graphs. A graph's boundary is defined by an ordered set of vertices (which you already have) that form edges.

Graphs can be added/merged together along an edge. When this happens, you get a new (larger) Graph, which has the same outline of the Graphs that make it up, but with the common edges (vertices) removed.

The VertexArray you had before was an ordered set of vertices, but nothing else. Plus once you put vertices in it, it didn't know how many vertices it had. You need something that does a bit more.
1. It needs to be able to store an ordered set of Vertex.
2. It needs to know how many entries it has.
3. You need to define an Add funtion that merges two Graphs. The function should work out what the common edge(s) are and remove them, producing a new Graph with the correct vertices.

You don't need to represent edges seperately, they're inferred from the vertices.

Does this help?

[Espresso]

Hi kbw,

I don't understand it exactly. When I have an adjacency list, then my vertices are already in an orderd set, is this correct?

You say, I need to define an Add function that merges two Graphs, but I could use the member function "list::insert" to add a vertex, right?
After adding this vertex I can draw the graph using the new adjacency list.


Making a step back:
My input is a number of nodes. After I know how many node are in my Graph, I assign randomly a couple of neighbors to every node. Next I want to push this info (all the nodes and there connected neighbors) in an adjacency list.

Should I put all the info first in an array and then in a adjacency list, OR is is possible to put this info directly in an adjacency list???

For example: input = 5;
Then I make a linked list of 5 members.
After that I randomly assign a couple of neighbors to each node and this I merge (somehow) into my linked list of 5 members??

Could this be done?