a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices
0
votes
1answer
33 views
Dynamic Programming: Shortest path with exactly k edges in a directed and weighted graph
I came across this problem of finding the shortest path with exactly k edges. After some searching, I found the code below. It uses a 3D DP. States are there for number of edges used, source vertex ...
0
votes
1answer
36 views
Partition edges into areas
If I have a series of edges that branch and curve, such as in a road network, is there an algorithm that will identify the areas (defined by sequence of geographic points) defined between those lines?
...
1
vote
1answer
49 views
How many vertices/nodes are too many in a graph and stop being beneficial?
Background
I'm working on a project that requires me to keep track of transactions as well as the flow of items in a game.
In order to do that, I'm storing those transaction in a graph db ...
0
votes
0answers
30 views
Benefit and graphical representation of directed acyclic graph in code development
I think the relationship amongst the modules of a code can be represented by a directed acyclic graph (DAG) where a vertex represents a module and a directed edge from vertex a to vertex b represents ...
0
votes
2answers
78 views
The way to implement a configurable (at run-time) default style
I am coding a visualizer of graph algorithms. Each vertex of the graph has a style (color, size etc.). As long as the algorithm has done nothing to a vertex, that vertex has a default style. The ...
-1
votes
0answers
31 views
Algorithm to find minimum spanning tree in graph with weights in {1,2,3}
I have recently been doing some research into Prims/Kruskals algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem:
Let G be an undirected graph on ...
3
votes
0answers
68 views
Determine equality of a DAG
Given a fairly traditional node class (below), whats the best way to implement equality on a given graph?
If our node looks like this
public abstract class Node{
private final Set<Node> ...
0
votes
0answers
71 views
Decision making algorithm
I'm currently solving an optimisation problem of my own design, just to experiment and learn a little something.
Here's the concept:
I have a user that starts at home. The objective of this user is ...
6
votes
0answers
80 views
Algorithm to generate Edges and Vertexes outwards from origin with max multiplicity of 3
I am creating a 2d game for a website where the universe can grow extremely large (basically infinitely large). Initially, the universe is composed of 6 stars that are an equal distance from the ...
1
vote
0answers
42 views
Graph grouping with criteria
I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
4
votes
1answer
121 views
Single Source Shortest Path
In the lecture we are taught that we can solve All Pairs Shortest Path(APSP) with matrix multiplication.
In APSP we are creating a distance table for all the distances between each nodes in the ...
8
votes
2answers
317 views
Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
I would like to learn how to make graphs and perform some local operations on them in Haskell, but the question is not specific to Haskell, and instead of graphs we may consider doubly linked lists.
...
5
votes
2answers
244 views
How to optimize/parallelize the following clustering/joining algorithm:
I have relatively-small algorithm that takes up ~60% of the total run-time of my scientific code (57 lines of 3600), so I would like to find a way to optimize what I'm doing and make the code ...
3
votes
1answer
89 views
Are these graph coloring algorithms equivalent?
Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
1
vote
1answer
140 views
undirected c++ graph with a direction [closed]
I want to create a Graph in C++ that has directions, with directions I don't mean the direction of an edge but what I want is an undirected graph where the edges have a direction to the next vertex, ...
1
vote
0answers
71 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] ... ...
2
votes
0answers
36 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 ...
2
votes
1answer
218 views
Dependency ordering algorithm of a compiler
Let's say, hypothetically, I'm writing a Java compiler. And we assume that in my case a class can't be fully compiled until all signatures of dependencies (imports and other used classes) are known. ...
1
vote
1answer
51 views
How an add vertex operation could be performed in constant time for a graph represented using adjacency list?
Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex).
It is said ...
3
votes
1answer
153 views
why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?
Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex).
But ...
2
votes
1answer
176 views
Does a tree node have an ancestor?
Below is a rooted tree, where any node C except root has one parent P
Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root.
My ...
1
vote
0answers
100 views
Approaches to Modeling a Graph Database over the Google App Engine Datastore?
I want to model a graph database over the Google App Engine Datastore.
I am currently working on creating a Link entity to model the concepts of link/edge/relationship to the graph of objects.
I am ...
2
votes
1answer
110 views
Efficient algorithm for hierarchical traversing? JSON hydration, for example
I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example:
{
"date": "1970-01-01 00:00:00",
"foobar": "baz",
"user": {
"name": "foobar",
...
3
votes
1answer
211 views
Finding the optimal root
I am trying to solve a quora hackathon challenge question. The question descrpition is as follows :
For the purposes of this problem, suppose Quora has N questions, and
question i (1≤i≤N) takes ...
1
vote
1answer
33 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
94 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
241 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
111 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
50 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 ...
4
votes
1answer
249 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
168 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
62 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
213 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
184 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
51 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
73 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
48 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
271 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
365 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
206 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
55 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
398 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
267 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
281 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
123 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
129 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
237 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
2answers
284 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
937 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
374 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 ...
