From neos@mcs.anl.gov Mon Jun 16 08:41:56 2008 Date: Mon, 16 Jun 2008 08:41:21 -0500 From: neos@mcs.anl.gov To: olinick@engr.smu.edu Subject: NEOS Results for Job #1647459 Job 1647459 sent to newton.mcs.anl.gov password: GyePxMqt ---------- Begin Solver Output ----------- Executing /home/neosotc/neos-5-solvers/minos-ampl/minos-driver.py File exists You are using the solver minos. Executing AMPL. processing data. processing commands. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= MCF Cut Community Structure Algorithm Data file: FlorentineFamilies.txt Selection Criterion: sparsest component =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 1 Nodes in Component 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 density = 0.190476 Q = 0.000000 Selecting Component 1. MCF in Component 1 = 0.038462 set Saturated_Edges := (2,7) (2,9) (3,5) (3,9) (4,7) (9,13); set Cut_Edges := (9,13); Edges Removed From Component 1: set Cut_Edges := (9,13); Node Pairs Separated by Cut: set Separated_Demands := (1,10) (3,10) (5,10) (7,10) (9,10) (10,14) (13,14) (1,13) (3,13) (5,13) (7,13) (9,13) (10,15) (13,15) (2,10) (4,10) (6,10) (8,10) (10,11) (11,13) (2,13) (4,13) (6,13) (8,13) (10,12) (12,13); Cut Density = 1/26 = 0.038462 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 2 Nodes in Component 1: 1 2 3 4 5 6 7 8 9 11 12 14 15 density = 0.230769 Nodes in Component 2: 10 13 density = 1.000000 Q = 0.088750 Selecting Component 1. MCF in Component 1 = 0.075000 set Saturated_Edges := (2,7) (3,5) (4,7) (7,15) (12,14) (2,9) (3,9) (5,11) (9,12); set Cut_Edges := (3,9) (4,7) (12,14); Edges Removed From Component 1: set Cut_Edges := (3,9) (4,7) (12,14); Node Pairs Separated by Cut: set Separated_Demands := (1,3) (2,3) (3,6) (3,15) (4,12) (5,9) (7,11) (9,14) (1,4) (2,4) (3,7) (4,6) (4,15) (5,12) (7,14) (11,12) (1,5) (2,5) (3,8) (4,7) (5,6) (5,15) (8,11) (11,15) (1,11) (2,11) (3,9) (4,8) (5,7) (6,11) (8,14) (12,14) (1,14) (2,14) (3,12) (4,9) (5,8) (6,14) (9,11) (14,15); Cut Density = 3/40 = 0.075000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 3 Nodes in Component 1: 1 2 6 7 8 9 12 15 density = 0.321429 Nodes in Component 2: 3 4 5 11 14 density = 0.600000 Nodes in Component 3: 10 13 density = 1.000000 Q = 0.351250 Selecting Component 1. MCF in Component 1 = 0.125000 set Saturated_Edges := (2,7) (2,9) (7,15) (9,12); set Cut_Edges := (2,9) (7,15); Edges Removed From Component 1: set Cut_Edges := (2,9) (7,15); Node Pairs Separated by Cut: set Separated_Demands := (1,2) (1,7) (2,9) (2,15) (6,12) (7,9) (7,15) (8,12) (1,6) (1,8) (2,12) (6,9) (6,15) (7,12) (8,9) (8,15); Cut Density = 2/16 = 0.125000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 4 Nodes in Component 1: 1 9 12 15 density = 0.666667 Nodes in Component 2: 2 6 7 8 density = 0.500000 Nodes in Component 3: 3 4 5 11 14 density = 0.600000 Nodes in Component 4: 10 13 density = 1.000000 Q = 0.397500 Selecting Component 2. MCF in Component 2 = 0.250000 set Saturated_Edges := (2,7); set Cut_Edges := (2,7); Edges Removed From Component 2: set Cut_Edges := (2,7); Node Pairs Separated by Cut: set Separated_Demands := (2,7) (2,8) (6,7) (6,8); Cut Density = 1/4 = 0.250000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 5 Nodes in Component 1: 1 9 12 15 density = 0.666667 Nodes in Component 2: 2 6 density = 1.000000 Nodes in Component 3: 3 4 5 11 14 density = 0.600000 Nodes in Component 4: 7 8 density = 1.000000 Nodes in Component 5: 10 13 density = 1.000000 Q = 0.372500 Selecting Component 3. MCF in Component 3 = 0.250000 set Saturated_Edges := (3,5) (5,14); set Cut_Edges := (3,5); Edges Removed From Component 3: set Cut_Edges := (3,5); Node Pairs Separated by Cut: set Separated_Demands := (3,4) (3,5) (3,11) (3,14); Cut Density = 1/4 = 0.250000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 6 Nodes in Component 1: 1 9 12 15 density = 0.666667 Nodes in Component 2: 2 6 density = 1.000000 Nodes in Component 3: 3 density = 0.000000 Nodes in Component 4: 4 5 11 14 density = 0.833333 Nodes in Component 5: 7 8 density = 1.000000 Nodes in Component 6: 10 13 density = 1.000000 Q = 0.355000 Selecting Component 1. MCF in Component 1 = 0.333333 set Saturated_Edges := (1,9); set Cut_Edges := (1,9); Edges Removed From Component 1: set Cut_Edges := (1,9); Node Pairs Separated by Cut: set Separated_Demands := (1,9) (1,12) (1,15); Cut Density = 1/3 = 0.333333 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 7 Nodes in Component 1: 1 density = 0.000000 Nodes in Component 2: 2 6 density = 1.000000 Nodes in Component 3: 3 density = 0.000000 Nodes in Component 4: 4 5 11 14 density = 0.833333 Nodes in Component 5: 7 8 density = 1.000000 Nodes in Component 6: 9 12 15 density = 1.000000 Nodes in Component 7: 10 13 density = 1.000000 Q = 0.320000 Selecting Component 4. MCF in Component 4 = 0.666667 set Saturated_Edges := (4,11) (4,14) (5,11) (5,14); set Cut_Edges := (5,11) (5,14); Edges Removed From Component 4: set Cut_Edges := (5,11) (5,14); Node Pairs Separated by Cut: set Separated_Demands := (4,5) (5,11) (5,14); Cut Density = 2/3 = 0.666667 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 8 Nodes in Component 1: 1 density = 0.000000 Nodes in Component 2: 2 6 density = 1.000000 Nodes in Component 3: 3 density = 0.000000 Nodes in Component 4: 4 11 14 density = 1.000000 Nodes in Component 5: 5 density = 0.000000 Nodes in Component 6: 7 8 density = 1.000000 Nodes in Component 7: 9 12 15 density = 1.000000 Nodes in Component 8: 10 13 density = 1.000000 Q = 0.257500 Selecting Component 2. MCF in Component 2 = 1.000000 set Saturated_Edges := (2,6); MCF saturates all edges set Cut_Edges := (2,6); Edges Removed From Component 2: set Cut_Edges := (2,6); Node Pairs Separated by Cut: set Separated_Demands := (2,6); Cut Density = 1/1 = 1.000000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 9 Nodes in Component 1: 1 density = 0.000000 Nodes in Component 2: 2 density = 0.000000 Nodes in Component 3: 3 density = 0.000000 Nodes in Component 4: 4 11 14 density = 1.000000 Nodes in Component 5: 5 density = 0.000000 Nodes in Component 6: 6 density = 0.000000 Nodes in Component 7: 7 8 density = 1.000000 Nodes in Component 8: 9 12 15 density = 1.000000 Nodes in Component 9: 10 13 density = 1.000000 Q = 0.211250 Stopping criteria reached. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Best community structure found has 4 components with Q = 0.397500: Nodes in Component 1: 1 9 12 15 Nodes in Component 2: 2 6 7 8 Nodes in Component 3: 3 4 5 11 14 Nodes in Component 4: 10 13 Total CPU seconds to partition this graph = 0.148008