Criando o projeto

Vamos criar um projeto em C++ que utiliza o conceito de grafo orientado. Um nó pode se conectar por meio de arestas a outros nós, formando um grafo. Dessa forma, precisamos representar os nós, as arestas e o grafo em si.

Projeto

Acesse a pasta ~/dev/c_cpp_projects que criamos anteriormente. Dentro dela, crie um diretório chamado oriented_graph. Acesse-o e abra nele o Visual Studio Code.

Fedora, WSL ou Mint

mkdir -p ~/dev/c_cpp_projects
cd ~/dev/c_cpp_projects
mkdir -p oriented_graph
cd oriented_graph
code .

Dentro do diretório oriented_graph, crie um arquivo main.cpp e três pastas: node, edge e graph. Cada pasta deve conter um arquivo .cpp e um arquivo .hpp com o mesmo nome da pasta.

Fedora, WSL ou Mint

touch main.cpp .clang-tidy .clang-format
mkdir -p node edge graph
touch node/node.cpp node/node.hpp edge/edge.cpp edge/edge.hpp graph/graph.cpp graph/graph.hpp

Copie o código de cada arquivo a seguir para o seu projeto.

main.cpp

#include <iostream>

#include "graph/graph.hpp"

using namespace std;

int main() {
    Graph graph;

    graph.addNode(1, 10);
    graph.addNode(2, 20);
    graph.addNode(3, 30);
    graph.addNode(4, 40);
    graph.addNode(5, 50);

    graph.addEdge(1, 2, 10);
    graph.addEdge(1, 3, 20);
    graph.addEdge(2, 3, 30);
    graph.addEdge(3, 4, 40);
    graph.addEdge(4, 5, 50);

    vector<unsigned long> connected_nodes = graph.depthFirstSearch(1);

    for (unsigned long label : connected_nodes) {
        cout << label << " ";
    }

    cout << endl;

    return 0;
}

node/node.hpp

#ifndef __NODE_HPP__
#define __NODE_HPP__

class Node {
    private:
        unsigned long id;
        unsigned long label;
        int data;

    public:
        Node(unsigned long id, unsigned long label, int data);

        ~Node() {}

        unsigned long getId() const;
        unsigned long getLabel() const;
        int getData() const;

        void setData(int data);
};

#endif  // __NODE_HPP__

node/node.cpp

#include "node.hpp"

Node::Node(unsigned long id, unsigned long label, int data) {
    this->id = id;
    this->label = label;
    this->data = data;
}

unsigned long Node::getId() const {
    return this->id;
}

unsigned long Node::getLabel() const {
    return this->label;
}

int Node::getData() const {
    return this->data;
}

void Node::setData(int data) {
    this->data = data;
}

edge/edge.hpp

#ifndef __EDGE_HPP__
#define __EDGE_HPP__

#include "../node/node.hpp"

class Edge {
    private:
        unsigned long id;
        Node *source;
        Node *target;
        int weight;

    public:
        Edge(unsigned long id, Node *source, Node *target, int weight);

        ~Edge() {}

        unsigned long getId() const;
        Node *getSource() const;
        Node *getTarget() const;
        int getWeight() const;

        void setWeight(int weight);
};

#endif  // __EDGE_HPP__

edge/edge.cpp

#include "edge.hpp"

Edge::Edge(unsigned long id, Node *source, Node *target, int weight) {
    this->id = id;
    this->source = source;
    this->target = target;
    this->weight = weight;
}

unsigned long Edge::getId() const {
    return this->id;
}

Node *Edge::getSource() const {
    return this->source;
}

Node *Edge::getTarget() const {
    return this->target;
}

int Edge::getWeight() const {
    return this->weight;
}

void Edge::setWeight(int weight) {
    this->weight = weight;
}

graph/graph.hpp

#ifndef __GRAPH_HPP__
#define __GRAPH_HPP__

#include <optional>
#include <vector>

#include "../edge/edge.hpp"
#include "../node/node.hpp"

