graph construction analysis and problem solving

Ben Holland

Call graph construction algorithms explained.

A call graph is an artifact produced by program analysis tools to record the relationships between a function and the functions it calls. If you’ve ever wondered how these call graphs actually get generated then keep reading because in this post I’ll be exploring several call graph construction algorithms and their tradeoffs.

Note: Some issues with the information in the RTA section of this article have been brought to my attention and will be fixed shortly. Thanks to David Bacon for pointing them out to me.

If you just want the nitty-gritty formal stuff then check out the paper by Tip and Palsberg , which inspired this post.

Let’s start by taking a look at a call graph. The figure below shows a call graph for a simple Java program that indicates the Java program has a method B that calls the method C and that C in turn calls methods B and D .

I’ve implemented each variation of the algorithms discussed in this post in an open source Eclipse plugin project called the call-graph-toolbox , which runs on top of the Atlas program analysis framework. Atlas provides an interface for creating Smart Views that allow you to click on source code or program graphs to instantly produce an updated program graph relevant to what you clicked. The call-graph-toolbox provides each call graph implementation as a Smart View so the differences in the algorithms can be observed visually. I’ll be using call-graph-toolbox to help show the differences of each algorithm discussed in this post.

The Problem(s)

Let’s start by understanding why it might be hard to create a call graph. To keep things simple we are just going to be considering Java, but know that the problem gets harder when we start talking about dynamically typed languages (such as Python or Ruby) or languages with function pointers (such as C, C++, or Objective-C).

Consider the following program.

• What will it print if we run it?
• What methods would be called at runtime?
• What edges should the ideal call graph have?

Static vs. Dynamic Dispatch

In Java, when we call a method, the binding between the callsite and the method to be called may be done at compile time or runtime. If the method binding is resolvable at compile time we call it a static dispatch. If at compile time we can’t resolve the callsite we call it a dynamic dispatch and resolve the callsite later at runtime. Dynamic dispatches are extremely common in Object Oriented languages like Java, so we should spend some time making sure we understand how they work.

Since a static dispatch is resolvable at compile time, we know exactly where to find the code for the method we are calling before we even run the program. In Java, calls to methods marked static and calls to constructors are both static dispatches. Since everything in Java is an object it makes sense that we should always know exactly where the code to construct new objects is located in our program. Methods that are marked static (class methods) do not require that we create an instance of an object to invoke the method. Every executable Java program has at least one static method, the main method, which makes sense because before we run the program we haven’t created any new objects yet, but we still want to invoke some procedure to use as an entry point into the program.

Java methods that are not marked static (instance methods) require an instance of an object. We can imagine a Person class with a method getName() that returns the name of a person. Since we don’t want to assign the same name to all people, the getName() method should be associated with an instance of a person. This means we need to call getName() on a Person object (and not directly on the type like a class method). A call to an instance method is resolved at runtime using a dynamic dispatch and the reason why will become clear soon.

Let’s take a look at the print callsite in the main method of our example program from above. The print method is declared in class A and then overridden by A ’s children in classes B , C , and D . We know that print is an instance method because it is not marked as a static method. If we run this program, the print method declared in class B will get executed. This is because the variable b2 is an object of type B . If you wanted to call the print method declared in class C you could replace b2 with c2 . This means that we have to know the type of the object the instance method is being called on to know which method will get called at runtime!

Now remember that every object in Java can be drawn in a tree hierarchy with java.lang.Object at the very top. The type hierarchy for our small program is shown below.

Any non-private instance method declared in a parent type is inherited by the child, unless that child provides an alternative implementation of the inherited method (by overriding the method). As a result of Java’s type hierarchy we can also assign any object type to a variable of the same type or a variable with the type of any of the object’s parent types (including java.lang.Object ). This means that someone could write the following code.

The instance method toString is declared in java.lang.Object so it can be called on any object type. Since we don’t know the type of the object in variable o we have to assume that java.lang.Object ’s toString method or any object that overrides toString could be called at runtime! Since Java highly encourages developers to override the toString method this leaves us with quite a few possibilities (and only one correct answer).

To answer our questions from above, we would all probably agree that an edge from the print callsite (at b2.print(c2) ) to B ’s print method implementation should be in our call graph because B ’s print method is what gets executed at runtime. We also know that it could be tricky to figure out exactly which method would get called at runtime as a result of a dynamic dispatch because it could be tricky to statically determine the runtime type of b2 . So should we conservatively add edges to A , B , C , and D ’s print methods if we can’t figure out the type of b2 even though A , C , and D ’s print methods are never called? What’s better a call graph with all of the possible edges or a call graph with only the edges we are sure are correct?

We say a call graph is “sound” if it has all the edges that are possible at runtime. We say a call graph is “precise” if it does not have edges that do not occur at runtime. It’s easy to be sound, but its hard to be sound and precise.

Whole vs. Partial Program Analysis

Partial program analysis occurs when we don’t have the entire program or when we can’t scale up our analysis to run over the entire program. You might think your Hello World program is small, but don’t forget you are running it on top of a vast set of libraries provided with the Java Runtime Environment. If you’re really crazy you might also consider the native implementation of the virtual machine itself or the operating system that virtual machine is running on and so on and so on!

