Thursday, September 27, 2018

Graph (C++)


 

#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)


Friday, July 21, 2017

VSCode + java

task.json

{
// See https://go.microsoft.com/fwlink/?LinkId=733558
// for the documentation about the tasks.json format
"version": "2.0.0",
"tasks": [
{
"taskName": "build",
"command": "javac",
"args": [
"-g",
"${file}"
]
}
]
}

Saturday, July 8, 2017

CMake + SDL2

cmake_minimum_required(VERSION 3.8)
project(SDL_test)

set(CMAKE_CXX_STANDARD 11)

include_directories(C:/SDL2mingw64/include)
link_directories(C:/SDL2mingw64/lib)

set(SOURCE_FILES main.cpp)
add_executable(SDL_test ${SOURCE_FILES})

target_link_libraries(SDL_test mingw32 SDL2main SDL2)

Thursday, June 29, 2017

VS Code + SDL2

task


// See https://go.microsoft.com/fwlink/?LinkId=733558
// for the documentation about the tasks.json format
"version": "0.1.0",
"command": "g++",
"isShellCommand": true,
"args": [
"-g",
"-o",
"H:/CPPnew/Game/bin/main.exe",
"-std=c++11",
" main.cpp",
"-IH:/CPPnew/Game/common/include/SDL2",
"-LH:/CPPnew/Game/common/lib",
"-lmingw32",
"-lSDL2main",
"-lSDL2",
"-lSDL2_image",
"-lSDL2_ttf",
"-lSDL2_mixer"
],
"showOutput": "always"
}



cpp


"name": "Win32",
"includePath": [
"${workspaceRoot}",
"H:/CPPnew/Game/common/include/SDL2",
"C:/mingw64/x86_64-w64-mingw32/include",
"C:/Program Files (x86)/Microsoft Visual Studio/2017/Professional/VC/Tools/MSVC/14.10.25017/include/*",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/um",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/ucrt",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/shared",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/winrt"
],
"defines": [
"_DEBUG",
"UNICODE"
],
"intelliSenseMode": "msvc-x64",
"browse": {
"path": [
"H:/CPPnew/Game/common/include/SDL2",
"C:/mingw64/x86_64-w64-mingw32/include",
"C:/Program Files (x86)/Microsoft Visual Studio/2017/Professional/VC/Tools/MSVC/14.10.25017/include/*",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/um",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/ucrt",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/shared",
"C:/Program Files (x86)/Windows Kits/10/Include/10.0.15063.0/winrt"
],
"limitSymbolsToIncludedHeaders": true,
"databaseFilename": ""