File: newtonpolytope.cpp

package info (click to toggle)
gfan 0.6.2-2
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 8,372 kB
  • sloc: cpp: 53,144; makefile: 556
file content (72 lines) | stat: -rw-r--r-- 1,685 bytes parent folder | download | duplicates (8)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "newtonpolytope.h"

#include "lp.h"

void removeNonExtremeVerticesOfPolytope(IntegerVectorList &polytope)
{
  if(polytope.empty())return;

  int n=polytope.begin()->size();

  for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
    {
      j->resize(n+1);
      (*j)[n]=1;
    }

  for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
    if(!isFacet(polytope,j))
      {
	IntegerVectorList::iterator k=j;
	j++;
	polytope.erase(k);
	j--;
      }
  
  for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
    j->resize(n);
}


IntegerVectorList newtonPolytope(Polynomial const &p)
{
  IntegerVectorList polytope;

  for(TermMap::const_iterator i=p.terms.begin();i!=p.terms.end();i++)
    {
      polytope.push_back(i->first.exponent);      
    }

  removeNonExtremeVerticesOfPolytope(polytope);
  
  return polytope;
}


/*
  This routine should be split into several so that it can also handle closed cones and tropical hypersurfaces.
 */
HalfOpenConeList normalFan(int dimension, IntegerVectorList l, TermOrder const &t)
{
  HalfOpenConeList ret;

  removeNonExtremeVerticesOfPolytope(l);
  for(IntegerVectorList::const_iterator i=l.begin();i!=l.end();i++)
    {
      IntegerVectorList strictList,nonStrictList;
      for(IntegerVectorList::const_iterator j=l.begin();j!=l.end();j++)
	if(j!=i)
	  {
	    IntegerVector v=*i-*j;
	    if(t(*i,*j))//we don't need to find the facets, right?
	      strictList.push_back(v);
	    else
	      nonStrictList.push_back(v);
	    
	    IntegerVectorList empty;
	    ret.push_back(HalfOpenCone(dimension,empty,nonStrictList,strictList,true));
	  }
    }

  return ret;
}