Questions tagged [graph-traversal]

The tag has no usage guidance.

0
votes
1answer
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)...
1
vote
2answers
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 ...
1
vote
1answer
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): # ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
25
votes
3answers
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 ...
1
vote
1answer
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 ...
0
votes
3answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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, ...
3
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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,...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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, ...
2
votes
2answers
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 ...
7
votes
3answers
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 (...
3
votes
4answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
12
votes
1answer
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 ...
11
votes
3answers
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 ...
6
votes
6answers
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 ...
0
votes
2answers
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 ...
2
votes
2answers
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 ...
3
votes
2answers
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 ...
7
votes
4answers
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 ...
1
vote
1answer
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 ...
13
votes
3answers
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 ...
2
votes
1answer
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)...
7
votes
5answers
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 ...
0
votes
2answers
662 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 ...
2
votes
1answer
1k 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 ...