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 revisionBoth sides next revision
tutorial:matching_polytopes [2014/01/03 15:45] – external edit 127.0.0.1tutorial:matching_polytopes [2017/07/19 09:12] – added some formatting to enable automated tests 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 ($i=0; $i<4; ++$i) { 
-  for ($j=$i+1; $j<4; ++$j) { +>   for ($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>
Line 132: Line 129:
 {{ :tutorial:ilp:gale.png?300|The Gale diagram of ''facet0''}} {{ :tutorial: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