The graph-traversal tag has no wiki summary.
1
vote
2answers
36 views
Mutation operator for genetic algorithms for solving traveling salesman problem
I need help help for defining mutation operator for traveling salesman problem.
I'm currently using this now (pseudocode):
mutate ( strand ):
for n in random_interval ( min_gene_index, ...
0
votes
1answer
71 views
Big graph traversal with OOP
I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
7
votes
3answers
161 views
Algorithm or domain for finding cheapest subgraphs that connect vertex pairs
I am currently working on a project inspired by the Ticket to Ride board game. This board game is played on an undirected graph where each vertex represents a city and each edge represents a ...
4
votes
1answer
83 views
Mathematically correct A* heuristic / distance estimator for a latitude / longitude graph
I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates.
Correct ways to calculate the distance between two such points ...
0
votes
1answer
170 views
how to traverse towards child node from parent node in n-ary tree? [closed]
In an n-ary tree...
Given a reference to some child node
And a reference to a distant parent of the referenced child node
Is there a method that a parent node can use to figure out which of its ...
0
votes
1answer
183 views
Shortest path to visit all nodes [duplicate]
I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them.
The way i thought of it, is i will ignore if there are streets available and ...
2
votes
0answers
81 views
In a mutual credit network, how would you program an automatic jubilee?
A little explanation might be needed. I mean mutual credit the way that it's defined here:
a type of alternative currency in which the currency used in a transaction can be created at the time of ...
0
votes
1answer
187 views
Number of sequences when no adjacent items can be the same
I came across this one problem,
There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same.
Write a program that given n1 1s, n2 2s, n3 3s, n4 4s ...
1
vote
1answer
109 views
City exploration algorithm
The purpose of the algorithm is to create n routes on a geographical map, where n is being given, whereas all routes take no longer than t time units by foot and end where they start, while trying to ...
1
vote
2answers
325 views
Looking for an algorithm to connect dots - shortest route
I have written a program to solve a special puzzle, but now I'm kind of stuck at the following problem:
I have about 3200 points/nodes/dots. Each of these points is connected to a few other points ...
1
vote
3answers
615 views
Finding the shortest path through a digraph that visits all nodes
I am trying to find the shortest possible path that visits every node through a graph (a node may be visited more than once, the solution may pick any node as the starting node.). The graph is ...
1
vote
0answers
189 views
Understanding Tarjan's Bridge-finding algorithm
Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm.
However, I don't understand the condition for ...
2
votes
1answer
169 views
Improving the running time of Breadth First Search and Adjacency List creation
We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and ...
5
votes
5answers
537 views
Finding most Important Node(s) in a Directed Graph
I have a large (≈ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at ...
0
votes
2answers
533 views
What graph traversal algorithm should I use?
I would like to write an algorithm which can traverse a graph and hopefully later I can implement it to use for an indoor navigation system.
The graph would come from floor plans of a building and ...
3
votes
2answers
570 views
Breadth-first graph search problem
I thought I was doing breadth-first graph search correctly, but my instructor's grading script is telling me that my answer is incorrect.
From the instructions:
Consider a breadth-first graph ...
6
votes
1answer
183 views
Heuristic Approach for Flexible DIFF Implementation
I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations.
One thing that has become important is to take the list ...
1
vote
2answers
1k views
Is Pre-Order traversal same as Depth First Search?
It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
2
votes
2answers
251 views
Graph traversal and filtering in indoor navigation and path finding
Which of the following options take less processing time/is less expensive in a graph traversal algorithm for a (indoor)navigation system?
a) To produce all possible paths between start and ...
7
votes
4answers
209 views
Graph theory problem (name unknown)
I am trying to solve the following kind of problem. I do not know if there is already a name for this, or a solution; however, I'm willing to bet there is. I was hoping someone could point me in the ...
1
vote
1answer
393 views
Languages with graph data structures and algorithms in standard library
I am trying to improve my knowledge and ability with graphs and graph algorithms and have noticed something curious: as far as I can tell no "mainstream" language contains support for graphs in its ...
6
votes
3answers
5k views
Usefulness of pre and post order traversal of binary trees
This may be very naive, but I was wondering, it the context of binary trees (plain, sorted and balanced), of all the traversal types:
depth-first pre-order
depth-first in-order
depth-first ...
2
votes
1answer
768 views
Architecture for Social Graph data that has a Time Frame Associated?
I am adding some "social" type features to an existing application. There are a limited # of node & edge types. Overall the data itself is relatively small (50,000 - 70,000 for each type of ...
6
votes
5answers
443 views
Finding an A* heuristic for a directed graph
In a previous question, I asked about finding a route (or path if you will) in a city. That is all dandy. The solution I chose was with the A* algorithm, which really seems to suit my needs. What I ...
0
votes
2answers
228 views
Algorithm for searching the neighbors neighbor of a directed graph
Is there an algorithm to search a directed graph (tree) for its neighbors neighbor?
My current brute-force solution works as follows:
for each node n:
for each child c of n
for each parent ...
1
vote
1answer
751 views
Gremlin — do I have to know Java/Groovy
This is the excerpt from the project's Github page.
Gremlin provides graph traversal related syntactic sugar to Groovy. Groovy provides dynamic language syntactic sugar to Java. Realize that ...
