Graph Theory : Definition and Implementation

When it comes to an optimisation  problem where there are 2 different  types of objects which are interlinked than the technique used to solve such problems is called graph theory.

What is a Graph

A graph is a set of objects called nodes(or vertices) connected by a set of edges. If the edges are unidirectional the graph is called directed graph or digraph and edges are called arcs. In undirected graphs, the connections have no directions and are called edges. The algorithms done on graph are finding a path between two nodes, finding the shortes path between two nodes, determining the cycles in the graph (a cycle is a non-empty path from a node to itrself), finding a path that reaches all nodes and so on. Then there are weights or cost associated with edges or arcs and we have to find the cheapest path,

In this figure u,v,w,x,y, form the nodes while uv,vw,wx,xy,uy,vy,wy forms the edges




How it came into existence
The bridge of Konigsberg was regarded as the first problem of graph theory. Konigsberg , then the capital of East Prussia was built at the intersection of two rivers that contained a number of islands. The islands were connected to each other and to the mainland by seven bridges, as shown on the map. The residents of the city were obsessed with the question of whether it was possible to take a walk that crossed each bridge exactly once. This problem was simplified to a graph by euler and he  reasoned that if a walk were to traverse each edge exactly once , it must be the case that each node in the middle of the walk must have an even number of edges to which it is connected. Since none of the nodes in this graph has an even number of edges, Euler concluded that it is impossible to traverse each bridge exactly once.



When to use Graphs

As such graphs appear very theoretical but they are used to  represent many practical problems. They are often used to model problems or situations  in physics, biology, psychology an in computer science. For example
The data type which is ideal for representing graphs ids dictionaries . Since in dictionary one can define an objest associated wtih multiple obects, so while defining graphs we can write one node and relate it with other nodes.

Sample problems:

Facebook Friends network : A friend network on facebook is graph with nodes as friend list and their friedns as another set of nodes some may be common friends so they are connected by edges others are connceted to other nodes.

World Wide Web : The nodes are web pages and there is an edge from node A to node B if and only if there is a link to a page B on page A.

Airline booking : Each Airline offers flight from one destination to other these destinations can be termed as node and if the cost of each airline is given then it can be classified as wighted graph.

Intercity or intra-city network : The road network between cities of a state is a graph structure where each city is a node and the connecting roads are edges. If the lengths of the roads are given than it is a weighted graph and the shortest distance between two cities could be found.


Implementation of Graph theory

As said earlier the data type which is ideal for implementing graph is dictionaries.So lets define the graph that we have using dictionaries.

graph = { "u" : ["v", "y"],
          "v" : ["w", "y"],
          "w" : ["x"],
          "y" : ["x"],
           }

Here the keys of the dictionaries are vertices or nodes of our graph. The corresponding values are lists with the nodes which are connected to this node and forms an edge.
An edge can be seen as a 2-tuple with nodes as elements, i.e ("u", "v")

A function to generate list of all edges can be defined in following way

def gen_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))

This code will give the following output :

[('y', 'x'), ('u', 'v'), ('u', 'y'), ('w', 'x'), ('v', 'w'), ('v', 'y')]
 

In the next blog we will learn how to implement graph using classes.