C/C++ :: Path Finding For Weighted Cyclic Directed Graph For Robot
Mar 14, 2015
I've been trying to make a program to return node values for the shortest path from one node to another. I've searched up several algorithms like the Bellman Ford, A*, or Dijkstra and tried to think of ways to implement them if I store my map as a matrix. I've considered using a hash table, but since I am only a beginner, I am having trouble trying to understand how the concepts would translate into C.
View 1 Replies
ADVERTISEMENT
Dec 29, 2013
I was asked to find the longest path in a graph. I was thinking about using Dijsktra's algorithm after multiplying all the weights with -1 and run the program in normal way and find the shortest path. And then I'll multiply with -1 again and get the longest path. I think this should give me the longest path, do you think it would work? And also, I'm dealing with considerably big data, such as 1.000.000 nodes and many more edges. etc. and I have a time limit of 2 seconds and memory limit of 128mb. Any other data structure instead of Adjacency Matrix? Because I'm pretty sure it will exceed the limits.
View 2 Replies
View Related
Apr 14, 2013
This is a code I've written for Random Directed Acyclic Graph Generation:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
using namespace std;
[Code] .....
However this gives two LNK2019 error codes. I'm new to coding... I'd like to learn what I'm doing wrong.
View 9 Replies
View Related
Jul 14, 2014
I know how to create your basic programm that compiles as a CLI or exports and/or saves data to a .txt file... But how does one build a GUI?
I ask because I am currently working on a programm for my Arduino controlled robot, in which I want to have a virtual on screen controller next to a map of my bots path.
View 4 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
Oct 29, 2013
this is my first year programming, and in my class, each week we have to write a program. last week we wrote a program in c that made random value point and made a graph of the random points that continued on forever. this week, we have to use statistical functions to find the sum, mean, max, and min of the graph. below is the code i have so far.
Code:
#include <stdlib.h>
#include <strings.h>
#include <stdio.h>
#include <stdbool.h>
#include "SwinGame.h"
[code]....
so, as you can see from the code, the parts i need are finding/ coming up with a function to find the max min sum and mean of the functions.
View 7 Replies
View Related
Feb 17, 2013
How to find the number of connected components from an undirected disconnected graph.
the input I'm getting is like this:
7
1 2
4 5
3 6
2 7
the top number is the number of vertices and the rest of the numbers are the edges, eg. 1--2 is an edge.
Is there a way that you can implement DFS algorithm to find the number of connected components? like increment a variable every time DFS is called or something?
View 1 Replies
View Related
Feb 25, 2014
I am new to Path Finding so I just know BFS, DFS, Djisktra, and Basic A*
I've searched for a few multi agent pathfind paper here and there. But I can't seem to understand them..
I am path finding in a grid map, 4 ways neighbor movement
My map isn't so big it's 300 x 300 up to 400 x 400
Most of the map is open space, I would say that at worst case 4/5 of the map is open space.
And there is probably around 100 agents.
I've tried running BFS 100 times and it takes around 200ms on average
Changing BFS to A* which I am thinking right now will definitely cost lesser time
But are there better ways in doing this ? and also Does running Single Agent A* multiple times doesn't cause problem for other agent ? perhaps causes deadlocks ? ( Considering that the path that have been determine for agents before the current searched is considered blocked )
View 1 Replies
View Related
Mar 11, 2014
i've been writing some code for an assignment and it is mostly about pointers and string manipulations. It runs but crashes and I think it might be from over- valuating some strings maybe not. I have written in check points to make sure each function passes through but quits at findFirstPath loop, I had kept running the program through as i added more and more code. It had stopped when I near finished I believed it to just be because I hadn't finished the functions I called.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXSTRING 10
#define TRUE 1
[Code]....
View 3 Replies
View Related
Jul 25, 2014
I read online about Cyclic Redundancy Check and how it works.
ThisStack Overflow response explains it so well on a layman level.
I found some code online on how to implement it and what library to include in C#. I've looked at it and I can grasp how the algorithm works with the remainders.
What I don't understand is how can I integrate my database, which is a sql server localdb file into the CRC32 check, so that I can test for the database integrity. I'm not sure how to proceed.
Do I test each table individually and send the size of the table(in bytes) and compare it to the value it's supposed to be?
View 3 Replies
View Related
Jan 21, 2015
I'm looking to implement a Database Access Layer for the project I'm working on, it's a mature project and I'm trying to simplify the database access and as far as possible and remove the Database logic from the Business logic.
Bringing in an ORM solution isn't an option at the moment so I'm looking at bringing in DAO objects to break the coupling. The problem I can't get around in my head is how to avoid Cyclic references
We currently have 2 projects
BL contains types such as Customer, Component and Product which need saving to the Database, the Database project can't know about these items or it would create the cyclic dependency.
I tried adding Dao items to the DB project to mirror these items and to also mirror the DB structure but that requires that the BL project knows how to convert between it's own types and the DAO types which is something I'd like to avoid.
I also tried inserting a third intermediate project that would control the conversion and saving, I called it my DAL project and tried adding functions that would take the BL item and perform CRUD operations but again I ran into the cyclic dependency issue.
My ideal solution would be that the BL project would just have to call a function along the lines of "SaveCustomer(Customer inCustomer)" and not have to worry about doing any conversion.
Is there a project structure that would allow for this?
View 1 Replies
View Related
Oct 23, 2013
Im trying to tune my PID loop to make my robot balance but i dont know if im using the right terms for my robot? Im implementing a contemporary filter for my Gyro(98%) and Acc(2%).Is the following right?
output=(Kp*error)+(Ki*(error*dt))+(Kd*((error-prev_error)/dt))
error=robot angle --Balance point at 0deg
prev_error=--Previous error
dt=0.01 --10ms delay
View 2 Replies
View Related
Sep 12, 2014
I'm doing a practice problem where I need to read pseudo code and understand what it does.
For this code, I believe it will move the robot forward while i<650, so it moves it forward for 650 steps in total. Then it sets the motors to 0 when it's finished.
Code:
while(i<650)
{ rotateCW(2);
rotateCCW(1);
Delay1KTCYx(50);
i++;
LATD=0x00; //Set all Port D to 0
}
This code I'm having the most trouble with. So while(1) the pot(potentiometer) read's the ADC. Then it scales the adc, not 100% sure what the +20 and *.22 mean, I think it has to do with binary conversions?
Now it sets pin 1 of port 1 to 0, delays based on pot above, and sets it back to 1, and delays again. I assume something to do with controlling motor speed based on the potentiometer.
Code:
void main(void){TRISD = 0x00; // Setting port D to outputs
LATDbits.LATD0 = 1; // Setting bit 0 of port D to 1
while(1) {
pot = readADC();
pot = pot * 0.2297 + 20;
[Code] ......
My best guess is: The car moves forward 400 steps, stop, turn right for 230 steps, stop. At this point it would begin moving straight, and it would turn left/right as needed to keep the robot in the center of the track.
Code:
void main(void) {
for(i=0;i<400;i++) {
rotateCW(2,motor); //Rotate motor two (one step)
rotateCCW(1,motor); //Rotate motor one (one step)
Delay1KTCYx(50);
[Code].....
View 5 Replies
View Related
Oct 20, 2013
As the title says im trying to make a self balancing robot.
I am using an accelerometer and a gyro as sensors.
I am just really confused when it comes to programming in a PID loop to actually use feedback from the sensors to control the motors.
I sort of understand what needs to be done concering PID loops, just i dont know how to do it.
View 9 Replies
View Related
Sep 25, 2014
I am attempting to write a simple program and compile it onto a 3pi robot. My problem lies with my array, i need the array to increment by one every time through and whenever i run the code the print out reads "ROOM 0" every time.
#include <pololu/3pi.h> /* allow use of 3pi robot functions */
#include <avr/pgmspace.h> /* allow use of program space */
#include <stdio.h> /* for printf() */
#define NUM_ROOMS 11 /* the number of study rooms */
/* function prototype for battery check */
void bat_check( void );
[code].....
View 4 Replies
View Related
Feb 12, 2014
i have to make a programs that prompts the user to enter quiz grades and add them up. For examples the user enters 6 test grades they are out of 5 so he enters 0-5 and i store them in the array. This part works great but now i have to print out a bar of vertical asterisks for every part too. So if at the end we have one test grades that are 2 grades of 1 points, 1 grade of two point, 2 grades of three point and 1 grade of 5 point it will have to display them as this
There are 2 grades of 1
There are 1 grades of 2
There are 2 grades of 3
There are 1 grades of 5
i need to do for loops but i am stuck on what to count too and what to print i know i will need cout << "*" and a couple of spaces.
#include <iostream>
using namespace std;
int main (){
int size;
int tests;
int a[6]={0};
cout << "How many quiz scores will you enter: ";
cin >> size;
[code]....
View 1 Replies
View Related
May 18, 2013
You have to implement a data structure to represent graphs,directed or undirected,that tries to avoid the wasted space in the representation of a graph with adjacency matrix and the difficulty of searching the edges with adjacency list representation.We consider that the vertices are numbered from 1 to nverts and the exit degree of each vertex is at most MAXDEG. If deg[i] is the exit degree of the vertex i then the neighbors of the vertex i can be saved at the matrix edge[i][j], 1<=j<=deg[i].
Write a program that reads the datas from a file: if the graph is directed or undirected(1 or 0), the number of vertices (nverts),the number of edges (nedges) and the first and the last vertex of each edge.Write the function dfs that, with argument the data structure that you implemented before for the representation of a graph, prints the edges by the depth-first search of a graph. What I've done so far is: I wrote a program that reads these information from a file, calculates the exit degree of each vertex and creates the matrix edge[i][j]. What data structure do I have to implement???
View 1 Replies
View Related
May 24, 2013
for an assignment we need to create basically a program that asks the user for the result of standard six-sided die rolls (numbers from 1 to 6). The program will prompt the user with "Enter a die roll or 0 to exit " for the first entry and Next die roll? for all subsequent entries. The program will continue reading die rolls from the user until the user enters 0. At this point, the program prints two newline characters (one blank line) and finally, the bar chart showing the number of times each die roll has been entered, and then terminates.If the user enters an invalid number, the program will just ignore it, and ask for another number. Only numbers 1-6 inclusive and 0 are valid.
Example output Enter a die roll or 0 to exit 6 Next die roll? 6 Next die roll? 7 Next die roll? 4 Next die roll? 0
[code].....
View 3 Replies
View Related
Apr 16, 2014
I am using koolplot plot graph and able to plot two lines in a graph. My question is how to fill between the lines? Is it possible to do so with koolplot? or i should use another library?
View 2 Replies
View Related
Jan 5, 2014
I am trying to compare two vectors and make a bar graph. I have tried sorting it and pushing it into another vector but this issue is when I go to output it. My logic is wrong.
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iomanip>
int main(int argc, const char * argv[]) {
[Code] ....
Output
22 *
44 *
22 *
45 *
33 *
44 *
18 *
34 *
33 *
12 *
3 *
5 *
34 *
33 *
5 *
7 *
22 *
44 *
49 *
9 *
18 *
View 3 Replies
View Related
Mar 30, 2014
I used a BFS to simulate graph-join structure in a C++ code, and had a binary tree that asks the user e.g. to insert a node in the tree among other options, anyhow, I reached a point where I should pass a set of vertices from the graph to the tree, but how to do so. So I wanted to ask is such a thing possible? i.e. passing vertices from a graph to a tree automatically (no user involvement is needed)?
View 4 Replies
View Related
May 3, 2014
"My Programm is crashing and i dont know why?"
#include<iostream>
using namespace std;
int arr[3];
struct edges {
int edge_data;
edges *next;
[code]....
View 1 Replies
View Related
Apr 13, 2013
I need building a complete graph from a file. The format in the file is as follows.
[ vertex 1] [ x_coordinate 1] [ y_coordinate 1] [cityname 1]
[ vertex 2] [ x_coordinate 2] [ y_coordinate 2] [cityname 2]
. . .
[ vertex n] [ x_coordinate n] [ y_coordinate n] [cityname n]
What kind of data structure shall I use in order to store date in a complete graph so there is an edge between every pair?
View 7 Replies
View Related
Apr 18, 2012
I wrote class DFS - Depth-first search. This algorithm check that this graph is consistent. Below is code of class
Code:
#ifndef DFS_H
#defineDFS_H
class DFS{
private:
std::stack<int, std::vector<int> > stos;//stos do przechowywania wezlow w dfs'ie
int *odwiedzony;
int liczbaWezlow;
[Code] ....
When i initialize dfs i use 2 parameters. On the next step i would like show all content array odwiedzony. Regardless of the given parameters of the array always has a value of zero. Where i made mistake and how to repair?
View 10 Replies
View Related
May 29, 2013
I have a 'Graph' class, which has derived classes for Adjacency Matrix and Adjacency List representations.
How do I provide iterators for traversing vertices and edges, when the iterator classes would have different implementations for the different derived classes ?
The following way is the only one I can think of, but seems quite cumbersome.
Code:
class Base {
public:
class BaseIterator {
};
virtual const BaseIterator& begin();
virtual const BaseIterator& end();
[Code] .....
Or is there a pattern for doing this that I'm not aware of ? Would composition be a better idea here compared to polymorphism ? I mean, I can think like..a Graph can 'have' several representation 'objects' within it.
All the involved classes are templates,not sure if that makes the situation different.
View 7 Replies
View Related
Jan 14, 2015
Is not the first time I upload this program i know, but the problem now is that i try to export files, because i need to create an excel graph. But when I try to run it, I don't have any result, no file and no result of the program.
Code:
#include<stdio.h>#include <time.h>
#include <cstdlib>
#include <math.h>
int randfun(double arrX[], double arrY[], int size);
int cenfun(double arrX[], double arrY[], int size);
int rotatefun(double arrX[], double arrY[], int size, double center_x, double center_y, const double angle);
[Code] .....
View 2 Replies
View Related
