# Tag Info

49

Most path finding algorithms are defined in terms of graphs, not in terms of grids. In a graph, a connection between two otherwise distant nodes is not really a problem. However, you have to take care with your heuristics. With wormholes, the minimum distance between two nodes is no longer the euclidean distance and the distance does not satisfy the ...

30

Nice Question. Code may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code; this representation allows the compiler to perform common subexpression elimination efficiently. Most Source Control Management Systems implement the revisions as a DAG. Several Programming languages describe ...

27

A perfect layman's example might be Facebook. The network of you, your friends, and their friends etc, are collectively refered to as the social graph. In this "graph" the people are considered nodes of the graph and the edges are friendship links. In Facebook friend is a bidirectional relationship (A is B's Friend => B is A's friend) so the graph is ...

16

Graphs are one of the most important mathematical concepts used in computer science. You've seen graphs many times over. Imagine that you are taking a plane flight from one city to another. You'll inevitably find a nice glossy magazine from the airline in the seat pocket in front of you. Near the back of that magazine you can almost always find a map that ...

14

A better question would be "What aren't graphs used for?". Computer Science is, in many respects, the study of Graphs. A graph, in laymen's terms, is a collection of arbitrary abstract objects called "nodes" or "vertices" that represent points of connection. They are then connected via "paths" or "edges". The abstract data type "Graph" is an implementation ...

13

The answer is that it doesn't have much of anything to do with programming. It has to do with problem solving. Just like linked-lists are data structures used for certain classes of problems, graphs are useful for representing certain relationships. Linked lists, trees, graphs, and other abstract structures only have a connection to programming in that you ...

13

If your article "says the CC is 3 as there are three possible paths" then the article is missing some of the detail. The wikipedia definition of cyclomatic complexity defines it in terms of the number of nodes and edges in the graph of the function: M = E − N + 2P. This is the graph of your function: (+) | (if) |\ | (stmt) |/ ...

13

"Graph" is an ambigous term, refering to different kinds of mathematical objects. But whatever kind of graph you have in mind, each of these objects is an abstraction on its own, with certain operations which are essential to define the abstraction. For example, if you think of a graph in the sense of a line chart, the typical operations could be to add ...

12

What you are looking for is called a Persistent Data Structure. The canonical resource for persistent data structures is Chris Okasaki's Book Purely Functional Data Structures. Persistent data structures have gathered interest in recent times due to their popularization in Clojure and Scala. However, for some strange reason, Persistent Graphs seem to be ...

9

Very good question, but very tough to answer. I highly doubt, that such a book exists, because graphs are just another formalism and whether you apply it to your problem or not is a matter of two things: Knowledge about its existence. People who do not know about graphs and the corresponding algorithms for some very strange reason never come up with graph-...

9

Trees are Graphs. They are specifically directed, acyclic graphs where all child nodes only have one parent. If you need more than one parent then you use a DAG. If you need cycles or the graph needs to be undirected you'd use some kind of graph implementation. Note that the time and space complexity increases dramatically once you move into full graphs.

7