In practice sometimes we just want to analyze a specific library, which could be used by many applications, so we are forced to do partial program analysis. Consider our example from before. What would happen if we removed the main method and just consider the classes A , B , C , and D ? Since the main method is the only place any types are actually created, it would look like the four print instance methods are just dead code, but don’t forget that this “library” could be used by any Java program! Since we could conceive of Java programs that could call all four print methods we can’t consider any of them dead code. So with that in mind it is going to be important to specify whether or not we are analyzing a partial program or a whole program when we construct our call graphs.

Idea 1 - Class Hierarchy Analysis (CHA)

Let’s start by building a sound call graph (we’ll worry about precision later). The first algorithm you might think to implement would probably be a variation of Reachability Analysis (RA). The basic idea is that for each method, we visit each callsite and then get the name of the method the callsite is referencing. We then add an edge from the method containing the callsite to every method with the same name as the callsite.

The result is a completely sound call graph, but not a very precise call graph. We might even match callsites of print(Object o) to a method that takes a different number of parameters such as print(Object o1, Object o2) . We could make our matching implementation stronger by matching the entire method signature (method name, method parameter counts/types, return type), but we still are going to have plenty of bad (conservative) matches. Consider the following code snippet with respect to our first example.

A simple reachability analysis would add edges from the print callsite to A , B , C , and D ’s print methods, but we declared b as a B type so we know the dispatch has to at least go to B or a child of B ’s print method. We don’t know what happened in the ... , so it is possible that an instance of a C type could have been assigned to b .

At this point it should be becoming clear that we could improve upon RA by considering the type hierarchy. Class Hierarchy Analysis (CHA) was first proposed in a 1995 paper by Dean, Grove, and Chambers to do just this. Class Hierarchy Analysis looks at the declared type of the variable (the receiver object) used to invoke the dynamic dispatch and restricts call edges to the inherited method implementation or the methods declared in the subtype hierarchy of the declared type of the receiver object. The result is a vast improvement on RA that is still sound and cheap to compute.

I’ve implemented both RA and CHA call graph construction algorithms in my call-graph-toolbox . The results for our first example are shown below. Note that RA picks up an extra print method signature in java.io.PrintStream .

Now let’s take a look at how CHA would do when analyzing a library. For the most part, it does pretty well! A class hierarchy analysis doesn’t care about where the types are instantiated, since it only uses the declared type of the receiver object. The only tricky part is that an application could declare a type that overrides an instance method in the library, in which case the dynamic dispatch could actually dispatch to a method outside of the library (an application callback). So how can we create a call edge for a method that doesn’t exist yet!? Well all we have to work with is the fact that whatever method is going to override our library method has to be in a subtype of the library’s type that declared the method being overridden.

Consider the case where a library defines a single abstract class with a method sort . The library contains no subtypes of Data that implement the sort method. Somewhere else in the library a call to the sort method is made. At runtime a subtype of Data will exist with a sort method, but not when the library was compiled. The best place I’ve seen this problem defined is as the Separate Compilation Assumption by Karim Ali .

There is no concrete method implementation for sort in our library, so adding a call edge from sortIt to sort might be a bit misleading (because Data ’s sort method can’t actually be a runtime dispatch target). Instead what we could do is modify CHA to add a “library-call” edge to sort to indicate that any dynamic dispatch that gets resolved at runtime must override sort . Running the call-graph-toolbox algorithm for CHA in library mode (available in the Eclipse preference menu) for this example shows an example of a “library-call” edge. Aside from abstract methods without any concrete method implementations, remember that any non-final method in any non-final class could be overridden by an application to form a callback.

Idea 2 - Rapid Type Analysis (RTA)

Class Hierarchy Analysis gives us a sound and cheap call graph. In fact it is the default call graph implementation for most static analysis tools (including Atlas), but can we do better? Remember that a dynamic dispatch has to be called on an instance of an object, which means that in order for a dispatch to be made to a particular type’s instance method at least one object of that type (or subtype) must have been allocated somewhere in the program. This is the core idea behind Rapid Type Analysis (RTA), which was proposed by Bacon and Sweeney (implementation details available in the extended technical report ).

Given a CHA call graph we start at the main method and iteratively construct a new call graph that is a subset of the CHA call graph by adding only the edges to the methods that are contained in types of objects that were allocated in the main method. The methods that are reachable through the newly added edges are added to a worklist and the process is repeated until the worklist is empty.

Methods can be inherited from parent types so we should consider the supertypes of the allocated types as well. RTA considers that a type could be allocated in a method and then passed as a parameter to another method. Since the resolved calling relationships are being built on-the-fly it’s important to note that RTA may evaluate a method several times (if new callers are discovered the method has to be re-evaluated). RTA runs until the worklist is empty, at which point it has reached a fixed point and cannot resolve any new call edges to add to the call graph.

The result of RTA on our first example is shown below.

