sdn/graph.cpp at master · slashnick/sdn · 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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include "graph.h"
#include <stdint.h>
#include <map>
#include <queue>
#include <set>

typedef std::pair<uint32_t, std::pair<uint64_t, uint32_t> > edge_t;
typedef std::map<uint64_t, edges_t> vertices_t;

static void add_mst_edge(uint64_t, uint32_t, void*);

void Graph::add_single_edge(uint64_t from, uint32_t fport, uint64_t to,
                            uint32_t tport) {
    edges_t* from_e = &vertices[from];
    edges_t::iterator from_search = from_e->find(fport);
    std::pair<uint64_t, uint32_t> topair =
        std::pair<uint64_t, uint32_t>(to, tport);

    if (from_search != from_e->end()) {
        std::pair<uint64_t, uint32_t> existing_to = from_search->second;

        if (existing_to != topair) {
            // Remove the existing to-vertex's edge back to from
            vertices[existing_to.first].erase(existing_to.second);
            from_e->erase(from_search);
            from_e->insert(edge_t(fport, topair));
        }
    } else {
        from_e->insert(edge_t(fport, topair));
    }
}

void Graph::remove_edge(uint64_t from, uint32_t fport) {
    edges_t* from_e = &vertices[from];
    edges_t::iterator from_search = from_e->find(fport);

    if (from_search != from_e->end()) {
        std::pair<uint64_t, uint32_t> existing_to = from_search->second;
        vertices[existing_to.first].erase(existing_to.second);
        from_e->erase(from_search);
    }
}

void Graph::add_vertex(uint64_t id) {
    vertices[id];
}

void Graph::add_edge(uint64_t from, uint32_t fport, uint64_t to,
                     uint32_t tport) {
    add_single_edge(from, fport, to, tport);
    add_single_edge(to, tport, from, fport);
}

// Does this vertex have a specific switch & port connected to this port?
uint8_t Graph::has_edge(uint64_t from, uint32_t fport, uint64_t to,
                        uint32_t tport) const {
    vertices_t::const_iterator vsearch = vertices.find(from);
    if (vsearch == vertices.end()) {
        return 0;
    }
    edges_t::const_iterator esearch = vsearch->second.find(fport);
    if (esearch == vsearch->second.end()) {
        return 0;
    }
    return esearch->second.first == to && esearch->second.second == tport;
}

// Does this vertex have any switch connected to this port?
uint8_t Graph::has_any_edge(uint64_t from, uint32_t fport) const {
    vertices_t::const_iterator vsearch = vertices.find(from);
    if (vsearch == vertices.end()) {
        return 0;
    }

    edges_t edges = vsearch->second;
    return edges.find(fport) != edges.end();
}

void Graph::walk_shortest_path(uint64_t start, uint32_t start_port, void* data,
                               uint8_t bidirectional,
                               shortest_path_cb cb) const {
    std::queue<std::pair<uint64_t, uint32_t> > queue;
    std::set<uint64_t> visited;

    queue.push(std::pair<uint64_t, uint32_t>(start, start_port));
    visited.insert(start);

    while (!queue.empty()) {
        std::pair<uint64_t, uint32_t> vertex = queue.front();
        queue.pop();
        cb(vertex.first, vertex.second, data);

        edges_t edges = vertices.find(vertex.first)->second;
        for (edges_t::iterator it = edges.begin(); it != edges.end(); it++) {
            uint32_t my_port = it->first;
            uint64_t them = it->second.first;
            uint32_t their_port = it->second.second;
            if (visited.find(them) == visited.end()) {
                visited.insert(them);
                if (bidirectional) {
                    cb(vertex.first, my_port, data);
                }
                queue.push(std::pair<uint64_t, uint32_t>(them, their_port));
            }
        }
    }
}

#define IGNORE_EDGE 0xffffffff

void add_mst_edge(uint64_t vertex, uint32_t port, void* mst) {
    MST* m = reinterpret_cast<MST*>(mst);

    if (port == IGNORE_EDGE) {
        // The "start port" for an MST is meaningless to us
        return;
    }
    (*m)[vertex].insert(port);
}

MST* Graph::make_mst() const {
    MST* mst = new MST;

    vertices_t::const_iterator it = vertices.begin();
    if (it == vertices.end()) {
        return mst;
    }

    walk_shortest_path(it->first, IGNORE_EDGE, (void*)mst, 1, add_mst_edge);
    return mst;
}