FindPaths.cpp
#include <iostream>
#include "Graph.h"
#include <fstream>
#include <sstream>
#include <cstdlib>
//Opens and parses files Graph1.txt and Graph2.txt
//and fills graph with the corresponding vertices and edges
template <typename Object>
void Make_Graph(std::string const & graph_file, Graph<Object> & graph){
std::ifstream input;
input.open(graph_file);
if(input.fail()){
std::cout << "Failed to open " << graph_file << std::endl;
exit(1);
}
std::string line;
Object this_vertex;
Object a_new_vertex;
double a_new_weight;
//Kill first line in .txt that specifies the number of vertices
std::getline(input, line);
while(std::getline(input, line)){
if(!line.empty()){
std::stringstream ss(line);
ss >> this_vertex;
graph.Add_vertex(this_vertex);
while(ss >> a_new_vertex && ss >> a_new_weight){
graph.Add_connection(this_vertex, a_new_vertex, a_new_weight);
}
}
}
input.close();
}
int main(int argc, char **argv){
if(argc != 3){
std::cout << "Usage: " << argv[0] << " <graphInputFilename> <Vertex> " << std::endl;
return 0;
}
const std::string graph_filename(argv[1]);
const int vertex = atoi(argv[2]);
Graph<int> testgraph;
Make_Graph<int>(graph_filename, testgraph);
testgraph.Dijkstra(vertex);
int count = 1;
while(testgraph.Contains(count)){
testgraph.Print_shortest_path(count);
++count;
}
return 0;
}
Graph.cpp
template <typename Object>
bool Graph<Object>::Add_vertex(Object a){
if(vertex_map_.find(a) == vertex_map_.end()){
vertex_map_[a] = Vertex<Object>(a);
return true;
}
return false;
}
template <typename Object>
void Graph<Object>::Add_connection(Object a, Object b, double weight){
if(vertex_map_.find(a) == vertex_map_.end()){
vertex_map_[a] = Vertex<Object>(a);
}
if(vertex_map_.find(b) == vertex_map_.end()){
vertex_map_[b] = Vertex<Object>(b);
}
Vertex<Object>* temp = & vertex_map_[b];
std::pair<Vertex<Object>*, double> new_connection = std::make_pair(temp, weight);
vertex_map_[a].adjacent_nodes_.push_back(new_connection);
}
template <typename Object>
double Graph<Object>::Edge_weight(const Object &a, const Object &b) const{
auto x = vertex_map_.find(a);
if(x != vertex_map_.end()){
//return x->second.Get_edge_weight(b);
auto y = x->second.adjacent_nodes_.begin();
auto x_end = x->second.adjacent_nodes_.end();
while(y != x_end){
if(y->first->id_ == b)
return y->second;
y++;
}
return DBL_MAX;
}
else
return DBL_MAX;
}
template <typename Object>
bool Graph<Object>::Is_connected(const Object &v1, const Object &v2){
if(vertex_map_.find(v1) == vertex_map_.end() || vertex_map_.find(v2) == vertex_map_.end())
return false;
for(auto it = vertex_map_[v1].adjacent_nodes_.begin(); it != vertex_map_[v1].adjacent_nodes_.end(); ++it){
if(it->first->id_ == v2){
return true;
}
}
return false;
}
template <typename Object>
void Graph<Object>::Dijkstra(Object start){
std::priority_queue<Vertex<Object> *, std::vector<Vertex<Object> *>, CompVertDist<Object>> distance_queue;
for(auto it = vertex_map_.begin(); it != vertex_map_.end(); ++it ){
Reset_vertex(it->second);
}
vertex_map_[start].distance_ = 0.0;
Vertex<Object> *v = & vertex_map_[start];
v->starting_vertex_ = true;
distance_queue.push(v);
while(true){
bool success = false;
while(!distance_queue.empty() && !success){
v = distance_queue.top();
distance_queue.pop();
if(!v->known_)
success = true;
}
if(!success)
break;
v->known_ = true;
//THIS LOOP IS WHY I MADE GRAPH A FRIEND OF
for(auto it = v->adjacent_nodes_.begin(); it != v->adjacent_nodes_.end(); ++it){
if(v->distance_ + it->second < it->first->distance_){
it->first->distance_ = v->distance_ + it->second;
it->first->path_prev_ = v;
distance_queue.push(it->first);
}
}
}
}
//ANOTHER FUNCTION THAT EXPECTS TO BE VERTEX TO BE FRIEND
template <typename Object>
void Graph<Object>::Print_shortest_path(const Object & graph_node) const{
auto x = vertex_map_.find(graph_node);
if(x == vertex_map_.end()){
std::cout << "Vertex " << graph_node << " does not exist!\n";
return;
}
std::cout << graph_node << ": ";
const Vertex<Object> * temp = & x->second;
if(temp->starting_vertex_){
std::cout << temp->id_ << " is the starting point, Total Cost: 0.0\n";
return;
}
if(temp->path_prev_ == nullptr){
std::cout << "Total Cost: INFINITY\n";
}
else{
Print_shortest_path_internal(temp);
std::cout << "Total Cost: " << temp->distance_ << std::endl;
}
}
template <typename Object>
bool Graph<Object>::Contains(const Object & vertex_node) const{
return vertex_map_.find(vertex_node) != vertex_map_.end();
}
template <typename Object>
size_t Graph<Object>::Get_size() const{
return vertex_map_.size();
}
template <typename Object>
void Graph<Object>::Print_stats() const{
int smallest_out = INT_MAX;
int largest_out = 0;
int edge_total = 0;
for(auto it = vertex_map_.begin(); it != vertex_map_.end(); ++it){
int current = it->second.adjacent_nodes_.size();
edge_total += current;
if(current < smallest_out)
smallest_out = current;
if(largest_out < current)
largest_out = current;
}
std::cout << "The Random graph of size " << vertex_map_.size() << " has " << edge_total << " directed edges\n";
std::cout << "The smallest out degree is: " << smallest_out << std::endl;
std::cout << "The largest out degree is: " << largest_out << std::endl;
std::cout << "The average out degree is: " << edge_total / static_cast<double>(vertex_map_.size()) << std::endl;
}
template <typename Object>
void Graph<Object>::Print_shortest_path_internal(const Vertex<Object> * graph_node) const{
if(graph_node->path_prev_ == nullptr){
std::cout << graph_node->id_ << ", ";
}
else{
Print_shortest_path_internal(graph_node->path_prev_);
std::cout << graph_node->id_ << ", ";
}
}
template <typename Object>
void Graph<Object>::Reset_vertex(Vertex<Object> v){
v.distance_ = DBL_MAX;
v.known_ = false;
v.path_prev_ = nullptr;
v.starting_vertex_ = false;
}
Graph.h
#ifndef CSCI_335_GRAPH_H
#define CSCI_335_GRAPH_H
#include <unordered_map>
#include <iostream>
#include <list> //for list
#include <utility> //for std::pair
#include <float.h> //DBL_MAX
#include <climits> //INT_MAX
#include <queue>
template<typename Object>
class Graph;
template <typename Object>
class Vertex{
public:
friend class Graph<Object>;
Vertex() = default;
Vertex(Object key){
id_ = key;
distance_ = DBL_MAX;
known_ = false;
path_prev_ = nullptr;
starting_vertex_ = false;
}
//accessor function needed for comparator class
//no precondition
//returns a double corresponding to the sum
//of the edge weights along the shortest path
//to the starting vertex
int Get_distance() const {
return distance_;
}
private:
Object id_;
double distance_;
bool known_;
Vertex<Object> * path_prev_;
bool starting_vertex_;
std::list<std::pair< Vertex<Object>*, double>> adjacent_nodes_;
};
//Comparator class that orders vertices by
//their distance to the starting node
template <typename Object>
class CompVertDist{
public:
bool operator()(const Vertex<Object> *lhs, const Vertex<Object> * rhs) const{
//DEFINED THIS WAY TO MAKE PRIORITY_QUEUE A MIN HEAP
return lhs->Get_distance() > rhs->Get_distance();
}
};
template <typename Object>
class Graph{
public:
Graph() = default;
~Graph() = default;
Graph(const Graph & rhs) = delete;
Graph(Graph && rhs) = delete;
Graph & operator=(const Graph & rhs) = delete;
Graph & operator=(Graph && rhs) = delete;
//Adds a vertex to the graph with ID = a.
//If a is already an ID then nothing will happen
//returns true if vertex 'a' succesfully added
bool Add_vertex(Object a);
//Adds a directed edge from vertex with id 'a' to
//vertex of id 'b' with weight "weight".
//If there already exists an edge from a to b, this
//will add another edge.
//If either 'a' or 'b' are not in the graph, they are added.
void Add_connection(Object a, Object b, double weight);
//Returns a double corresponding to the weight of the
//edge connecting a to b. If no edge exists, then the
//function returns DBL_MAX
double Edge_weight(const Object &a, const Object &b) const;
//returns true if there exists an edge from v1 to v2
//otherwise returns false
bool Is_connected(const Object &v1, const Object &v2);
//Expects there to be no cycles in the graph
//Finds the shortest path from 'start' to all other vertices
//afterwords, each vertex has it's distance_ set to shortest
//path distance if it exists and DBL_MAX otherwise.
//path_prev_ is a pointer pointing to prevous vertex in shortest path
void Dijkstra(Object start);
//Prints the shortest path from the starting vertex to graph_node
//if dijkstra has not been run yet then distances
//will print out as infinity
void Print_shortest_path(const Object & graph_node) const;
//returns true if vertex_node is an id of a vertex in the graph
//returns false otherwise
bool Contains(const Object & vertex_node) const;
//Returns the size_t corresponding to the number of vertices in the graph
size_t Get_size() const;
//Function for CSCI_335 HW 4, outputs the following:
//The Random graph of size N has M edges
//The smallest out degree is: ?
//The largest out degree is: ?
//The average out degree is: ?
void Print_stats() const;
private:
//recursive function for printing the shortest path
//called by Print_shortest_path(const Object & graph_node)
//Prints id of current node and then calls itself on
//node pointed to by path_prev_ stored in vertex
void Print_shortest_path_internal(const Vertex<Object> * graph_node) const;
//sets distance_ = DBL_MAX / known_ = false / path_prev_ = nullptr
//and starting_vertex_ = false
void Reset_vertex(Vertex<Object> v);
std::unordered_map<Object, Vertex<Object>> vertex_map_;
size_t edge_count_;
};
#include "Graph.cpp"
#endif
希望对您有帮助：https://blog.csdn.net/it_xiangqiang/category_10581430.html