Skip to main content

Questions tagged [topological-ordering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
5 answers
468 views

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
Gizmo's user avatar
  • 73
6 votes
1 answer
168 views

Is there an algorithm to minimize working set during a topological traversal?

I have a dependency graph of tasks, which forms a DAG. I'm looking for an algorithm to calculate the optimal topological traverse to minimize the "working set". Specifically, I define the current ...
cberner's user avatar
  • 163
5 votes
1 answer
720 views

What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
porton's user avatar
  • 493
4 votes
3 answers
1k views

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes. Two nodes $u$, $v$ are said to be incomparable if there is ...
Johntrik's user avatar
4 votes
3 answers
617 views

Genetic algorithms applied to topological orderings of a DAG

I need to solve an optimization problem, whose search space is all possible topological orderings of a DAG. There is a cost function associated with each ordering, which has no simple mathematical ...
swineone's user avatar
  • 161
3 votes
1 answer
298 views

Getting all vertices with fixed index in their topological ordering of a DAG

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve. There are typically more than one order of a topological ordering ...
DarkCave's user avatar
3 votes
2 answers
222 views

Ordering of operations in a DAG of git commits

Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug Summary of the current algorithm and shortcomings git-bug is a distributed bug-tracker that ...
Michael Muré's user avatar
3 votes
1 answer
503 views

Construct a DAG from given multiple topological orderings

I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
Kunal Gupta's user avatar
3 votes
0 answers
123 views

Order the vertices to maximize the weights of edges in the induced subgraph

I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$. Goal: Find the topological order such that the smallest edge weight of the ...
Johannes's user avatar
2 votes
1 answer
313 views

Topological sort with minimum maximal distance in array

I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order. ...
dpdp's user avatar
  • 21
2 votes
1 answer
682 views

What is the relation between Topological Sort and Strongly Connected Components?

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex. I find difficult to find an explaination because ...
AlessandroF's user avatar
2 votes
1 answer
3k views

Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

For this I came up with a DFS recursion. Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing. The element with ...
Joshua Anderson's user avatar
2 votes
1 answer
64 views

Algorithm to identify common subsets

Given a large dataset $D$ and multiple sets of filters that can be applied to $D$, e.g. $setA = \{filterOnColorRed\}$ $setB = \{filterOnAgeGreaterThan20\}$ $setC = \{filterOnColorRed, ...
foo's user avatar
  • 121
2 votes
1 answer
432 views

Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
user avatar
2 votes
0 answers
92 views

How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?

Let's have a standard topological ordering algorithm (from CLRS): ...
AlessandroF's user avatar
2 votes
0 answers
127 views

Constrained/Optimal Topological Order to enhance/reduce the performance/memory usage of other algorithms

I originally posted this question here Lets assume we have a highly connected directed acyclic graph (DAG, more edges then nodes). Since it is a DAG, we can retrieve a topological order of nodes to ...
Luxii's user avatar
  • 21
2 votes
1 answer
140 views

Modified topological sort

I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways. Let's define a &...
Chip Bell's user avatar
1 vote
2 answers
317 views

Why compute finish time in topological sort

In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search ...
shark's user avatar
  • 11
1 vote
1 answer
386 views

Checking if there exists a 'source' vertex

In a directed graph $G=(V,E)$ we denote a vertex $s\in V$ to be a 'source' if there exists in $G$ a path from $s$ to all other vertices $u \in V$. The problem asks for an efficient algorithm to return ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
96 views

Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?

For the given figure, let's consider vertex v3. For v3, v0 has a higher partial order,v1 & v2 has the same partial order, and v4 & v5 have lower order than v3, e.g., higher: {v0}, same: {v1,v2}...
skdr's user avatar
  • 11
1 vote
0 answers
62 views

Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
Aryan Agarwal's user avatar
1 vote
0 answers
106 views

Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line

Consider a DAG such as one shown below: How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
nepee's user avatar
  • 280
1 vote
1 answer
178 views

Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph?

I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. I want a method to effectively parallelize these tasks. One way would be to topological sort them based ...
thambi's user avatar
  • 123
1 vote
1 answer
228 views

Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
daniel's user avatar
  • 11
1 vote
0 answers
137 views

Proof that "the last vertex in any postordering (in a DFS) of G lies in a source component of G"

From the book Algorithms (Jeff Erickson), there's a lemma that states: The last vertex in any postordering of G lies in a source component of G My initial reaction to this was that the proof would ...
user126667's user avatar
1 vote
0 answers
46 views

Optimally find one of the total orderings for a poset based on some metadata about the elements

Given a finite, partially ordered set with the following two properties: Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
luisfer's user avatar
  • 11
1 vote
0 answers
21 views

Shortest sequence of jobs, with dependencies, subject to capacity constraints

Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while ...
D.W.'s user avatar
  • 162k
0 votes
2 answers
307 views

Find minimum of a function only knowing the ordering of a set of input points

Suppose I have a function $f: \mathbb{R}^n\rightarrow\mathbb{R}$. All I know about the function is, I have a set of pairs of vectors ($\vec{v}_a$, $\vec{v}_b$) for which I know which one is greater (i....
XerneraC's user avatar
0 votes
2 answers
1k views

Why do we do topological sorting to find shortest or longest path in weighted DAG?

I was wondering why do we need to do the topological sort before performing relaxing of edges. Wouldn't it'd be better if we do : if starting vertex is "s" ...
vivek gupta's user avatar
0 votes
2 answers
1k views

Valid orderings for topological sort

I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F. Are the other 3? B, A, D, C,...
heretoinfinity's user avatar
0 votes
1 answer
201 views

DFS produces the correct Topologically ordered sequence

Prove that DFS produces the correct topologically ordered sequence. I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?
Tabris's user avatar
  • 3
0 votes
1 answer
57 views

Topological Ordering

I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order. For example consider ...
Turing101's user avatar
  • 1,200
0 votes
0 answers
8 views

Profitable sequence in a $k$-partite DAG

This question is an extension of this one. Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\...
Matheus Diógenes Andrade's user avatar
0 votes
1 answer
607 views

Is topological sort of an original graph same as post-ordering dfs of its transpose graph

I have an intuition that topo-sort of an original graph A -> B -> C D -> B topo-sort is [D, A, B, C] or [A, D, B, C] If I transpose the graph <...
wenchao jiang's user avatar