Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
prints the assigned colors using Graph Coloring algorithm
More...
#include <iostream>
#include <array>
#include <vector>
|
template<size_t V> |
void | backtracking::printSolution (const std::array< int, V > &color) |
|
template<size_t V> |
bool | backtracking::isSafe (int v, const std::array< std::array< int, V >, V > &graph, const std::array< int, V > &color, int c) |
|
template<size_t V> |
void | backtracking::graphColoring (const std::array< std::array< int, V >, V > &graph, int m, std::array< int, V > color, int v) |
|
int | main () |
|
prints the assigned colors using Graph Coloring algorithm
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
- Author
- Anup Kumar Panwar
-
David Leal
◆ main()
Main function
115 backtracking::graphColoring<V>(
graph, m, color, 0);
void mov(tower *From, tower *To)
Definition: tower_of_hanoi.cpp:39
Combined Intersion-Merge sorting algorithm.
int main()
Definition: knuth_morris_pratt.cpp:76
int main()
Definition: fenwick_tree.cpp:69
void ternary_search(int N, int A[], int target)
Definition: ternary_search.cpp:127
void test3()
Definition: smallest_circle.cpp:188
int main(void)
Definition: decimal_to_hexadecimal.cpp:11
void method2(int number)
Definition: decimal_to_binary.cpp:27
int main()
Definition: exponential_search.cpp:74
ll mat_size
Definition: matrix_exponentiation.cpp:45
int main()
Definition: stairs_pattern.cpp:17
int hash_search(int key, int *counter)
Definition: hash_search.cpp:76
void shell_sort(T *arr, size_t LEN)
Definition: shell_sort2.cpp:45
int main()
Definition: fibonacci_search.cpp:123
std::string tolowerRoman(int n)
Definition: decimal_to_roman_numeral.cpp:24
void test_f(const int NUM_DATA)
Definition: shell_sort2.cpp:145
String search algorithms.
Definition: brute_force_string_searching.cpp:13
X chain_query(int a, int b)
Utility function to break down a path query into two chain queries.
Definition: heavy_light_decomposition.cpp:409
#define MAX
Definition: fibonacci_fast.cpp:27
std::vector< int > t_size
a vector to store the subtree size rooted at node
Definition: heavy_light_decomposition.cpp:89
void show_data(T *arr, size_t LEN)
Definition: shell_sort2.cpp:18
void dfs_lca(int u, int p=-1)
Utility function to populate the t_par vector.
Definition: heavy_light_decomposition.cpp:116
void heapSort(T *arr, int n)
Definition: heap_sort.cpp:84
int t_root
the root of the tree
Definition: heavy_light_decomposition.cpp:91
int main()
Definition: binomial_dist.cpp:84
double addition_rule_dependent(double A, double B, double B_given_A)
Definition: addition_rule.cpp:25
const int t_maxlift
maximum possible height of the tree
Definition: heavy_light_decomposition.cpp:85
int lca(int a, int b)
The function returns the least common ancestor of two nodes.
Definition: heavy_light_decomposition.cpp:229
void set_node_val(const std::vector< X > &node_val)
Set the values for all the nodes.
Definition: heavy_light_decomposition.cpp:175
void test2()
Definition: smallest_circle.cpp:173
void init()
This function must be called after the tree adjacency list and node values are populated The function...
Definition: heavy_light_decomposition.cpp:186
static void test_3()
Definition: heavy_light_decomposition.cpp:592
A Basic Tree, which supports binary lifting.
Definition: heavy_light_decomposition.cpp:78
void update(int p, X v)
Update the value at a node.
Definition: heavy_light_decomposition.cpp:293
Tree(int nodes)
Class parameterized constructor, resizes the and initializes the data members.
Definition: heavy_light_decomposition.cpp:140
bool random_tests()
random tests which cover cases when we have one, multiple or zero occurences of the value we're looki...
Definition: fibonacci_search.cpp:96
X sret_init
inital query return value
Definition: heavy_light_decomposition.cpp:264
double x
Definition: smallest_circle.cpp:16
static void test_2()
Definition: heavy_light_decomposition.cpp:549
int main()
Definition: decimal_to_roman_numeral.cpp:90
std::array< int, N > pigeonSort(std::array< int, N > arr)
Definition: pigeonhole_sort.cpp:34
int sum_range(int l, int r)
Definition: fenwick_tree.cpp:65
void test()
Definition: heap_sort.cpp:99
#define absolutePrecision
Definition: ternary_search.cpp:22
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
void init()
This function must be called after the tree adjacency list and node values are populated The function...
Definition: heavy_light_decomposition.cpp:450
X combine(X lhs, X rhs)
Function that specifies the type of operation involved when segments are combined.
Definition: heavy_light_decomposition.cpp:274
Definition: fenwick_tree.cpp:17
void add_edge(const int u, const int v)
Adds an undirected edge from node u to node v in the tree.
Definition: heavy_light_decomposition.cpp:157
int main()
Definition: gnome_sort.cpp:130
void insertionSort(T *arr, int n)
Insertion Sort Function.
Definition: insertion_sort.cpp:59
#define HASHMAX
Determines the length of the hash table.
Definition: hash_search.cpp:22
#define PRIME
Prime modulus for hash functions.
Definition: rabin_karp.cpp:16
int partition(int arr[], int low, int high)
Definition: quick_sort.cpp:37
Type * binary_s(Type *array, size_t size, Type key)
Definition: exponential_search.cpp:34
Definition: avltree.cpp:13
double y
Definition: smallest_circle.cpp:17
int FindNextGap(int gap)
Definition: comb_sort.cpp:29
#define MAX
Determines how much data.
Definition: hash_search.cpp:21
int main()
Definition: pascal_triangle.cpp:52
int main()
Definition: bayes_theorem.cpp:26
vector< vector< ll > > multiply(const vector< vector< ll >> &A, const vector< vector< ll >> &B)
Definition: matrix_exponentiation.cpp:57
static void test_double()
Definition: quick_sort_3.cpp:160
static void test()
Definition: gnome_sort.cpp:85
int main(void)
Definition: qr_decomposition.cpp:23
int main()
Definition: palindrome_of_number.cpp:19
int main()
Definition: vector_important_functions.cpp:11
void merge(Iterator, Iterator, const Iterator, char[])
merges 2 sorted adjacent segments into a larger sorted segment
Definition: non_recursive_merge_sort.cpp:57
std::array< T, N > shuffle(std::array< T, N > arr)
Definition: bogo_sort.cpp:36
int main()
Definition: linear_search.cpp:27
void update(int node, X val)
This function updates the value at node with val.
Definition: heavy_light_decomposition.cpp:475
static float eqd(float y)
Definition: successive_approximation.cpp:17
void show_array(const std::array< T, N > &arr)
Definition: bogo_sort.cpp:68
SG(int size)
Class parameterized constructor. Resizes the and initilizes the data members.
Definition: heavy_light_decomposition.cpp:282
std::string fill(char c, int n)
Definition: decimal_to_roman_numeral.cpp:15
void mat_mul(const std::valarray< std::valarray< double >> &A, const std::valarray< std::valarray< double >> &B, std::valarray< std::valarray< double >> *OUT)
Definition: qr_eigen_values.cpp:54
int64_t create_hash(const std::string &s, int n)
Definition: rabin_karp.cpp:25
int stack_idx
pointer to track stack index
Definition: paranthesis_matching.cpp:23
int main(int argc, char *argv[])
Definition: shell_sort2.cpp:183
The Heavy-Light Decomposition class.
Definition: heavy_light_decomposition.cpp:336
int main()
Definition: interpolation_search2.cpp:32
int compare(const void *a, const void *b)
Definition: shell_sort2.cpp:87
int brute_force(const std::string &text, const std::string &pattern)
Definition: brute_force_string_searching.cpp:21
int main()
Definition: buzz_number.cpp:9
int fibonacci_search(const std::vector< int > &arr, int value)
using fibonacci search algorithm finds an index of a given element in a sorted array
Definition: fibonacci_search.cpp:23
Functions to compute QR decomposition of any rectangular matrix.
void lift(int *const p, int dist)
The function lifts a node, k units up the tree. The lifting is done in place, and the result is store...
Definition: heavy_light_decomposition.cpp:200
int offset(int x)
Definition: fenwick_tree.cpp:22
void create_matrix(std::valarray< std::valarray< double >> *A)
Definition: qr_eigen_values.cpp:28
int main()
Definition: happy_number.cpp:29
int main()
Definition: text_search.cpp:15
void show(int *arr, int size)
Definition: merge_sort.cpp:96
const std::vector< std::vector< std::string > > test_set
Definition: brute_force_string_searching.cpp:41
int rec_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:90
Definition: linkedlist_implentation_usingarray.cpp:14
int main()
Definition: pigeonhole_sort.cpp:127
int y
Point respect to x coordinate.
Definition: line_segment_intersection.cpp:14
std::valarray< double > eigen_values(std::valarray< std::valarray< double >> *A, bool print_intermediates=false)
Definition: qr_eigen_values.cpp:98
int64_t recalculate_hash(const std::string &s, int old_index, int new_index, int64_t old_hash, int patLength)
Definition: rabin_karp.cpp:42
int main()
Definition: smallest_circle.cpp:198
void test_int(const int NUM_DATA)
Definition: shell_sort2.cpp:105
void dfs_par(int u, int p=-1)
Utility function to assign highest parent that can be reached though heavy chains.
Definition: heavy_light_decomposition.cpp:371
int ** pascal_triangle(int **arr, int n)
Definition: pascal_triangle.cpp:36
void CombSort(int *arr, int l, int r)
Definition: comb_sort.cpp:42
void quicksort(std::vector< T > *arr, int32_t low, int32_t high)
Definition: quick_sort_3.cpp:94
node * insert(node *root, int item)
Definition: avltree.cpp:66
std::vector< int > h_heavychlid
stores the heavy child of a node
Definition: heavy_light_decomposition.cpp:340
FenwickTree(const std::vector< int > &arr)
Definition: fenwick_tree.cpp:28
void mergeSort(int *arr, int l, int r)
Definition: merge_sort.cpp:83
int main()
Definition: matrix_exponentiation.cpp:126
std::vector< std::list< int > > t_adj
an adjacency list to stores the tree edges
Definition: heavy_light_decomposition.cpp:83
std::vector< X > s_tree
Everything here is private, and can only be accessed through the methods, in the derived class (HLD)
Definition: heavy_light_decomposition.cpp:262
Library functions to compute QR decomposition of a given matrix.
void merge(int *arr, int l, int m, int r)
Definition: merge_sort.cpp:33
int kth_ancestor(int p, const int &dist)
The function returns the kth ancestor of a node.
Definition: heavy_light_decomposition.cpp:218
static void create_random_array(T *arr, int N)
Create a random array objecthelper function to create a random array.
Definition: insertion_sort.cpp:101
int h(int key)
Definition: hash_search.cpp:45
void non_recursive_merge_sort(const Iterator first, const Iterator last)
bottom-up merge sort which sorts elements in a non-decreasing order
Definition: non_recursive_merge_sort.cpp:86
void update(int id, int val)
Definition: fenwick_tree.cpp:45
int main(int argc, char const *argv[])
Definition: binary_search.cpp:31
Definition: tower_of_hanoi.cpp:11
#define _target
Definition: ternary_search.cpp:27
void test()
Definition: bogo_sort.cpp:78
int binary_search(int a[], int r, int key)
Definition: binary_search.cpp:15
const int t_nodes
number of nodes
Definition: heavy_light_decomposition.cpp:84
char opening(char ch)
Definition: paranthesis_matching.cpp:36
void dfs_hc(int u, int p=-1)
Utility function to assign heavy child to each node (-1 for a leaf node)
Definition: heavy_light_decomposition.cpp:350
bool is_happy(T n)
Definition: happy_number.cpp:14
bool check_if_equal(const std::string &str1, const std::string &str2, int start1, int end1, int start2, int end2)
Definition: rabin_karp.cpp:60
int main()
Definition: ternary_search.cpp:134
double binomial_range_successes(double n, double p, double lower_bound, double upper_bound)
Definition: binomial_dist.cpp:74
double LenghtLine(const Point &A, const Point &B)
Definition: smallest_circle.cpp:37
bool kmp(const std::string &pattern, const std::string &text)
Definition: knuth_morris_pratt.cpp:56
double poisson_range_successes(double expected, double lower, double upper)
Definition: poisson_dist.cpp:54
int main()
Definition: tower_of_hanoi.cpp:65
void non_recursive_merge_sort(const Iterator first, const Iterator last, const size_t n)
bottom-up merge sort which sorts elements in a non-decreasing order
Definition: non_recursive_merge_sort.cpp:25
int label
utility member to assign labels in dfs_labels()
Definition: heavy_light_decomposition.cpp:338
#define ll
Definition: matrix_exponentiation.cpp:33
double binomial_standard_deviation(double n, double p)
Definition: binomial_dist.cpp:36
static void test_1()
Definition: pigeonhole_sort.cpp:68
void gnomeSort(T *arr, int size)
Definition: gnome_sort.cpp:34
std::vector< std::vector< int > > t_par
a matrix to store every node's 2^kth parent
Definition: heavy_light_decomposition.cpp:87
double TriangleArea(const Point &A, const Point &B, const Point &C)
Definition: smallest_circle.cpp:54
int main()
Definition: brute_force_string_searching.cpp:47
double binomial_x_successes(double n, double p, double x)
Definition: binomial_dist.cpp:65
void test2()
Definition: qr_eigen_values.cpp:210
#define endl
Definition: matrix_exponentiation.cpp:36
struct list * link
pointer to nodes
void spiralPrint(int **a, int r, int c)
Definition: spiral_print.cpp:29
double bayes_BgivenA(double AgivenB, double A, double B)
Definition: bayes_theorem.cpp:20
int main()
Definition: quick_sort_3.cpp:183
vector< ll > fib_b
Definition: matrix_exponentiation.cpp:50
double poisson_rate(double events, double timeframe)
Definition: poisson_dist.cpp:17
int key
key value for node
Definition: hash_search.cpp:30
int main(int argc, char **argv)
Definition: qr_eigen_values.cpp:243
double circle(const std::vector< Point > &P)
Definition: smallest_circle.cpp:87
static void test()
Function with test cases for Horspool's algorithm.
Definition: horspool.cpp:100
void print(uint32_t N, const std::vector< bool > &is_prime)
Definition: sieve_of_eratosthenes.cpp:44
static float eq(float y)
Definition: successive_approximation.cpp:12
static void test_int()
Definition: quick_sort_3.cpp:138
Type * struzik_search(Type *array, size_t size, Type key)
Definition: exponential_search.cpp:59
int main()
Definition: poisson_dist.cpp:65
double binomial_expected(double n, double p)
Definition: binomial_dist.cpp:22
int main()
Definition: heap_sort.cpp:120
node hashtab[HASHMAX]
array of nodes
Definition: hash_search.cpp:35
Heavy light decomposition algorithm.
int it_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:48
int jumpSearch(int arr[], int x, int n)
Definition: jump_search.cpp:12
int data[MAX]
test data
Definition: hash_search.cpp:24
void method1(int number)
Definition: decimal_to_binary.cpp:11
void test1()
Definition: qr_eigen_values.cpp:177
bool no_occurence_tests()
random tests for checking performance when an array doesn't contain an element
Definition: fibonacci_search.cpp:72
static void test_1()
Definition: heavy_light_decomposition.cpp:505
X query(int l, int r)
Make a range query from node label l to node label r.
Definition: heavy_light_decomposition.cpp:305
void dfs_labels(int u, int p=-1)
Utility function to lable the nodes so that heavy chains have a contigous lable.
Definition: heavy_light_decomposition.cpp:390
void printArray(T *arr, int sz)
Definition: heap_sort.cpp:37
int main()
Definition: hash_search.cpp:99
std::vector< X > t_val
values of nodes
Definition: heavy_light_decomposition.cpp:92
int s_size
number of leaves in the segment tree
Definition: heavy_light_decomposition.cpp:263
int main()
Main function.
Definition: merge_insertion_sort.cpp:159
static void test_3()
Definition: pigeonhole_sort.cpp:109
void create_list(int key)
Definition: hash_search.cpp:55
double fact(double x)
Definition: poisson_dist.cpp:30
int main()
Main Function that calls test function.
Definition: horspool.cpp:119
void set_sret_init(X new_sret_init)
Set the initialization for the query data type, based on requirement.
Definition: heavy_light_decomposition.cpp:329
Segment Tree, to store heavy chains.
Definition: heavy_light_decomposition.cpp:254
int main()
Definition: heavy_light_decomposition.cpp:634
double addition_rule_independent(double A, double B)
Definition: addition_rule.cpp:14
std::array< T, N > randomized_bogosort(std::array< T, N > arr)
Definition: bogo_sort.cpp:51
void show(const struct tower *const F, const struct tower *const T, const struct tower *const U)
Definition: tower_of_hanoi.cpp:19
int main()
Definition: sparse_matrix.cpp:9
void test()
Definition: smallest_circle.cpp:158
Algorithms and Data Structures that support range queries and updates.
Definition: huffman.cpp:28
int main()
Definition: spiral_print.cpp:69
#define MAX
Definition: paranthesis_matching.cpp:16
vector< vector< ll > > power(const vector< vector< ll >> &A, ll p)
Definition: matrix_exponentiation.cpp:76
static void InsertionSort(std::array< T, N > *A, size_t start, size_t end)
Insertion merge algorithm.
Definition: merge_insertion_sort.cpp:37
int main()
Definition: successive_approximation.cpp:20
std::vector< int > h_parent
stores the top of the heavy chain from a node
Definition: heavy_light_decomposition.cpp:341
void tests()
Definition: insertion_sort.cpp:109
X query(int a, int b)
This function returns the sum of node values in the simple path from from node_1 to node_2.
Definition: heavy_light_decomposition.cpp:489
int LinearSearch(int *array, int size, int key)
Definition: linear_search.cpp:16
bool IsPrime(int number)
Definition: primality_test.cpp:18
double nCr(double n, double r)
Definition: binomial_dist.cpp:47
int values[10]
Values in the tower.
Definition: tower_of_hanoi.cpp:13
void qr_decompose(const std::valarray< std::valarray< T >> &A, std::valarray< std::valarray< T >> *Q, std::valarray< std::valarray< T >> *R)
Definition: qr_decompose.h:146
int main()
Definition: insertion_sort.cpp:150
void genArray(int **a, int r, int c)
Definition: spiral_print.cpp:12
int main()
Definition: comb_sort.cpp:88
static std::ostream & operator<<(std::ostream &out, matrix< T > const &v)
Definition: hill_cipher.cpp:54
void dfs_size(int u, int p=-1)
Utility function to compute sub-tree sizes.
Definition: heavy_light_decomposition.cpp:101
int main()
Definition: interpolation_search.cpp:37
std::string add(std::string a, std::string b)
Definition: string_fibonacci.cpp:24
int main()
Definition: addition_rule.cpp:30
std::string toupperRoman(int n)
Definition: decimal_to_roman_numeral.cpp:58
#define LIMS
Definition: qr_eigen_values.cpp:20
double bayes_AgivenB(double BgivenA, double A, double B)
Definition: bayes_theorem.cpp:14
int sum(int id)
Definition: fenwick_tree.cpp:54
int main()
Definition: quick_sort.cpp:82
static void test()
Function to test code using random arrays.
Definition: merge_insertion_sort.cpp:132
void change_root(int new_root)
Set the root for the tree.
Definition: heavy_light_decomposition.cpp:167
FenwickTree(int x)
Definition: fenwick_tree.cpp:39
Point(double a=0.f, double b=0.f)
Definition: smallest_circle.cpp:23
int main()
Definition: primality_test.cpp:31
std::vector< int > h_label
stores the label of a node
Definition: heavy_light_decomposition.cpp:339
struct list * next
pointer to next link in the chain
Definition: hash_search.cpp:31
int top
top tower ID
Definition: tower_of_hanoi.cpp:15
Definition: line_segment_intersection.cpp:12
void TH(int n, tower *From, tower *Using, tower *To)
Definition: tower_of_hanoi.cpp:52
int interpolation_search(int arr[], int value, int len)
Definition: interpolation_search.cpp:15
void push(char ch)
push byte to stack variable
Definition: paranthesis_matching.cpp:26
int main()
Definition: bogo_sort.cpp:104
static void test_2()
Definition: pigeonhole_sort.cpp:88
int main()
Definition: merge_sort.cpp:102
char pop()
pop a byte out of stack variable
Definition: paranthesis_matching.cpp:29
int InterpolationSearch(int A[], int n, int x)
Definition: interpolation_search2.cpp:15
Functions for Horspool's algorithm.
double poisson_expected(double rate, double time)
Definition: poisson_dist.cpp:25
double poisson_x_successes(double expected, double x)
Definition: poisson_dist.cpp:46
int main(void)
Definition: rabin_karp.cpp:105
T random_shuffle(T... args)
void quickSort(int arr[], int low, int high)
Definition: quick_sort.cpp:63
std::vector< int > getFailureArray(const std::string &pattern)
Definition: knuth_morris_pratt.cpp:33
void show_pascal(int **arr, int n)
Definition: pascal_triangle.cpp:18
int rabin_karp(const std::string &str, const std::string &pat)
Definition: rabin_karp.cpp:83
void get_input()
Definition: ternary_search.cpp:36
bool PointInCircle(const std::vector< Point > &P, const Point &Center, double R)
Definition: smallest_circle.cpp:72
void tests()
Definition: comb_sort.cpp:73
Definition: list_array.cpp:8
std::unordered_map< char, int > findShiftTable(const std::string &prototype)
Definition: horspool.cpp:26
std::vector< int > t_depth
a vector to store the depth of a node,
Definition: heavy_light_decomposition.cpp:88
double binomial_variance(double n, double p)
Definition: binomial_dist.cpp:29
T sum(const std::vector< std::valarray< T >> &A)
Definition: vector_ops.hpp:232
int main()
Definition: graph_coloring.cpp:96
void shell_sort(std::vector< T > *arr)
Definition: shell_sort2.cpp:75