github_mirrors/vectorscan
3
0
Fork 1
mirror of https://github.com/VectorCamp/vectorscan.git synced 2025-06-28 16:41:01 +03:00
Code Issues Packages Projects Releases Wiki Activity
vectorscan/unit/internal/graph.cpp
Matthew Barr 46f74300f2 update copyright year
2017-01-17 11:38:09 +11:00

1788 lines
44 KiB
C++
Raw Permalink Blame History

/*
* Copyright (c) 2015-2017, 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/graph.h"
#include "util/ue2_graph.h"
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <type_traits>
using namespace boost;
using namespace std;
using namespace ue2;
typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, no_property,
no_property> unit_graph;
typedef unit_graph::vertex_descriptor unit_vertex;
typedef unit_graph::edge_descriptor unit_edge;
TEST(graph_util, parallel) {
unit_graph g;
ASSERT_FALSE(has_parallel_edge(g));
unit_vertex v1 = add_vertex(g);
unit_vertex v2 = add_vertex(g);
ASSERT_FALSE(has_parallel_edge(g));
add_edge(v1, v2, g);
ASSERT_FALSE(has_parallel_edge(g));
add_edge(v2, v1, g);
ASSERT_FALSE(has_parallel_edge(g));
add_edge(v2, v1, g);
ASSERT_TRUE(has_parallel_edge(g));
}
TEST(graph_util, dag) {
unit_graph g;
ASSERT_TRUE(is_dag(g));
unit_vertex v1 = add_vertex(g);
unit_vertex v2 = add_vertex(g);
ASSERT_TRUE(is_dag(g));
add_edge(v1, v2, g);
unit_vertex v3 = add_vertex(g);
add_edge(v1, v3, g);
add_edge(v2, v3, g);
ASSERT_TRUE(is_dag(g));
add_edge(v2, v2, g);
ASSERT_FALSE(is_dag(g));
ASSERT_TRUE(is_dag(g, true)); /* only cycle is self loop */
unit_vertex v4 = add_vertex(g);
add_edge(v3, v4, g);
add_edge(v4, v1, g);
ASSERT_FALSE(is_dag(g, true)); /* now have a large cycle */
}
TEST(graph_util, degrees) {
unit_graph g;
unit_vertex a = add_vertex(g);
unit_vertex b = add_vertex(g);
unit_vertex c = add_vertex(g);
unit_vertex d = add_vertex(g);
unit_vertex e = add_vertex(g);
unit_vertex f = add_vertex(g);
add_edge(a, b, g);
add_edge(b, c, g);
add_edge(d, e, g);
add_edge(f, a, g);
add_edge(f, b, g);
add_edge(f, c, g);
unit_graph::vertex_iterator vi, ve;
tie(vi, ve) = vertices(g);
ASSERT_FALSE(anySelfLoop(g, vi, ve));
add_edge(b, b, g);
tie(vi, ve) = vertices(g);
ASSERT_TRUE(anySelfLoop(g, vi, ve));
add_edge(e, e, g);
ASSERT_FALSE(isLeafNode(a, g));
ASSERT_FALSE(isLeafNode(b, g));
ASSERT_TRUE( isLeafNode(c, g));
ASSERT_FALSE(isLeafNode(d, g));
ASSERT_FALSE( isLeafNode(e, g));
ASSERT_FALSE(isLeafNode(f, g));
ASSERT_FALSE(hasSelfLoop(a, g));
ASSERT_TRUE( hasSelfLoop(b, g));
ASSERT_FALSE(hasSelfLoop(c, g));
ASSERT_FALSE(hasSelfLoop(d, g));
ASSERT_TRUE( hasSelfLoop(e, g));
ASSERT_FALSE(hasSelfLoop(f, g));
ASSERT_EQ((size_t)1, proper_out_degree(a, g));
ASSERT_EQ((size_t)1, proper_out_degree(b, g));
ASSERT_EQ((size_t)0, proper_out_degree(c, g));
ASSERT_EQ((size_t)1, proper_out_degree(d, g));
ASSERT_EQ((size_t)0, proper_out_degree(e, g));
ASSERT_EQ((size_t)3, proper_out_degree(f, g));
ASSERT_EQ((size_t)1, proper_in_degree(a, g));
ASSERT_EQ((size_t)2, proper_in_degree(b, g));
ASSERT_EQ((size_t)2, proper_in_degree(c, g));
ASSERT_EQ((size_t)0, proper_in_degree(d, g));
ASSERT_EQ((size_t)1, proper_in_degree(e, g));
ASSERT_TRUE( has_successor(a, g));
ASSERT_TRUE( has_successor(b, g));
ASSERT_FALSE(has_successor(c, g));
ASSERT_TRUE( has_successor(d, g));
ASSERT_TRUE( has_successor(e, g));
ASSERT_TRUE( has_successor(f, g));
ASSERT_TRUE( has_proper_successor(a, g));
ASSERT_TRUE( has_proper_successor(b, g));
ASSERT_FALSE(has_proper_successor(c, g));
ASSERT_TRUE( has_proper_successor(d, g));
ASSERT_FALSE(has_proper_successor(e, g));
ASSERT_TRUE( has_proper_successor(f, g));
}
struct SimpleV {
size_t index;
string test_v = "SimpleV";
};
struct SimpleE {
size_t index;
string test_e = "SimpleE";
};
struct SimpleG : public ue2_graph<SimpleG, SimpleV, SimpleE> {
};
TEST(ue2_graph, graph_concept) {
static_assert(std::is_same<SimpleG::vertex_descriptor,
graph_traits<SimpleG>::vertex_descriptor>::value,
"vertex_descriptor");
static_assert(std::is_same<SimpleG::edge_descriptor,
graph_traits<SimpleG>::edge_descriptor>::value,
"edge_descriptor");
static_assert(std::is_same<SimpleG::directed_category,
graph_traits<SimpleG>::directed_category>::value,
"directed_category");
static_assert(std::is_same<SimpleG::edge_parallel_category,
graph_traits<SimpleG>::edge_parallel_category>::value,
"edge_parallel_category");
static_assert(std::is_same<SimpleG::traversal_category,
graph_traits<SimpleG>::traversal_category>::value,
"traversal_category");
UNUSED SimpleG::vertex_descriptor n = SimpleG::null_vertex();
BOOST_CONCEPT_ASSERT((GraphConcept<SimpleG>));
}
TEST(ue2_graph, vertex_list_concept) {
BOOST_CONCEPT_ASSERT((VertexListGraphConcept<SimpleG>));
}
TEST(ue2_graph, edge_list_concept) {
BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<SimpleG>));
}
TEST(ue2_graph, incidence_concept) {
BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<SimpleG>));
}
TEST(ue2_graph, bidi_concept) {
BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept<SimpleG>));
}
TEST(ue2_graph, mutable_concept) {
BOOST_CONCEPT_ASSERT((MutableGraphConcept<SimpleG>));
}
TEST(ue2_graph, property_concept) {
static_assert(std::is_same<SimpleG::vertex_property_type, SimpleV>::value,
"vertex_property_type");
static_assert(std::is_same<SimpleG::edge_property_type, SimpleE>::value,
"edge_property_type");
/* Although documented as part of the MutablePropertyGraph concept,
* (vertex|edge)_property_type don't appear to exist in the traits for any
* existing graph types and the typedefs are not installed by default */
// static_assert(std::is_same<
// typename graph_traits<SimpleG>::vertex_property_type,
// SimpleV>::value,
// "vertex_property_type");
// static_assert(std::is_same<
// typename graph_traits<SimpleG>::edge_property_type,
// SimpleE>::value,
// "edge_property_type");
/* However, there does seem to be an undocumented templated structure
* paralleling the main graph_traits */
static_assert(std::is_same<
typename vertex_property_type<SimpleG>::type,
SimpleV>::value,
"vertex_property_type");
static_assert(std::is_same<
typename edge_property_type<SimpleG>::type,
SimpleE>::value,
"edge_property_type");
BOOST_CONCEPT_ASSERT((VertexMutablePropertyGraphConcept<SimpleG>));
BOOST_CONCEPT_ASSERT((EdgeMutablePropertyGraphConcept<SimpleG>));
}
TEST(ue2_graph, add_vertex) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
}
TEST(ue2_graph, add_and_remove_vertex) {
SimpleG g;
ASSERT_EQ(0U, num_vertices(g));
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
ASSERT_NE(SimpleG::null_vertex(), a);
auto p = vertices(g);
ASSERT_NE(p.first, p.second);
ASSERT_EQ(a, *p.first);
++p.first;
ASSERT_EQ(p.first, p.second);
remove_vertex(a, g);
ASSERT_EQ(0U, num_vertices(g));
auto q = vertices(g);
ASSERT_EQ(q.first, q.second);
}
TEST(ue2_graph, add_edge) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
auto q = edge(a, b, g);
ASSERT_TRUE(q.second);
ASSERT_EQ(p.second, q.first);
}
TEST(ue2_graph, add_remove_edge1) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
remove_edge(p.first, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_remove_edge2) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
remove_edge(a, b, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_edge_clear1) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
clear_vertex(a, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_edge_clear2) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
clear_vertex(b, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_edge_clear_out) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
clear_out_edges(a, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_edge_clear_in) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
clear_in_edges(b, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, add_remove_edge_iter) {
SimpleG g;
SimpleG::vertex_descriptor a = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), a);
SimpleG::vertex_descriptor b = add_vertex(g);
ASSERT_NE(SimpleG::null_vertex(), b);
ASSERT_NE(a, b);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
ASSERT_EQ(a, source(p.first, g));
ASSERT_EQ(b, target(p.first, g));
remove_edge(edges(g).first, g);
auto q = edge(a, b, g);
ASSERT_FALSE(q.second);
ASSERT_EQ(q.first, SimpleG::null_edge());
ASSERT_EQ(0U, num_edges(g));
}
TEST(ue2_graph, vertices_0) {
SimpleG g;
auto p = vertices(g);
ASSERT_EQ(p.first, p.second);
}
TEST(ue2_graph, vertices_1) {
SimpleG g;
SimpleG::vertex_iterator vi;
SimpleG::vertex_iterator ve;
auto a = add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(a, *vi++);
ASSERT_EQ(vi, ve);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
ASSERT_EQ(4U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(a, *vi++);
ASSERT_EQ(b, *vi++);
ASSERT_EQ(c, *vi++);
ASSERT_EQ(d, *vi++);
ASSERT_EQ(vi, ve);
remove_vertex(c, g);
ASSERT_EQ(3U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(a, *vi++);
ASSERT_EQ(b, *vi++);
ASSERT_EQ(d, *vi++);
ASSERT_EQ(vi, ve);
remove_vertex(a, g);
ASSERT_EQ(2U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(b, *vi++);
ASSERT_EQ(d, *vi++);
ASSERT_EQ(vi, ve);
auto e = add_vertex(g);
ASSERT_EQ(3U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(b, *vi++);
ASSERT_EQ(d, *vi++);
ASSERT_EQ(e, *vi++);
ASSERT_EQ(vi, ve);
remove_vertex(e, g);
ASSERT_EQ(2U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(b, *vi++);
ASSERT_EQ(d, *vi++);
ASSERT_EQ(vi, ve);
remove_vertex(b, g);
remove_vertex(d, g);
ASSERT_EQ(0U, num_vertices(g));
tie(vi, ve) = vertices(g);
ASSERT_EQ(vi, ve);
}
TEST(ue2_graph, out_edges_1) {
SimpleG g;
auto a = add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
ASSERT_EQ(0U, out_degree(a, g));
SimpleG::out_edge_iterator ei;
SimpleG::out_edge_iterator ee;
tie(ei, ee) = out_edges(a, g);
ASSERT_TRUE(ei == ee);
auto p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
SimpleG::edge_descriptor e1 = p.first;
ASSERT_EQ(1U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e2 = p.first;
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
}
TEST(ue2_graph, out_edges_2) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
ASSERT_EQ(3U, num_vertices(g));
ASSERT_EQ(0U, out_degree(a, g));
SimpleG::out_edge_iterator ei;
SimpleG::out_edge_iterator ee;
tie(ei, ee) = out_edges(a, g);
ASSERT_TRUE(ei == ee);
auto p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
SimpleG::edge_descriptor e1 = p.first;
ASSERT_EQ(1U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, c, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e2 = p.first;
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(c, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(3U, num_edges(g));
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(b, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(4U, num_edges(g));
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
remove_edge(a, c, g);
ASSERT_EQ(3U, num_edges(g));
ASSERT_EQ(1U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_EQ(4U, num_edges(g));
ASSERT_TRUE(p.second);
SimpleG::edge_descriptor e3 = p.first;
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e3, *ei++);
ASSERT_EQ(ei, ee);
clear_out_edges(a, g);
ASSERT_EQ(2U, num_edges(g));
ASSERT_EQ(0U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(ei, ee);
}
TEST(ue2_graph, in_edges_1) {
SimpleG g;
auto a = add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
ASSERT_EQ(0U, in_degree(a, g));
SimpleG::in_edge_iterator ei;
SimpleG::in_edge_iterator ee;
tie(ei, ee) = in_edges(a, g);
ASSERT_TRUE(ei == ee);
auto p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
SimpleG::edge_descriptor e1 = p.first;
ASSERT_EQ(1U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e2 = p.first;
ASSERT_EQ(2U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
}
TEST(ue2_graph, in_edges_2) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
ASSERT_EQ(3U, num_vertices(g));
ASSERT_EQ(0U, in_degree(a, g));
SimpleG::in_edge_iterator ei;
SimpleG::in_edge_iterator ee;
tie(ei, ee) = in_edges(a, g);
ASSERT_TRUE(ei == ee);
auto p = add_edge(b, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
SimpleG::edge_descriptor e1 = p.first;
ASSERT_EQ(1U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(c, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e2 = p.first;
ASSERT_EQ(2U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(c, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(3U, num_edges(g));
ASSERT_EQ(2U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, b, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(4U, num_edges(g));
ASSERT_EQ(2U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
remove_edge(c, a, g);
ASSERT_EQ(3U, num_edges(g));
ASSERT_EQ(1U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_EQ(4U, num_edges(g));
ASSERT_TRUE(p.second);
SimpleG::edge_descriptor e3 = p.first;
ASSERT_EQ(2U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e3, *ei++);
ASSERT_EQ(ei, ee);
clear_in_edges(a, g);
ASSERT_EQ(2U, num_edges(g));
ASSERT_EQ(0U, in_degree(a, g));
tie(ei, ee) = in_edges(a, g);
ASSERT_EQ(ei, ee);
}
TEST(ue2_graph, parallel_1) {
SimpleG g;
SimpleG::vertex_iterator vi;
SimpleG::vertex_iterator ve;
auto a = add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
ASSERT_EQ(0U, out_degree(a, g));
SimpleG::out_edge_iterator ei;
SimpleG::out_edge_iterator ee;
tie(ei, ee) = out_edges(a, g);
ASSERT_TRUE(ei == ee);
auto p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(1U, num_edges(g));
SimpleG::edge_descriptor e1 = p.first;
ASSERT_EQ(1U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e2 = p.first;
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
remove_edge(e1, g);
ASSERT_EQ(1U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ei, ee);
p = add_edge(a, a, g);
ASSERT_TRUE(p.second);
ASSERT_EQ(2U, num_edges(g));
SimpleG::edge_descriptor e3 = p.first;
ASSERT_EQ(2U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(e3, *ei++);
ASSERT_EQ(ei, ee);
remove_edge(a, a, g);
ASSERT_EQ(0U, out_degree(a, g));
tie(ei, ee) = out_edges(a, g);
ASSERT_EQ(ei, ee);
}
TEST(ue2_graph, edges_0a) {
SimpleG g;
auto p = edges(g);
ASSERT_EQ(p.first, p.second);
}
TEST(ue2_graph, edges_0b) {
SimpleG g;
add_vertex(g);
ASSERT_EQ(1U, num_vertices(g));
auto p = edges(g);
ASSERT_EQ(p.first, p.second);
}
TEST(ue2_graph, edges_0c) {
SimpleG g;
add_vertex(g);
add_vertex(g);
ASSERT_EQ(2U, num_vertices(g));
auto p = edges(g);
ASSERT_EQ(p.first, p.second);
}
TEST(ue2_graph, edges_1a) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
auto v = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(v, v, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_1b) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
auto u = add_vertex(g);
auto v = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(u, v, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_1c) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
auto u = add_vertex(g);
auto v = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(v, u, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_1d) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
UNUSED auto u = add_vertex(g);
UNUSED auto v = add_vertex(g);
auto w = add_vertex(g);
auto x = add_vertex(g);
UNUSED auto y = add_vertex(g);
UNUSED auto z = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(w, x, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_2a) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
auto v = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(v, v, g).first;
auto e2 = add_edge(v, v, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(2U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e2, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_2b) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
auto u = add_vertex(g);
auto v = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(u, v, g).first;
auto e2 = add_edge(v, u, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(2U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(1U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e2, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_2c) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
UNUSED auto s = add_vertex(g);
UNUSED auto t = add_vertex(g);
auto u = add_vertex(g);
UNUSED auto v = add_vertex(g);
auto w = add_vertex(g);
auto x = add_vertex(g);
UNUSED auto y = add_vertex(g);
UNUSED auto z = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(w, x, g).first;
auto e2 = add_edge(u, x, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(2U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
clear_in_edges(x, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, edges_3a) {
SimpleG g;
ASSERT_EQ(0U, num_edges(g));
UNUSED auto s = add_vertex(g);
UNUSED auto t = add_vertex(g);
auto u = add_vertex(g);
auto v = add_vertex(g);
auto w = add_vertex(g);
auto x = add_vertex(g);
UNUSED auto y = add_vertex(g);
auto z = add_vertex(g);
ASSERT_EQ(0U, num_edges(g));
auto e1 = add_edge(w, x, g).first;
auto e2 = add_edge(u, v, g).first;
auto e3 = add_edge(u, z, g).first;
SimpleG::edge_iterator ei, ee;
ASSERT_EQ(3U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(e2, *ei++);
ASSERT_EQ(e3, *ei++);
ASSERT_EQ(e1, *ei++);
ASSERT_EQ(ee, ei);
remove_edge(e1, g);
ASSERT_EQ(2U, num_edges(g));
clear_out_edges(u, g);
ASSERT_EQ(0U, num_edges(g));
tie(ei, ee) = edges(g);
ASSERT_EQ(ee, ei);
}
TEST(ue2_graph, degree) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
add_edge(a, b, g);
add_edge(a, c, g);
add_edge(a, d, g);
ASSERT_EQ(3U, degree(a, g));
ASSERT_EQ(1U, degree(b, g));
ASSERT_EQ(1U, degree(c, g));
ASSERT_EQ(1U, degree(d, g));
add_edge(b, c, g);
ASSERT_EQ(3U, degree(a, g));
ASSERT_EQ(2U, degree(b, g));
ASSERT_EQ(2U, degree(c, g));
ASSERT_EQ(1U, degree(d, g));
add_edge(d, d, g);
ASSERT_EQ(3U, degree(a, g));
ASSERT_EQ(2U, degree(b, g));
ASSERT_EQ(2U, degree(c, g));
ASSERT_EQ(3U, degree(d, g));
add_edge(b, a, g);
ASSERT_EQ(4U, degree(a, g));
ASSERT_EQ(3U, degree(b, g));
ASSERT_EQ(2U, degree(c, g));
ASSERT_EQ(3U, degree(d, g));
add_edge(b, a, g);
ASSERT_EQ(5U, degree(a, g));
ASSERT_EQ(4U, degree(b, g));
ASSERT_EQ(2U, degree(c, g));
ASSERT_EQ(3U, degree(d, g));
add_edge(d, d, g);
ASSERT_EQ(5U, degree(a, g));
ASSERT_EQ(4U, degree(b, g));
ASSERT_EQ(2U, degree(c, g));
ASSERT_EQ(5U, degree(d, g));
}
TEST(ue2_graph, adj) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
add_edge(a, b, g);
add_edge(a, c, g);
add_edge(a, d, g);
add_edge(b, a, g);
add_edge(b, b, g);
SimpleG::adjacency_iterator ai, ae;
tie(ai, ae) = adjacent_vertices(a, g);
ASSERT_EQ(b, *ai++);
ASSERT_EQ(c, *ai++);
ASSERT_EQ(d, *ai++);
ASSERT_EQ(ai, ae);
tie(ai, ae) = adjacent_vertices(b, g);
ASSERT_EQ(a, *ai++);
ASSERT_EQ(b, *ai++);
ASSERT_EQ(ai, ae);
tie(ai, ae) = adjacent_vertices(c, g);
ASSERT_EQ(ai, ae);
tie(ai, ae) = adjacent_vertices(d, g);
ASSERT_EQ(ai, ae);
}
TEST(ue2_graph, inv_adj) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
add_edge(a, b, g);
add_edge(a, c, g);
add_edge(a, d, g);
add_edge(b, a, g);
add_edge(b, b, g);
SimpleG::inv_adjacency_iterator ai, ae;
tie(ai, ae) = inv_adjacent_vertices(a, g);
ASSERT_EQ(b, *ai++);
ASSERT_EQ(ai, ae);
tie(ai, ae) = inv_adjacent_vertices(b, g);
ASSERT_EQ(a, *ai++);
ASSERT_EQ(b, *ai++);
ASSERT_EQ(ai, ae);
tie(ai, ae) = inv_adjacent_vertices(c, g);
ASSERT_EQ(a, *ai++);
ASSERT_EQ(ai, ae);
tie(ai, ae) = inv_adjacent_vertices(d, g);
ASSERT_EQ(a, *ai++);
ASSERT_EQ(ai, ae);
}
TEST(ue2_graph, square_brackets_v) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
ASSERT_EQ(0U, g[a].index);
ASSERT_EQ(1U, g[b].index);
ASSERT_EQ(2U, g[c].index);
ASSERT_EQ(3U, g[d].index);
ASSERT_EQ("SimpleV", g[a].test_v);
ASSERT_EQ("SimpleV", g[b].test_v);
ASSERT_EQ("SimpleV", g[c].test_v);
ASSERT_EQ("SimpleV", g[d].test_v);
g[a].test_v = "a";
g[b].test_v = "b";
g[c].test_v = "c";
g[d].test_v = "d";
ASSERT_EQ("a", g[a].test_v);
ASSERT_EQ("b", g[b].test_v);
ASSERT_EQ("c", g[c].test_v);
ASSERT_EQ("d", g[d].test_v);
}
TEST(ue2_graph, square_brackets_e) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto b = add_edge(u, v, g).first;
auto c = add_edge(u, u, g).first;
auto d = add_edge(v, u, g).first;
ASSERT_EQ(0U, g[a].index);
ASSERT_EQ(1U, g[b].index);
ASSERT_EQ(2U, g[c].index);
ASSERT_EQ(3U, g[d].index);
ASSERT_EQ("SimpleE", g[a].test_e);
ASSERT_EQ("SimpleE", g[b].test_e);
ASSERT_EQ("SimpleE", g[c].test_e);
ASSERT_EQ("SimpleE", g[d].test_e);
g[a].test_e = "a";
g[b].test_e = "b";
g[c].test_e = "c";
g[d].test_e = "d";
ASSERT_EQ("a", g[a].test_e);
ASSERT_EQ("b", g[b].test_e);
ASSERT_EQ("c", g[c].test_e);
ASSERT_EQ("d", g[d].test_e);
}
TEST(ue2_graph, vertex_ordering_1) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
ASSERT_LE(a, b);
ASSERT_LE(a, c);
ASSERT_LE(a, d);
ASSERT_LE(b, c);
ASSERT_LE(b, d);
ASSERT_LE(c, d);
g[a].index = 5;
g[b].index = 0;
g[c].index = 3;
g[d].index = 1;
ASSERT_LE(a, b);
ASSERT_LE(a, c);
ASSERT_LE(a, d);
ASSERT_LE(b, c);
ASSERT_LE(b, d);
ASSERT_LE(c, d);
}
TEST(ue2_graph, vertex_ordering_2) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto c = add_vertex(g);
auto d = add_vertex(g);
set<SimpleG::vertex_descriptor> s;
s.insert(a);
s.insert(b);
s.insert(c);
s.insert(d);
auto it = s.begin();
ASSERT_EQ(a, *it++);
ASSERT_EQ(b, *it++);
ASSERT_EQ(c, *it++);
ASSERT_EQ(d, *it++);
ASSERT_EQ(it, s.end());
g[a].index = 5;
g[b].index = 0;
g[c].index = 3;
g[d].index = 1;
it = s.begin();
ASSERT_EQ(a, *it++);
ASSERT_EQ(b, *it++);
ASSERT_EQ(c, *it++);
ASSERT_EQ(d, *it++);
ASSERT_EQ(it, s.end());
}
TEST(ue2_graph, get_v_2_arg) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto pm = get(&SimpleV::test_v, g);
ASSERT_EQ("SimpleV", pm[a]);
ASSERT_EQ("SimpleV", pm[b]);
pm[a] = "a";
pm[b] = "b";
ASSERT_EQ("a", pm[a]);
ASSERT_EQ("b", pm[b]);
ASSERT_EQ("a", g[a].test_v);
ASSERT_EQ("b", g[b].test_v);
g[a].test_v = "X";
g[b].test_v = "Y";
ASSERT_EQ("X", pm[a]);
ASSERT_EQ("Y", pm[b]);
ASSERT_EQ("X", get(pm, a));
ASSERT_EQ("Y", get(pm, b));
put(pm, a, "A");
put(pm, b, "B");
ASSERT_EQ("A", g[a].test_v);
ASSERT_EQ("B", g[b].test_v);
}
TEST(ue2_graph, get_v_2_arg_const) {
SimpleG g;
const SimpleG &gg = g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto pm = get(&SimpleV::test_v, gg);
ASSERT_EQ("SimpleV", pm[a]);
ASSERT_EQ("SimpleV", pm[b]);
g[a].test_v = "a";
g[b].test_v = "b";
ASSERT_EQ("a", pm[a]);
ASSERT_EQ("b", pm[b]);
ASSERT_EQ("a", get(pm, a));
ASSERT_EQ("b", get(pm, b));
}
TEST(ue2_graph, get_e_2_arg) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto b = add_edge(v, u, g).first;
auto pm = get(&SimpleE::test_e, g);
ASSERT_EQ("SimpleE", pm[a]);
ASSERT_EQ("SimpleE", pm[b]);
pm[a] = "a";
pm[b] = "b";
ASSERT_EQ("a", pm[a]);
ASSERT_EQ("b", pm[b]);
ASSERT_EQ("a", g[a].test_e);
ASSERT_EQ("b", g[b].test_e);
g[a].test_e = "X";
g[b].test_e = "Y";
ASSERT_EQ("X", pm[a]);
ASSERT_EQ("Y", pm[b]);
ASSERT_EQ("X", get(pm, a));
ASSERT_EQ("Y", get(pm, b));
put(pm, a, "A");
put(pm, b, "B");
ASSERT_EQ("A", g[a].test_e);
ASSERT_EQ("B", g[b].test_e);
}
TEST(ue2_graph, get_e_2_arg_const) {
SimpleG g;
const SimpleG &gg = g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto b = add_edge(v, u, g).first;
auto pm = get(&SimpleE::test_e, gg);
ASSERT_EQ("SimpleE", pm[a]);
ASSERT_EQ("SimpleE", pm[b]);
g[a].test_e = "a";
g[b].test_e = "b";
ASSERT_EQ("a", pm[a]);
ASSERT_EQ("b", pm[b]);
ASSERT_EQ("a", get(pm, a));
ASSERT_EQ("b", get(pm, b));
}
TEST(ue2_graph, get_v_3_arg) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
ASSERT_EQ("SimpleV", get(&SimpleV::test_v, g, a));
ASSERT_EQ("SimpleV", get(&SimpleV::test_v, g, a));
get(&SimpleV::test_v, g, a) = "a";
get(&SimpleV::test_v, g, b) = "b";
ASSERT_EQ("a", get(&SimpleV::test_v, g, a));
ASSERT_EQ("b", get(&SimpleV::test_v, g, b));
ASSERT_EQ("a", g[a].test_v);
ASSERT_EQ("b", g[b].test_v);
g[a].test_v = "X";
g[b].test_v = "Y";
ASSERT_EQ("X", get(&SimpleV::test_v, g, a));
ASSERT_EQ("Y", get(&SimpleV::test_v, g, b));
//std::decay<decltype(get(&SimpleV::test_v, g)[a])>::type x = "A";
put(&SimpleV::test_v, g, a, "A");
put(&SimpleV::test_v, g, b, "B");
ASSERT_EQ("A", g[a].test_v);
ASSERT_EQ("B", g[b].test_v);
}
TEST(ue2_graph, get_v_3_arg_const) {
SimpleG g;
const SimpleG &gg = g;
auto a = add_vertex(g);
auto b = add_vertex(g);
ASSERT_EQ("SimpleV", get(&SimpleV::test_v, gg, a));
ASSERT_EQ("SimpleV", get(&SimpleV::test_v, gg, b));
g[a].test_v = "a";
g[b].test_v = "b";
ASSERT_EQ("a", get(&SimpleV::test_v, gg, a));
ASSERT_EQ("b", get(&SimpleV::test_v, gg, b));
}
TEST(ue2_graph, get_e_3_arg) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto b = add_edge(v, u, g).first;
ASSERT_EQ("SimpleE", get(&SimpleE::test_e, g, a));
ASSERT_EQ("SimpleE", get(&SimpleE::test_e, g, b));
get(&SimpleE::test_e, g, a) = "a";
get(&SimpleE::test_e, g, b) = "b";
ASSERT_EQ("a", get(&SimpleE::test_e, g, a));
ASSERT_EQ("b", get(&SimpleE::test_e, g, b));
ASSERT_EQ("a", g[a].test_e);
ASSERT_EQ("b", g[b].test_e);
g[a].test_e = "X";
g[b].test_e = "Y";
ASSERT_EQ("X", get(&SimpleE::test_e, g, a));
ASSERT_EQ("Y", get(&SimpleE::test_e, g, b));
}
TEST(ue2_graph, get_e_3_arg_const) {
SimpleG g;
const SimpleG &gg = g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto b = add_edge(v, u, g).first;
ASSERT_EQ("SimpleE", get(&SimpleE::test_e, gg, a));
ASSERT_EQ("SimpleE", get(&SimpleE::test_e, gg, b));
g[a].test_e = "a";
g[b].test_e = "b";
ASSERT_EQ("a", get(&SimpleE::test_e, gg, a));
ASSERT_EQ("b", get(&SimpleE::test_e, gg, b));
}
TEST(ue2_graph, get_vertex_index) {
SimpleG g;
auto a = add_vertex(g);
auto pm = get(vertex_index, g);
ASSERT_EQ(0U, pm(a));
pm(a) = 1;
ASSERT_EQ(1U, pm[a]);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(vertex_index, g, a));
}
TEST(ue2_graph, get_vertex_index_const) {
SimpleG g;
const SimpleG &gg = g;
auto a = add_vertex(g);
auto pm = get(vertex_index, gg);
ASSERT_EQ(0U, pm(a));
g[a].index = 1;
ASSERT_EQ(1U, pm[a]);
ASSERT_EQ(1U, get(vertex_index, gg, a));
}
TEST(ue2_graph, get_edge_index) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_index, g);
ASSERT_EQ(0U, pm(a));
pm(a) = 1;
ASSERT_EQ(1U, pm[a]);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(edge_index, g, a));
}
TEST(ue2_graph, get_edge_index_const) {
SimpleG g;
const SimpleG &gg = g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_index, gg);
ASSERT_EQ(0U, pm(a));
g[a].index = 1;
ASSERT_EQ(1U, pm[a]);
ASSERT_EQ(1U, get(edge_index, gg, a));
}
TEST(ue2_graph, get_vertex_all) {
SimpleG g;
auto a = add_vertex(g);
auto pm = get(vertex_all, g);
ASSERT_EQ(0U, pm(a).index);
pm(a).index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(vertex_all, g, a).index);
auto &a_all = get(vertex_all, g, a);
ASSERT_EQ(1U, a_all.index);
g[a].index = 2;
ASSERT_EQ(2U, a_all.index);
}
TEST(ue2_graph, get_vertex_all_const) {
SimpleG g;
const SimpleG &gg = g;
auto a = add_vertex(g);
auto pm = get(vertex_all, gg);
ASSERT_EQ(0U, pm(a).index);
g[a].index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, get(vertex_all, gg, a).index);
auto &a_all = get(vertex_all, gg, a);
ASSERT_EQ(1U, a_all.index);
g[a].index = 2;
ASSERT_EQ(2U, a_all.index);
}
TEST(ue2_graph, get_vertex_bundle) {
SimpleG g;
auto a = add_vertex(g);
auto pm = get(vertex_bundle, g);
ASSERT_EQ(0U, pm(a).index);
pm(a).index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(vertex_bundle, g, a).index);
auto &a_bundle = get(vertex_bundle, g, a);
ASSERT_EQ(1U, a_bundle.index);
g[a].index = 2;
ASSERT_EQ(2U, a_bundle.index);
}
TEST(ue2_graph, get_vertex_bundle_const) {
SimpleG g;
const SimpleG &gg = g;
auto a = add_vertex(g);
auto pm = get(vertex_bundle, gg);
ASSERT_EQ(0U, pm(a).index);
g[a].index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, get(vertex_bundle, gg, a).index);
auto &a_bundle = get(vertex_bundle, gg, a);
ASSERT_EQ(1U, a_bundle.index);
g[a].index = 2;
ASSERT_EQ(2U, a_bundle.index);
}
TEST(ue2_graph, get_edge_all) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_all, g);
ASSERT_EQ(0U, pm(a).index);
pm(a).index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(edge_all, g, a).index);
auto &a_all = get(edge_all, g, a);
ASSERT_EQ(1U, a_all.index);
g[a].index = 2;
ASSERT_EQ(2U, a_all.index);
}
TEST(ue2_graph, get_edge_all_const) {
SimpleG g;
const SimpleG &gg = g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_all, gg);
ASSERT_EQ(0U, pm(a).index);
g[a].index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, get(edge_all, gg, a).index);
auto &a_all = get(edge_all, gg, a);
ASSERT_EQ(1U, a_all.index);
g[a].index = 2;
ASSERT_EQ(2U, a_all.index);
}
TEST(ue2_graph, get_edge_bundle) {
SimpleG g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_bundle, g);
ASSERT_EQ(0U, pm(a).index);
pm(a).index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, g[a].index);
ASSERT_EQ(1U, get(edge_bundle, g, a).index);
auto &a_bundle = get(edge_bundle, g, a);
ASSERT_EQ(1U, a_bundle.index);
g[a].index = 2;
ASSERT_EQ(2U, a_bundle.index);
}
TEST(ue2_graph, get_edge_bundle_const) {
SimpleG g;
const SimpleG &gg = g;
auto u = add_vertex(g);
auto v = add_vertex(g);
auto a = add_edge(u, v, g).first;
auto pm = get(edge_bundle, gg);
ASSERT_EQ(0U, pm(a).index);
g[a].index = 1;
ASSERT_EQ(1U, pm[a].index);
ASSERT_EQ(1U, get(edge_bundle, gg, a).index);
auto &a_bundle = get(edge_bundle, gg, a);
ASSERT_EQ(1U, a_bundle.index);
g[a].index = 2;
ASSERT_EQ(2U, a_bundle.index);
}
TEST(ue2_graph, add_vertex_prop) {
SimpleG g;
SimpleV vp;
vp.index = 42;
vp.test_v = "prop";
auto u = add_vertex(vp, g);
auto v = add_vertex(vp, g);
ASSERT_EQ(0U, g[u].index);
ASSERT_EQ(1U, g[v].index);
ASSERT_EQ("prop", g[u].test_v);
ASSERT_EQ("prop", g[v].test_v);
}
TEST(ue2_graph, add_edge_prop) {
SimpleG g;
SimpleE ep;
ep.index = 42;
ep.test_e = "prop";
auto u = add_vertex(g);
auto v = add_vertex(g);
auto e = add_edge(u, v, ep, g).first;
auto f = add_edge(u, v, ep, g).first;
ASSERT_EQ(0U, g[e].index);
ASSERT_EQ(1U, g[f].index);
ASSERT_EQ("prop", g[e].test_e);
ASSERT_EQ("prop", g[f].test_e);
}
TEST(ue2_graph, reverse_graph) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto e = add_edge(a, b, g).first;
reverse_graph<SimpleG, SimpleG &> rg(g);
auto index_map = get(vertex_index, rg);
ASSERT_EQ(0U, rg[a].index);
ASSERT_EQ(1U, rg[b].index);
ASSERT_EQ(0U, rg[e].index);
ASSERT_EQ(0U, get(vertex_index, rg, a));
ASSERT_EQ(1U, get(vertex_index, rg, b));
ASSERT_EQ(0U, get(edge_index, rg, edge(b, a, rg).first));
ASSERT_EQ(0U, index_map(a));
ASSERT_EQ(1U, index_map(b));
ASSERT_TRUE(edge(b, a, rg).second);
ASSERT_FALSE(edge(a, b, rg).second);
}
TEST(ue2_graph, reverse_graph_const) {
SimpleG g;
auto a = add_vertex(g);
auto b = add_vertex(g);
auto e = add_edge(a, b, g).first;
reverse_graph<const SimpleG, const SimpleG &> rg(g);
auto index_map = get(&SimpleV::index, rg);
// Note: reverse_graph fails to make bundles const so things break.
// ASSERT_EQ(0U, rg[a].index);
// ASSERT_EQ(1U, rg[b].index);
// ASSERT_EQ(0U, rg[e].index);
ASSERT_EQ(0U, get(vertex_index, g, a));
ASSERT_EQ(1U, get(vertex_index, g, b));
ASSERT_EQ(0U, get(edge_index, g, e));
ASSERT_EQ(0U, index_map(a));
ASSERT_EQ(1U, index_map(b));
ASSERT_TRUE(edge(b, a, rg).second);
ASSERT_FALSE(edge(a, b, rg).second);
}
TEST(ue2_graph, default_param) {
struct TestGraph : ue2_graph<TestGraph> { };
TestGraph g;
auto v = add_vertex(g);
auto e = add_edge(v, v, g).first;
ASSERT_EQ(0U, get(vertex_index, g, v));
ASSERT_EQ(0U, get(edge_index, g, e));
#if !defined(_MSC_VER)
/* This makes MSVC up to VS2015 sad in ways that shouldn't happen. */
ASSERT_EQ(0U, get(&ue2::graph_detail::default_edge_property::index, g, e));
#endif
}
Reference in New Issue View Git Blame Copy Permalink