Other people have applied DAG to data, but I think it is at least as applicable (if not more so) to code. Mahbubur R Aaman mentions this, so really this is more of an addendum to his answer than a complete answer on its own. It occurs to me than any imperative computer program that is free of infinite loops (thanks @AndresF.) is a Directed Acyclic Graph (...

7

As depicted here, what you are looking for is the 1st-order 2-dimensional Voronoi diagram under the Manhattan, or L1-metric. This is a quite non-trivial problem (to solve efficiently), fortunately with many existing algorithms and software. You actually want the subset of the Voronoi diagram that coincides with the discrete grid defined by your matrix ...

7

2 simple solutions that immediately arise: Precompute everything via something like Johnson's algorithm, or use a standard search algorithm every time as you suggested - Dijkstra for example (which boils down to simple BFS, since the graph is unweighted). The first requires way too much storage/RAM to do. The second is prohibitively slow. What you (likely) ...

7

Your problem seems like a combination of maximum coverage and set packing problems. So my guess is that algorithms for them should be helpful. A greedy heuristic would be to choose the set that contains the largest number of uncovered elements over the conflicts with other sets.Another approach would be to use the integer linear program formulation of max ...

6

Currently DAG is underrated in programming. Historically many things related to development were made with trees and hierarchies because moving something in a box is convenient for our brain to make complex things easier to manage. But if you look at events and how they depend on other events and states then you will get DAG because anything in our life and ...

6

The simplest way I can think of to explain spotting graph cycles in layman's terms, is something like this: First, I assume you know the basics of what a graph is, and what nodes and edges are. This example assumes that you have a graph in which all edges are one-way only. Create your graph, and select one node as the starting point. Create a container ...

6

There is really an off-the-shelf algorithm for this: flood fill The idea is simply to start a search (DFS or BFS) from any empty space and mark it. If you want to be able to tell the chamber for each cell, you could mark it with a chamber number and a size number, whereas the latter increments during the search. Once the search terminates due to completely ...

6

Basic Algorithm Maintain two sets of the nodes you can reach from the start and end node. In alternating fashion, go three steps from both sides. Each time replacing your set with nodes you can reach through one more step. After each step you check the two sets for common nodes. Optimizations Make sure you can iterate the sets as sorted so that you can ...

6

Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph? It seems to me that you should use what we could label ”layered graphs”, i.e. add a combinator for graphs, say @, so that: If A and B are graphs then A@B is also a graph (i.e. can be fed to the algorithms of your ...

6

Your solution seems to try to tackle average reading time of nodes and all paths from them. This will, of course, work, provided it's properly implemented. The problem with this approach is that the quantities you calculate are not reusable. The average reading time of a node depends on how you got to it. Hence the quadratic behaviour of your naive solution....

6

There could be other efficient immutable data structures that fit your particular task, but are not as general as a doubly-linked list (which is unfortunately prone to concurrent modification bugs due to its mutability). If you specify your problem more narrowly, such a structure can probably be found. The general answer for (relatively) economic traversing ...

6

This is either fundamentally meaningless or you've left out an important detail. Your diagrams give each node 3 states: ● Unchanged, don't propagate ◌ Just now changed and in need of propagation ○ Old change, don't propagate But in the end it all goes back to ● unchanged. So nothing is learned. Which makes me think it's not really the same state as we ...

5

Proof by induction: Every acyclic graph can be represented as a tree, if all the nodes are connected. So let's think about trees. You've got one root node. Let's look at the simplest, case, in which the tree only has one branch, and so it's a simple linked list. If there are two nodes, there's one edge between them. Add one node to the end of the ...

5

This is NP-hard. If you have a solution for this problem, then you can use it on a graph with all edge weights set to 1. Then the resulting path will have the same number of nodes as the graph if and only if there is a Hamiltonian path. Since determining the existence of a Hamiltonian path is NP-hard even without finding specific solutions, any solution to ...

5

We keep thinking that we have all the tricky ones covered and then we realise that a certain structure causes problems we hadn't considered before. Testing every tricky that we can think of is what we are doing. That sounds like a good start. I guess you already tried to apply some classic techniques like boundary value analysis or equivalence partitioning,...

5

1. Randomized test generation Write an algorithm that generates graphs, have it generate a few hundred (or more) random graphs and throw each at your algorithm. Keep the random seed of the graphs that cause interesting failures and add those as unit tests. 2. Hard-code tricky parts Some graphs structures that you know are tricky you can code in right ...

5

If the area where the nodes can be is small (relatively, the size of half the US is small enough) and away from the poles then you can reasonably approach the problem using just the longitude and latitude as X/Y coordinates. Near the poles you can treat them as polar coordinates with the 90°-latitude as the distance from center and the longitude as the angle ...

5

Am I right that there are many possible answers to this question? And is my trace of the DPS correct? Yes, there is no 'natural' ordering of the nodes of a graph. So there is also no 'natural' ordering in the result of the DFS of a graph. Of course, in the example above, you could sort the nodes alphabetically as you have labels on them. If you assume ...

5

To compile a source file, you do not need to have compiled all dependencies before it. However, you do need something to link against: a kind of interface or header. In languages like Java, this is fairly simple since all user defined types have reference semantics. The structure and implementation of a type do not matter, only that it is named. Therefore, ...

Only top voted, non community-wiki answers of a minimum length are eligible