RTA produces a more precise call graph than CHA (because it is a subset of CHA and removes edges that are likely not feasible at runtime), but the result is no longer sound. Let’s consider a few cases where RTA might not produce a sound call graph.

In the example above main calls foo , which allocates a new A type and stores the instance to a field v . Then main calls bar , which accesses the field and calls toString on the instance stored in v . RTA will not include an edge from bar to toString because neither bar or its parents ( main ) allocated any instance that toString could be called on (however some implementations might consider the String[] args to be a special implicit allocation of an array type of String types, but the type A still does not reach bar in the basic RTA implementation).

Let’s consider another example of unsoundness.

In this example main calls foo , which returns an allocation of type A that is then passed as a parameter in the call to bar . Again in this case the call edge to A ’s toString method would be missing because neither bar or its parents ( main ) allocated a type of A .

As you may have guessed we could modify RTA to consider fields and the types of method parameters and method return types to improve the accuracy of RTA, which is exactly what Tip and Palsberg proposed to do in the paper that inspired this post. In their paper, Tip and Palsberg propose to add several more constraints to RTA.

The first set of constraints concerns global variables and forms the basis for the first variation of RTA, Field Type Analysis (FTA). FTA adds the constraint that any method that reads from a field can inherit the field-compatible allocated types of any method that could write to that field.

The second variation of RTA, Method Type Analysis (MTA), adds constraints involving method parameter types and method return types. MTA adds the constraint that types allocated in a method and then passed to a method through a parameter should be compatible with the called method’s parameter types. MTA also adds the constraint that the return type of each called method be added to the set of allocated types. At first this may seem difficult because the return type would appear to depend on the resolution of dynamic dispatches, but the set of potential dynamic dispatches are statically typed to be the same return type.

Finally, we can combine both sets of constraints defined by MTA and FTA to form a Hybrid Type Analysis (XTA). The result of XTA on our first example is shown below. Note that the call graph depth has been expanded to reveal three newly resolved dispatches to getSimpleName , which are not resolved by RTA because the instance of the Class object is returned by getClass .

The idea of adding constraints to RTA to improve the accuracy and soundness of the base algorithm is an interesting idea and worth pursuing deeper. If we assume the standard Von Neumann model of a computer, then programs can only communicate data through the stack or the heap. FTA adds constraints for communicating through the heap when new allocations are created and stored in a global variable, while MTA adds additional constraints for communicating through the stack when methods are called with parameters and then subsequently return results. One other way to pass information is by creating and throwing an exception. Tip and Palsberg mention exception handling as an implementation issue, but do not propose a set of contraints to use as an approximation for analyzing programs with exceptions.

Since exception handling is extremely common in Java code, I propose another RTA variation, Exception Type Analysis (ETA), which adds the following constraint. Add the allocated and inherited types of any method with a throw site to every method that contains a reachable type compatible catch block in the current reverse call graph of throwing method. Of course this constraint could be added to XTA, so we should differentiate between the classic XTA and XTA with ETA. The result of ETA for the following code snippet is shown below.

Note that none of the RTA variants proposed by Tip and Palsberg specifically address this case and would fail to add the edge to MyException ’s toString method.

Now let’s play out the idea of adding constraints a bit further. Consider how RTA would address the following snippet of code.

The variable o1 is assigned an allocation of type A and then the variable o2 is assigned an allocation of type B . RTA is only looking at the allocation types, so the fact that o2 could only be a type B is lost in the approximation. Without considering the assignments that were made to the variable o2 it is impossible to rule out any other dispatch possibilities. We are reaching the point where we can no longer add any more constraints to refine the precision of our call graph without trying to directly determine the type of the variable for the callsite, which brings us to Variable Type Analysis (VTA) in the next section.

Before we move on, let’s consider how RTA performs on a library. Since RTA starts with a worklist containing only the main method, a library without a main method would result in an empty call graph without some modifications to RTA. Without the application code that is using the library, we have to assume that any method could be called by the application. Depending on how many assumptions we want to make we could restrict that set to say only public methods in the library, but we’d be ruling out the fact that an application might extend a type and inherit a protected method or use reflection to call a private method.

We should also assume that the application could allocate any type and pass it to a method, which pretty much brings us back to a Class Hierarchy Analysis in terms of precision. FTA and MTA would fair better than RTA alone for this last assumption as they would at least filter those types based on the compatibility of their types. Finally there is still the possibility the library contains calls to abstract methods that do not have any concrete implementations, so RTA should at least include the library calls calculated in CHA.

Idea 3 - Variable Type Analysis (VTA)

The last approach is rather direct. We have a reference to the variable that is used in the callsite, but we need to learn know its type. One rather straightforward idea is to start at every allocation site and record its type. Then we iterate over every assignment building a graph of each variable and the assignment of the allocation type to a variable or an assignment of a variable to a variable. At the end we can use the graph to answer which set of types a variable could point to based on what could have been assigned to that variable during the execution of the program.

The algorithm looks remarkably similar to RTA in that it is a fixed point algorithm using a worklist, but since we are considering much more information than RTA the cost of running VTA is going to be much higher. Without getting too deep into points-to analysis (a subject for another day) it’d be good to note that a VTA implementation could be accomplished with an implementation of a full blown points-to, which tracks the allocation site that each variable in the program could point-to, or a slimmed down version of a points-to that is only tracking the type of the allocation site for each variable in the program.

