a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices
4
votes
0answers
29 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
31 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
112 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
290 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
236 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
86 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
124 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
64 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
30 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
167 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
42 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
125 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
121 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
90 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
86 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",
...
