mirror of
https://github.com/VectorCamp/vectorscan.git
synced 2025-06-28 16:41:01 +03:00
239 lines
7.6 KiB
C++
239 lines
7.6 KiB
C++
/*
|
|
* Copyright (c) 2015-2018, Intel Corporation
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions are met:
|
|
*
|
|
* * Redistributions of source code must retain the above copyright notice,
|
|
* this list of conditions and the following disclaimer.
|
|
* * Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
* * Neither the name of Intel Corporation nor the names of its contributors
|
|
* may be used to endorse or promote products derived from this software
|
|
* without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
|
|
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
|
|
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
|
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
|
|
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
|
* POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#include "config.h"
|
|
#include "gtest/gtest.h"
|
|
#include "util/container.h"
|
|
#include "util/graph.h"
|
|
#include "util/graph_range.h"
|
|
#include "util/graph_undirected.h"
|
|
#include "util/ue2_graph.h"
|
|
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
|
|
using namespace std;
|
|
using namespace ue2;
|
|
|
|
struct SimpleV {
|
|
size_t index = 0;
|
|
string test_v = "SimpleV";
|
|
};
|
|
|
|
struct SimpleE {
|
|
size_t index = 0;
|
|
string test_e = "SimpleE";
|
|
};
|
|
|
|
struct SimpleG : public ue2_graph<SimpleG, SimpleV, SimpleE> {};
|
|
|
|
using SimpleVertex = SimpleG::vertex_descriptor;
|
|
|
|
template<typename Graph, typename Range>
|
|
vector<size_t> to_indices(const Range &range, const Graph &g) {
|
|
vector<size_t> indices;
|
|
for (const auto &elem : range) {
|
|
// cppcheck-suppress useStlAlgorithm
|
|
indices.push_back(g[elem].index);
|
|
}
|
|
sort(indices.begin(), indices.end());
|
|
return indices;
|
|
}
|
|
|
|
template<typename Graph, typename T>
|
|
vector<size_t> to_indices(const std::initializer_list<T> &range,
|
|
const Graph &g) {
|
|
vector<size_t> indices;
|
|
for (const auto &elem : range) {
|
|
// cppcheck-suppress useStlAlgorithm
|
|
indices.push_back(g[elem].index);
|
|
}
|
|
sort(indices.begin(), indices.end());
|
|
return indices;
|
|
}
|
|
|
|
TEST(graph_undirected, simple_ue2_graph) {
|
|
SimpleG g;
|
|
auto a = add_vertex(g);
|
|
ASSERT_NE(SimpleG::null_vertex(), a);
|
|
auto b = add_vertex(g);
|
|
ASSERT_NE(SimpleG::null_vertex(), b);
|
|
auto c = add_vertex(g);
|
|
ASSERT_NE(SimpleG::null_vertex(), c);
|
|
|
|
add_edge(a, b, g);
|
|
add_edge(b, a, g);
|
|
add_edge(a, c, g);
|
|
add_edge(c, b, g);
|
|
add_edge(c, c, g);
|
|
|
|
auto ug = make_undirected_graph(g);
|
|
|
|
ASSERT_EQ(3, num_vertices(ug));
|
|
ASSERT_EQ(4, num_edges(ug));
|
|
|
|
// Check adjacencies
|
|
|
|
ASSERT_EQ(2, out_degree(a, ug));
|
|
ASSERT_EQ(to_indices({b, c}, ug),
|
|
to_indices(adjacent_vertices_range(a, ug), ug));
|
|
|
|
ASSERT_EQ(2, out_degree(b, ug));
|
|
ASSERT_EQ(to_indices({a, c}, ug),
|
|
to_indices(adjacent_vertices_range(b, ug), ug));
|
|
|
|
ASSERT_EQ(3, out_degree(c, ug));
|
|
ASSERT_EQ(to_indices({a, b, c}, ug),
|
|
to_indices(adjacent_vertices_range(c, ug), ug));
|
|
|
|
ASSERT_EQ(2, in_degree(b, ug));
|
|
ASSERT_EQ(to_indices({a, c}, ug),
|
|
to_indices(inv_adjacent_vertices_range(b, ug), ug));
|
|
|
|
// Test reverse edge existence
|
|
|
|
ASSERT_TRUE(edge(a, b, ug).second);
|
|
ASSERT_TRUE(edge(b, a, ug).second);
|
|
ASSERT_TRUE(edge(a, c, ug).second);
|
|
ASSERT_TRUE(edge(c, a, ug).second); // (a,c) actually exists
|
|
ASSERT_TRUE(edge(b, c, ug).second); // (c,b) actually exists
|
|
ASSERT_FALSE(edge(a, a, ug).second);
|
|
|
|
// Vertex properties
|
|
|
|
g[c].test_v = "vertex c";
|
|
ASSERT_EQ("vertex c", ug[c].test_v);
|
|
ASSERT_EQ("vertex c", get(&SimpleV::test_v, ug, c));
|
|
|
|
ug[c].test_v = "vertex c again";
|
|
ASSERT_EQ("vertex c again", g[c].test_v);
|
|
ASSERT_EQ("vertex c again", get(&SimpleV::test_v, g, c));
|
|
|
|
put(&SimpleV::test_v, ug, c, "vertex c once more");
|
|
ASSERT_EQ("vertex c once more", g[c].test_v);
|
|
|
|
const auto &vprops1 = ug[b];
|
|
ASSERT_EQ(1, vprops1.index);
|
|
|
|
const auto &vprops2 = get(boost::vertex_all, ug, b);
|
|
ASSERT_EQ(1, vprops2.index);
|
|
|
|
// Edge Properties
|
|
|
|
auto edge_undirected = edge(a, b, ug).first;
|
|
ug[edge_undirected].test_e = "edge (a,b)";
|
|
ASSERT_EQ("edge (a,b)", ug[edge_undirected].test_e);
|
|
ASSERT_EQ("edge (a,b)", get(&SimpleE::test_e, ug, edge_undirected));
|
|
|
|
ug[edge_undirected].test_e = "edge (a,b) again";
|
|
put(&SimpleE::test_e, ug, edge_undirected, "edge (a,b) once more");
|
|
}
|
|
|
|
TEST(graph_undirected, simple_adjacency_list) {
|
|
using AdjListG =
|
|
boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS,
|
|
SimpleV, SimpleE>;
|
|
|
|
AdjListG g;
|
|
auto a = add_vertex(g);
|
|
ASSERT_NE(AdjListG::null_vertex(), a);
|
|
g[a].index = 0;
|
|
auto b = add_vertex(g);
|
|
ASSERT_NE(AdjListG::null_vertex(), b);
|
|
g[b].index = 1;
|
|
auto c = add_vertex(g);
|
|
ASSERT_NE(AdjListG::null_vertex(), c);
|
|
g[c].index = 2;
|
|
|
|
add_edge(a, b, g);
|
|
add_edge(b, a, g);
|
|
add_edge(a, c, g);
|
|
add_edge(c, b, g);
|
|
add_edge(c, c, g);
|
|
|
|
auto ug = make_undirected_graph(g);
|
|
|
|
ASSERT_EQ(3, num_vertices(ug));
|
|
ASSERT_EQ(4, num_edges(ug));
|
|
|
|
// Check adjacencies
|
|
|
|
ASSERT_EQ(2, out_degree(a, ug));
|
|
ASSERT_EQ(to_indices({b, c}, ug),
|
|
to_indices(adjacent_vertices_range(a, ug), ug));
|
|
|
|
ASSERT_EQ(2, out_degree(b, ug));
|
|
ASSERT_EQ(to_indices({a, c}, ug),
|
|
to_indices(adjacent_vertices_range(b, ug), ug));
|
|
|
|
ASSERT_EQ(3, out_degree(c, ug));
|
|
ASSERT_EQ(to_indices({a, b, c}, ug),
|
|
to_indices(adjacent_vertices_range(c, ug), ug));
|
|
|
|
ASSERT_EQ(2, in_degree(b, ug));
|
|
ASSERT_EQ(to_indices({a, c}, ug),
|
|
to_indices(inv_adjacent_vertices_range(b, ug), ug));
|
|
|
|
// Test reverse edge existence
|
|
|
|
ASSERT_TRUE(edge(a, b, ug).second);
|
|
ASSERT_TRUE(edge(b, a, ug).second);
|
|
ASSERT_TRUE(edge(a, c, ug).second);
|
|
ASSERT_TRUE(edge(c, a, ug).second); // (a,c) actually exists
|
|
ASSERT_TRUE(edge(b, c, ug).second); // (c,b) actually exists
|
|
ASSERT_FALSE(edge(a, a, ug).second);
|
|
|
|
// Vertex properties
|
|
|
|
g[c].test_v = "vertex c";
|
|
ASSERT_EQ("vertex c", ug[c].test_v);
|
|
ASSERT_EQ("vertex c", get(&SimpleV::test_v, ug, c));
|
|
|
|
ug[c].test_v = "vertex c again";
|
|
ASSERT_EQ("vertex c again", g[c].test_v);
|
|
ASSERT_EQ("vertex c again", get(&SimpleV::test_v, g, c));
|
|
|
|
put(&SimpleV::test_v, ug, c, "vertex c once more");
|
|
ASSERT_EQ("vertex c once more", g[c].test_v);
|
|
|
|
const auto &vprops1 = ug[b];
|
|
ASSERT_EQ(1, vprops1.index);
|
|
|
|
const auto &vprops2 = get(boost::vertex_all, ug, b);
|
|
ASSERT_EQ(1, vprops2.index);
|
|
|
|
// Edge Properties
|
|
|
|
auto edge_undirected = edge(a, b, ug).first;
|
|
ug[edge_undirected].test_e = "edge (a,b)";
|
|
ASSERT_EQ("edge (a,b)", ug[edge_undirected].test_e);
|
|
ASSERT_EQ("edge (a,b)", get(&SimpleE::test_e, ug, edge_undirected));
|
|
|
|
ug[edge_undirected].test_e = "edge (a,b) again";
|
|
put(&SimpleE::test_e, ug, edge_undirected, "edge (a,b) once more");
|
|
}
|