1. ## 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. 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.

3. 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. 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. 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
};

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?

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. 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. 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. 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
};

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. 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.