user_guide:tutorials:matching_polytopes

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
Next revisionBoth sides next revision
tutorial:matching_polytopes [2014/01/03 15:45] – external edit 127.0.0.1user_guide:matching_polytopes [2019/01/25 09:27] – ↷ Links adapted because of a move operation oroehrig
Line 5: Line 5:
 First we construct a graph, the complete graph on four nodes: First we construct a graph, the complete graph on four nodes:
 <code> <code>
-$K4=new props::Graph(4); +> $K4=new props::Graph(4); 
- +> 
-for ($i=0; $i<4; ++$i) { +> for (my $i=0; $i<4; ++$i) { 
-  for ($j=$i+1; $j<4; ++$j) { +>   for (my $j=$i+1; $j<4; ++$j) { 
-    $K4->edge($i,$j); +>     $K4->edge($i,$j); 
-  } +>   } 
-}+> }
 </code> </code>
  
Line 18: Line 18:
 Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of ''polymake'' does not yet support this, we have to write the function ourselves: Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of ''polymake'' does not yet support this, we have to write the function ourselves:
 <code> <code>
-sub node_edge_incidences { +> sub node_edge_incidences { 
- my $g=shift; +> my $g=shift; 
- my $A=new Matrix<Int>($g->nodes, $g->edges); +> my $A=new Matrix<Int>($g->nodes, $g->edges); 
- my $k=0; +> my $k=0; 
- for (my $i=0; $i<$g->nodes-1; ++$i) { +> for (my $i=0; $i<$g->nodes-1; ++$i) { 
- foreach (@{$g->adjacent_nodes($i)}) { +> foreach (@{$g->adjacent_nodes($i)}) { 
- if ($_>$i) { +> if ($_>$i) { 
- $A->[$i]->[$k]=1; +> $A->[$i]->[$k]=1; 
- $A->[$_]->[$k]=1; +> $A->[$_]->[$k]=1; 
- ++$k; +> ++$k; 
- } +> } 
- } +> } 
- } +> } 
- return $A; +> return $A; 
-}+> }
 </code> </code>
 Now we can construct the node-edge-incidence matrix of our graph ''K4'': Now we can construct the node-edge-incidence matrix of our graph ''K4'':
 <code> <code>
-$A=node_edge_incidences($K4); +> $A=node_edge_incidences($K4); 
- +> print $A;
-print $A;+
 1 1 1 0 0 0 1 1 1 0 0 0
 1 0 0 1 1 0 1 0 0 1 1 0
Line 47: Line 46:
 With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x<sub>e</sub><html>&ge;</html>0 ... With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x<sub>e</sub><html>&ge;</html>0 ...
 <code> <code>
-$I=new Matrix<Int>([[1,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,1]]); +> $I=new Matrix<Int>([[1,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,1]]); 
- +> $Block1=new Matrix<Int>((new Vector<Int>([0,0,0,0,0,0])) | $I);
-$Block1=new Matrix<Int>((new Vector<Int>([0,0,0,0,0,0])) | $I);+
 </code> </code>
  
Line 55: Line 53:
  
 <code> <code>
-$Block2=new Matrix<Int>((new Vector<Int>([1,1,1,1])) | (-$A));+> $Block2=new Matrix<Int>((new Vector<Int>([1,1,1,1])) | (-$A));
 </code> </code>
  
 Now we can put both parts together and define the polytope: Now we can put both parts together and define the polytope:
 <code> <code>
-$Ineqs=new Matrix<Rational>($Block1 / $Block2); +> $Ineqs=new Matrix<Rational>($Block1 / $Block2); 
- +> $P=new Polytope<Rational>(INEQUALITIES=>$Ineqs);
-$P=new Polytope<Rational>(INEQUALITIES=>$Ineqs);+
 </code> </code>
  
 The matching polytope of ''K4'' is the integer hull of ''P'': The matching polytope of ''K4'' is the integer hull of ''P'':
 <code> <code>
-$P_I=new Polytope<Rational>(POINTS=>$P->LATTICE_POINTS);+> $P_I=new Polytope<Rational>(POINTS=>$P->LATTICE_POINTS);
 </code> </code>
  
 We can analyse some elementary properties of ''P_I'' ... We can analyse some elementary properties of ''P_I'' ...
 <code> <code>
-print $P_I->POINTS;+> print $P_I->POINTS;
 1 0 0 0 0 0 0 1 0 0 0 0 0 0
 1 0 0 0 0 0 1 1 0 0 0 0 0 1
Line 84: Line 81:
 1 1 0 0 0 0 1 1 1 0 0 0 0 1
  
-print $P_I->FACETS;+> print $P_I->FACETS;
 0 0 0 0 0 0 1 0 0 0 0 0 0 1
 0 1 0 0 0 0 0 0 1 0 0 0 0 0
Line 100: Line 97:
 0 0 0 1 0 0 0 0 0 0 1 0 0 0
  
-print $P_I->N_FACETS;+> print $P_I->N_FACETS;
 14 14
 </code> </code>
Line 106: Line 103:
 ... and compare them with the according properties of the defining polytope ''P'': ... and compare them with the according properties of the defining polytope ''P'':
 <code> <code>
-print $P->VERTICES;+> print $P->VERTICES;
 1 0 0 0 1 0 0 1 0 0 0 1 0 0
 1 0 1 0 0 0 0 1 0 1 0 0 0 0
Line 122: Line 119:
 1 0 0 1 1 0 0 1 0 0 1 1 0 0
  
-print $P->VOLUME;+> print $P->VOLUME;
 1/72 1/72
  
-print $P_I->VOLUME;+> print $P_I->VOLUME;
 1/90 1/90
 </code> </code>
  
 Next we analyse the combinatorics of ''P_I'': Next we analyse the combinatorics of ''P_I'':
-{{ :tutorial:ilp:gale.png?300|The Gale diagram of ''facet0''}}+{{ user_guide:ilp:gale.png?300|The Gale diagram of ''facet0''}}
 <code> <code>
-print $P_I->AMBIENT_DIM, " ", $P_I->DIM;+> print $P_I->AMBIENT_DIM, " ", $P_I->DIM;
 6 6 6 6
  
-print $P_I->F_VECTOR;+> print $P_I->F_VECTOR;
 10 39 78 86 51 14 10 39 78 86 51 14
  
-print $P_I->FACET_SIZES;+> print $P_I->FACET_SIZES;
 8 8 6 6 6 6 6 6 6 6 8 8 8 8 8 8 6 6 6 6 6 6 6 6 8 8 8 8
  
-$facet0=facet($P_I,0);+> $facet0=facet($P_I,0);
  
-print $facet0->AMBIENT_DIM, " ", $facet0->DIM;+> print $facet0->AMBIENT_DIM, " ", $facet0->DIM;
 6 5 6 5
  
-print rows_labeled($facet0->VERTICES_IN_FACETS);+> print rows_labeled($facet0->VERTICES_IN_FACETS);
 0:0 1 2 3 4 5 6 0:0 1 2 3 4 5 6
 1:1 2 4 6 7 1:1 2 4 6 7
Line 157: Line 154:
 8:0 1 2 5 6 7 8:0 1 2 5 6 7
  
-$facet0->GALE;+> $facet0->GALE;
 </code> </code>
 The Gale diagram of ''facet0'' is depicted on the right. The Gale diagram of ''facet0'' is depicted on the right.
  • user_guide/tutorials/matching_polytopes.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1