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 .

Lembre-se de ativar o perfil C/C++ que criamos anteriormente.

Vamos construir um projeto de código da seguinte forma. Os arquivos de configuração do ambiente estarão na raiz do projeto. Já os arquivos de código serão criados dentro de uma pasta chamada src.

• Directorysrc

  • Directoryedge

    • edge.cpp
    • edge.hpp
  • Directorygraph

    • graph.cpp
    • graph.hpp
  • Directorynode

    • node.cpp
    • node.hpp
  • main.cpp
• .clang-format
• .clang-tidy
• .gitignore

Dentro do diretório oriented_graph, crie os arquivos .clang-tidy e .clang-format.

Fedora, WSL ou Mint

touch .clang-tidy .clang-format

Então, preencha-os com os snippets clang-tidy e clang-format.

Agora, crie a pasta src, abra-a e crie o arquivo main.cpp dentro dela.

Fedora, WSL ou Mint

mkdir -p src
cd src
touch main.cpp

Dentro da pasta src, também crie três pastas: node, edge e graph.

Fedora, WSL ou Mint

mkdir -p node edge graph

Dentro de cada uma, crie um arquivo .cpp e um arquivo .hpp com o mesmo nome da pasta.

Fedora, WSL ou Mint

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.

src/main.cpp

#include <iostream>

#include "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;
}

src/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__

src/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;
}

src/edge/edge.hpp

#ifndef __EDGE_HPP__
#define __EDGE_HPP__

#include "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__

src/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;
}

src/graph/graph.hpp

#ifndef __GRAPH_HPP__
#define __GRAPH_HPP__

#include <optional>
#include <vector>

#include "edge.hpp"
#include "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__

src/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;
}

Git

Da mesma forma como fizemos anteriormente, vamos criar um arquivo .gitignore na raiz do projeto.

Fedora, WSL ou Mint

cd ~/dev/c_cpp_projects/oriented_graph
touch .gitignore

Agora, inicialize-no com o snippet gitignore-c-cpp para que arquivos de compilação não sejam versionados.

Então, inicialize o repositório Git.

Fedora, WSL ou Mint

git init
git add .
git commit -m "Initialize project"

Compilação

Assim como antes, você pode compilar esse projeto diretamente pelo comando 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

cd ~/dev/c_cpp_projects/oriented_graph
mkdir -p build
clang++ src/main.cpp src/node/node.cpp src/edge/edge.cpp src/graph/graph.cpp -I src/node -I src/edge -I src/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.