The precision of VTA is going to be much better than RTA, but depends on a whole new set of hard problems in computer science that is the focus of much of the recent research in this area. I’ll group all of these problems into one bucket and call them “sensitivities”. One such sensitivity is “flow sensitivity”, which refers to whether or not the ordering of the assignments is taken into account. For example if we assigned the result of a new A type allocation to a variable o and then immediately overwrote the value of o with a different allocation type of B , a locally flow-sensitive implementation could take advantage of the fact that o could only be of type B immediately after the second assignment.

For basic blocks it’s possible to be locally flow-sensitive relatively easily using a Static Single Assignment (SSA) form , but things get tricky when we start talking about loops or the ordering of inter-procedural flows (also known as context-sensitivity). In fact, we know a perfectly precise points-to analysis is simply not possible, because the entire problem can be reduced to the halting problem (see Landi , Ramalingam , Reps ).

The call graph toolbox implements a call graph based on the results of a context-insensitive points-to analysis I wrote available in the points-to toolbox . A context-insensitive points-to analysis is called a 0-CFA (when context is defined as calling context). The results for our first example are shown below.

In general a points-to based call graph will suffer from similar ailments as RTA and its variants when it comes to library analysis. The difficultly in being precise is not knowing what could happen outside of the code being analyzed. Without a main method a points-to analysis has to consider every allocation type as being possible at runtime and propagate that information forward until a fixed point is reached, but this can be incredibly expensive for large applications. Current research focuses on performing precise yet scalable points-to analysis because it is the basis for solving many program analysis tasks (such as alias analysis, type inference, and call graph construction).

Evaluation and Conclusion

So…which call graph construction algorithm should I use? Well let’s run some numbers on a large application and see.

ConnectBot (Android Application)

Personally, when I test out a new program analysis tool, I like to use the Android application ConnectBot because I’m familiar with it, it is open source, it is fairly large (~235 classes, 33K logical lines of code), and it is decently complex. The developer(s) always seem to do something a little differently than you would expect.

For instance, ConnectBot has an abstract class that defines a concrete method, which is then intentionally overridden by all the abstract class’s children. The base method is an empty method implementation that just has a comment to the effect of “all base classes should override this method” , which just pains me to see because without marking the method abstract we can’t actually guarantee that all children will implement the method. It’s a bug waiting to happen if a new developer doesn’t notice this pattern and accidently, but silently inherits the empty implementation from its parent type. This is one of the reasons why we have abstract methods in the first place!

So if it is true that all the children override the concrete method and the base method’s type cannot be instantiated (because it’s abstract) then the base method is actually dead code and should be removed from the CHA result. Thank you ConnectBot developers for making my program analysis code better by writing goofy code, but…

The results of running each call graph construction algorithm on ConnectBot are shown in the table below.

ConnectBot contains 9,966 callsites with 3,938 static dispatches and 6,028 dynamic dispatches. Of the 6,028 dynamic dispatch callsites, I computed the minimum, maximum, and average number of potential dispatch targets each algorithm resolved. The number of nodes refers to the number of methods in the resulting call graph, whereas the number of edges refers to the number of call edge relationships in the resulting call graph.

It’s also important to note that ConnectBot is an Android application, which means it does not have a main method. It is possible to model the Android lifecycle to figure out the application entry points, but that was not done for this analysis and the call graphs were simply produced using the library assumptions stated earlier for each algorithm.

The time column should be taken with a grain of salt. I implemented most algorithms focusing on correctness and readability and didn’t optimize the code too heavily (some caching would go a long way). The points-to analysis on the hand is very optimized code and completes in under half a second and the results are then used to reconstruct the call and control flow graphs after the fact.

Aside from timing, the Min column is interesting. In this table we are including library calls (call edges to abstract methods when no implementation is available) so a callsite with no resolvable dispatches means the algorithm is unsound. We should expect this from RTA and its variants and depending on the implementation, points-to analysis as well. In this case, the points-to analysis is unsound because it was not considering new allocations that occur inside the Java Runtime libraries.

The Average column is also interesting. At runtime only one dispatch target is actually possible for a callsite at a given point in the program execution (its possible the callsite location could be a different target at a later point in the execution). So in an ideal world, our static analysis tool would report exactly one potential dispatch target for each callsite (in a given context). An average number of potential dispatch targets that approaches 1.0 is a sign of a precise call graph. In our results the 0-CFA is the closest to the ideal value.

Apache Commons IO (Application Mode)

Let’s analyze one more application just so we can try out whole program analysis. For this project, I downloaded the source code of the Apache Commons IO 2.4 library and imported all library code into an Eclipse project. I then included the HexDumpTest test from the test package. To make things simple I remove the JUnit assertions and added a main method that created a new HexDumpTest and called the testDump . The results are shown in the table below.

The project contained 2,931 callsites, with 1,634 static dispatches and 1,297 dynamic dispatches.

