-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathedge.hpp
87 lines (73 loc) · 2.79 KB
/
edge.hpp
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
/**
* Copyright (C) 2019 Dean De Leo, email: hello[at]whatsthecraic.net
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#pragma once
#include <cstddef>
#include <cstdint>
#include <ostream>
#include <utility>
struct Edge {
uint32_t m_source;
uint32_t m_destination;
Edge(): m_source{0}, m_destination{0} {}
Edge(uint32_t source, uint32_t destination) : m_source(source), m_destination(destination) { };
uint32_t source() const { return m_source; }
uint32_t destination() const { return m_destination; }
// Relative order of the edges
bool operator==(const Edge&) const noexcept;
bool operator!=(const Edge&) const noexcept;
bool operator<(const Edge&) const noexcept;
bool operator<=(const Edge&) const noexcept;
bool operator>(const Edge&) const noexcept;
bool operator>=(const Edge&) const noexcept;
};
struct WeightedEdge : public Edge {
double m_weight;
WeightedEdge();
WeightedEdge(uint32_t src, uint32_t dst, double weight);
double weight() const { return m_weight; }
// Check whether two edges are equal
bool operator==(const WeightedEdge&) const noexcept;
bool operator!=(const WeightedEdge&) const noexcept;
Edge edge() const;
};
std::ostream& operator<<(std::ostream& out, const Edge& e);
std::ostream& operator<<(std::ostream& out, const WeightedEdge& e);
namespace std {
template<>
struct hash<Edge> { // hash function for graph::Edge
private:
// Adapted from the General Purpose Hash Function Algorithms Library
// Author: Arash Partow - 2002
// URL: http://www.partow.net
// URL: http://www.partow.net/programming/hashfunctions/index.html
// MIT License
unsigned int APHash(uint64_t value) const {
unsigned int hash = 0xAAAAAAAA;
unsigned int i = 0;
char* str = (char*) &value;
for (i = 0; i < sizeof(value); ++str, ++i) {
hash ^= ((i & 1) == 0) ? ((hash << 7) ^ (*str) * (hash >> 3)) :
(~((hash << 11) + ((*str) ^ (hash >> 5))));
}
return hash;
}
public:
size_t operator()(const Edge& e) const {
return APHash((static_cast<uint64_t>(e.source()) << 32) + (e.destination() & 0xFFFFFFFF));
}
};
} // namespace std