327
questions
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 ...
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 ...
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 ...
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 ...
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][...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
-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 ...
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....
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 ...
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 ...
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.
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,...
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
...
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 ...
-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 ...
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:...
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 ...
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 ...
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 ...
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'...
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;
...
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 ...
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 = ...
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 ...
-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 ...
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????
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 ...
-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 ...
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:...
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 ...
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?
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 ...
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 ...
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?
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) ...
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):
...
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, ...
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 ...