In this table the Min , Max , and Average columns should be taken with another grain of salt because we are only considering methods reachable from the main method, so callsites outside of that reachable set of methods are dead code and should not have resolvable targets!

Apache Commons IO (Library Mode)

For comparison, I commented out the HexDumpTest.main method and collected the table statistics again with library analysis enabled. Without the main method, the project contained 2,929 callsites, with 1,633 static dispatches and 1,296 dynamic dispatches.

So to answer the question, which algorithm is the best? CHA is a great contender for when soundness is required and we don’t want to invest a lot of computation time. If we can relax the soundness requirement a bit we might consider RTA or one of its variants, but in my experience most research is trending towards figuring out how to scale a points-to analysis for sound-ish and precise results.

Closing Thoughts

Tip and Palsberg present a nice overview diagram in Figure 1 of their paper , which I have reproduced below with some modifications.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Graph Data Structure And Algorithms

• Introduction to Graph Data Structure
• Graph and its representations
• Types of Graphs with Examples
• Basic Properties of a Graph
• Applications, Advantages and Disadvantages of Graph
• Transpose graph
• Difference Between Graph and Tree

BFS and DFS on Graph

• Breadth First Search or BFS for a Graph
• Depth First Search or DFS for a Graph
• Applications, Advantages and Disadvantages of Depth First Search (DFS)
• Applications, Advantages and Disadvantages of Breadth First Search (BFS)
• Iterative Depth First Traversal of Graph
• BFS for Disconnected Graph
• Transitive Closure of a Graph using DFS
• Difference between BFS and DFS

Cycle in a Graph

• Detect Cycle in a Directed Graph
• Detect cycle in an undirected graph
• Detect Cycle in a directed graph using colors
• Detect a negative cycle in a Graph | (Bellman Ford)
• Cycles of length n in an undirected and connected graph
• Detecting negative cycle using Floyd Warshall
• Clone a Directed Acyclic Graph

Shortest Paths in Graph

• How to find Shortest Paths from Source to all Vertices using Dijkstra's Algorithm
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson's algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Multistage Graph (Shortest Path)
• Shortest path in an unweighted graph
• Karp's minimum mean (or average) weight cycle algorithm
• 0-1 BFS (Shortest Path in a Binary Weight Graph)
• Find minimum weight cycle in an undirected graph

Minimum Spanning Tree in Graph

• Kruskal’s Minimum Spanning Tree (MST) Algorithm
• Difference between Prim's and Kruskal's algorithm for MST
• Applications of Minimum Spanning Tree
• Total number of Spanning Trees in a Graph
• Minimum Product Spanning Tree
• Reverse Delete Algorithm for Minimum Spanning Tree

Topological Sorting in Graph

• Topological Sorting
• All Topological Sorts of a Directed Acyclic Graph
• Kahn's algorithm for Topological Sorting
• Maximum edges that can be added to DAG so that it remains DAG
• Longest Path in a Directed Acyclic Graph
• Topological Sort of a graph using departure time of vertex

Connectivity of Graph

• Articulation Points (or Cut Vertices) in a Graph
• Biconnected Components
• Bridges in a graph
• Eulerian path and circuit for undirected graph
• Fleury's Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Word Ladder (Length of shortest chain to reach a target word)
• Find if an array of strings can be chained to form a circle | Set 1
• Tarjan's Algorithm to find Strongly Connected Components
• Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
• Dynamic Connectivity | Set 1 (Incremental)

Maximum flow in a Graph

• Max Flow Problem Introduction
• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem
• Introduction to Push Relabel Algorithm
• Introduction and implementation of Karger's algorithm for Minimum Cut
• Dinic's algorithm for Maximum Flow

Some must do problems on Graph

• Find size of the largest region in Boolean Matrix
• Count number of trees in a forest
• A Peterson Graph Problem
• Clone an Undirected Graph
• Introduction to Graph Coloring
• Traveling Salesman Problem (TSP) Implementation
• Introduction and Approximate Solution for Vertex Cover Problem
• Erdos Renyl Model (for generating Random Graphs)
• Chinese Postman or Route Inspection | Set 1 (introduction)
• Hierholzer's Algorithm for directed graph
• Boggle (Find all possible words in a board of characters) | Set 1
• Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
• Construct a graph from given degrees of all vertices
• Determine whether a universal sink exists in a directed graph
• Number of sink nodes in a graph
• Two Clique Problem (Check if Graph can be divided in two Cliques)

Graph Data Structure is a collection of nodes connected by edges . It’s used to represent relationships between different entities. Graph algorithms are methods used to manipulate and analyze graphs, solving various problems like finding the shortest path or detecting cycles.

Table of Content

What is Graph Data Structure?

• Components of a Graph
• Basic Operations on Graphs
• Applications of Graph
• Basics of Graph
• BFS and DFS in Graph
• Cycles in Graph
• Shortest Path in Graph
• Minimum Spanning Tree
• Connectivity in Graph
• Maximum Flow in Graph
• Some must do Problems on Graph
• Some Quizzes

Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a  Graph  is composed of a set of vertices(  V  ) and a set of edges(  E  ). The graph is denoted by  G(V, E).

