#pragma once
#include <string>
template<typename T>
class Vertex
{
private:
int Index;
T _data;
public:
Vertex();
Vertex(T data);
~Vertex();
int IndexGet();
void IndexSet(int index);
T Data();
std::string toString();
};
template<typename T>
Vertex<T>::Vertex()
{
}
template<typename T>
Vertex<T>::Vertex(T data)
{
_data = data;
Index = -1;
}
template<typename T>
Vertex<T>::~Vertex()
{
}
template<typename T>
int Vertex<T>::IndexGet()
{
return Index;
}
template<typename T>
void Vertex<T>::IndexSet(int index)
{
Index = index;
}
template<typename T>
T Vertex<T>::Data()
{
return _data;
}
template<typename T>
std::string Vertex<T>::toString()
{
return "{Vertex} " + _data;
}
=======================================
#pragma once
#include <vector>
class AdjacencyMatrix
{
private:
int _size;
std::vector<std::vector<float> > _matrix;
public:
AdjacencyMatrix() {};
AdjacencyMatrix(int size=0);
~AdjacencyMatrix();
int Size();
void AddDirectedEdge(int from, int to , float weight);
void AddUndirectedEdge(int v1, int v2, float weight);
float GetEdgeWeight(int x, int y);
std::vector<int> GetAdjacencyList(int sourceIndex);
};
AdjacencyMatrix::AdjacencyMatrix(int size) :_size(size)
{
std::vector< std::vector<float> > tmpVec(size, std::vector<float>(size));
_matrix = tmpVec;
}
AdjacencyMatrix::~AdjacencyMatrix()
{
}
int AdjacencyMatrix::Size()
{
return _size;
}
void AdjacencyMatrix::AddDirectedEdge(int from, int to, float weight)
{
_matrix[from][to] = weight;
}
void AdjacencyMatrix::AddUndirectedEdge(int v1, int v2, float weight)
{
_matrix[v1][v2] = weight;
_matrix[v2][v1] = weight;
}
float AdjacencyMatrix::GetEdgeWeight(int x, int y)
{
return _matrix[x][y];
}
std::vector<int> AdjacencyMatrix::GetAdjacencyList(int sourceIndex)
{
std::vector<int> adjacenceList;
for (int i = 0; i < _size; i++) {
if (_matrix[sourceIndex][i] != 0) {
adjacenceList.push_back(i);
}
}
return adjacenceList;
}
==================================================
#pragma once
class AdjacencyMatrix;
template<typename T>
class Graph
{
private:
std::vector<Vertex<T>*> _vertices;
AdjacencyMatrix* _adjacencyMatrix;
public:
Graph() {};
Graph(std::vector<Vertex<T>*> vertices);
~Graph();
std::vector<Vertex<T>*> Vertices();
void CreateDirectedEdge(int fromIndex, int toIndex, float weight);
void CreateDirectedEdge(Vertex<T> from, Vertex<T> to, float weight);
void CreateUndirectedEdge(int v1, int v2, float weight);
void CreateUndirectedEdge(Vertex<T> v1, Vertex<T> v2, float weight);
std::vector<Vertex<T>*> GetAdjacentVertices(int sourceIndex);
std::vector<Vertex<T>*> GetAdjacentVertices(Vertex<T> source);
float GetEdgeWeight(Vertex<T> v1, Vertex<T> v2);
std::string toString();
};
#include <vector>
#include <string>
#include "AdjacencyMatrix.h"
#include "Vertex.h"
//#include "Graph.h"
template<typename T>
Graph<T>::Graph(std::vector<Vertex<T>*> vertices)
{
_vertices = vertices;
for (int i = 0; i < _vertices.size(); i++) {
_vertices.at(i)->IndexSet(i);
}
_adjacencyMatrix = new AdjacencyMatrix(_vertices.size());
}
template<typename T>
Graph<T>::~Graph()
{
delete _adjacencyMatrix;
}
template<typename T>
std::vector<Vertex<T>*> Graph<T>::Vertices()
{
return _vertices;
}
template<typename T>
void Graph<T>::CreateDirectedEdge(int fromIndex, int toIndex, float weight) {
if (weight == 0) {
weight = 1;
}
_adjacencyMatrix->AddDirectedEdge(fromIndex, toIndex, weight);
}
template<typename T>
void Graph<T>::CreateDirectedEdge(Vertex<T> from, Vertex<T> to, float weight) {
if (weight == 0) {
weight = 1;
}
this->CreateDirectedEdge(from.IndexGet(), to.IndexGet(), weight);
}
template<typename T>
void Graph<T>::CreateUndirectedEdge(int v1, int v2, float weight) {
if (weight == 0) {
weight = 1;
}
_adjacencyMatrix->AddUndirectedEdge(v1, v2, weight);
}
template<typename T>
void Graph<T>::CreateUndirectedEdge(Vertex<T> v1, Vertex<T> v2, float weight) {
if (weight == 0) {
weight = 1;
}
this->CreateUndirectedEdge(v1.IndexGet(), v2.IndexGet(), weight);
}
template<typename T>
std::vector<Vertex<T>*> Graph<T>::GetAdjacentVertices(int sourceIndex) {
std::vector<int> adjacentIndices = _adjacencyMatrix->GetAdjacencyList(sourceIndex);
std::vector<Vertex<T>*> adjacentVertices;
for (int vertexIndex : adjacentIndices) {
adjacentVertices.push_back(_vertices.at(vertexIndex));
}
return adjacentVertices;
}
template<typename T>
std::vector<Vertex<T>*> Graph<T>::GetAdjacentVertices(Vertex<T> source) {
return GetAdjacentVertices(source.IndexGet());
}
template<typename T>
float Graph<T>::GetEdgeWeight(Vertex<T> v1, Vertex<T> v2) {
return _adjacencyMatrix->GetEdgeWeight(v1.IndexGet(), v2.IndexGet());
}
template<typename T>
std::string Graph<T>::toString() {
std::string sb;
sb.append("Graph: \n");
for (Vertex<T>* vertex : _vertices) {
sb.append(vertex->Data());
sb.append("\t");
std::vector<Vertex<T>*> adjacentVertices = GetAdjacentVertices(*vertex);
if (adjacentVertices.size() > 0) {
sb.append("Edge to: ");
for (Vertex<T>* adjVertex : adjacentVertices) {
sb.append(adjVertex->Data());
sb.append("(w=");
sb.append(std::to_string(GetEdgeWeight(*vertex, *adjVertex)));
sb.append(") ");
}
}
else {
sb.append("No outgoing edges");
}
sb.append("\n");
}
return sb;
}
=============================================
#include <iostream>
#include <vector>
#include <string>
#include "Vertex.h"
#include "Graph.h"
int main()
{
std::cout << "Graphs" << std::endl;
//auto* v1 = new Vertex<std::string>("v1");
//std::string xxx = v1->toString();
//std::cout << xxx << std::endl;
Vertex<std::string>* v1 = new Vertex<std::string>("v1");
Vertex<std::string>* v2 = new Vertex<std::string>("v2");
Vertex<std::string>* v3 = new Vertex<std::string>("v3");
Vertex<std::string>* v4 = new Vertex<std::string>("v4");
std::vector<Vertex<std::string>*> vertices;
vertices.push_back(v1);
vertices.push_back(v2);
vertices.push_back(v3);
vertices.push_back(v4);
Graph<std::string>* graph = new Graph<std::string>(vertices);
graph->CreateDirectedEdge(*v1, *v2, 3);
graph->CreateDirectedEdge(*v4, *v1, 1);
graph->CreateDirectedEdge(*v2, *v3, 1);
graph->CreateDirectedEdge(*v2, *v4, -5);
std::cout << graph->toString() << std::endl;
std::cout << "End " << std::endl;
delete graph;
return 0;
}
Graph:
v1 Edge to: v2(w=3.0)
v2 Edge to: v3(w=1.0) v4(w=-2.0)
v3 No edges
v4 Edge to: v1(w=1.0)
