# Tagged Questions

34 views

### Equidistant polygons

Consider these polygons: For reasons of simplicity I only consider triangles or polygons with 4 vertices. These shapes are specified by the vertices, the output of the program should be modified ...
47 views

### An algorithm for finding converse duplicates of ordered pairs

Given an array of ordered pairs of values, is there a well-known algorithm to find converse duplicates? [Converse meaning the same values, but in the opposite order.] That is, given ...
29 views

### Matching weighted unbalanced Bipartite graph

I am looking for a way to solve an assignment problem, but I am having some problems finding the correct algorithm to use. I have 2 list of nodes A and B, and in my problem may the length of A not be ...
46 views

### How to canonise a road network

I am working on geographical data which represents the road network of some city and I need to automatically fix inaccuracies in the data. Data was manually produced by “drawing” the road network ...
72 views

### Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
130 views

### Euclidean Space Fully Connected Nondirectional Graph: Shortest Path to all nodes

So this may be a question that is born of my inability to properly express my intentions to Google. In a fully connected non-directional graph such that any three points can be properly represented ...
251 views

### How to find number of points with same minimal distances on matrix

I'm trying to find the number of points in a matrix with the same minimal distances. Start with a MxN matrix, where M and N < 50000. There is given a set of fixed points, with their respective ...
148 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 ...
120 views

### Algorithm for defragmenting cross-pipe issues in a network for routing signals through?

I have a network I'm responsible for routing signals through. You can think of the network as a directed graph of nodes (hardware) but each edge is really a pipe capable of fitting a specific ...
178 views

### Weight-maximizing (weighted vertices) path algorithm

I am looking for description (name of algorithm, code, pseudocode, etc.) that can help me frame this problem and find the appropriate recursion and the most efficient solution. Problem: Given a ...
286 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 ...
337 views

### Optimal “if-else” tree algorithm to minimize duplicate code

I'm having trouble formulating this problem as an algorithm: I have a set of conditionals (combined with &&) and operations, for example: if (A && B) execute C else if (D ...
197 views

### How to solve binary labeling with graph cut?

Many literature references suggest that the binary labeling problem can be converted into a graph cut problem and solved with the max flow/min cut algorithm. I'm trying to understand the formulation ...
370 views

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 ...
189 views

### Algorithm in undirected BFS graph

I'm trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it's an undirected graph. I'm not sure how to ...
97 views

### Placing elements in graph with a streaming/online algorthm

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that ...
474 views

### Where to learn graph theory applications [closed]

I am completely new to designing algorithms with graphs. I am following CLRS and other video lectures in Youtube, notably from IIT/MIT. They are pretty good, and I currently have decent idea about ...
654 views

### How can you prove an acyclic graph has n-1 edges? [closed]

I'm not so hot on the maths for this but for what I understand... A graph g exists with v vertices and edges. g = (V,E); The spanning graph for this is an acyclic copy of this where all the vertices ...
1k views

### What algorithm should I use to find the shortest path in this graph?

I have a graph with about a billion vertices, each of which is connected to about 100 other vertices at random. I want to find the length of the shortest path between two points. I don't care about ...
510 views

### using ant colony algorithm to create cross word game [closed]

I have difficulty to learn about ant colony algorithm (ACO), I have read about generating crossword game using (genetic algorithm) GA.I Know both of GA ant ACO usually used for optimization, but my ...
604 views

### Visiting points on a number line while minimizing a cost not related to distance

I need some help on this ACM ICPC problem. My current idea is to model this as a shortest path problem, which is described under the problem statement. Problem There are N = 1000 nuclear waste ...
155 views

### Implementing a sort of navigation system

So I am undertaking a project which does navigation sort of thing. So here is how the problem statement looks like. Say, given a map of a floor, with different rooms, now somehow, this information is ...
229 views

### Chambers In A Castle Algorithm

Problem Statement - Given a NxM grid of 1s & 0s (1s mark walls, while 0s indicate empty chambers), the task is to identify the number of chambers & the size of the largest. And just to ...
890 views

### Tree vs Graphs in search

Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
6k views

### When to use DAG (Directed Acyclic Graph) in programming?

I recently found a framework named ecto. In this framework, a basic component named "plasm", which is the ecto Directed Acyclic Graph.In ecto, plasm can be operated by ecto scheduler. I am ...
581 views

### Nearest color algorithm using Hex Triplet

Following page list colors with names http://en.wikipedia.org/wiki/List_of_colors. For example #5D8AA8 Hex Triplet is "Air Force Blue". This information will be stored in a databse table (tbl_Color ...
3k views

### Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra's algorithm is used only ...
447 views

### Algorithm for perfect non-binary graph layout

I have a complex non-binary graph model. Each tree node can have multiple children&parents (a node can also have a connection to it's "brother"). A node is represented as square on screen with ...
5k views

### Efficient graph clustering algorithm

I'm looking for an efficient algorithm to find clusters on a large graph (It has approximately 5000 vertices and 10000 edges). So far I am using the Girvan–Newman algorithm implemented in the JUNG ...
419 views

### Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...