Graph data structures are a powerful tool for representing and analyzing complex relationships between objects or entities. They are particularly useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structures can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Components of a Graph:

• Vertices:  Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabeled.
• Edges:  Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabelled.

Basic Operations on Graphs:

Below are the basic operations on the graph:

• Insertion of Nodes/Edges in the graph – Insert a node into the graph.
• Deletion of Nodes/Edges in the graph – Delete a node from the graph.
• Searching on Graphs – Search an entity in the graph.
• Traversal of Graphs – Traversing all the nodes in the graph.

Applications of Graph:

Following are the real-life applications:.

•  Graph data structures can be used to represent the interactions between players on a team, such as passes, shots, and tackles. Analyzing these interactions can provide insights into team dynamics and areas for improvement.
• Commonly used to represent social networks, such as networks of friends on social media.
• Graphs can be used to represent the topology of computer networks, such as the connections between routers and switches.
• Graphs are used to represent the connections between different places in a transportation network, such as roads and airports.
• Graphs are used in Neural Networks where vertices represent neurons and edges represent the synapses between them. Neural networks are used to understand how our brain works and how connections change when we learn. The human brain has about 10^11 neurons and close to 10^15 synapses.

Basics of Graph:

• Introduction to Graphs
• Difference between graph and tree

BFS and DFS in Graph:

• Breadth First Traversal for a Graph
• Depth First Traversal for a Graph
• Applications of Depth First Search
• Applications of Breadth First Traversal
• Iterative Depth First Search

Cycles in Graph:

• Detect cycle in a direct graph using colors
• Union By Rank and Path Compression in Union-Find Algorithm
• Introduction to Disjoint Set Data Structure or Union-Find Algorithm

Shortest Path in Graph:

• Dijkstra’s shortest path algorithm
• Johnson’s algorithm for All-pairs shortest paths
• Dial’s Algorithm
• Karp’s minimum mean (or average) weight cycle algorithm

Minimum Spanning Tree:

• Prim’s Minimum Spanning Tree (MST)
• Kruskal’s Minimum Spanning Tree Algorithm
• Difference between Prim’s and Kruskal’s algorithm for MST
• Applications of Minimum Spanning Tree Problem
• Minimum cost to connect all cities
• Boruvka’s algorithm for Minimum Spanning Tree

Topological Sorting:

• All topological sorts of a Directed Acyclic Graph
• Kahn’s Algorithm for Topological Sorting
• Maximum edges that can be added to DAG so that is remains DAG

Connectivity in Graph:

• Eulerian path and circuit
• Fleury’s Algorithm for printing Eulerian Path or Circuit
• Length of shortest chain to reach the target word
• Find if an array of strings can be chained to form a circle
• Tarjan’s Algorithm to find strongly connected Components

Maximum Flow in Graph:

• Karger’s Algorithm- Set 1- Introduction and Implementation
• Dinic’s algorithm for Maximum Flow

Some must do Problems on Graph:

• Find length of the largest region in Boolean Matrix
• Graph Coloring (Introduction and Applications)
• Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)
• K Centers Problem | Set 1 (Greedy Approximate Algorithm)
• Hierholzer’s Algorithm for directed graph
• Check whether a given graph is Bipartite or not
• Snake and Ladder Problem
• Boggle (Find all possible words in a board of characters)
• Hopcroft Karp Algorithm for Maximum Matching-Introduction
• Minimum Time to rot all oranges

Some Quizzes:

• Quizzes on Graph Traversal
• Quizzes on Graph Shortest Path
• Quizzes on Graph Minimum Spanning Tree
• Quizzes on Graphs

Quick Links :

• Top 10 Interview Questions on Depth First Search (DFS)
• Some interesting shortest path questions
• Practice Problems on Graphs
• Videos on Graphs

Recommended:

• Learn Data Structure and Algorithms | DSA Tutorial

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

• solidarity - (ua) - (ru)
• news - (ua) - (ru)
• donate - donate - donate

for scientists:

• ERA4Ukraine
• Assistance in Germany
• Ukrainian Global University
• #ScienceForUkraine

default search action

• combined dblp search
• author search
• venue search
• publication search

"Data-driven causal knowledge graph construction for root cause analysis in ..."

Details and statistics.

DOI: 10.1080/00207543.2022.2078748

access: closed

type: Journal Article

metadata version: 2023-08-28

Please note: Providing information about references and citations is only possible thanks to to the open metadata APIs provided by crossref.org and opencitations.net . If citation data of your publications is not openly available yet, then please consider asking your publisher to release your citation data to the public. For more information please see the Initiative for Open Citations (I4OC) . Please also note that there is no way of submitting missing references or citation data directly to dblp.

Please also note that this feature is work in progress and that it is still far from being perfect. That is, in particular,

• the lists below may be incomplete due to unavailable citation data,
• reference strings may not have been successfully mapped to the items listed in dblp, and
• we do not have complete and curated metadata for all items given in these lists.

JavaScript is requires in order to retrieve and display any references and citations for this record.

manage site settings

