DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithm of the Week: Topological Sort of a Graph

Algorithm of the Week: Topological Sort of a Graph

Stoimen Popov user avatar by
Stoimen Popov
·
Oct. 02, 12 · Interview
Like (0)
Save
Tweet
Share
16.62K Views

Join the DZone community and get the full member experience.

Join For Free

Introduction

Let’s assume we have a list of tasks to accomplish. Some of the tasks depend on others, so we must be very careful with the order of their execution. If the relationship between these tasks were simple enough we could represent them as a linked list, which would be great, and we would know the exact order of their execution. The problem is that sometimes the relations between the different tasks are more complex and some tasks depend on two or more other tasks, which in their turn depend on one or more tasks, etc.

Thus we can’t model this problem using linked lists or trees. The only rational solution is to model the problem using a graph. What kind of graph do we need? Well, we definitely need a directed graph, to desribe the relations, and this graph shouldn’t have cycles. So we need the so called directed acyclic graph (DAG).

Topological Sort. Directed Graph.

In order to sort a graph using topological sort we need this graph to be acyclic and directed!

Why we don’t what a cycle in the graph? The answer of this question is simple and obvious. In case of cyclic graph, we wouldn’t be able to determine the priority of task execution, thus we won’t be able to sort the tasks properly.

Now the solution we want is to sort the vertices of the graph in some order so for each edge (u, v) u will precede v. Then we’ll have a linear order of all tasks and by starting their execution we’ll know that everything will be OK.

Topological Sort. Sort the vertices.

The output of topological sort should be a list of vertices!

This kind of sort is also known as “topological” sort (or topsort) and it is one of the very basic graph algorithms.

Overview

OK, so we have an acyclic directed graph, how do we proceed to get a linked list with all the vertices sorted? Since it’s an acyclic graph we know that there is at least one vertex without predecessor. Thus at first place, we can put all the vertices without predecessors into our linked list.

Topological Sort. First Step.

Initially we get only the vertices without a predecessor!

This approach answers the question – is there a possibility to have more than one valid topological sort of a graph? Indeed, the only thing we’d like to do is to put all the vertices in the correct order, but since there might be vertices with no predecessors any combination of them will be a valid topological sort for a graph.

As we can see from the picture above even for vertices with predecessors our topological sort can vary. Thus [9, 6, 2, 7, 4, 1] is a valid topological sorted graph, but [6, 9, 2, 7, 4, 1] is also a valid topological sort out of the same graph!

Now we can generalize the algorithm in some basic steps.

1. Make an empty list L and an empty list S;
2. Put all the vertices with no predecessors in L;
3. While L has items in it;
3.1. Pop an item from L – n, and push it to S;
3.2. For each vertex m adjacent to n;
3.2.1. Remove (n, m);
3.2.2. If m has no predecessors – push it to L;

Topological Sort. Second Step.

The image above explains step 3.2. from the algorithm!

Code

Here’s the very basic PHP implementation. As you can see the short implementation shows us how easy this algorithm is. However its importance to computer science and programming is enormous.

class G
{
    protected $_g = array(
        array(0, 1, 1, 0, 0, 0, 0),
        array(0, 0, 0, 1, 0, 0, 0),
        array(0, 0, 0, 0, 1, 0, 0),
        array(0, 0, 0, 0, 1, 0, 0),
        array(0, 0, 0, 0, 0, 0, 1),
        array(0, 0, 0, 0, 0, 0, 1),
        array(0, 0, 0, 0, 0, 0, 0),
    );
    protected $_list = array();
    protected $_ts   = array();
    protected $_len  = null;
 
    public function __construct()
    {
        $this->_len = count($this->_g);
 
        // finds the vertices with no predecessors
        $sum = 0;
        for ($i = 0; $i < $this->_len; $i++) {
            for ($j = 0; $j < $this->_len; $j++) {
                $sum += $this->_g[$j][$i];
            }
 
            if (!$sum) {
                // append to list
                array_push($this->_list, $i);
            }
            $sum = 0;
        }
    }
 
    public function topologicalSort() 
    {
        while ($this->_list) {
            $t = array_shift($this->_list);
            array_push($this->_ts, $t);
 
            foreach ($this->_g[$t] as $key => $vertex) {
                if ($vertex == 1) {
                    $this->_g[$t][$key] = 0;
 
                    $sum = 0;
                    for ($i = 0; $i < $this->_len; $i++) {
                        $sum += $this->_g[$i][$key];
                    }
 
                    if (!$sum) {
                        array_push($this->_list, $key);
                    }
                }
                $sum = 0;
            }
        }
 
        print_r($this->_ts);
    }
}
 
$g = new G();
/*
Array
(
    [0] => 0
    [1] => 5
    [2] => 1
    [3] => 2
    [4] => 3
    [5] => 4
    [6] => 6
)*/
$g->topologicalSort();

Application

As I already mentioned above this algorithm is practically used to sort the execution of different tasks that depend on each other. However this isn’t its only use. Actually any kind of objects that depend on each other can be modeled with a graph. Indeed sometimes these graphs may be a trees, but most of the cases that isn’t true.

Related posts:

  1. Computer Algorithms: Graph Breadth First Search
  2. Computer Algorithms: Graph Depth-First Search
  3. Computer Algorithms: Graph Best-First Search
  4. Computer Algorithms: Graphs and their Representation
  5. Computer Algorithms: Shell Sort

 

 

Graph (Unix) Sort (Unix) Algorithm

Published at DZone with permission of Stoimen Popov, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Top Authentication Trends to Watch Out for in 2023
  • Core Machine Learning Metrics
  • Writing a Modern HTTP(S) Tunnel in Rust
  • How To Generate Code Coverage Report Using JaCoCo-Maven Plugin

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: