ProjectDomesDedomenwn/Graph.cpp at main · Despmouk/ProjectDomesDedomenwn · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "Graph.h"
#include <fstream>
#include <iostream>
#include <sstream>
#include <utility>

using namespace std;

Graph::Vertex* Graph::findVertex(int id) {
    Vertex* temp = vertices;
    while (temp != nullptr) {
        if (temp->id == id)
            return temp;
        temp = temp->next;
    }
    return nullptr;
}

void Graph::addVertex(int id) {
    if (findVertex(id) == nullptr) {
        Vertex* newVertex = new Vertex{id, nullptr, vertices};
        vertices = newVertex;
        numVertices++;
    }
}

Graph::Edge* Graph::findEdge(int node1, int node2) {
    Vertex* vertex = findVertex(node1);
    if (vertex != nullptr) {
        Edge* edge = vertex->edgeList;
        while (edge != nullptr) {
            if (edge->node2 == node2)
                return edge;
            edge = edge->next;
        }
    }
    return nullptr;
}

Graph::Graph(std::string& filename) : vertices(nullptr), numVertices(0), numEdges(0) {
    std::ifstream file(filename);
    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        int node1, node2, weight;
        iss >> node1 >> node2 >> weight;
        insertEdge(node1, node2, weight);
    }
    file.close();
}

Graph::~Graph() {
    while (vertices != nullptr) {
        Vertex* tempVertex = vertices;
        vertices = vertices->next;

        Edge* edge = tempVertex->edgeList;
        while (edge != nullptr) {
            Edge* tempEdge = edge;
            edge = edge->next;
            delete tempEdge;
        }
        delete tempVertex;
    }
}

std::pair<int, int> Graph::getSize() {
    return std::make_pair(numVertices, numEdges);
}

void Graph::insertEdge(int node1, int node2, int weight) {
    if (!findEdge(node1, node2)) {
        addVertex(node1);
        addVertex(node2);

        Edge* newEdge = new Edge{node1, node2, weight, findVertex(node1)->edgeList};
        findVertex(node1)->edgeList = newEdge;
        numEdges++;
    }
}

void Graph::deleteEdge(int node1, int node2, int weight) {
    Vertex* vertex = findVertex(node1);
    if (vertex != nullptr) {
        Edge** edge = &vertex->edgeList;
        while (*edge != nullptr) {
            if ((*edge)->node2 == node2 && (*edge)->weight == weight) {
                Edge* temp = *edge;
                *edge = (*edge)->next;
                delete temp;
                numEdges--;
                return;
            }
            edge = &(*edge)->next;
        }
    }
}