The Real-Life Applications of Graph Data Structures You Must Know

These insanely huge applications of graphs outside Academia are shaping the future.

Graphs are the ultimate abstraction for many real world problems and today, technology exists that can treat them as such.

The best applications of graphs are when they capture arbitrary high-value relationships in data that would otherwise be lost.

Some of the best use cases for Graph Data Structures are in; Social Graph APIs such as Facebook's Graph API, Recommendation Engines such as Yelp's GraphQL Api, Path Optimization Algorithms such as Google Maps Platform (Maps, Routes APIs) and Car Navigations, Web Analytics and Scientific Computations

What is a Graph Data Structure

When discussing Graph Data Structures, the question of a common query language often keeps coming. The whole ecosytem of graph technology, especially the databases are centered around specific languages.

At a very high level, a graph data structure is a data structure where data is stored in a collection of interconnected vertices (nodes) and edges (paths).

Therefore, a graph data structure (V, E) consists of:

  1. A collection of vertices (V) or nodes.
  2. A collection of edges (E) or paths.
        
V = {0 , 1, 2, 3}
E = {(0, 1), (0, 2), (0, 3), (1, 2)}
G = { V, E }
        
      

Graph data structures are said to contain graph data, often stored in graph databases. Graph data tends towards intricate connections with high-value relationships.

Graph Databases are good examples of graph data structures. The they offer semantic storage for graph data structures.

Graphs can either have a directional bias from one vertex to another (directed graphs) or have no bias (undirected graphs).

Graph data structures are queried in Graph Query Languages.

Common Operations on Graph Data Structures

Graph data structures can be managed with these common operations:

  • addNode add vertices to graphs
  • removeNode removes vertices to graphs
  • addEdge adds connections or paths between vertices in graphs
  • removeEdge removes connection or paths between vertices in graphs
  • contains check if a graph contains a certain value
  • hasEdge checks if a connection or path exists between any two vertices in a graph

Graphs can also be weighted or unweighted.

5 Practical Applications of Graph Data Structures in Real Life

  1. Social Graphs
  2. Social graphs draw edges between you and the people, places and things you interact with online.

    Facebook's Graph API

    Facebook's Graph API is perhaps the best example of application of graphs to real life problems. The Graph API is a revolution in large-scale data provision.

    On The Graph API, everything is a vertice or node. This are entities such as Users, Pages, Places, Groups, Comments, Photos, Photo Albums, Stories, Videos, Notes, Events and so forth. Anything that has properties that store data is a vertice.

    And every connection or relationship is an edge. This will be something like a User posting a Photo, Video or Comment etc., a User updating their profile with a their Place of birth, a relationship status Users, a User liking a Friend's Photo etc.

    The Graph API uses this collections of vertices and edges (essentially graph data structures) to store its data. The Graph API is also a GraphQL API. This is the language it uses to build and query the schema.

    The Graph API has come into some problems because of it's ability to obtain unusually rich info about user's friends.

  3. Knowledge Graphs
  4. Google's Knowledge Graph

    A knowledge graph has something to do with linking data and graphs...some kind of graph-based representation of knowledge. It still isn't what is can and can't do yet.

    Google defined

  5. Recommendation Engines
  6. Yelp's Local Graph

    Yelps has been slowly phasing out their old Fusion API for a GraphQL API.

    The Local Graph API promises to make it easier for developers to integrate Yelp's data and share great local businesses through their apps.

    GraphQL leverages the power of graph data structures by modeling the business problem as a graph within its schema.

    The most common use case for GraphQL is operating on graph data structures. Both Apollo Client and Relay operate on GraphQL data as a normalized graph.

    On the Local Graph API, Yelp represents your business as a vertice with name, id, alias, is_claimed, is_closed etc. graph properties.

    Yelp also creates additional vertices for Place (as custom type Location in GraphQL schema, ), Categories (as custom type Category in GraphQL schema), Review (as type Review) and Hours (as type Hours)

    Yelp creates edges with relationships such as the location of a business with a certain name, the opening hours of a business, the reviews of a business, the category of a business.

    Using the local graph feature, a yelp app can uses your location to match recommendations of businesses close to you. In this case your location and the location of the business are both vertices while the recommendation is the edge.

  7. Path Optimization Algorithms
  8. Path optimizations are primarily occupied with finding the best connection that fits some predefined criteria e.g. speed, safety, fuel etc or set of criteria e.g prodecures, routes.

    In unweighted graphs, the Shortest Path of a graph is the path with the least number of edges. Breadth First Search (BFS) is used to find the shortest paths in graphs—we always reach a node from another node in the fewest number of edges in breadth graph traversals.

    Any Spanning Tree is a Minimum Spanning Tree unweighted graphs using either BFS or Depth First Search.

    Google Maps Platform (Maps, Routes APIs)

    Google Maps and Routes APIs are classic Shortest Path APIs. This a graph problem that's very easy to solve with edge-weighted directed graphs (digraphs).

    The idea of a Map API is to find the shortest path from one vertex to every other as in a single source shortest path variant, from your current location to every other destination you might be interested in going to on the map.

    The idea of by contrast Routing API to find the shortest path from one vertex to another as in a source sink shortest path variant, from s to t.

    Shortest Path APIs are typically directed graphs. The underlying data structures and graphy too.

    Flight Networks

    For flight networks, efficient route optimizations perfectly fit graph data strutures. Using graph models, airport procedures can be modeled and optimized efficiently.

    Computing best connections in flight networks is a key application of algorithm engineering.

    In flight network, graph data strutures are used to compute shortest paths and fuel usage in route planning, often in a multi-modal context.

    The vertices in flight networks are places of departure and destination, airports, aircrafts, cargo weights.

    The flight trajectories between airports are the edges. Turns out it's very feasible to fit graph data strutures in route optimizations because of precompiled full distance tables between all airports.

    Entities such as flights can have properties such as fuel usage, crew pairing which can themselves be more graphs.

    GPS Navigations Systems

    Car navigations also use Shortest Path APIs.

    Although this is still a type of a routing API it would differ from the Google Maps Routing API because it is single-source (from one vertex to every other i.e. it computes locations from where you are to any other location you might be interested in going.)

    BFS is used to find all neightbouring locations.

  9. Scientific Computations