0
|
6583 Views
|
2 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

# Topological Sort Order, Partial Ordering

Posted 10 years ago
 Are there any routines in Mathematica for topological sorting or generating graphs for partially ordered sets? I think these are also called directed acyclic graphs, also used in PERT charts in project management. Here is a matrix for nine nodes. The matrix contains a 1 if node i precedes node j and 0 otherwise.  {{0, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 0, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0}}  The graph should have an edge if x precedes y and there is no z such that x precedes z precedes y, which means some of the 1's must be removed to have an adjacency matrix.
2 Replies
Sort By:
Posted 10 years ago
 AdjacencyGraph will create graph with your matrix and then you can do TopologicalSort over it. m = {{0, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 0, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0}}; g = AdjacencyGraph[m] g // TopologicalSort  {1, 3, 2, 5, 4, 7, 6, 8, 9}
Posted 10 years ago
 Thanks, Jaebum, for the information.
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.