What are good examples of problems that graphs can

Question

After reading Stevey Yegge's Get That Job At Google article, I found this little quote interesting:

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50–50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!

What are some examples of problems that are best represented and/or solved by graph data structures/algorithms?

One example I can think of: navigation units (ala Garmin, TomTom), that supply road directions from your current location to another, utilize graphs and advanced pathing algorithms.

What are some others?

Answer 1

Graphs are great for managing dependencies.

I recently started to use the Castle Windsor Container, after inspecting the Kernel I found a GraphNodes property. Castle Windsor uses a graph to represent the dependencies between objects so that injection will work correctly. Check out this article.

I have also used simple graph theory to develop a plugin framework, each graph node represent a plugin, once the dependencies have been defined I can traverse the graph to create a plugin load order.

I am planning on changing the algorithm to implement Dijkstra's algorithm so that each plugin is weighted with a specific version, thus a simple change will only load the latest version of the plugin.

I with I had discovered this sooner. I like that quote "Whenever someone gives you a problem, think graphs." I definitely think that's true.

Answer 2

Graphs are not data structures. They are mathematical representation of relations. Yes, you can think and theoretize about problems using graphs, and there is a large body of theory about it. But when you need to implement an algorithm, you are choosing data structures to best represent the problem, not graphs. There are many data structures that represent general graphs, and even more for special kinds of graphs.

In your question, you mix these two things. The same theoretical solution may be in terms of graph, but practical solutions may use different data structures to represent the graph.

Answer 3

Social connections between people make an interesting graph example. I've tried to model these connections at the database level using a traditional RDMS but found it way too hard. I ended up choosing a graph database and it was a great choice because it makes it easy to follow connections (edges) between people (nodes).

Answer 4

You can utilise graphs anywhere you can define the problem domain objects into nodes and the solution as the flow of control and/or data amongst the nodes.

Considering the fact that trees are indeed connected-acyclic graphs, there are even more areas you can use the graph theory.

Answer 5

You could take a look at some of the examples in the Neo4j wiki,

http://wiki.neo4j.org/content/Domain_Modeling_Gallery

and the projects that Neo4j is used in (the known ones)

http://wiki.neo4j.org/content/Neo4j_In_The_Wild .

Otherwise, Recommender Algorithms are a good use for Graphs, see for instance PageRank, and other stuff at

http://wiki.github.com/tinkerpop/gremlin/pagerank

Answer 6

Profiling and/or Benchmarking algorithms and implementations in code.