topological sort using queue in a graph
This Algorithm is of topological sort using queue written in my Text book
Can anyone tell me why my algorithm is failing if this algorithm is partially incorrect if you think then Please make the required changes and I know that we can also implement topological sort using
DFS
,but i want to implement the below algorithm
void topologicalsort(struct Graph* G){
struct queue* Q;
int counter;
int v,w;
Q=createqueue();
counter=0;
for(v=0;v<G>V;v++){
if(indegree[v]==0)
enqueue(Q,v);
while(!isemptyqueue(Q)){
v=dequeue(Q);
topologicalorder[v]=++counter;
for each w to adjacent to v
if(indegree[w]==0){
enqueue(Q,w);
}
}
}
}
if in the given graph initially 7 5 3 has indegree zero then they will be inserted in the queue but for any of the vertices adjacent to 7 5 3
we are not having any vertex with degree 1 This imply if(indegree[w]==0)
will not hold true for 7 5 3
hence there will be no further enqueue inside queue hence algorithm will not process further vertices and graph is also DAG then i want to ask why this algorithm is failing
Note> Algorithm is failing for above graph
1 answer

Your algorithm implementation is incorrect. Here
while(!isemptyqueue(Q))
isn't under thefor(v=0;v<G>V;v++)
(See the indentation in the algorithm). See below for more clarification:void topologicalsort(struct Graph* G){ struct queue* Q; int counter; int v,w; Q=createqueue(); counter=0; for(v=0;v<G>V;v++){ if(indegree[v]==0) enqueue(Q,v); } while(!isemptyqueue(Q)){ v=dequeue(Q); topologicalorder[v]=++counter; for each w to adjacent to v { if(indegree[w]==0){ enqueue(Q,w); } } } }
This will work for every DAG.
See also questions close to this topic

Drawing AImage onto ANativeWindow
How can I draw an AImage onto a ANativeWindow in the Android NDK. I was following the steps in this guide (although I left out the OpenGL parts), however I am under the impression that the guide left out some crutial parts (mostly because I pretty much have identical code but the captured image is not being rendered).

strncpy() in loop removes all values from an array of strings
I have the below descending order insertion sort algorithm. I am trying to sort an array of names as well as an array of numbers at the same time. Before I do this I have two arrays looking like this:
scores = [0,0,0,0,0,7] names = [null,null,null,null,null,"James"]
After I do this, I have two arrays looking like this:
scores = [7,0,0,0,0,0] names = [null,null,null,null,null,null]
For some reason my value in the names array has disappeared. The expected output is the below:
scores = [7,0,0,0,0,0] names = ["James",null,null,null,null,null]
uint8_t scores[6]; uint8_t names[6][13]; static void sort_in_highscore(void) { uint8_t k, temp; int8_t j; for (k=1; k < 6; k++) { temp = scores[k]; j = k  1; while (j >= 0 && temp > scores[j]) { scores[j+1] = scores[j]; strncpy((char*)names[j+1], (const char*)names[j], 12); j; } scores[j+1] = temp; } }

Problem with manage memory and Valgrind message
I work on School task, where I have to manage memory in C. Basically I need to allocate memory pages with mmap and then free the space with munmap. But now when I run test with Valgrind on our school test page I get this error, which I have no idea that it means.
If anybody could help, I'll be very thankfull.

Maximum sum of elements in each interval
Array of size n, size of interval k and x amount of wanted elements Problem is to find maximum sum of x elements such that there is at least one element in such interval, so there needs to be at least one in each window of size k
1<=n<=5000, 1<=x<=n, 1<=k<=n
I've solved it with complexity O(nkx) but it's to slow and I need at least O(n*log(k)*x)
[19, 1, 22, 10, 1, 5, 50, 8, 10, 99, 100] n = 11, k = 3, x = 4
answer is 181 becouse we pick 22, 10, 50, 99 we can't pick 100 instead of 99 becouse then distance between 50 and 100 is more then k

