CXXGraph/test/BellmanFordTest.cpp at c795f4ddbdb2f0531d32bddf13a850b59656ff5b · ZigRazor/CXXGraph · 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
#include "gtest/gtest.h"
#include "CXXGraph.hpp"

// check if algorithm works using a complicated test case
TEST(BellmanFordTest, test_1)
{
    CXXGRAPH::Node<int> node0(0, 0);
    CXXGRAPH::Node<int> node1(1, 1);
    CXXGRAPH::Node<int> node2(2, 2);
    CXXGRAPH::Node<int> node3(3, 3);
    CXXGRAPH::Node<int> node4(4, 4);

    CXXGRAPH::DirectedWeightedEdge<int> edge1(1, node0, node1, 6);
    CXXGRAPH::DirectedWeightedEdge<int> edge2(1, node0, node2, 7);

    CXXGRAPH::DirectedWeightedEdge<int> edge3(1, node1, node2, 8);
    CXXGRAPH::DirectedWeightedEdge<int> edge4(1, node1, node3, -4);
    CXXGRAPH::DirectedWeightedEdge<int> edge5(1, node1, node4, 5);


    CXXGRAPH::DirectedWeightedEdge<int> edge6(1, node2, node4, -3);
    CXXGRAPH::DirectedWeightedEdge<int> edge7(1, node2, node3, 9);

    CXXGRAPH::DirectedWeightedEdge<int> edge8(1, node3, node4, 7);
    CXXGRAPH::DirectedWeightedEdge<int> edge9(1, node3, node0, 2);

    CXXGRAPH::DirectedWeightedEdge<int> edge10(1, node4, node1, -2);
    std::list<const CXXGRAPH::Edge<int> *> edgeSet;
    edgeSet.push_back(&edge1);
    edgeSet.push_back(&edge2);
    edgeSet.push_back(&edge3);
    edgeSet.push_back(&edge4);
    edgeSet.push_back(&edge5);
    edgeSet.push_back(&edge6);
    edgeSet.push_back(&edge7);
    edgeSet.push_back(&edge8);
    edgeSet.push_back(&edge9);
    edgeSet.push_back(&edge10);

    CXXGRAPH::Graph<int> graph(edgeSet);
    CXXGRAPH::BellmanFordResult res = graph.bellmanford(node0, node3);
    ASSERT_TRUE(res.success);
    ASSERT_FALSE(res.negativeCycle);
    ASSERT_EQ(res.errorMessage, "");
    ASSERT_EQ(res.result, -2);
}

// a graph with negative cycle
TEST(BellmanFordTest, test_2)
{
    CXXGRAPH::Node<int> node0(0, 0);
    CXXGRAPH::Node<int> node1(1, 1);
    CXXGRAPH::Node<int> node2(2, 2);
    CXXGRAPH::DirectedWeightedEdge<int> edge1(1, node0, node1, 2);
    CXXGRAPH::DirectedWeightedEdge<int> edge2(2, node1, node2, 3);
    CXXGRAPH::DirectedWeightedEdge<int> edge3(3, node2, node0, -7);
    std::list<const CXXGRAPH::Edge<int> *> edgeSet;
    edgeSet.push_back(&edge1);
    edgeSet.push_back(&edge2);
    edgeSet.push_back(&edge3);
    CXXGRAPH::Graph<int> graph(edgeSet);
    CXXGRAPH::BellmanFordResult res = graph.bellmanford(node0, node2);
    ASSERT_TRUE(res.success);
    ASSERT_TRUE(res.negativeCycle);
    ASSERT_EQ(res.errorMessage, "");
    ASSERT_EQ(res.result, CXXGRAPH::INF_DOUBLE);
}

// UndirectedWeightedEdge
TEST(BellmanFordTest, test_3)
{
    CXXGRAPH::Node<int> node1(1, 1);
    CXXGRAPH::Node<int> node2(2, 2);
    CXXGRAPH::Node<int> node3(3, 3);
    std::pair<const CXXGRAPH::Node<int> *, const CXXGRAPH::Node<int> *> pairNode(&node1, &node2);
    CXXGRAPH::DirectedWeightedEdge<int> edge1(1, pairNode, 1);
    CXXGRAPH::DirectedWeightedEdge<int> edge2(2, node2, node3, 1);
    CXXGRAPH::UndirectedWeightedEdge<int> edge3(3, node1, node3, 6);
    std::list<const CXXGRAPH::Edge<int> *> edgeSet;
    edgeSet.push_back(&edge1);
    edgeSet.push_back(&edge2);
    edgeSet.push_back(&edge3);
    CXXGRAPH::Graph<int> graph(edgeSet);
    CXXGRAPH::BellmanFordResult res = graph.bellmanford(node1, node3);
    ASSERT_TRUE(res.success);
    ASSERT_FALSE(res.negativeCycle);
    ASSERT_EQ(res.errorMessage, "");
    ASSERT_EQ(res.result, 2);
}

// No weighted edge
TEST(BellmanFordTest, test_4)
{
    CXXGRAPH::Node<int> node1(1, 1);
    CXXGRAPH::Node<int> node2(2, 2);
    CXXGRAPH::Node<int> node3(3, 3);
    std::pair<const CXXGRAPH::Node<int> *, const CXXGRAPH::Node<int> *> pairNode(&node1, &node2);
    CXXGRAPH::DirectedWeightedEdge<int> edge1(1, pairNode, 1);
    CXXGRAPH::DirectedWeightedEdge<int> edge2(2, node2, node3, 1);
    CXXGRAPH::DirectedEdge<int> edge3(3, node1, node3);
    std::list<const CXXGRAPH::Edge<int> *> edgeSet;
    edgeSet.push_back(&edge1);
    edgeSet.push_back(&edge2);
    edgeSet.push_back(&edge3);
    CXXGRAPH::Graph<int> graph(edgeSet);
    CXXGRAPH::BellmanFordResult res = graph.bellmanford(node1, node3);
    ASSERT_FALSE(res.success);
    ASSERT_FALSE(res.negativeCycle);
    ASSERT_EQ(res.errorMessage, CXXGRAPH::ERR_NO_WEIGHTED_EDGE);
    ASSERT_EQ(res.result, CXXGRAPH::INF_DOUBLE);
}