Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [graph]

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

192 questions
41
votes
8 answers

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 wondering what's the advantage of this mechanism, and in…
Po-Jen Lai
  • 553
  • 1
  • 4
  • 9
25
votes
3 answers

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 with warps. In the image, you can see that it only…
Jeff smith
  • 341
  • 3
  • 7
20
votes
9 answers

How do you unit-test code using graph structures?

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 that one of our main concerns is will the code…
Sled
  • 1,868
  • 2
  • 17
  • 24
20
votes
3 answers

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 java library but it is quite slow when I try to…
mariosangiorgio
  • 322
  • 1
  • 2
  • 8
18
votes
6 answers

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 containers located along a 1-D number line at distinct…
Barron W.
  • 189
  • 6
18
votes
4 answers

What are graphs in laymen's terms

What are graphs, in computer science, and what are they used for? In laymen's terms preferably. I have read the definition on Wikipedia: In computer science, a graph is an abstract data type that is meant to implement the graph and hypergraph…
ConditionRacer
  • 5,682
  • 6
  • 38
  • 56
17
votes
5 answers

Algorithm to determine fastest route?

Let's say we're going from 1 to 5. The shortest route will be 1-4-3-5 (total: 60 km). We can use Dijkstra's algorithm to do that. Now the problem is, the shortest route is not always the fastest one, because of traffic jams or other factors. For…
anta40
  • 281
  • 1
  • 2
  • 6
15
votes
3 answers

Is it possible to represent mutation of object-graph efficiently with immutable states?

I am practicing using of immutable object in C++. My personal goal is representing generic object graph (in heap) with sequence of immutable graphs. Building the multi-version graph itself isn't that much hard. The problem is performance.…
Eonil
  • 1,719
  • 1
  • 13
  • 28
13
votes
1 answer

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 when you have a single source and you want to know…
Programming Noob
  • 473
  • 4
  • 7
12
votes
2 answers

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. Question: What would be an idiomatic or…
Alexey
  • 932
  • 7
  • 19
12
votes
1 answer

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 of changes and interpret them into human readable…
ptpaterson
  • 179
  • 6
11
votes
1 answer

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 origin (0, 0). My task is to be able to generate more…
John F.
  • 111
  • 4
11
votes
3 answers

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 form networks of computers where all potential…
Pops
  • 4,093
  • 4
  • 28
  • 41
11
votes
3 answers

Randomly generate directed graph on a grid

I am trying to randomly generate a directed graph for the purpose of making a puzzle game similar to the ice sliding puzzles from Pokemon. This is essentially what I want to be able to randomly generate:…
Talon876
  • 211
  • 1
  • 6
10
votes
5 answers

Pros and cons of representing routes as legs or stops?

What are some pros and cons of representing routes as legs or as stops? A leg is a departure and arrival location, a departure time and a duration (or an arrival time and a duration). A stop is an arrival time, a location, and a departure time. The…
François Beausoleil
  • 209
  • 2
  • 5
1
2 3
…
12 13