Message Boards Message Boards

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

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
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

Thanks, Jaebum, for the information.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract