Welcome to my 4th article of the #2Articles1Week challenge! Though I seem to have lost the challenge, but that won't stop me lel.
We do often see the most important tag next to Algorithms with Graphs on almost every video or articles for cracking coding interviews. So in this article we will take a brief look into that. This is more focused on the applications of the structure and it's overall importance, so you might want to look at a different article for implementations or algorithm analysis.
Speaking of coding interviews do check out Coding Tips's blog post on How to Ace the Coding Interviews. I am probably gonna refer to this guide when my interviews come around.
A Brief Introduction :
Graph is a Data Structure. A Data Structure is a way of organizing data in an efficient manner and in graphs that data is organised in a symbolic representation of networks between vertices/nodes and edges.
We can look at nodes as chunk of data and edges as relations between those chunks.
There are Directed Graphs that specify the degree of access ( number of nodes accessed from the present node ) for a particular vertex with other vertices and there are Undirected Graphs that don't specify the degree of access. Others include Weighted graphs where each edge is given a particular numerical weight.
Brief look on the implementation :
There are 3 ways in which graphs can be implemented :
1. Adjacency Lists :
This is often used when graphs are sparse, i.e, when the number of edges are much lesser than the possible number of nodes. It's efficient in storage and represents sparse graphs very well.
Nodes are stored as objects and every node holds a list of adjacent nodes. This data structure allows the storage of additional data on the nodes in the form of lists. Example :
adjacency_list['Alice Smith'] = [{'friends_with': 'Kim'}, {'enemies_with':'Kourtney'}, {'fan_of':'Khloé'}, {'friends_with': 'Rob'}, {'ride_or_die_with':'Kendall'}, {'bff_with': 'Kylie'}]
here we can see Alice Smith to be connected with everyone by the list and the type of connection is denoted by the dictionary key.
2. Ajacency Matrices :
This is used when the graphs are dense or when connection speed needs to be super fast. Because of matrix implementation, determining connection between node A and node B requires a time complexity of O(1). The main drawback is the storage needs which is O(N>2) where N is number of nodes.
A 2D list where the first dimension index represent source nodes and the second dimension index represent the destination node. Sounds simple yes.
For example, in the list list[0][1] , 0 represents the 0th index source node and 1 represents the 1th index destination node. If the relationship between the two nodes have specific weights ( quanititative value ), the value for list[0][1]=4 will be it's weight. Data for the nodes must be stored externally from the adjacency matrix.
3. Incidence Matrix :
This is used when edges are super important. If I care more about the relationships than the nodes in the relationships, this can be helpful.
A 2D list where first dimension represents nodes and the second dimension represents edges. For exampe, in the list list[0][1], 0 represents the 0th index source node and 1 represents the 1st edge. This is useful when you want to do complicated matrix math or search for a relationship such as give me all the nodes that have a relationship of "brother".
For a more detailed look into the technical aspects you can take a look at this article. I prefer them for most of my DSAlgo needs.
WHY Graph Theory ?
Every non-trivial program is a graph. Calls to functions, variable access and scoping, objects, all of that is graph theory.
If you want something more explicit, every memory management method. The simplest mark-and-sweep involves creating a spanning tree of a digraph. Using reference counting effectively requires awareness of cyclic and acyclic graphs.
In more specific terms, Adventure games are an example too. Locations are vertices and motion between them requires edge traversal. Auto help requires finding paths between them. Also Google Maps involves the finding of shortest path from the source to destination involves the use of Algorithms like Djikstra's.
The Algorithms and Ideas for Personal Projects.
Choosing an algorithms for a problem is a matter of prefernce. In case of :
- Coding Interviews : We go for DFS, BFS, Djikstra's Algorithm and A* Algorithm.
There are many more and one extends on the other. There is not a need to know all of them thoroughly, but we can play around with some cool personal projects, among which the most popular ones include pathfinding visualizers using Djikstra's Algorithm that guarantees the shortest path to the destination node or using A* Algorithm to optimize it for more practical applications.
- Check out this Path Finding Visualizer by Clement using different Graph traversal Algorithms. This is just so freaking cool!
- Here's a list of Pathfinding projects for reference.
Broader Industrial Applications :
1. Network System and its Security :
A Twitter Social Graph
Determining friends of friends and other relationship paths in these type of graphs without the graph data model can be painful and become grossly inefficient with only a relatively few records.
Graph theory is widely used in representation of Network System. Graph theory in networking can be observed in two categories: Topology and Network theory. Topology is the way to represent a network structure in various formats that can help in making the problem easier and deriving more accurate results. The term network and graph are similar as both refer to topology (structure) in which vertices and edges are arranged. The term Network theory represents the different methodologies to analyze a graph and applying network theory using a topology. In more simple terms it is great in determining relationships.
The team of computer scientists at the Virology and Cryptology Lab, ESAT and the French Navy, has recently used the vertex cover algorithm to design optimal strategies for protecting the network against virus attacks in real time. This is an optimal solution for designing the network defense strategy. The network activity is used to solve large number of combinatorial problems.
2. Website Designing :
The graph theory is used to model the website designing process, where web pages
are represented by vertices and the hyper links between them are represented by edges in the
graph. This concept is known as web graph. Graph representation helps in finding all connected components
and using directed graph we can evaluate website utility and hierarchy structure.
3. Data Science Problems :
In data science there are various entities that have different correlations with one another for coming around with the optimal insight. Graphs help in describing those relationships using different algorithms like :
- Shortest Path Algorithms
- Minimum Spanning Trees
- PageRank Algorithms
And many more are being used in different Business problems in Data Science. For more details check out this article for an in depth look.
4. Operating System :
An operating system is a program that acts as an interface between user and
computer hardware. The purpose of operating system is to provide an environment in which
a user can execute programs in an efficient and convenient manner. Graph theory plays an
important role in operating system in solving job scheduling and resource allocation
problems. The concept of graph coloring is applied in job scheduling problems of CPU. Jobs are assumed as vertices of a graph and there will be an edge between two jobs that cannot be
executed simultaneously. Graphs are also used in disk scheduling algorithms.
Conclusion :
So that's it for this article, hopefully this shed some more light into the applications side. This article was purely out of curiosity while I was learning all about the Graph Data Structure and implementing it so I took my time with this. Leave a like and share if you find this informative. Signing off :).