dradestGraph/main.cpp at master · dRadest/dradestGraph · 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
#include <iostream>
#include <vector>
#include "dradest_graph.h"

// demonstrating functionality of dradest graph
int main()
{
	// construct a graph
	dradestGraph graph(5);
	// add edges
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(2, 3);
	graph.addEdge(3, 1);
	graph.addEdge(0, 4);
	graph.addEdge(1, 4);
	graph.addEdge(3, 4);
	graph.addEdge(4, 0); // testing inserting duplicate

	/*** constructed graph

			0
		   / \
		  4___1
		   \  |\
		    \ | 2
		     \|/
		      3

    ********************/

    // print adjacency list of each node
    graph.printGraph();

    // perform breadth first search
    graph.BFS(0);
    graph.BFS(3);
    graph.BFS(5); // invalid node

    // preform depth first search
    graph.iterativeDFS(0);
    std::vector<int> idfs = graph.iterativeDFS(3);
    graph.iterativeDFS(5); // invalid node

    graph.recursiveDFS(0);
    std::vector<int> rdfs = graph.recursiveDFS(3);
    graph.recursiveDFS(5); // invalid node

    std::cout << "do iterative and recursive approach yield same result? " << (idfs==rdfs ? "yes" : "no") << "\n";

    // use DFS to check if graph contains a cycle
    std::cout << "DFS check for cycle returns: " << graph.hasCycle() << "\n";

    // use union find to check if the graph contains a cycle
    std::cout << "UF check for cycle in cyclic graph returns: " << graph.containsCycle() << "\n";

    // construct acyclic graph
    dradestGraph dg(6);
    dg.addEdge(0,1);
    dg.addEdge(0,2);
    dg.addEdge(2,5);
    dg.addEdge(2,3);
    dg.addEdge(2,4);
    dg.addEdge(4,6); // safety check for index out of bounds

    /*** constructed graph

    	0
       / \
      1   2
         /|\
        3 4 5

    *********************/

    // print acyclic graph adjacency list
    dg.printGraph();

    std::cout << "UF check for cycle in acyclic graph returns: " << dg.containsCycle() << "\n";

    std::vector<int>* wadj;
    // perform Prim's algorithm
    wadj = graph.primMST();
    // print found MST
    std::cout << "MST using Prim's algorithm has following edges\n";
    for(int i=0; i<5; ++i)
    {
    	if(!wadj[i].empty())
    	{
    		for(auto it=wadj[i].begin(); it!=wadj[i].end(); ++it)
    		{
    			std::cout << i << " -> " << *it << "\n";
    		}
    	}
    }
    // perform Kruskal's algorithm
    wadj = graph.kruskalMST();
    std::cout << "MST using Kruskal's algorithm has following edges\n";
    for(int i=0; i<5; ++i)
    {
    	if(!wadj[i].empty())
    	{
    		for(auto it=wadj[i].begin(); it!=wadj[i].end(); ++it)
    		{
    			std::cout << i << " -> " << *it << "\n";
    		}
    	}
    }

    // perform Dijkstra's algorithm
    graph.dijkstraSPT(0);
    graph.dijkstraSPT(2);
    dg.dijkstraSPT(0);
    dg.dijkstraSPT(4);

    // testing out copy constructor
    dradestGraph dg_copy = dg;
    dg_copy.addEdge(3, 4);
    dg.printGraph();
    dg_copy.printGraph();

    return 0;
}