Message Boards Message Boards

0
|
6347 Views
|
2 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Topological Sort Order, Partial Ordering

David J M Park Jr
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.
POSTED BY: David J M Park Jr
2 Replies
Sort By:

Thanks, Jaebum, for the information.
POSTED BY: David J M Park Jr
Jaebum Jung
Jaebum Jung, Wolfram
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 BY: Jaebum Jung
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract