8 months, 3 weeks

Graphlib Module




 

A graph is an ordered pair G=(V,E), where Vis a finite set and E ⊆ VxV. The elements of V are called nodes or vertices,and the elements of E are called edges.

This is a module added in Python 3.9 that provides utilities for working with graphlike data structures.

A graph is a data structure consisting of nodes connected by edges. Graphs are a 
concept from the field of mathematics known as graph theory. Depending on the 
edge type, we can distinguish between two main types of graphs:

• An undirected graph is a graph where every edge is undirected. If a graph 
was a system of cities connected by roads, the edges in an undirected graph 
would be two-way roads that can be traversed from either side. So, if two 
nodes, A and B, are connected to edge E in an undirected graph, you can 
traverse from A to B and from B to A using the same edge, E.

• A directed graph is a graph where every edge is directed. Again, if a graph 
was a system of cities connected by roads, the edges in a directed graph 
would be a single-way road that can be traversed from a single point of 
origin only. If two nodes, A and B, are connected to a single edge, E, that 
starts from node A, you can traverse from A to B using that edge, but can't 
traverse from B to A

Moreover, graphs can be either cyclic or acyclic. A cyclic graph is a graph that 
has at least one cycle—a closed path that starts and ends at the same node. An 
acyclic graph is a graph that does not have any cycles.

Graph theory deals with many mathematical problems that can be modeled using 
graph structures. In programming, graphs are used to solve many algorithmic 
problems. In computer science, graphs can be used to represent the flow of data or 
relationships between objects. This has many practical applications, including:

• Modeling dependency trees
• Representing knowledge in a machine-readable format
• Visualizing information
• Modeling transportation systems

Topological sorting is the operation of ordering nodes of a Directed Acyclic Graph
(DAG) in a specific way. The result of topological sorting is a list of all nodes where 
every node appears before all the nodes that you can traverse to from that node, in 
other words:
• The first node will be the node that cannot be traversed to from any other 
node
• Every next node will be a node from which you cannot traverse to previous 
nodes
• The last node will be a node from which you cannot traverse to any node

 


Responses(0)







Related