a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

learn more… | top users | synonyms

-5
votes
0answers
45 views

Algorithm to find nearest cabs used by Uber?

What is the algorithm used by Uber/Ola Cabs to show nearby cabs on their application? Also, How is the time to reach the user calculated ? A link to a blog or a paper would be highly appreciated. I ...
1
vote
1answer
23 views

How can I avoid needing to check for the existence another vertex when adding to an adjacency list?

I'm writing a Graph, and decided to make the Adjacency List its own class. Right now, (stripped down) it looks like this: public class AdjacencyList<Vertex> { //A map between a vertex, ...
1
vote
4answers
36 views

How definite of an order is there to a depth-first search of a graph?

I have the following graph that I need to simulate a depth-first search of; starting at g: My question is: How definite of an order is there when performing a depth-first search? When doing a DFS of ...
4
votes
2answers
125 views

Algorithm to find the optimal trade route (negative cycle with lowest cost per edge in a digraph)

Given the following problem (a slightly simplified description of trading in the computer game Escape Velocity: Nova (system map)): Given a set of (solar) systems. Each system is connected by ...
0
votes
1answer
49 views

Graphs and minimum spanning trees?

I am having a hard time finding information on how Graphs and spanning tree's work and how to construct/structure them. The reason is that I'm using a Delaunay Triangulation algorithm within the ...
0
votes
0answers
26 views

Graph curve and actual curve plotted on screen implementation patterns

I'm implementing a graph plotter. There are Curve objects, that contains points of actual XY data. When I plot to screen, I need to calculate the XY points on screen, resulting a PlottedCurve. This ...
2
votes
0answers
72 views

How to implement efficient heterogeneous microservice data queries?

Our team has an idea of implementing a simple declarative DSL that would let users query the enterprise's domain model via a single interface without caring which specific microservices to call to get ...
4
votes
1answer
123 views

Algorithm to find whether there is a path (any path) above length X between two vertices

We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than ...
0
votes
0answers
50 views

algorithm for group reassignment of points

I have a list of clustered points but they are not in the cluster which has the center closest to them. The objective is to reassign them to minimize the total distance of each point to its cluster ...
5
votes
1answer
127 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
5
votes
1answer
175 views

What is the maximum number of steps to find a bug using bisecting?

Assume that a node A in the commit tree of a codebase contains a bug but some ancestor B of A is clean from that very bug. Given the topology of the commit tree [B,A] leading from B to A, can we ...
0
votes
1answer
45 views

Render order of two-edge directed node graphs

I'm trying to find an algorithm for graphs with the following contents: Nodes with no edges leading out of them (shown here as a red circle) All other nodes have exactly two edges leading out ...
0
votes
0answers
55 views

All clustering possibilities for a graph

Is there a known algorithm for finding all clustering possibilities for a directed graph? EDIT: By cluster i mean a weakly connected sub-graph G, so that E(G) > 0. By a clustering possibility I ...
1
vote
0answers
43 views

Domination algorithm in graphs

I'm working on a project, on an app, that can visualize undirected graphs and show on this domination algorithm. There are some examples: I have some open questions about programmable solution of ...
1
vote
2answers
212 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
241 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 ...
1
vote
1answer
81 views

Connected components of undirected graph

Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation. For every time moment I have as input some subset of vertices that are "active" ...
1
vote
0answers
34 views

Codeforces : 505C. Mr. Kitayuta, the Treasure Hunter

Question : Is the attached logic correct? I am asking since my code based on this logic failed. Here is the problem link. Reproducing here verbatim : The Shuseki Islands are an archipelago of ...
3
votes
1answer
194 views

Is there some structured format for drawing source control branching diagrams?

Everyone on my team draws branch diagrams differently, including how branches exit or reintegrate to the parent, how cherry-pick merges are shown, and a host of other aesthetic choices. Is there some ...
1
vote
1answer
202 views

Why does this algorithm work in O(n m)?

This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m) This is a graph problem, where we are supposed to find the ...
1
vote
2answers
203 views

Why does this implementation of Dijkstra's algorithm work in O(n^2)?

Here is the code I use for implementing Dijkstra's algorithm. Consider a graph with n vertices and m edges. Shouldn't it run in O(n^2 m) ? Someone may say that there are n vertices and each edge gets ...
4
votes
1answer
93 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
87 views

Setting and getting values from a x-y graph

I have a bunch of x-y graphs given to me and I need to be able to transform them into some kind of data structure from which I will be able to get Y with X value. The problem is, though that I have 4, ...
1
vote
1answer
99 views

What is the minimum cost graph inside a strongly connected component, which connects every vertex?

So for MST there are 2 possible definitions in an undirected graph. Keep in mind that in an undirected graph the MST algorithm always has n - 1 edges and no cycles. In an undirected graph, it doesn't ...
4
votes
1answer
126 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
16
votes
7answers
778 views

How do you unit-test code using graphs?

I am writing (recursive) code that is navigating a dependency graph looks for cycles or contradictions in the dependencies. However, I am not sure how to approach unit testing this. The problem is ...
2
votes
2answers
202 views

Finding shortest path between nodes with a twist

Note: if you feel that I should include code, please tell me. I am solving a problem of finding shortest path between nodes. I am given the vertices between nodes, however they are one sided (ie you ...
0
votes
1answer
170 views

Find 'Connected Components' in undirected, unweighted graph coded as a 2d array

Given an undirected, unweighted graph coded as a 2d array, how can I find the number of different connected components? Example There is the following 2d array (I'm not putting any brackets to ...
0
votes
1answer
242 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 ...
3
votes
1answer
265 views

Shortest Path Between Two Nodes in a +10 Million Nodes Graph

I have my own knowledge graph representation, read from ConceptNet and NELL, containing tens of millions of nodes in which I want to calculate the nearest distance (if any) between two concept nodes. ...
0
votes
0answers
21 views

A heuristic approach to Clique problem over undirected Graph

I'm trying to get all complete subgraph given a graph G. Needless to say it is an NP-problem complete: Clique_problem. I understand getting the full set is not possible in real time(since it'll take ...
2
votes
1answer
203 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
2
votes
1answer
192 views

Find n nodes farthest away from each other

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other. Can this be accomplished relatively efficiently? To clarify my question: I think of the problem as ...
3
votes
2answers
326 views

How can I find the shortest path between two subgraphs of a larger graph?

I'm working with a weighted, undirected multigraph (loops not permitted; most node connections have multiplicity 1; a few node connections have multiplicity 2). I need to find the shortest path ...
2
votes
4answers
1k 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 ...
10
votes
2answers
672 views

How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage. In my scenario, a number of users who are hostile to each other are all trying to ...
1
vote
1answer
130 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
97 views

Which approach would be better for persisting these overridable configuration keys and values? A simple key-value store, or a graph database?

I'm creating a system where there are config keys and values. So for example: config.key = 10 Is an example of a configuration key and a value. These keys can also have overrides based on ...
1
vote
1answer
57 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 ...
0
votes
4answers
395 views

An algorithm for finding converse duplicates of ordered pairs

Given an array of ordered pairs of values, what algorithm will find converse duplicates? [Converse meaning the same values, but in the opposite order.] That is, given [ab,ac,ad,bc,bd,ca,db] is there ...
2
votes
1answer
284 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 ...
0
votes
1answer
71 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 ...
2
votes
1answer
231 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 ...
2
votes
1answer
140 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 ...
2
votes
1answer
162 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 ...
0
votes
1answer
212 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 ...
3
votes
2answers
371 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 ...
6
votes
1answer
189 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 ...
5
votes
5answers
599 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 ...
1
vote
1answer
212 views

Question on Graph

I am trying to implement a graph data structure in C#. I have the following interfaces: public interface IVertex<TValue> { TValue Value { get;} ...