Will a source-removal sort always return a maximal cycle?

Posted by Jason Baker on Stack Overflow See other posts from Stack Overflow or by Jason Baker
Published on 2010-04-02T17:58:05Z Indexed on 2010/04/02 18:03 UTC
Read the original article Hit count: 142

Filed under:

graph-theory

|

topological-sort

|

dependencies

|

source-removal

I wrote a source-removal algorithm to sort some dependencies between tables in our database, and it turns out we have a cycle. For simplicity, let's say we have tables A, B, C, and D. The edges are like this:

(A, B)
(B, A)
(B, C)
(C, D)
(D, A)

As you can see, there are two cycles here. One is between A and B and another is between all four of them. Will this type of sort always choke on the largest cycle? Or is that not necessarily the case?

© Stack Overflow or respective owner

Related posts about graph-theory

Graph theory in python

as seen on Stack Overflow - Search for 'Stack Overflow'
I was wondering how people deal with graph theory in python? How is a graph stored? Are there libraries for this? For example how would I input a graph and then find its Chromatic polynomial? Or its girth? Or the number of unique spanning trees? How about problems that involve edge weight like salesman… >>> More
What is the relaxation condition in graph theory

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm trying to understand the main concepts of graph theory and the algorithms within it. Most algorithms seem to contain a "Relaxation Condition" I'm unsure about what this is. Could some one explain it to me please. An example of this is dijkstras algorithm, here is the pseudo-code. 1 … >>> More
Translation of clustering problem to graph theory language

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a rectangular planar grid, with each cell assigned some integer weight. I am looking for an algorithm to identify clusters of 3 to 6 adjacent cells with higher-than-average weight. These blobs should have approximately circular shape. For my case the average weight of the cells not containing… >>> More
box stacking in graph theory

as seen on Stack Overflow - Search for 'Stack Overflow'
Please help me find a good solution for this problem. We have n boxes with 3 dimensions. We can orient them and we want to put them on top of another to have a maximun height. We can put a box on top of an other box, if 2 dimensions (width and lenght) are lower than the dimensions of the box below… >>> More
Is finding graph minors without single node pinch points possible?

as seen on Game Development - Search for 'Game Development'
Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up your graph into a Hamiltonian cycle and then from that find the graph minors but it seems to be such… >>> More

Related posts about topological-sort

Sample Directed Graph and Topological Sort Code

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello Anyone know where I can obtain sample code for a Directed Graph and sample code for performing a topological sort on a directed graph? (preferably in Java) Thanks >>> More
Will a source-removal sort always return a maximal cycle?

as seen on Stack Overflow - Search for 'Stack Overflow'
I wrote a source-removal algorithm to sort some dependencies between tables in our database, and it turns out we have a cycle. For simplicity, let's say we have tables A, B, C, and D. The edges are like this: (A, B) (B, A) (B, C) (C, D) (D, A) As you can see, there are two cycles here. One is… >>> More
directed unweighted graphs C

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm planning to write a program in C that builds the adjacency list, performs the depth first search, performs the breadth first search, and performs the topological sort. Where can I get some info about this subject in C? Any help is appreciated >>> More
Nervous about the "real" world

as seen on Programmers - Search for 'Programmers'
I am currently majoring in Computer Science and minoring in mathematics (the minor is embedded in the major). The program has a strong C++ curriculum. We have done some UNIX and assembly language (not fun) and there is C and Java on the way in future classes that I must take. The program I am in did… >>> More
Pecking order of pigeons?

as seen on Stack Overflow - Search for 'Stack Overflow'
I was going though problems on graph theory posted by Prof. Ericksson from my alma-mater and came across this rather unique question about pigeons and their innate tendency to form pecking orders. The question goes as follows: Whenever groups of pigeons gather, they instinctively establish a… >>> More