Graphs

This is a discussion on Graphs within the C++ Programming forums, part of the General Programming Boards category; I'm trying to create a graph, and I'm a little confused on how to implement the vertices, edges, and their ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    Graphs

    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
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Edit* - Ok, i got it.
    Thanks
    Last edited by Cpro; 03-31-2008 at 01:09 PM.
    IDE - Visual Studio 2005
    Windows XP Pro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graphs and the STL
    By smitsky in forum C++ Programming
    Replies: 1
    Last Post: 12-04-2004, 06:32 PM
  2. graphs and algorithms
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2004, 02:13 PM
  3. Generate Graphs
    By beet in forum C Programming
    Replies: 6
    Last Post: 08-19-2003, 08:14 PM
  4. graphs
    By cmpcnic1@livjm. in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2003, 07:06 AM
  5. graphs
    By res025ol in forum C++ Programming
    Replies: 0
    Last Post: 03-28-2002, 08:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21