# Questions tagged [graph-traversal]

The tag has no usage guidance.

49 questions
102 views

### Walking a graph without recursion

I'm working on a class that receives a relational EDM/data model (e.g. a SQL DB or OData API manifest) and performs a couple tasks on them (not necessarily at the same time, could be two separate runs)...
88 views

### Algorithm. Find the group of documents with the least amount of words

I need help with a problem which I have been working for the last month. I have a group of documents, each document has a set of unique words (if the word appears more than once in the document, I ...
34 views

### Modified graph traversal

This question is most easy to describe as a modification of that my question. Suppose that question is solved as the following Python class: class Traversal(object): # ... def next(self): # ...
55 views

### Not sure how to setup my data for a waypoint system

I have a system i've written on paper and am trying to write this into C# in a easy to use manner. I want a series of connected waypoints (where by waypoints can be connected to any number of other ...
154 views

### Algorithm to select sets of objects while maximizing number of objects covered

If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set ...
179 views

### 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 ...
430 views

### Heuristic for optimising the traveling salesman problem (tsp) in under O(n²)

I have a large data set (more than 3 Million distinct data points that have 6 integer numbers). I want to compute the shortest route in terms of hamming distance. (amount of numbers that change ...
145 views

### Breadth-first traversal with some edges preferred

Let we have a (finite or infinite) directed graph and a start vertex. For each vertex we have the set of edges from this vertex totally ordered to specify the traversal order. Let we also have a set P ...
5k views

### 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 ...
267 views

### graph database - how to avoid that the edge becomes a vertex

In my current project I have a situation where I would need to use an edge collection as vertex collection. I would like to find a way to avoid it. This is the (reduced) scenario. These are the ...
121 views

### Use case, design, and how to append to an immutable object in functional programming

This is not (supposed to be) an opinion question, but it is a newbie question, so if there is just a resource I haven't found that I need to read, point me there :) I am in the design stages of a ...
175 views

### Moving from Batch to Streaming architecture using a Graph datastructure

The use case I am trying to solve is, assigning millions of users to their groups/segments. I have thousands of different criteria from which buckets of users are created. E.g. bucket criteria: All ...
698 views

### Finding the shortest path in a fully-connected undirected graph

I am trying to solve a problem in which I have a list of two-dimensional coordinates, and I want to find the shortest path that connects all of them. At first I thought this was a case of the ...
113 views

### 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, ...
134 views

### 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 ...
174 views

### Searching, storing, and finding graph attributes and vertices

I've been reading the 3rd edition of [Algorithms][1] by Cormen, Leiserson, Rivest and Stein. For DFS and BFS their algorithm loops through all the vertices first and colors them white. 1) If the ...
116 views

### How do travel search engines combine flights

I'm curious about how the flight/train search engines combine the results from multiple sources. For example, let's say I'm asking to go from London to Paris, and let's assume there are no direct ...
333 views

### The maximum number of induced cycle in a simple directed graph

Given a simple directed graph G=(V,E) an induced cycle is a cycle where no two vertices of the cycle have an edge that is not in the cycle. (Chordless cycles are induced cycles with at lease 4 ...
244 views

### Belman-Ford 2d array variation problem

I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph) Input array has m x n dimensions: s[1,1] s[1,2] ... s[1,n] -> Exit s[2,1] s[2,2] ... s[2,...
157 views

### Filter out noise in line graphs

I have a question regarding finding relevant events in a line graph. The following graphs show the views (y-axis) of a video over time (x-axis). Certain events lead to an huge increase in views and ...
535 views

### How to calculate number of indirect dependencies of a class?

Most of the static code analysis tools which analyse class dependencies generate dependency pairs of classes where each pair represents a direct dependency between two classes. Given those dependency ...
582 views

### How to avoid loop in a dept-search in a graph?

I must implement , in Lisp , a depth-search algorithm in an implict graph (namely a graph where I have the starting node, the goal node, and the successor function ,f, that give a node create his ...
486 views

### 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 ...
587 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, ...
635 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 ...
1k 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 ...
417 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 ...
1k 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 ...
180 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 ...
632 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 ...
2k 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 ...
3k 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 (...
6k 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 ...
420 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 ...
2k 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 ...
748 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 ...
388 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 ...
14k 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 ...
4k 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 ...
2k 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 ...
793 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 ...
2k 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 ...
331 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 ...
1k 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 ...
23k 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 post-order ...
1k 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 node)...
2k 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 ...