Skip to main content
Filter by
Sorted by
Tagged with
0 votes
0 answers
29 views

How to visit all reachable nodes between 2 points in topological order, visiting each edge once?

I have a directed (potentially cyclic) graph. Some nodes are inputs and some nodes are outputs. I want to iterate over all the edges that form paths between an input and an output. I want to ignore ...
Chechy Levas's user avatar
  • 2,310
0 votes
1 answer
78 views

Handling cycles in topological sorting in T-SQL

I've been trying to write a T-SQL script - I am aware it's probably not the best tool for this scenario - that can do a topological sort given a table of nodes and their edges. I've eventually come up ...
dlp_dev's user avatar
  • 148
1 vote
0 answers
72 views

CSAPP 3e (global): Possible erratum for "Practice Problem 8.3" (p. 781)?

Due to the relative lack of popularity of CSAPP's global edition, I have been unable to figure out whether exercise problem 8.3 (partial screenshots shown above) is entirely correct. I have only found ...
RobSim's user avatar
  • 41
2 votes
1 answer
68 views

Topological Sort as Reverse Post-DFS | Course Schedule II LeetCode

Currently solving Course Schedule II on LeetCode and this is the code that DOES NOT pass all test cases because of the following line: Collections.reverse(postOrder);. Removing this line solves all ...
Lola's user avatar
  • 21
1 vote
0 answers
59 views

Shortest path in Directed Acyclic Graph. Is topological Sort Really needed?

Here's a famous problem: Given a Directed Acyclic Graph of N vertices from 0 to N-1 and a 2D Integer array(or vector) edges[ ][ ] of length M, where there is a directed edge from edge[i][0] to edge[i][...
ABGR's user avatar
  • 5,059
0 votes
0 answers
35 views

Topological Sorting question. Does the values of an edge impact the order in which they are sorted?

I am currently working on the "Longest Road" Dag problem, and finished writing my topological sorting algorithm in Java. Currently I am using edges with no value associated to them, and I am ...
VampX Helix's user avatar
2 votes
1 answer
157 views

Generate Random Topological Sort of Graph in Python?

As we all know, topological sorts are not unique. A graph can have many topological sorts. For example, the graph {A, B, C}, {(A,C)} has exactly three sorts: {A,B,C}, {B,A,C}, and {A,C,B}. My problem ...
leaf's user avatar
  • 25
0 votes
0 answers
82 views

How to detect separate chains in a topological sort

EDIT: My question was originally about how to sort the following data. I was pointed in the direction of topological sort which got me started, but I am editing the question now to my new issue. Given ...
DeejC's user avatar
  • 139
0 votes
0 answers
17 views

Topological Sort - Usual Ordering of First Source Nodes Added to Queue

I am reviewing the 14 coding interview patterns by Fahim ul Haq; what is the usual ordering, or orderings, of source nodes that are added to the source queue in topological sorting? Suppose I have ...
Gregory Desrosiers's user avatar
0 votes
1 answer
95 views

How to get reasonable "topological order" of control flow graph (CFG) which may have loops when calculating MD index?

I am a noob in binary analysis and I am looking for your help. I am working on calculating the MD index of callgraph function nodes by Python, and I have to analyze the control flow graph (CFG) inside ...
PeterMouse's user avatar
0 votes
0 answers
23 views

Select vertex on DAG and ensure topological sorting depth in limit

Given a directed acyclic graph, some node's indegree are zero. I want to select some other nodes and set their indegree to zero mannual, then perform topological sorting on the directed graph and ...
01xz's user avatar
  • 1
0 votes
0 answers
37 views

Checking if there exists an edge in constant time

Original Question: Algorithm for finding a Hamiltonian Path in a DAG Chosen Answer: You can first topologically sort the DAG (every DAG can be topologically sorted) in O(n+m). Once this is done, you ...
anon60707's user avatar
0 votes
1 answer
39 views

How to find the ideal topological ordering (fewest steps as explained in description below)?

Given a network of N computers, there are N-1 cables that connect the computers into a tree. A message is passed to computer 1 and it will propogate it to its neighbouring computers and so on until ...
snowcoffeebean's user avatar
0 votes
0 answers
31 views

How do I topologically sort a rooted tree from the "parentOf" relation?

I have a N-node rooted tree whose nodes are labeled 0 through N-1. I am given the parentOf relation, that is, for each node i, parentOf[i] is the single node j such that j is the parent of i. I ...
Mark Lavin's user avatar
  • 1,142
0 votes
0 answers
146 views

pytorch and topological sorting

I want to understand in which cases and how (automatically, when model is built, or not) PyTotch uses topological sorting. I can't check it manually, cause of some circumstances, so I've tried ...
Paul Ivanov's user avatar
0 votes
0 answers
24 views

Number of topological sortings of neural network DAG

