Graphs_Cpp/Graph.template at master · kodecreer/Graphs_Cpp · 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

#include <cassert>
#include <cstdlib>
#include <set>


template <class Item>
void Graph<Item>::add_vertex(const Item& label){
    size_t new_vertex_number;
    size_t other_number;

    assert(size() < MAXIMUM);
    new_vertex_number = many_vertices;
    ++many_vertices;
    for (other_number = 0; other_number < many_vertices; ++other_number) {
        bool_edges[other_number][new_vertex_number] = false;
        bool_edges[new_vertex_number][other_number] = false;
        edges[other_number][new_vertex_number] = -1;
        edges[new_vertex_number][other_number] = -1;
    }
    labels[new_vertex_number] = label;
}

template <class Item>
void Graph<Item>::add_edge(size_t source, size_t target, size_t weight){
    assert(source < size());
    assert(target < size());
    bool_edges[source][target] = true;
    edges[source][target] = weight; //-1 means infinity
}

template <class Item>
void Graph<Item>::remove_edge(size_t source, size_t target){
    assert(source < size());
    assert(target < size());
//    edges[source][target] = false;
    edges[source][target] = -1;
    bool_edges[source][target] = false;
}

template <class Item>
int Graph<Item>::edge_at(size_t source, size_t target) const{
    assert(source < size());
    assert(target < size());
    return edges[source][target];
}
template <class Item>
bool Graph<Item>::is_edge(size_t source, size_t target) const{
    assert(source < size());
    assert(target < size());
    return bool_edges[source][target];
}

template <class Item>
std::set<size_t> Graph<Item>::neighbors(size_t vertex) const{
    std::set<size_t> answer;
    size_t i;

    assert(vertex < size());

    for (i = 0; i < size(); ++i) {
        if (bool_edges[vertex][i]) {
            answer.insert(i);
        }
    }
    return answer;
}

template <class Item>
Item Graph<Item>::operator [] (size_t vertex) const{
    assert(vertex < size());
    return labels[vertex];
}
template <class Item>
Item& Graph<Item>::operator [](size_t vertex){
    assert(vertex < size());
    return labels[vertex];
}