Topological Sort Order, Partial Ordering

Questions
, ,
1

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

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}

3

Thanks, Jaebum, for the information.