topological-sort Questions
3
I am trying to implement topological sort using Spark's GraphX library.
This is the code I've written so far:
MyObject.scala
import java.util.ArrayList
import scala.collection.mutable.Queue
im...
Eventide asked 18/10, 2016 at 13:11
5
Solved
Problem: Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph.
Please find the reference graph: lin...
Gulp asked 23/12, 2014 at 1:31
6
Solved
I'm trying to work out if my problem is solvable using the builtin sorted() function or if I need to do myself - old school using cmp would have been relatively easy.
My data-set looks like:
x =...
Coastal asked 19/7, 2012 at 8:56
4
Solved
I'm trying to reproduce this GitHub project on my machine, on Topological Data Analysis (TDA).
My steps:
get best parameters from a cross-validation output
load my dataset feature selection
extrac...
Sampling asked 15/1, 2021 at 20:17
9
Solved
I know the common way to do a topological sort is using DFS with recursion. But how would you do it using stack<int> instead of recursion? I need to obtain the reversed post-order but I'm kin...
Shuck asked 22/11, 2013 at 20:1
5
Solved
Extracted from here we got a minimal iterative dfs routine, i call it minimal because you can hardly simplify the code further:
def iterative_dfs(graph, start, path=[]):
q = [start]
while q:
v ...
Saritasarkaria asked 9/11, 2017 at 1:51
11
Solved
NOTE
The question has been edited following the good advise from @Kaddath to highlight the fact that the ordering doesn't have to be alphabetical but depending on the position of items inside the ...
Connivance asked 11/12, 2018 at 9:21
2
Solved
I am looking for a way to perform a topological sorting on a given directed unweighted graph, that contains cycles. The result should not only contain the ordering of vertices, but also the set of ...
Ames asked 17/6, 2013 at 13:1
1
Solved
Alien Dictionary
Link to the online judge -> LINK
Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in t...
Lorenalorene asked 24/2, 2021 at 13:17
4
Solved
I was trying to write code for detecting a cycle in a directed graph and if there is no cycle then return a topological order of the same.
While I was searching for it I came across different tec...
Submarine asked 15/10, 2019 at 6:31
2
Solved
Assume that there are an unlimited number of workers each of which can
complete one task, each of which takes some time. There are also
precedence constraints where one task cannot be completed...
Cepheus asked 1/1, 2014 at 0:51
2
Solved
Say, we have some items, and each defines some partial sorting rules, like this:
I'm A and I want to be before B
I'm C and I want to be after A but before D
So we have items A,B,C,D with th...
Elater asked 6/1, 2011 at 21:32
5
Solved
This is probably a 2 liner, but for some reason I have hit a wall.
I'd like to convert an array of objects to an object of key-value pairs.
So this:
var items = [
{
name: 'hello',
va...
Hanoverian asked 18/4, 2020 at 22:16
5
Solved
I must show a set of images that depend on each other. For example
Image A depends on no one
Image B depends on A
Image C depends on A and B
Image D depends on F
Image E depends on D and C
Im...
Nauseating asked 24/1, 2019 at 12:3
1
Solved
I have a set of items and a comparator function which defines a partial ordering -- given two items, it returns "=", "<", ">", or "no defined ordering" (say "<>"). I want to produce a sorted ...
Sonni asked 29/1, 2020 at 11:11
10
Solved
I have a collection:
List<VPair<Item, List<Item>> dependencyHierarchy;
The first item in pair is some object (item) and the second one is a collection of the same type objects tha...
Rathskeller asked 5/11, 2010 at 14:34
2
I am interested in finding some real world massive data sets (>=1M) which needed to be topologically sorted. Perhaps something relating to bioinformatics?
Togo asked 12/6, 2017 at 0:3
3
Solved
The following question was found in Sedgewick and Wayne book about algorithms in java:
4.2.19 Topological sort and BFS. Explain why the following algorithm does not necessarily produce a topologic...
Nunnery asked 16/6, 2015 at 14:4
2
I have a DAG with N nodes, i.e., 1, 2, ..., N, and each node has a weight (we can call it time) x_1, x_2, ..., x_N. I want to do a topological sorting but the difficulty is that I have an objective...
Axum asked 13/7, 2016 at 7:56
3
Solved
I've been studying SCC and algorithms about them, and I've seen that people almost always mention that Kosaraju's algorithm finds the SCC and also gives them ordered in a (reversed) topological sor...
Sheena asked 23/9, 2015 at 22:25
6
Solved
I have a list of items that have a partial order relation, i. e, the list can be considered a partially ordered set. I want to sort this list in the same way as in this question. As correctly answe...
Jalap asked 30/12, 2009 at 21:30
2
Solved
There's a gap in my knowledge but I'm not sure exactly where. Topological sorting can be done using depth first search, as wikipedia explains. However I've only seen depth first search implemented ...
England asked 19/4, 2016 at 8:1
2
I've created a lightweight graph lib, which has 3 objects (Vertex, Edge, Graph) and 1 function (topo_sort), which looks like:
class DAGError(Exception): pass
def topo_sort(graph):
sorted_list = ...
Lactoscope asked 18/8, 2013 at 15:17
4
Solved
Consider the following dependencies (where A --> B means B depends on A, so effectively, A is the 'parent')
A --> B
A --> C
C --> D
C --> E
More graphically:
A
|
----------
| |...
Dziggetai asked 17/1, 2014 at 15:11
1
Solved
I have to develop an O(|V|+|E|) algorithm related to topological sort which, in a directed acyclic graph (DAG), determines the number of paths from each vertex of the graph to t (t is a node with o...
Ayo asked 6/8, 2013 at 18:17
1 Next >
© 2022 - 2024 — McMap. All rights reserved.