How many topological sortings are there of a DAG G such that G is a fully connected neural network with layers of width 3, 2, and 1? I would think the answer would be 3! * 2! * 1!, since any sorting ...
johnnyb's user avatar
  • 41
1 vote
0 answers
28 views

Can you give me adjacency list of a graph whose BFS and topological sort are not equivalent?

Can you give me adjacency list of a graph whose BFS and topological sort are not equivalent ? I visualze them the same way but googling if they both are same never quite provided a satisfactory ...
Mohak Gupta's user avatar
1 vote
1 answer
196 views

Topological Sort Space Complexity

Here is the topological sort algorithm, I checked everywhere and I always found the space complexity as O(V) which is the size of the stack, but what I don't understand is: Why nobody considers this ...
Alper Arslan's user avatar
-1 votes
2 answers
429 views

How to find bottleneck in directed graph

Let's say we have a directed graph that represents school courses. Some courses are a prerequisite of others (e.g. [2,1] means that course 1 needs to be taken before course 2). We can take as many ...
jmtt's user avatar
  • 43
0 votes
0 answers
57 views

Implementing a Topological Sort Method

I'm currently trying to implement a topological sort method but I'm struggling to finish it and need some advice. The errors I get when I test this method are: "Expected exception: java.lang....
Preston Little's user avatar
0 votes
1 answer
280 views

Trying to use topological sort algorithm to determine if a tree is a valid

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the ...
ndnchapathi69's user avatar
0 votes
1 answer
328 views

Creating a Hierarchy of dependencies from two columns in Excel/Power BI

I am working with Power BI for the first time. I have two columns: node1 and node2. The column relationship is that Node 1 depends on Node 2. Node 1 can have dependencies on multiple nodes. Also, Node ...
David Jackson's user avatar
0 votes
0 answers
166 views

If there is a Unique topological ordering in a dag then there exists a hamiltonian path

How do you prove this ? If there is a Unique topological ordering in a dag then there exists a hamiltonian path Or is there a counter-example? I proved the other direction of iff which is easy.
SotirisD's user avatar
0 votes
1 answer
192 views

Topological sort, creating adjaceny list

