Introduction to Graph Data Structures
Graph theory is a key area in computer science which we use to present relationships, connections and interactions between entities. As opposed to linear data structures which mainly present data in simple sequences — graphs are put in place for when an entity may tie into many other entities in many ways. In a graph the entities we are looking at are called vertices or nodes, and the elements that connect them are called edges. For example a road map may be represented by a graph in which cities are nodes and roads which connect them are edges.
Also social networks may use persons as nodes and relationships like friendships or follows as edges. Also because of these features Graph data structures are very useful for issues related to relationships, paths, connections, dependencies and networks. In navigation apps, communication networks, recommendation engines and transport planning we see that graphs give computers a framework in which to make sense of complex relationships and to work through large sets of related info.
What Is a Graph Data Structure?
A graph is a type of non linear data structure which we see as a set of vertices and edges that present relationships between the former. Each vertex in this structure stands for a separate entity, place, item or object. At the same time an edge is a relationship which ties together two vertices. What that connection means is up to the issue at hand. In a transport network for example vertices may represent train stations, airports, or cities and the edges the tracks which connect them.
In a social network model, vertices may stand for people and the edges for their relationships which may be of a friendship nature or some other type. Also what is very important in graphs is that a single vertex may have many connections to other vertices which in turn allows us to model very complex systems which would be very hard to represent with simple linear data structures. Also to fit the needs of a given application graphs may also include more info in the edges like direction of a connection, distance, cost, capacity or time.
Understanding Vertices and Edges
Vertices and out from which edges grow are the basic elements which make up a graph that in turn is used to represent relationships. A vertex at times is also referred to as a node. It is what we use to represent a single element within the system we are modeling. For instance in a graph which is a model of a set of universities each university is a vertex. An edge in this context is what we use to represent the relationship or the connection between two vertices. If we are to take the example of universities again and we have two that have a direct transport link between them an edge which in this case is the transport link we use to represent that.
Also what we see is that the number of edges attached to a vertex which we term its degree can vary greatly and that is a key element in the analysis of a graph. A vertex which has a high degree may be a very important hub while one which has only a single connection may be a peripheral element. By use of vertices and edges graphs we as programmers are able to represent relationships in a way that mirrors how real world connected systems function.
Directed Graphs
A directed graph is a type of graphic in that each edge has a defined direction. We no longer just present that vertex is connected in a directed graph instead we present which vertex the connection is going out from and which it is going into. Also this is useful when we do not have mutual relationships. For example in a social media site which reports that User A may follow User B but that does not mean User B follows back.
Thus the relationship may be represented by a directed edge from A to B. Also directed graphs are used for web page links, task sequences, transport networks, and info flow. In a directed graph it is possible to have an edge go in both directions between the same set of vertices which is so in some systems. This feature makes directed graphs very useful for processes which have a start and a finish point which may also include elements of permission or which are dependent on each other.
Undirected Graphs
An undirected graph which is used to present relationships that do not have a specific direction between entities. An edge which connects Vertex A and Vertex B in such a graph does not attach a direction or start/ end point to the relationship. For example in a social network which tracks friendships, if person X is friends with person Y then person Y is also friends with person X.
Also we may model a network of roads where the road goes both ways between 2 points. In this type of graph which we may call a social or road network the relationship is what is of importance not the direction of flow. In an analysis of the graph an undirected edge may be traveled from either of the connected vertices. We choose between a directed and undirected graph based on if the relationship we are modeling has direction or not.
Weighted Graphs
A weighted graph which puts a number or some measurable value to one or more of its edges. We associate a value to each edge which we call its weight that may represent distance, time, cost, bandwidth, risk, or capacity among other things. For instance in a GPS which is used for navigation, we may use cities as our nodes and roads as our edges. To each road we assign the distance or the estimated travel time which then becomes that edge’s weight.
As the navigation system determines best routes it takes into account these weights rather than the total number of roads which makes up a route. Thus weighted graphs are very important in this and similar applications which deal with quality and cost of a connection. Two paths may have the same number of roads but very different distances or travel time and it is the weight of the edges which brings this to light for the analysis which goes into determining the best path.
Unweighted Graphs
An unweighted graph doesn’t put numbers to its edges. What it does is report out there is a relationship or a connection between two points. This type of graph is useful when all connections are of equal importance. For example a basic social network graph which uses points to represent users and lines to indicate that two users are connected. If what is needed is to determine if users are connected or what the degree of separation is between them, we may not need to put in numerical weights.
Also unweighted graphs are useful for some network connectivity issues and basic relationship analysis. While they don’t give out as much info per connection as weighted graphs do, they are able to represent very large complex systems of interrelated elements and support search, traversal, connectivity and relationship discovery algorithms.
Common Graph Representation Methods
Computers have at present no very efficient way to put graph info into memory but do use two very common methods which are adjacency matrices and adjacency lists. An adjacency matrix which is a 2D table is used in which we have rows and columns that represent the vertices. In this table a value indicates if an edge is present between two vertices. In a weighted graph that value also includes the weight of the edge. This does make it easy to see which vertices are connected but the matrix uses a lot of memory which is not necessary in a graph which has few edges as compared to the number of vertices.
An adjacency list which takes a different approach puts each vertex with a group of vertices it is connected to. This method is often better in terms of memory use for what is called a sparse graph which has few actual connections as compared to possible connections. What method to use really depends on the graph in question and what the application is asking of it.
Graph Traversal Algorithms
Graph traversal is the process of going through vertices and edges in a methodical way which in turn allows programs to analyze or work through the structure of the graph. Of the main types, we have Breadth-First Search also known as BFS, and Depth First Search also known as DFS. In BFS the graph is looked at level by level with all adjacent vertices visited before going to a higher level, which makes it very useful for identifying the minimum set of connections between two points in an unweighted graph. In contrast, with DFS the algorithm will follow a branch of the graph as far as it goes before backtracking and then will move to another branch if present.
This is useful for structural analysis and to find connected components as well as sort out issues related to order of processing. Also, these algorithms may be implemented with appropriate support data structures. It is important to understand graph traversal because a lot of the more complex graph algorithms use this base function of looking at the whole picture in order to get to a solution.
Shortest Path Algorithms
In the field of graph theory we see that shortest path algorithms have been put forward to determine the best routes between vertices as per a given measure. In an unweighted graph setting, BFS is used to determine the path with minimal number of edges between two vertices. For weighted graphs we have a range of options based on graph and problem properties. Dijkstra’s is a well known algorithm which we use to determine the path of minimal total weight from a given start point when edge weights are non negative.
Also we have other solutions like Bellman-Ford and which are used for different issues. It also is a fact that what we term as the shortest path is not always the physical shortest distance. It may in fact be the path of lowest cost, least travel time, minimal network delay which is what the edge weights represent. This is what makes shortest path algorithms so relevant to real world systems which require efficient movement through networks.
Graphs in GPS Navigation
GPS navigation systems also present very clear examples of graph data in the real world as road networks naturally do. We may think of a map as a graph which has vertices that represent intersections, cities, points of interest which we are for instance, and edges which are the roads that connect them. Also we may put into the edges information like distance, expected travel time, road access issues, or traffic reports.
When a driver inputs a destination the navigation system looks at what paths are available through the graph and applies appropriate algorithms to present a best option based on the given parameters. Also the information is dynamic and changes the value of a path. For example, heavy traffic will raise the price of a route. By regarding the roads and places as a set of interrelated graph elements, navigation software is able to work out complex transport networks and present useful route info.
Graphs in Social Networks
Social media networks also put in nature to present themselves as graphs which is a result of users and their interactions which in itself is a complex system. In a simple model we can say each user is a node, and the connection between them like friendship or following is an edge. When the relation is one way like following someone out which is not followed back we use a directed graph, for that which is mutual we use an undirected graph. Also we use graph analysis to see how users are connected to each other, to find groups of users which have more in common, to see how well the network is doing as a whole and to what degree one user is related to another.
Also we use relationship info to put forward recommendations of users which may have similar interests. As large social platforms grow to include very large numbers of users and relations between them it is very important to have efficient graph structures and algorithms. Graphs give us a math and comp sci based model to look at these complex systems as a whole instead of looking at each user in isolation.
Graphs in Telecommunications and Computer Networks
Telecommunication networks require great deal of interconnection between devices, locations and network elements which is what makes graphs a very useful model for them. In a network graph we put in computers, routers, switches, towers which are elements of the communication system as nodes, and we use edges to represent communication links between them. As per the use case, edges may also have weights which represent bandwidth, latency, cost, reliability etc. With the help of graph algorithms we are able to study how info travels through the network and also to determine what are the best paths between points of interest.
Also we are able to do in depth analysis of network connectivity and see what happens to the network when a connection fails. This type of modeling becomes very valuable as networks grow in scale which in turn makes manual evaluation of each and every connection an impractical solution. What we get out of graph based analysis is a systematic way to look at relationships which in turn support in the planning, monitoring, optimization and troubleshooting of very complex communication structures.
Graphs in Transportation Systems
Transportation systems go well beyond what we see in standard road maps and may include rail networks, bus systems, air traffic, shipping lanes and other means of transport. In graphs these systems are modeled as networks which in turn have nodes that may represent stations, terminals, cities or stops and edges that represent routes. Weights on these may in turn represent elements like distance, ticket price, travel time, or number of connections.
Also a transport application will use this data to study various travel options from point to point. In a rail network for example there may be many routes between two cities which have different travel times and stopovers. A graph based model gives the software a structured way to present these options and also for algorithms to find the best fit based on what the user is looking for. This is also a very useful approach for logistics, delivery routing, fleet management and transport infrastructure analysis.
Graphs in Recommendation Engines
Recommendation systems use graph based relationships to connect users with products, services, videos, books, songs, articles and other forms of content. We see users and items as nodes which are connected via edges that represent actions like purchase, rating, view, search, preference. Also we find in some models different kinds of nodes and relationships are included which in turn present a picture of how users interact with the content. By way of analysis of these relationships software is able to identify trends which in turn may be used to put forward recommendations.
For example if many users interact with the same products the system will look at what is going on between those users and products to find related items. Graph based models do very well because recommendations play off of relationships between pieces of data rather than stand alone data points. Also instead of looking at just what a single user is doing at present time, a graph is able to present a larger picture of interaction and connection.
Graphs in Network Analysis
Network analysis is the study of the structure and behavior of what are in fact connected systems for which we use graph based data structures as a base. In these networks we see how some components are more related to each other, we also see the most related points in the whole network and at the same time we see outlying sets and the ways in which one section of the system talks to another. This network may be that of computer systems, transport networks, organizations, web sites, scientific co authorship and in fact many other kinds of relationships.
Also we find that graphs can present a picture which is not at all clear from a plain list or a simple in and out table. For instance we see through a highly connected node what component of a network is in fact very involved in relationships while at the same time looking at unconnected elements brings out different sections of a network that don’t have a direct connection. Also we see that this application of graph structures in network analysis transforms relationship data into a form that the computer can methodically analyze.
Advantages and Issues of Graph Data Structures.
Graphs present a few key benefits in problems which deal with relationships and connections. They do a great job at representing complex networks, support many types of relationships, and also do well at what algorithms do which is to explore paths, out to which communities and dependencies. Also in terms of flexibility, graphs are very do, which is that they may be directed or undirected, weighted or unweighted, and may be presented in various storage forms. At the same time though the work which goes into graphs can also become very compute intensive as the number of vertices and edges grow.
We see some of our best algorithms which perform analysis on very large networks breaking out in terms of time or memory requirements. Into this is the issue of choice in what we use for our graph models and what we go with in our analysis. In practical application developers must bear in mind the number of vertices and edges, the rate of change, the type of analysis we are doing, the attributes of the relationships. Good graph design is that which you balance between accurate model and efficient storage and performance.
Conclusion
Graph models present computers with an excellent way to structure relationships between put together elements and to study systems which in other terms would be hard to represent. We see from nodes we use to represent entities and edges which we use to present the relationships that graphs are able to depict from which we get out models of things like roads and transport routes to social connections, communication networks, and user and product interactions. Also different graph types give us more options, with directed graphs for one way relationships, undirected for two way, weighted for measurable values in connections, and unweighted which mainly look at if the connection is there or not.
Also we have graph algorithms like BFS, DFS and shortest path which allow programs to get into these structures and solve real world issues. Also their use in GPS, telecommunication, transport, recommendation engines, social networks and network analysis shows why graphs are such a key concept in computer science and software development.
