# Tag Info

49

Yes: Dijkstra Dijkstra works just as well for this situation. You just use time rather than distance as the weight of each arc.

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 ...

29

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 ...

26

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

Yes. Dijkstra's algorithm will solve this problem. The problem in your case is that you automatically assume the shortest path equates to distance travelled, when in fact it more appropriately equates to the COST of taking a route. If one path has a roadblock then its COST should be higher, and the algorithm still applies.

16

The NP-Hard domain of problems means that, as far as current mathematical knowledge goes, the problem can only be solved by trying every permutation and choosing the correct answer. If you can solve the problem more efficiently than the brute force method, you will win a Noble Prize in mathematics as a bonus. The best mathematicians have been working on a ...

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

I personally suggest Markov clustering. I have used it several times in the past with good results. Affinity propagation is another viable option, but it seems less consistent than Markov clustering. There are various other options, but these two are good out of the box and well suited to the specific problem of clustering graphs (which you can view as ...

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

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 ...

12

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) |/ ...

11

This doesn't answer your question. However. It seems necessary. class Person: name = None age = None Doesn't do what you're suggesting. Those are two class-level attributes. They're emphatically not instance variables. Also. You don't "declare" attributes at all. You don't declare them like that. Person p isn't proper Python. p= Person() ...

11

You should just be able to replace your distance with the time between nodes and solve it the same way.

11

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 ...

10

Dijkstra As said before, it is not only used for shortest distance. I believe this animation gives a good understanding of the "power" (for lack of a better word) of Dijkstra:

10

Hierarchical Clustering This was recommended to me by a friend. According to Wikipedia: In this method one defines a similarity measure quantifying some (usually topological) type of similarity between node pairs. Commonly used measures include the cosine similarity, the Jaccard index, and the Hamming distance between rows of the adjacency matrix. Then ...

9

As others pointed out, a site like cstheory may be more helpful. From what I can understand of your problem this sounds pretty much exactly like the subgraph isomorphism problem: Given two graphs G and H find a subgraph of H that is isomorphic to G. What you tried to express with "matching" 0 and 1, and so on, is referred to as isomorphism in a 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.

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-...

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

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 (...

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

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

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 ...

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