Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [graph-traversal]

54 questions
25
votes
3 answers

How to find the shortest path with wormhole nodes?

This is an example of what I want to do via code. I know you can use jump point search to easily get from the green node to the red node with no problems, or even A*. But how do you calculate this with warps. In the image, you can see that it only…
Jeff smith
  • 341
  • 3
  • 7
21
votes
4 answers

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 correct me if I am wrong? Thanks in advance!
Srikanth Kandalam
  • 313
  • 1
  • 2
  • 4
13
votes
3 answers

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 post-order breadth-first what's the actual utility of pre…
Shivan Dragon
  • 4,583
  • 5
  • 24
  • 31
12
votes
1 answer

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 of changes and interpret them into human readable…
ptpaterson
  • 179
  • 6
7
votes
3 answers

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 claimable train line connecting two cities. Players get…
sadakatsu
  • 109
  • 8
7
votes
6 answers

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 least it is already well understood. The way I am…
Srikar Appalaraju
  • 309
  • 4
  • 11
7
votes
4 answers

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 direction of implementing a solution for it, or…
Serge
  • 173
  • 5
7
votes
5 answers

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 find puzzling is heuristic. How do I find one in an…
Janis Peisenieks
  • 227
  • 2
  • 5
6
votes
1 answer

Toll placement problem (Graph theory)

I'm working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to find the minimal set of toll plaza nodes that can…
user3298142
  • 73
  • 4
6
votes
1 answer

What is the fastest algorithm to find what point of Type 1 is closest for each point of Type 2 on a rectangular grid?

In my contrived example, I have a rectangular grid of nodes, where each node is either empty, of Type 1 or of Type 2. All nodes are directed to the eight nodes around them (horizontal, vertical, diagonal). For each of the nodes of Type 1, I want to…
Qqwy
  • 4,709
  • 4
  • 31
  • 45
5
votes
1 answer

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 could be the Haversine Formula for spherical…
Tiborg
  • 283
  • 1
  • 2
  • 9
5
votes
1 answer

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 the transaction Imagine you have a network of…
Greg
  • 389
  • 2
  • 7
4
votes
1 answer

Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present Perform in-order operation Perform post-order operation where…
9a3eedi
  • 2,101
  • 3
  • 23
  • 29
4
votes
2 answers

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, max_gene_index ): i := random_interval (…
Jossi
  • 153
  • 6
3
votes
1 answer

Mapping points to squares

I am working on writing a code for Hilbert algorithm to solve a Traveling Salesmen Problem. Although there are several efficient methods out there, I am just curious about the implementation of Hilbert Space filling curve. First we create a…
jhon_wick
  • 141
  • 4
1
2 3 4