Thread: Help with Graphs

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    16

    Help with Graphs

    I am supposed to create a weighted directed graph and implement a variety of functions for this graph. Creating a directed graph, Depth first search, Breadth first search, adding edges, removing edges, telling if there is an edge between two vertexes, adding vertexes, removing vertexes, etc. My problem is that in class we were taught how these things worked in theory being drawn on paper, but we were never taught the slightest thing about implementing them.

    I am supposed to use a vector to store the vertices in the graph and use the adjacency list representation for edges in the graph.

    there is a function called weightedGraph(Costtype none) that is supposed to create a directed graph giving all edges a weight of none.

    How do i do this?

    also how do i implement the addedge function? it accepts two vertexes (to go from one vertex to the next) and it also accepts a cost for the edge.

    please help I am clueless on how to implement this stuff. Any info would help. (helping me conceptualize it or anything)

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Well I assume you arent given a "Vertex" class or anything, so thats where you would start I imagine. A simple "struct Vertex" is probably good enough--it needs two fields, the vertex it is connected with, and the cost of that edge. So something like this should be ok (the syntax might be incorrect, because I dont remember the syntax--but thats a minor detail)
    Code:
    struct Vertex
    {
      int vertex;
      int cost
    }
    Overall, the struct might be a "vector" of "linked lists" of "Vertex"s. Each element in the root container "vector" contains a list of vertices, which is your adjacency list.

    Say we had a small direct weighted graph and it is represented as a triple (v1, v2, w) where v1 is a vertex that goes to v2 with cost w. Say we have: (1, 2, 0), (1, 3, 5), (2, 3, 1), (3, 1, 0). This could be represented as a vector with 3 linked lists, such as:
    1 -> (2, 0), (3, 5)
    2 -> (3, 1)
    3 -> (1, 0)

    Where, for example edge 1 goes to edge 2 with weight 0, and also to edge 3 with weight 5, etc.

    there is a function called weightedGraph(Costtype none) that is supposed to create a directed graph giving all edges a weight of none.
    Well to create the graph you need to know the vertices and which one goes to which. Therefore you need more than just a "costtype none" argument. You would need something like an array/list/vector/any collection of "Vector"s. So you take in the list of pairs of vertices and assign them all weight 0.

    If you are overwhelmed with some task, such as this, do not look at the big picture (in my opinion): start with the very basics, which is the required data structure which is what I described above. After you have that then try and create one given, say, a 2-d array of integers, i.e.
    Code:
    vector<list<Vertex>> createGraph(int ** vertices, int len)
    Of course, again the syntax might not be exact because I dont remember it and am just typing it without testing. So the function takes in a 2-d array of integers with length "len", so using the example vertices I said above, it might be called like:
    Code:
    int vertices[4][2];
    // pair (1,2)
    vertices [0][0] = 1;
    vertices[0][1] = 2;
    // pair (1,3)
    vertices[1][0] = 1;
    vertices[1][1] = 3;
    // pair (2,3)
    vertices[2][0]=2;
    vertices[2][1]=3;
    //etc
    vector<list<Vertex>> = createGraph( vertices, 4 );
    So this function should create a vector linkedlists of "Vertex" structs, and assign each "weight" field 0. For example, at index 1 of the vector you create the linked list with "Vector" structs (2, 0), (3,0).
    Anyways, I think Ive given more than enough to get you started.
    Last edited by nadroj; 11-22-2009 at 11:34 AM.

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    16
    ok so my addedge function would just be like
    addEdge(vertexType origin, vertexType destination, cost cost)
    {
    origin->(destination, cost);
    }

    is that all it does?

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    If you arent listening to anything Im suggesting then I give up. Did you get the createGraph done or did you just jump to this step? It can be implemented many ways--do it however you want.

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    16
    sorry, I am having trouble understanding. Ok I am given these structs:
    Code:
    private:
    		// information for each edge
    		struct EdgeInfo
    		{
    		public:
    			int      to;            // vertex number edge adjacent to
    			VertexType to_name;          // vertex name edge adjacent to
    			CostType cost;          // cost associated with edge
    			EdgeInfo(int t, CostType c) {to = t; cost = c;}; // constructor
    			bool operator==(const EdgeInfo& e) const {return e.to == to;}; // comparison, only care about destination
    		};
    
    	     // "Head nodes" of adjacency lists
    		struct VertexInfo
    		{
    		public:
    			VertexType data;       // Vertext Data (name)
    			bool       marked;     // For search methods
    			int        predecesor; // Index of predecesor node; for use by shortest path algorithm
    			CostType   pathCost;   // Total length of path to this node in shortest path algorithm
    			list<EdgeInfo> adjacencyList; //List Containing EdgeInfo structs for each edge from this vertex.
    		};
    I thought I was supposed to implement addEdge first. so based on these structs and the fact that I need to accept more values in my weightedgraph function do you mean I have to create another function for this?

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    I dont understand what your asking.

    As I said, there are many ways to implement this, and I described my suggested implementation above, which is quite different from what you have so I dont know what your doing. For example, if "VertexType" is just a name, why not just use the existing string class for it? Similarly, If "CostType" is just a "length" or "cost" as you have called them both, why not just use an existing type of "int" for it? Are you required to use these custom types/classes? Are you given their definitions?

    It seems more like you are given strict implementation requirements, which I couldnt possibly know what they are so all of what Im suggesting probably doesnt apply because youre already told how to implement it. So it seems I cant help without all of the detailed strict requirements. However, just giving us those requirements isnt a good idea, i.e. "heres what I have to do--do it".

    So just continue with whatever your doing, and when you run into any compiler or logic errors, post your code, error messages, and what your trying to do/dont understand. Implement whatever functions you want in whatever order you think is best.

  7. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    16
    When I write my addedge function I get an error saying that I cannot create an iterator of type VertexInfo.

    Code:
    template <class VertexType, class CostType>
    void WDiGraph< VertexType, CostType >::AddEdge(VertexType origin, VertexType destination, CostType c)
    {
    int i = 0;
    for( vector<VertexInfo>::iterator itv = v.begin();; itv != v.end(); itv++, i++ )
    {
    if( itv->data == origin )
    {
    itv->adjacencyList.push_back( EdgeInfo( i, destination, c ) );
    return;
    }
    }
    }

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Assuming the rest of your code is ok, you need to remove the highlighted semicolon
    Code:
    for( vector<VertexInfo>::iterator itv = v.begin();; itv != v.end(); itv++, i++ )

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    16
    sorry that was a typo on my part. I only have one semi colon there when i get that error. here is what my class looks like.

    Code:
    template <class VertexType, class CostType>
    class WDiGraph
    {
    private:
    		// information for each edge
    		struct EdgeInfo
    		{
    		public:
    			int	  to;			// vertex number edge adjacent to
    			VertexType to_name;		  // vertex name edge adjacent to
    			CostType cost;		  // cost associated with edge
    			EdgeInfo(int t, CostType c) {to = t; cost = c;}; // constructor
    			bool operator==(const EdgeInfo& e) const {return e.to == to;}; // comparison, only care about destination
    		};
    
    		 // "Head nodes" of adjacency lists
    		struct VertexInfo
    		{
    		public:
    			VertexType data;	   // Vertext Data (name)
    			bool	   marked;	 // For search methods
    			int		predecesor; // Index of predecesor node; for use by shortest path algorithm
    			CostType   pathCost;   // Total length of path to this node in shortest path algorithm
    			list<EdgeInfo> adjacencyList; //List Containing EdgeInfo structs for each edge from this vertex.
    		};
    }

  10. #10
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Earlier I was trying it out and wasnt able to get it working the way your doing it. I think what you have is unnecessarily complex, for a simple directed weighted graph.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scene graphs
    By VirtualAce in forum Game Programming
    Replies: 1
    Last Post: 08-09-2009, 12:40 PM
  2. graphs and algorithms
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2004, 01:13 PM
  3. Generate Graphs
    By beet in forum C Programming
    Replies: 6
    Last Post: 08-19-2003, 07: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