using namespace std;

class Graph {
    private:
        unsigned long last_node_id;
        vector<Node *> nodes;
        unsigned long last_edge_id;
        vector<Edge *> edges;

        Node *getNodeByLabel(unsigned long label) const;

        void clearNodes();
        void clearEdges();

    public:
        Graph();
        ~Graph();

        optional<int> getNodeData(unsigned long label) const;

        void addNode(unsigned long label, int data);
        void addEdge(unsigned long source_label, unsigned long target_label, int weight);

        vector<unsigned long> depthFirstSearch(unsigned long start_label) const;
};

#endif  // __GRAPH_HPP__

graph/graph.cpp

#include "graph.hpp"

#include <algorithm>

Graph::Graph() {
    this->last_node_id = 0;
    this->last_edge_id = 0;
}

Graph::~Graph() {
    this->clearNodes();
    this->clearEdges();
}

Node *Graph::getNodeByLabel(unsigned long label) const {
    for (Node *node : this->nodes) {
        if (node->getLabel() == label) {
            return node;
        }
    }

    return nullptr;
}

void Graph::clearNodes() {
    for (Node *node : this->nodes) {
        delete node;
    }

    this->nodes.clear();
}

void Graph::clearEdges() {
    for (Edge *edge : this->edges) {
        delete edge;
    }

    this->edges.clear();
}

optional<int> Graph::getNodeData(unsigned long label) const {
    Node *node = this->getNodeByLabel(label);

    if (node == nullptr) {
        return nullopt;
    }

    return node->getData();
}

void Graph::addNode(unsigned long label, int data) {
    Node *node = new Node(this->last_node_id++, label, data);
    this->nodes.push_back(node);
}

void Graph::addEdge(unsigned long source_label, unsigned long target_label, int weight) {
    Node *source = this->getNodeByLabel(source_label);
    Node *target = this->getNodeByLabel(target_label);

    if (source == nullptr || target == nullptr) {
        return;
    }

    Edge *edge = new Edge(this->last_edge_id++, source, target, weight);
    this->edges.push_back(edge);
}

vector<unsigned long> Graph::depthFirstSearch(unsigned long start_label) const {
    vector<unsigned long> visited;
    vector<unsigned long> stack;

    stack.push_back(start_label);

    while (!stack.empty()) {
        unsigned long current_label = stack.back();
        stack.pop_back();

        if (find(visited.begin(), visited.end(), current_label) != visited.end()) {
            continue;
        }

        visited.push_back(current_label);

        Node *current_node = this->getNodeByLabel(current_label);

        for (Edge *edge : this->edges) {
            if (edge->getSource() == current_node) {
                stack.push_back(edge->getTarget()->getLabel());
            }
        }
    }

    return visited;
}

Também crie o arquivo .clang-tidy na raiz do projeto e o preencha com o snippet clang-tidy. Igualmente, crie o arquivo .clang-format e o preencha com o snippet clang-format.

Git

Da mesma forma como fizemos anteriormente, vamos inicializar o repositório Git e criar um arquivo .gitignore para que arquivos de compilação não sejam versionados.

Fedora, WSL ou Mint

git init
echo -e "## Build\n.cache/\nbuild/" >> .gitignore
git add .
git commit -m "Initialize project"

Compilação

Assim como antes, você pode compilar esse projeto diretamente pelo clang++ ou utilizando os arquivos tasks.json e launch.json do Visual Studio Code.

O comando de compilação é o seguinte.

Fedora, WSL ou Mint

mkdir -p build
clang++ main.cpp node/node.cpp edge/edge.cpp graph/graph.cpp -I node -I edge -I graph -o build/oriented_graph

Ao executar o programa, você verá a seguinte saída.

Fedora, WSL ou Mint

./build/oriented_graph
# 1 3 4 5 2

Ela representa a ordem de visitação dos nós do grafo em uma busca em profundidade iniciando pelo nó 1.