Numbers which constitute the Maximum sum
I Just wrote my program which finds out the maximum sum from the array. But i am struck in is there any way by which i can find which numbers constitued to the max sum??
Rule of Maximum sum is given: No adjacent elements should constitute to sum.
My solution to maximum sum in array:
public class MaximumELementInARray { public static void main(String[] args) { Scanner reader = new Scanner(System.in); String[] al = reader.nextLine().split(" "); int[] input = Arrays.stream(al).mapToInt(Integer::parseInt).toArray(); MaximumELementInARray mm = new MaximumELementInARray(); int maxi = mm.maximumm(input); System.out.println(maxi); } public int maximumm(int[] a) { List<Integer> ex = new ArrayList<>(); List<Integer> inc = new ArrayList<>(); int incl = a[0]; int excl = 0; int excl_new; for (int i = 1; i < a.length; i++) { excl_new = Math.max(incl, excl); incl = excl + a[i]; excl = excl_new; } System.out.println(incl > excl ? inc : ex); return incl > excl ? incl : excl; } }
Now in the
maximum
function is there a tweak where i can put all the index of elements which constituted to the maximum sum??Input:
1,7,8,5,4,9,2,3
Output:
20
**
I require how 20 came?? The answer should say
8+9+3
**
i believe that in maximum function we could put a Arraylist and record which which elemenst are constituting to sum, but i am not able to implement. I have made two Arraylist :
List<Integer> ex = new ArrayList<>(); List<Integer> inc = new ArrayList<>();

Find the axis around which there is the most rotation?
Given a 3d rotation, is there a way to compute the axis around which the largest component of the rotation happens?
To ground this in the actual task I'm attempting: I am getting data from a smartphone gyroscope and I want to figure out what axis the user is turning their phone around but without knowing anything other than the absolute rotation. This is using Java and Android.

Sorting Json data between name and cost with Jquery?
Hi i have this function which retrieves the product names and costs and inputs them into my html. I want to be able to sort between name and cost by either clicking the "Product" heading, or the "Cost" heading. I have figured out how to sort my products by name but thats in the function without the click feature. This is what i have so far with my code that just sorts the data by alphabetical order
function drawPage() { $.get('/products', function (data) { console.log(data); var prod = data.products; prod.sort(function(a, b){ var x = a.name.toLowerCase(); var y = b.name.toLowerCase(); if (x < y) {return 1;} if (x > y) {return 1;} return 0; }); for(var i=0; i<prod.length; i++){ var el = document.createElement('P'); el.innerHTML = prod[i].name; var al = document.createElement('P'); al.innerHTML = prod[i].unit_cost; $('#app').append(el); $('#costof').append(al); } }) } document.addEventListener('load', drawPage()); <div class="row"> <div class="column"> <div id="app"> Product </div> </div> <div class="column"> <div id="costof"> Cost </div> </div> </div>
My Jquery code is above aswell as my Html code
I want to be able to toggle between sorting by costs and sorting by product name but i cant figure it out.
Thanks

How to sort multilevel index on column values
I'm trying to sort data in a multilevel index for visualisation. At this point it is purely to order the data based on the values
I've tried working with sort_index and sort_values, however neither have worked. I'm assuming there is a way to combine the 2 that is not clear to me.
Example code
import pandas as pd data = {'lev1':[1,1,2,2], 'lev2':['item1', 'item2', 'item3', 'item2'], 'col1':[.55, .44, .22, .34], 'col2':[.54, .86, .55, .44]} df = pd.DataFrame(data=data) df.set_index(['lev1', 'lev2'], inplace=True)
This should result in :
col1 col2 lev1 lev2 1 item1 0.55 0.54 item2 0.44 0.86 2 item3 0.22 0.55 item2 0.34 0.44
What I would like to see is the output ordered based on the values in col2. However, keeping the multilevel index intact.
Meaning, the results should show:
col1 col2 lev1 lev2 1 item2 0.44 0.86 item1 0.55 0.54 2 item3 0.22 0.55 item2 0.34 0.44
Any ideas or suggestions are welcome.
Thank you!