To protect your privacy, all features that rely on external API calls from your browser are turned off by default . You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.

Unpaywalled article links

load links from unpaywall.org

Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy .

Archived links via Wayback Machine

load content from archive.org

Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy .

Reference lists

load references from crossref.org and opencitations.net

Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org , opencitations.net , and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy , as well as the AI2 Privacy Policy covering Semantic Scholar.

Citation data

load citations from opencitations.net

Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.

OpenAlex data

load data from openalex.org

Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex .

see also: Terms of Use | Privacy Policy | Imprint

dblp was originally created in 1993 at:

since 2018, dblp has been operated and maintained by:

the dblp computer science bibliography is funded and supported by:

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

What are good examples of problems that graphs can solve better than the alternative? [closed]

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?

• data-structures
• graph-theory

• 3 By the way, don't buy those myths about Google interviews. Compared to other places, they sometimes ask super simple and straightforward questions, which can actually throw you off. –  Uri Commented Apr 1, 2009 at 4:08

19 Answers 19

Computer Networks: Graphs model intuitively model computer networks and the Internet. Often nodes will represent end-systems or routers, while edges represent connections between these systems.

Data Structures: Any data structure that makes use of pointers to link data together is making use of a graph of some kind. This includes tree structures and linked lists which are used all the time.

Pathing and Maps: Trying to find shortest or longest paths from some location to a destination makes use of graphs. This can include pathing like you see in an application like Google maps, or calculating paths for AI characters to take in a video game, and many other similar problems.

Constraint Satisfaction: A common problem in AI is to find some goal that satisfies a list of constraints. For example, for a University to set it's course schedules, it needs to make sure that certain courses don't conflict, that a professor isn't teaching two courses at the same time, that the lectures occur during certain timeslots, and so on. Constraint satisfaction problems like this are often modeled and solved using graphs.

Molecules: Graphs can be used to model atoms and molecules for studying their interaction and structure among other things.

• 5 +1 for Constraint Satisfaction. –  hasan Commented Nov 19, 2009 at 20:11
• 1 The part on constraint satisfaction sounds interesting. Do you have any articles or papers on this topic to share? –  Markus Johnsson Commented Feb 8, 2011 at 22:03
• @MahlerFive, I'd love to learn more about constraint satisfaction that as well. Could you please point to the resources worth looking into? –  Uzbekjon Commented Feb 25, 2012 at 18:33

I am very very interested in graph theory and ive used it solved so many different kinds of problem. You can solve a lot of Path related problem, matching problem, structure problems using graph.

Path problems have a lot of applications.

This was in a career cup's interview question. Say you want to find the longest sum of a sub array. For example, [1, 2, 3, -1] has the longest sum of 6. Model it as a Directed Acyclic Graph ( DAG ), add a dummy source, dummy destination. Connect each node with an edge which has a weight corresponding to the number. Now use the Longest Path algorithm in the DAG to solve this problem.

Similarly, Arbitrage problems in financial world or even geometry problems of finding the longest overlapping structure is a similar path problem.

Some obvious ones would be the network problems (where your network could have computers people, organisation charts, etc). You can glean a lot of structural information like

• which point breaks the graph into two pieces
• what is the best way to connect them
• what is the best way to reach one place to another
• is there a way to reach one place from another, etc.

I've solved a lot of project management related problems using graphs. A sequence of events can be pictured as a directed graph (if you don't have cycles then thats even better). So, now you can

• sort the events according to their priority
• you can find the event that is the most crucial (that is would free a lot of other projects)
• you can find the duration needed to solve the total project (path problem), etc.

A lot of matching problems can be solved by graph. For example, if you need to match processors to the work load or match workers to their jobs. In my final exam, I had to match people to tables in restaurants. It follows the same principle (bipartite matching -> network flow algorithms). Its simple yet powerful.

A special graph, a tree , has numerous applications in the computer science world. For example, in the syntax of a programming language, or in a database indexing structure.

Most recently, I also used graphs in compiler optimization problems. I am using Morgan's Book, which is teaching me fascinating techniques.

The list really goes on and on and on. Graphs are a beautiful math abstraction for relation . You really can do wonders, if you can model it correctly. And since the graph theory has found so many applications, there are many active researches in the field. And because of numerous researches, we are seeing even more applications which is fuelling back researches.

If you want to get started on graph theory, get a good beginner discrete math book ( Rosen comes to my mind), and you can buy books from authors like Fould or Even . CLRS also has good graph algorithms.

Your source code is tree structured, and a tree is a type of graph. Whenever you hear people talking about an AST (Abstract Syntax Tree), they're talking about a kind of graph.

Pointers form graph structures. Anything that walks pointers is doing some kind of graph manipulation.

The web is a huge directed graph. Google's key insight, that led them to dominate in search, is that the graph structure of the web is of comparable or greater importance than the textual content of the pages.

State machines are graphs. State machines are used in network protocols, regular expressions, games, and all kinds of other fields.

It's rather hard to think of anything you do that does not involve some sort of graph structure.

