Weighted Graphs (and graphs in general)

[Mr Spudtastic]

Hi, I'm new to graphs, and I need to build one. The graph is a weighted graph that holds some number of city names with edges linking them together. Each edge will have a weight (hopefully) equivalent to the driving distance between the two places.

As for functionality, the user should be able to set a starting point and a destination, and then the function should send back the shortest route between the two.

I understand a little bit about pointers (although I'm not great with them), and I know how to set up a node (for example, like the nodes one would find in a binary search tree). In fact... I probably already know everything I need to know to actually do this, but I'm having trouble putting it all together.

So... how would I start?

[Smac89]

You start by creating a graph class.
The graph can be represented using either adjacency list representation or matrix representation. The later uses more memory but allows for looking up edges connected to each vertex in O(1) time.

a vertex is dependent on the representation of the graph.
for adjancecy list, the vertex will hold:

- list of all vertices it is pointing to
- shortest distance from itself to source

for matrix representation:

- shortest distance from itself to source

finally to implement shortest distance algorithm you have some options:

- breadth first search (BFS)
- Dijkstra's shortest path algorithm
- Bellman Ford algorithm

To really understand graph theory, you have to learn some of the terms usually associated with graphs, especially these:

- directed graphs (digraphs)
- undirected graphs
- vertex
- edge
- degree
- cycle
- adjacency

http://www.utm.edu/departments/math/graph/glossary.html

Here is an interface for a graph class:

#pragma once
#include <list>
#include <vector>

template <typename vertex>
class GraphInterface {
protected:
	virtual void addEdge(int, int) = 0;
	virtual int countNodes() const  = 0;
        //given a vertex return list of vertex's adjacent to it
	virtual std::list<vertex> adjacent(int) = 0;
	std::vector<vertex> nodeList;	
};

[Mr Spudtastic]

Alright... I think I understand all the graph terms reasonably well, I just don't really know how to apply any of that information. Am I right in assuming that the vertex and edges need to be classes/structs within the graph class?

If so, I'm thinking the vertex and edge should look something like this:

struct vertex{
    string city;    //holds the city name
    vector<edge> edgeName[arrSize];
};

struct edge{
    string city;    //This one holds the name of the city at the other end of the edge
    int distance;    //weight of the edge
};

So, the graph class would look something like...

class graph{
public:
    graph();
    ~graph();

vertex *point = new vertex[MAX];

bool searchGraph(string);    //searches the vertex array for a match. 
                                            //If no match, returns false.
    
    void setPointA(string);
    void setPointB(string;

    string findRoute(string pointA, string pointB);
        //This should implement the shortest path algorithm at some point

    struct vertex{
        string city;
        vector<edge> road[MAX];
	};

    struct edge{
	string city;
	int distance;
    };

private:
	string pointA;    //Starting point
	string pointB;    //Target city
};

I'm not really sure where to go from here. I feel like I'm missing something obvious, but I can't figure out what that might be. Any tips?

[Smac89]

Here is how I would write the vertex object

#include <list> //std::list
#include <utility> //std::pair

typedef struct vert {

	//List of edges connected to current vertex
	std::list<std::pair<double, vert&> > edges;

	//Smallest distance from source to this node
	double distance;
	
        //unique id to use for indexing this vertex
	int ID;
} Vertex;

And here is a graph class that I have used in the past:
http://www.mediafire.com/view/1wp935mdb9wb22j/Graph.cpp