I am solving a Leetcode problem called course-schedule II. In summary, we are given dependencies between courses and need to find the order in which they can be taken. For example [1,0] [2,0] [3,1] [3,...
CaptainHastings's user avatar
0 votes
2 answers
253 views

Optimal reorder algorithm on ordered list

Context I have an SQL table containing items. id name order ============== 1 book 3 2 table 1 3 chair 2 4 bag 4 So as we can see, the items are sorted in this order: table chair book bag ...
Anwar's user avatar
  • 4,248
0 votes
2 answers
369 views

Topological Graph Sorting

I am trying to implement a topological graph sort, and my program is compiling however I am not getting a populated vector. I have tried running a debugger to track where my variables are going and I ...
Nicole Sood's user avatar
-1 votes
1 answer
126 views

How to take the output of Tarjan's algorithm (Strongly Connected Components) and then iterate over the nodes in topologically sorted order?

Here is an adapted Tarjan's JavaScript code: function execute(graph) { const state = { stack: [], indexCounter: 0, traversibleVertex: {}, components: [], } for (const vertex ...
HareSurf's user avatar
  • 78.2k
1 vote
2 answers
466 views

How to start topological sort after a certain element in JavaScript?

I have pieced together this topological sort in JavaScript, and have a graph based on this post: const graph = { edges: { c: ['d', 'f'], d: ['e'], f: ['e'], a: ['b', 'c'], b:...
HareSurf's user avatar
  • 78.2k
3 votes
3 answers
573 views

Algorithm To Schedule Processes with Dependencies, (Linear Time)

I'm having a bit of trouble trying to figure out how to create an algorithm that creates a schedule to minimise the smallest possible time used. Here is the problem. Consider a program with processes ...
asudoiha oaihd's user avatar
0 votes
0 answers
399 views

Topological Sort Algorithm Comparison for DAG: BFS vs DFS

I was comparing two topological sort algorithm based on DFS and BFS respectively. I have found out that for higher number of edges (around 50000 or more) BFS is faster than DFS. But I have read ...
T.I.Mahmud's user avatar
2 votes
2 answers
542 views

How to Topologically Sort a Directed Graph with Cycles

I'm struggling to define this problem exactly, which is part of the reason I cannot solve it. Basically, I want to assign numbers to nodes that provides a kind of topological sorting, but if there is ...
Sam Gates's user avatar
0 votes
0 answers
132 views

Is .NET dependency injection container implemented by topological sort?

I'm studying Kahn's Algorithm now and figured out that the usage of this alg is solving the topological sort. I found a document said that the topological sort is always used for dependency, so there'...
BlueCake's user avatar
0 votes
0 answers
117 views

What is the intuition behind topological sort to find the shortest distance in weighted DAG?

#include<iostream> #include <list> #include <stack> #include <limits.h> #define INF INT_MAX using namespace std; class AdjListNode { int v; int weight; ...
Shroud's user avatar
  • 35
1 vote
4 answers
626 views

Is there a way to modify topological sort to handle concurrent prerequites?

I've been trying to build a schedule generator for my school using topological sort, but am stuck dealing with classes that have prerequisites that can be taken concurrently. I was wondering if there ...
Jeffrey Tang's user avatar
0 votes
1 answer
254 views

CycleErrors in graphlib

I'm currently learning the graphlib of python 3.9. And I want to generate a CycleError but when I run the following code: #!/usr/bin/python3 from graphlib import TopologicalSorter ts = ...
ChsharpNewbie's user avatar
0 votes
1 answer
440 views

no back edges in topological ordering of DAGs

When doing a topological ordering on a DAG (directed acyclic graph) using depth-first traversal, it is important to notice that no back edges are present since the graph does not have cycles. But why ...
Tryer outer's user avatar
-1 votes
1 answer
277 views

Write a program to solve the topological sorting problem by using Depth First Search (DFS) algorithm

I want to use topological sorting using Depth First Search (DFS) for the given problem (the directed graph attached below). click here to see the image. Could you please help by writing the ...
Sarah's user avatar
  • 1
2 votes
1 answer
381 views

In what condition i should use topological sort using bfs and topological using dfs?

both topological sorting using bfs and dfs has same time complexity ie O(V+E) where V => number of vertices and E => number of edges but the question is which algo to use in what condition????
AABHINAAV's user avatar
0 votes
1 answer
449 views

Why does the existence of a Hamilton path in a Directed Acyclic Graph (DAG) show there is single way to topologically order the DAG?

Here is my understanding- we can find a Hamilton path by topologically sorting a DAG and checking if an edge exists between each vertex in this sorted order. And that somehow this shows that this ...
mary doesy's user avatar
-1 votes
1 answer
554 views

Course schedule - Topological sort

Problem statement: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you ...
Souvik Ghosh's user avatar
  • 4,576
3 votes
2 answers
229 views

How to combine hierarchical lists into one while respecting the hierarchy of each one of them using networkx and python?

For a medical application I want to combine several lists into one list. The items in each list represent actions to be taken for a specific disease. For instance the list Malaria would look like that:...
Aneho's user avatar
  • 79
1 vote
1 answer
99 views

I wrote a topological sort alg and it's not returning an output

I think my topological sort algorithm is correct, but perhaps my node class isn't working. This is my node class and my main function that creates the graph. When I run this, I get no output. I think ...
David Em-Yinn's user avatar
0 votes
1 answer
84 views

In course schedule II : Leetcode, how can we ensure when there are multiple answers the solution is the one with increasing order of course number?

When there are multiple solutions, I want to return the solution where courses are in ascending order. How can I do that by the topological sort algorithm?
sam's user avatar
  • 21
0 votes
1 answer
108 views

Topological Sort basic analogy

I was recently going through Topological Sort and DFS from CRLS. They have this entry/exit time concept by which we can classify graph edges into tree edge forward edge back edge cross edge So the ...
user 923227's user avatar
  • 2,677
0 votes
2 answers
461 views

Topological sort complexity in linear time?

I am trying to calculate the algorithmic complexity of Kahn's algorithm implemented in python, I came across this article :https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ in ...
Factral's user avatar
  • 45
0 votes
0 answers
88 views

Graph theory, topological sorting, how to modify DFS to check "corequisites"

Say each node in my graph represents a college course, how can I use DFS to check what's a corequisite of course X and what's a prerequisite?
Ali's user avatar
  • 17
5 votes
1 answer
2k views

Topological Sort Kahn's algorithm BFS or DFS

Is Topological sort's method BFS or DFS, Which is right? (I think BFS is right but some site said DFS and some said BFS. I'm confused...) Is Kahn's algorithm same to the BFS(or DFS)? or BFS(or DFS) ...
ywbird's user avatar
  • 105
0 votes
1 answer
70 views

I am working on topological search but giving me a error

#Initializing the Graph Class class Graph: def __init__(self, numberofVertices): self.graph = defaultdict(list) self.numberofVertices = numberofVertices def addEdge(self, vertex, edge): ...
Habib Ur Rehman's user avatar
1 vote
1 answer
161 views

Grading partial orders (starting from topological sort)

This blog post discusses an interesting variation on topological sort: http://jdh.hamkins.org/linear-gradings-of-partial-orders/ A linear grading of a partial order is just like a topological sort, ...
Theo H's user avatar
  • 243
1 vote
1 answer
268 views

Could you topologically sort a complete acyclic directed graph through classical sorting algorithms like quicksort?

If you have a complete directed acyclic graph (i.e each vertex has either an ongoing or outgoing edge with any other vertex), you can topologically sort it with the classic topological sort algorithm ...
Ricola's user avatar
  • 2,872

1
2 3 4 5
7