An example most people are familiar: build systems. Make is the typical example, but almost any good build system relies on a Directed Acyclic Graph. The basic idea is that the direction models the dependency between a source and a target, and you should "walk" the graph in a certain order to build things correctly -> this is an example of topological sort.

Another example is source control system: again based on a DAG. It is used for merging, for example, to find common parent.

Well, many program optimization algorithms that compilers use are based on graphs (e.g., figure out call graph, flow control, lots of static analysis).

Many optimization problems are based on graph. Since many problems are reducable to graph colouring and similar problems, then many other problems are also graph based.

I'm not sure I agree that graphs are the best way to represent every relation and I certainly try to avoid these "got a nail, let's find a hammer" approaches. Graphs often have poor memory representations and many algorithms are actually more efficient (in practice) when implemented with matrices, bitsets, and other things.

OCR. Picture a page of text scanned at an angle, with some noise in the image, where you must find the space between lines of text. One way is to make a graph of pixels, and find the shortest path from one side of the page to the other, where the difference in brightness is the distance between pixels.

This example is from the Algorithm Design Manual , which has lots of other real world examples of graph problems.

One popular example is garbage collection.

The collector starts with a set of references, then traverses all the objects they reference, then all the objects referenced there and so on. Everything it finds is added into a graph of reachable objects. All other objects are unreachable and collected.

To find out if two molecules can fit together. When developing drugs one is often interested in seeing if the drug molecules can fit into larger molecules in the body. The problem with determining whether this is possible is that molecules are not static. Different parts of the molecule can rotate around their chemical bindings so that a molecule can change into quite a lot of different shapes.

Each shape can be said to represent a point in a space consisting of shapes. Solving this problem involves finding a path through this space. You can do that by creating a roadmap through space, which is essentially a graph consisting of legal shapes and saying which shape a shape can turn into. By using a A* graph search algorithm through this roadmap you can find a solution.

Okay that was a lot of babble that perhaps wasn't very understandable or clear. But my point was that graphs pop up in all kinds of problems.

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.

The following are based on graph theory:

• Binary trees and other trees such as Red-black trees, splay trees, etc.
• Linked lists
• Anything that's modelled as a state machine (GUIs, network stacks, CPUs, etc)
• Decision trees (used in AI and other applications)
• Complex class inheritance

IMHO most of the domain models we use in normal applications are in some respect graphs. Already if you look at the UML diagrams you would notice that with a directed, labeled graph you could easily translate them directly into a persistence model. There are some examples of that over at Neo4j

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

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.

Profiling and/or Benchmarking algorithms and implementations in code.

Anything that can be modelled as a foreign key in a relational database is essentially an edge and nodes in a graph.

Maybe that will help you think of examples, since most things are readily modelled in a RDBMS.

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

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

• 2 This answer is a great example of why link only answers should not be well received on stack overflow. All of your links are broken now. –  mikeazo Commented Apr 23, 2015 at 18:15

Analysing transaction serialisability in database theory.

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.

Basically nearlly all common data structures like trees, lists, queues, etc, can be thought as type of graph, some with different type of constraint.

To my experiences, I have used graph intensively in network flow problems , which is used in lots of areas like telecommunication network routing and optimisation, workload assignment , matching , supply chain optimisation and public transport planning .

Another interesting area is social network modelling as previous answer mentioned.

There are far more, like integrated circuit optimisation , etc.

Not the answer you're looking for? Browse other questions tagged data-structures graph graph-theory or ask your own question .

• Featured on Meta
• Upcoming sign-up experiments related to tags
• Policy: Generative AI (e.g., ChatGPT) is banned
• The [lib] tag is being burninated
• What makes a homepage useful for logged-in users

Hot Network Questions

• How will the ISS be decommissioned?
• Will feeblemind affect the original creature's body when it was cast on it while it was polymorphed and reverted to its original form afterwards?
• A 90s (maybe) made-for-TV movie (maybe) about a group of trainees on a spaceship. There is some kind of emergency and all experienced officers die
• Is there any legal justification for content on the web without an explicit licence being freeware?
• DSP Puzzle: Advanced Signal Forensics
• Tombs of Ancients
• Weird behavior by car insurance - is this legit?
• Would the category of directed sets be better behaved with the empty set included, or excluded?
• What kind of sequence is between an arithmetic and a geometric sequence?
• Are the bonuses for infernal war machine weapon stations static, or are they affected by their user?
• Are there paintings with Adam and Eve in paradise with the snake with legs?
• What was the first game to intentionally use letterboxing to indicate a cutscene?
• Fantasy TV series with a male protagonist who uses a bow and arrows and has a hawk/falcon/eagle type bird companion
• How do you say "living being" in Classical Latin?
• Interchangeability of る and ている
• Old book about a man who finds an abandoned house with a portal to another world
• Were there engineers in airship nacelles, and why were they there?
• Are both vocal cord and vocal chord correct?
• À + infinitive at start of sentence
• Visit USA via land border for French citizen
• How to fix misaligned objects that look fine in viewport but not in render?
• How do guitarists remember what note each string represents when fretting?
• What does ‘a grade-hog’ mean?
• Cleaning chain a few links at a time