Graphs

**Cpro** · 03-30-2008

I'm trying to create a graph, and I'm a little confused on how to implement the vertices, edges, and their pointers. So, I'm following the adjacency-list model where it is similar to a hash table. The vertices are stored in an array and point to their edges that are stored in linked lists. Here is where I'm a little confused.
From my understanding, instead of a vertex pointing to the next vertex, it points to an edge, and this edge points to another vertex. If it is undirected, it also points back to the original vertex.
Now, the way it is stored in the hash table, the vertex points to an edge, which points to another edge, and so on, with no previous pointers.
Here is my code for the vertices and edges:

Code:

struct edge
{
	edge() : weight(1) {};
	int target;
	string label;
	int weight;

	edge *nextEdge;
};

struct vertex
{
	int id;
	string label;

	int edgeCount;

	edge *next;
};

So, if i read in a new vertex. I create a new vertex with "new vertex". Then, when I read a new edge, i set "edge *next" to point to the new edge. When i create the edge, i set the target to the vertex it points to. If i read in another edge for that vertex, the previous edge's "nextEdge" points to the next edge. So, "int target" points to the vertex the edge is pointing to. Am i on the right track here? And, how do i differentiate between a directed edge and an undirected edge? I was thinking about adding an "int source" in to edge, and have source be Null if it is directed, and set it to the vertex number if it is undirected. This is probably the wrong way to do it. Or maybe i should be using pointers?

Any help is appreciated.
Thanks

**tabstop** · 03-30-2008

I'm thinking you want to separate the "edge" from the concept of "list of edges". For example, you might have

Code:

struct Edge {
    Vertex *from_vertex;  //for digraph
    Vertex *to_vertex;
    int weight;
}

Then you can make a list of Edges (using std::set or std::list or your own struct EdgeList if you want) (edit: std::set seems like too much work) for each Vertex (std::map seems like the obvious thing, or if your vertices are numbered a plain array of EdgeLists would work too).

Then when you read in an edge, you would create an Edge and add it to the appropriate EdgeList(s).

Also, if you have a digraph technically you don't have undirected edges. You can have two edges that go between the same vertices in different directions, though.

**Cpro** · 03-30-2008

Edit* - Ok, i got it.
Thanks

Thread: Graphs

Thread Tools

Search Thread

Display

Graphs

Similar Threads

Graphs and the STL

graphs and algorithms

Generate Graphs

graphs

graphs