C# :: Applying Dijkstra Algorithm To Graphs?
Jan 30, 2015
I'm attempting to build a tool for a Minecraft mod called Thaumcraft. In it, there are various aspects of magic that are used in a little research minigame; basically, you have to link Aspect A to Aspect B by the aspects either used to make them, or the aspects that use them in their creation. I figured the easiest way to find a path from A to B would be to relate them via graph object, the code for which I found here, minus the IEnumerable<T> dependency on the Graph<T> class itself, because that requires I build an IEnumerator<T> class and it seems difficult I can do without.
Must be between MinSteps and MaxSteps (say, between 3 and 5 steps).Must use either a source aspect (as in, the current aspect requires it to be built), or a destination aspect (as in, the current aspect is used in its creation).An aspect requires two other aspects of a lower tier to create it.The only exceptions to the above rule are the Primal aspects, which require no aspects to build them.
Here's my Aspect class:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.IO;
namespace Pathfinder
[code].....
View 2 Replies
ADVERTISEMENT
Feb 28, 2014
So I have been trying to implement the Dijkstra Algorithm for shortest path in a directed graph using adjacency lists, but for I don't know what reason, it doesn't print out the results (prints the minimum distance as 0 to all nodes).
The code I wrote is:
#include <fstream>
#include <functional>
#include <climits>
#include <vector>
#include <queue>
#include <list>
using namespace std;
struct node {
int vertex;
int weight;
[Code] ....
The input data was:
5 7
1 2 10
1 3 2
1 5 100
2 4 3
3 2 5
4 3 15
4 5 5
It means there are 5 nodes, 7 arcs (directed edges), and the arcs exist from node 1 to 2 with the cost of 10, from 1 to 3 with the cost of 2, and so on.
However, the output is wrong. Where the program might fail. I took the main idea from here: [URL] ....
(At the end it gives the idea for Dijkstra's Algorithm using a priority_queue).
View 3 Replies
View Related
Mar 20, 2014
Program to implement Dijkstra's Algorithm. Have Problems storing graph info into linked-list . The input is in the following format
5
1 2 9.0
1 3 12.0
2 4 18.0
2 3 6.0
2 5 20.0
3 5 15.0
0
1 5
The first number is the number of vertexes in the graph. Then next lines up to 0 are the edges of the graph. With the first and second numbers being the vertexes and the third being how far the edge is between them. Trying to read in the data and store the edges into there locations in the List adjacency for that vertex. This example would make a graph with five vertexes with edges from 1 to 2&3. 2 to 4&3&1 etc. It also stores in the opposites ex 2 1 9.0.
When reading it in and printing it back out it seems that it is only storing the last data entered for that vertex. EX. When trying to print out the data read in i only get 1 3 12.0, 2 5 20.0, 3 5 15.0, ( 4 2 18.0, 5 3 15.0 would show up if `if(i<n)` was removed it is there so it does not show duplicate edges).
#include <cstdio>
using namespace std;
struct ListCell {
ListCell* next;
int vertex;
double weight;
ListCell(int v, double w, ListCell* nxt)
[Code] ....
View 5 Replies
View Related
Apr 19, 2012
Code that finds a shortest path in a dense graph, using Dijkstra's algorithm in the simple array version. You write a function
struct listnode shortest path(int n, int s, int t, int *dist)
with
struct listnode f struct listnode * next; int vertexnumber; g ;
Being used to return the list of vertices on the shortest path. Your function has the following arguments:
- n: the number of vertices of the graph,
- s: the start vertex,
- t: the target vertex
- dist: the matrix of edgelengths.
The vertices are numbered from 0 to n -1, so s and t are numbers in that range. dist is a pointer to the n * n matrix of edgelengths; vertices which are not connected will be joined by an edge of length 9999. To access the array element dist[i][j], we can use *(dist + i*n + j). Your function should return the list of vertices on the shortest path from s to t, starting with s and ending with t.
View 4 Replies
View Related
Feb 13, 2013
How a graph can be implemented in the form of a c program?
View 2 Replies
View Related
Mar 21, 2014
I am writing sample programs for graph problems like Dijkstra or Bellman-Ford algorithms. In Dijkstra, for instance, when I input my program a set of vertices and edges, ask to find shortest path from Vertex A to Vertex B, my program currently outputs shortest path from A to B. I want to display graph and have a visualization of the output generated. Is there a way to display nodes and connecting lines? What C++ classes would required achieve this?
View 2 Replies
View Related
Apr 19, 2015
I am currently trying to apply a texture to a sphere I made, and have been following various tutorials. My program no longer crashes (used to be a problem but I figured it out), but the texture isn't being applied to the sphere. I used glut and SOIL to do this, but I am pretty sure that I am missing some necessary code from my own program for the textures to work. Because my program is a bit different from the tutorials though, I can't figure out what it is that I am missing. Below is what I have written to this point. It all compiles, and it successfully displays two objects (a sphere, and a pyramid), but neither object has textures, the pyramid simply has the colors it was set with (supposed to, I want to texture map the sphere first), while the sphere is a solid blue. What am I missing or what do I need to move?
#include <stdio.h>
#include <stdarg.h>
#include <math.h>
#include <stdlib.h>
#include <GL/glew.h>
#include <GL/glut.h>
[code]....
View 9 Replies
View Related
Sep 25, 2012
Objective : Code a game allowing two human players to play tictactoe.
Create 2 classes:
-Create a 3 x 3, 2-D array board class to play the game.
-Player; has a private string name data member and a method that reads the players’ row and column selections from the keyboard.
Create 2 player objects from this class. Name the players Orestes and Xerxes.
Think carefully about board and player classes responsibilities and how they interaction with one another. The players do not collaborate with one another but they collaborate with the board.
My Problem : The program compiles with the header file, but it the displaying is wrong as you will see when you enter your row and column.
Sources
Header file:
Code:
#include <iostream>
#include <string>
using namespace std;
class Board {
public:
void display(char Z[][3], int row, int col);
[Code] ....
View 1 Replies
View Related
Jul 9, 2014
I wrote this code, but now need to apply a limit to the recursive depth. This is the format that I have to use. How would I pass a limit so that it stops after a given number? I'm just confused about where to apply it.
int compute_edit_distance(char *string1, char *string2, int i, int j, int limit) {
if (strlen(string1) == i) return strlen(string2) - j;
if (strlen(string2) == j) return strlen(string1) - i;
if (string1[i] == string2[j]) return compute_edit_distance(string1, string2, i + 1, j + 1, limit);
[Code] .....
View 4 Replies
View Related
Apr 21, 2014
I am trying to write udf for heat flux on X-Y plane in Fluent having the formula
Q(Y) = (0.304)/(deltaY + deltaY/2)^-3
Where deltaY = 50cm and
Y = 10m
but I am unable to do it. Can write udf for heat flux? Y is the length on Y-axis and X whixh is equal to 5m is length on X-axis. Q is heat flux goes through X-Y plane in Z direction. Geometry is a cube with dimension 10*5*0.005 all are in meters.
View 1 Replies
View Related
Feb 27, 2015
I'm trying to apply a bubble sort on a linked list. It works in the first traversal, but then after the code cPtr = nPtr;, it inputs repeated digits at the end of the (semi-sorted) linked lists.
View 1 Replies
View Related
May 28, 2013
Been trying to figure out why my program freezes. I know exactly what line of code is causing it, but I can't figure out WHY it's causing it. It compiles fine, there are no errors returned, and then the game just stalls and I have to ctrl+alt+del to kill it.
Anyway, what I have set up is something like this:
main.cpp
#include "SDL.h"
#include "SDL_gfxPrimitives.h"
#include "SDL_image.h"
#include "SDL_rotozoom.h"
[Code]....
This is the line of code that's freezing the program. Simply put, so that you don't really have to go through it piece by piece, what I have done is:
*each player gets their own drawing surface called PlayScreen
*each player gets an array of 360 drawing surfaces called ShipPic. These are to keep the game from having to render the rotation pics of the ship on the fly.
*Get_Ship clips the requested ship picture out of the ship sprite sheet and puts it in ShipPic[0] for the original angle.
*the original picture is rotated by 1 degree and put into the 360 ShipPic slots.
*when the player rotates their ship, the angle changes, and it calls the ShipPic with the same number as the player's angle and places it on the screen.
All of this works perfectly.
Then, in Player::draw_screen(), I have it set up so that each player looks at all the other players and gets their distance. If they're within range, it takes the other player's picture rotated by the other player's angle and puts it on the current player's PlayScreen. This is where it freezes.
I've checked for NULL pictures, I've checked to be sure the angle is between 0 and 359, nothing makes any difference. I know it's reading the other player's information since I can output all of the player's X & Y coordinates, angles, the width/height of their pictures, etc. on each other's screens. So they're definitely talking.
To test the code, I've changed it from
Apply_Surface(ShipX, ShipY, p[i].ShipPic[(int)p[i].angle], PlayScreen);
to
Apply_Surface(ShipX, ShipY, p[ID].ShipPic[(int)p[ID].angle], PlayScreen);
And it works perfectly, placing the player's OWN picture in for the other players. So the function works. It's just when I try to take another player's picture and place it on the current player's screen that it freezes.
I've tried quite a few different ideas, such as creating a temp drawing surface to blit the other player's picture onto, but again, it freezes as soon as I try using the other player's pictures.
View 5 Replies
View Related
Apr 9, 2014
I am writing a simple console-based tic-tac-toe game. I am trying to write a function to check whether someone has won the game.
The board data is saved in an array called board: Code: int board[3][3] with each element corresponding either to an empty spot, an X, or an O, using the numbers 0, 1, and 2, respectively. For clarity:
Code:
#define EMPTY 0
#define X 1
#define O 2 Here is my function: Code: int check_state(int board[3][3]) {
int winner = 0;
[Code].....
View 1 Replies
View Related
Mar 7, 2013
A few days ago I got a "bright idea" to see if I could match a string, with an arbitrary length from 1 to 12, to its formulated sequence by using an algorithm to find all possible combinations of the integer combinations from 0 to 9 at each length (1 to 12).
Example: Desired numerical combinations from integers 1 to 3:
At Length 1:
1, 2, 3
At Length 2:
11, 12, 13, 21, 22, 23, 31, 32, 33
At Length 3:
111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333
And so on until the nth length (in my case a length of 12).
First off, I would like to say that this is not as easy as I thought. I clearly underestimated the problem seeing as I've spent hours attempting to write a working algorithm, but feel like I've made no progress.
Here are a few of my attempts:
Attempt 1:
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
[Code]....
I can't exactly explain this one. It works if the length is 2 or less; however, the order of the output is horrendous.
Attempt 3: I tried using recursion, but only found myself getting more and more lost the further I tried developing my function. Cannot find my work for this attempt.
I would really like to figure this out on my own, but I am very stuck as you can see. I also lack time that I can spend working on this since im a full time student.
View 14 Replies
View Related
Jul 24, 2013
I wrote a version of find_all() which searches through containers for matches and returns another container that holds iterators pointing to each match. When I compared what I wrote to what the authors of Professional C++ wrote, I found the two find_all() functions to be very different.Here they are:
//Mine
template<typename Iterator, typename Predicate>
std::list<Iterator> find_all
(Iterator front, Iterator back, const Predicate& match) {
std::list<Iterator> toreturn;
for(; front != back; ++front) if(*front == match) toreturn.push_back(front);
[code]...
View 5 Replies
View Related
Jun 27, 2014
I have VRP algorithm written in C++, run with command prompt Windows. input (command line) -> VRP.exe -> output (txt file)
Now I want to built a website to run it as SaaS. How to run an exe application(compiled c++) in server used as Saas? What kind of programming do I have to use? Ruby or html5 or others? I don't know how to start.
View 3 Replies
View Related
Aug 27, 2013
i was trying to achieve a better way of game looping. so i have a game loop algrithm. but i dont think its quite good. i want it to be better.
here is my algorithm
bool quit = false;
while(quit == false) {
while(blah blah events)//here we hold events {
if(the user want to quits) {
quit = true;
[code]....
View 2 Replies
View Related
May 12, 2014
To construct and write down algorithm of determination of the sum of squares of consecutive integers with recursion use. I tried to do something:
public static int RecSumSquare(int x, int n)
{
if (n < 0) throw new ArgumentException("n should be greater than zero");
if (n == 0) return 0;
else return x*x+RecSumSquare(x, n - 1);
}
But I don't know as the beginning and the end of this algorithm will look.
View 2 Replies
View Related
Mar 10, 2014
I'm still a beginner at C++ programming, I have tried to implement some optimization algorithms (related to database) in C++, I cannot say it is going as far as I thought it will be, some errors does not even make sense, I will cut to the chase, I need to implement SA (Simulated Annealing) in C++, SA, which is an example of the Randomized Algorithms, functions on the concept of randomness and probability. In addition, I searched the internet with no (let say "accurate") code that might give me insight on how to begin, I only found one code for SA that I could understand, and edited it (which will be shown below), still looking to enhance and correct it more.
The code for SA is as follows:
Code:
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <cmath>
[Code] .....
If the concept of Simulated Annealing is not clear, you may refer to the following papers which can be found in a simple Google search: Simulated Annealing Algorithms: an overview.An Introduction to Interacting Simulated Annealing. Query Optimization (there is a sub-section for Simulated Annealing in this paper that explains SA briefly) ....
View 6 Replies
View Related
Sep 17, 2014
I'm trying to draw and pivot a rectangle. How to get the new coordinates if I turn it 90 degree for example?
From this:
To this:
This is not good because it will reduce it in size.
Code:
int size = 50;
if(b) // draw rectangle
{
POINT points[4] =
{{xCoord, yCoord},
[Code] ....
View 7 Replies
View Related
Jun 3, 2013
Trying to multiply to matrixes using the following algorithm,
Code:
ABrec(A,B)
n=A.rows; //n must be multiple of 2
C is a new n*n matrix.
if(n==1)
C[0][0]=A[0][0]*B[0][0];
[Code] ....
but the code doesn't work !!!
View 4 Replies
View Related
Aug 3, 2014
Now I know there's a simple way to calculate highest value. But here i have this algorithm which i understood part of it.
I know that *largest is point to the first element of begin which is 5. so in the first if statement its 5<5 at the first iteration ?
// i marked the parts i didnt understand with " //"
Code:
#include <stdio.h>
int *print(int *begin ,int *end ){
if(begin==end)
return 0;
int *largest = begin;
[Code] ....
View 10 Replies
View Related
Dec 24, 2014
i can't seem to get this merge sort to work. running through gdb though;
Code:
*Filename: mergeSort.c
*Usage: This implements merge sort algorithm to sort and array of numbers.
*/
#include <stdio.h>
#include <stdlib.h>
}
[code]...
View 2 Replies
View Related
Jul 22, 2014
write an algorithm using stack to determine if an input of string is in the form xCy where y is the reverse of x.x and y are strings of A and B. eg : AABACABAA
View 8 Replies
View Related
Mar 25, 2013
I'm trying to implement the flocking algorithm in C++. I've tried to implement it myself by making all the particles 'home-in' on the player. When 2 particles then collide within their larger bounding boxes they home-in to each other. And when the 2 particles are actually touching they repel each other until they are outside of their bounding boxes and find another particle to home-into.when I run my application the particles all home into the player and come to a stand still along the Y-axis above the player.
All the particles in question are stored in a Vector, with a pos and velocity.
for(int i = 0; i < swarm.size(); i++) {
for (int j = 0; j < swarm.size(); j++) {
if (swarm.at(i)->getParticleModel()->getPosition().x < gameObjects.front()->getParticleModel()->getPosition().x) {
if (swarm.at(i)->getParticleModel()->getTouching() == false)
[code]....
View 5 Replies
View Related
Jun 22, 2014
I made this program in C++ that should, by a genetic algorithm, build a word identical to the initial one improving itself recursively.
The code is:
main.cpp
#include <stdio.h>
#include <cstdlib>
#include "Genetic.h"
using namespace std;
[Code] ....
The problem is: when running with gdb it gave me this
warning: Could not load shared library symbols for linux-vdso.so.1.
Do you need "set solib-search-path" or "set sysroot"?
CREATA LA PRIMA POPOLAZIONE
PARTE L'EVOLUZIONE
TROVATO BEST: fzlrq
TROVATO BEST: hglhe
Program received signal SIGSEGV, Segmentation fault.
0x000000000040720e in Genetic::Gene::Gene (this=0x7fffff7ff030) at Genetic.h:20
20 struct Gene {
The line corresponds to the struct declaration. Every 1000 executions it runs well.
View 5 Replies
View Related