How to make my code sort data fetch'ed as JSON text from Reddit?
[Sort array of object by property value]
I want to compare the amount of upvotes and sort, but I have a problem with understanding how to get to the object "ups" from my api. I created the compare function and I want to call it. I probably call it on the wrong object.
function fetchData(url) { return fetch(url).then((resp) => resp.json()); } function createTableRow(data) { const tableRow = document.createElement('tr'); const { title, ups, downs, score, num_comments, created } = data; console.log(ups); tableRow.appendChild(createElement('td', title)) tableRow.appendChild(createElement('td', ups)) tableRow.appendChild(createElement('td', downs)) tableRow.appendChild(createElement('td', score)) tableRow.appendChild(createElement('td', num_comments)) tableRow.appendChild(createElement('td', created)) return tableRow; } function createElement(tag_name, text) { const el = document.createElement(tag_name); const content = document.createTextNode(text); el.appendChild(content); return el; } **function compare(a,b) { if(a.ups<b.ups) { return 1; } if(a.ups>b.ups){ return 1; } return 0; }** const butt = document.getElementById('button'); const swTable = document.getElementById('sw_table').getElementsByTagName('tbody')[0]; fetchData('https://www.reddit.com/r/funny.json') .then(data => { data.data.children.forEach(result => { const table = createTableRow(result.data); swTable.appendChild(table); // butt.onclick(sortData(ups)); **data.data.children.ups.sort(compare);** }); });
Error: Uncaught (in promise) TypeError: Cannot read property 'sort' of undefined

Dynamic Programming Problem "Total rating must be highest after buying players with input price"
Players Input Table The problem is making total rating maximum , while buying one player from each position with some price. For example 29000€. You can use 27000€ but you can't use 29001€.
Note: You can only buy one player from each positions so if there are 6 positions and each position has 10 players , count of all possibilities is 11^6
All i can see is knapsack problem but i think there should be some great solution for this problem.
I already tried knapsack algorithm but it didn't work well for bigger inputs like 11 positions and each position have 50 players to check.
int DP() { int price = 29000; int positions = 3; // I tried this approach , it is unfinished though. int players = 3; int ratings[][] = new int[positions][players]; int prices[][] = new int[positions][prices]; int K[][][] = new int[positions][price][players]; for(int i = 0; i <= positions; i++) { for(int j = 0; j<=players; j++) { for(int w = 0; w<=price; w++) { if(i==0j==0w==0) // Base case. K[i][j][w]=0; else if(prices[i1][w1] <=w) K[i][j][w] = max(ratings[i1][j1] + K[i1][j1][wprice[i1][j1]], K[i1][j1][w]; else K[i][j][w] = K[i1][j1][w]; } } } return K[positions][players][price]; }
Example Output:
Enter the amount to spend (X): 100 000 Enter the number of the positions (N): 6 //The first N position Enter the number of the available players for each position (K): 5 // The first K players of each position DP results: Total ratings : 547 Total cost: 98 925 Players: 1Gianfranco Zola 2Jimmy Floyd Hasselbaink 3... 4...

Struct containing references to self OR other struct type?
I wish to use structures to create a datatype which contains other references of an array of the structure itself OR structures of another type. Using templates will obviously result in an infinite declaration of the type itself when the reference is of same generic type. My current solution is to explicitly declare another struct type and the struct type of itself. I was wondering if there was a more clever solution (using structs).
struct Transform { float x; float y; float z; float qx; float qy; float qz; float qw; }; struct Pattern { enum type{ linear, rectangular, circular }; char name[20]; int id; Transform t[PATTERN_SIZE]; }; struct Group { enum type{ pattern, group }; char name[20; int id; Group *g[20]; Pattern *p[20]; };

Minimal coin change with better time complexity (I used top down approach) I want to know bottom up approach
The problem wants user to return a list of minimal coins as a change. For example , [.01, .10, .25] , .40 should return [.10, .10, .10,.10] but not [.25,.1,.01,.01,.01,.01,.01]
The greedy approach doesn't work. This problem is Dynamic Programming problem. The described solution is O(2^n). How can we optimize it to O(n^2) or better with bottom up approach?
class CoinChange { public static List<Double> findMinRefundCombination(List<Double> inputCoins, double refundToMake) { List<Double> minCoins = new ArrayList<>(); List<Double> coinsAccumulatedSoFar = new ArrayList<>(); double refundSoFar = 0.0d; findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins,coinsAccumulatedSoFar, 0, refundSoFar); System.out.println(minCoins.size()); return minCoins; } public static void findMinRefundCombinationHelper(List<Double> inputCoins, double refundToMake, List<Double> minCoins, List<Double> coinsAccumulatedSoFar, int curIndex, double refundSoFar) { if(refundSoFar > refundToMake  curIndex == inputCoins.size()) { return; } if(refundSoFar == refundToMake) { if(minCoins.isEmpty()) { for(Double coin: coinsAccumulatedSoFar) minCoins.add(coin); } else { if(coinsAccumulatedSoFar.size() < minCoins.size()) { minCoins.clear(); for(Double coin: coinsAccumulatedSoFar) minCoins.add(coin); } } } coinsAccumulatedSoFar.add(inputCoins.get(curIndex)); findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar,curIndex,refundSoFar + inputCoins.get(curIndex)); findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar + inputCoins.get(curIndex)); coinsAccumulatedSoFar.remove(coinsAccumulatedSoFar.size()  1); findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar); } public static void main(String[] args) { List<Double> inputCoins = new ArrayList<>(); inputCoins.add(.01); // inputCoins.add(); inputCoins.add(.10); inputCoins.add(.25); inputCoins.add(0.50); inputCoins.add(1.0); double refundToMake = 0.40; List<Double> minCoins = findMinRefundCombination(inputCoins, refundToMake); for(Double coin: minCoins) System.out.print(coin + " "); System.out.println(); } }

How to plot multidimensional array and twodimensional array in R
Suppose I have two arrays [100x100x100] and [100x100]
Can I plot them together? Thanks

Creating a 3D graph out of 3 lists that contain recurring values
I'm new to python. I'm working on a machine learning problem in which I value my models by their accuracy given a theta (learning rate) and a number of epochs. How can I create a clear 3D graph that will represent a 2 argument function like the following: f(theta, num of epochs) = accuracy. I want to clarify that each theta runs through all number of epochs therefore for example if: theta values = 0.1, 1 epoch values = 5, 10, 15 then I will value the accuracy of the cartesian product of theta values and epoch values and then I need to plot it.
Here is an example for such lists:
[1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002, 1, 0.1, 0.010000000000000002, 0.0010000000000000002]
[5, 5, 5, 5, 10, 10, 10, 10, 20, 20, 20, 20, 40, 40, 40, 40, 80, 80, 80, 80, 160, 160, 160, 160, 320, 320, 320, 320]
[0.6576355636979362, 0.6494099087220626, 0.6488214366675455, 0.6494219372389003, 0.6606834048104814, 0.6515514473544203, 0.648811721327023, 0.6454677936461672, 0.6567195458772259, 0.6561162694942934, 0.6533700665732143, 0.6503374924243476, 0.6558169444791421, 0.6536837332815182, 0.6479040309410463, 0.6427229786308771, 0.6570221093392181, 0.6497263512419444, 0.652764477013967, 0.6536897475399369, 0.6567246348651186, 0.6485054567829269, 0.6479012551294685, 0.6442506002692537, 0.6625038745703276, 0.6512535102450578, 0.6509463204304359, 0.6494219372389003]

Dijkstra's Algorithm for graph structure
I'm currently trying to learn some graph theory online and from a friend and he's had me working with a specific structure of graph, I now want to implement Dijkstra's algorithm using the struct but i cant figure out how to. I understand the onpaper theory of Dijkstra but cannot interpret it into code
Below is the header file, used to define the graph
typedef struct edge { int to_vertex; float weight; } Edge; typedef struct edgeNode { Edge edge; struct edgeNode *next; } *EdgeNodePtr; typedef struct edgeList { EdgeNodePtr head; } EdgeList; typedef struct graph { int V; int *vertex_types; EdgeList *edges; } Graph;