22 #ifndef TULIP_PLANARITYIMPL_H 
   23 #define TULIP_PLANARITYIMPL_H 
   25 #ifndef DOXYGEN_NOTFOR_USER 
   30 #include <tulip/Edge.h> 
   31 #include <tulip/MutableContainer.h> 
   32 #include <tulip/BmdList.h> 
   33 #include <tulip/tulipconf.h> 
   34 #include <tulip/Node.h> 
   38 enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC };
 
   39 static const node NULL_NODE = node();
 
   40 static const edge NULL_EDGE = edge();
 
   42 class TLP_SCOPE PlanarityTestImpl {
 
   45   PlanarityTestImpl(Graph *sg);
 
   46   bool isPlanar(
bool embedsg = 
false);
 
   47   static bool isPlanarEmbedding(
const Graph *sG);
 
   48   std::list<edge> getObstructions();
 
   51   bool compute(Graph *);
 
   54   edge edgeReversal( edge e);
 
   55   void makeBidirected(Graph *sG);
 
   56   void swapNode(node &n1, node &n2);
 
   57   void findTerminalNodes(Graph *sG, node n, std::list<node>& listOfComponents,
 
   58                          std::map<node, std::list<node> > &terminalNodes);
 
   59   bool findObstruction(Graph *sG, node n, std::list<node>& terminalNodes);
 
   60   void setInfoForNewCNode(Graph *sG, node n, node newCNode,
 
   61                           std::list<node>& terminalNodes);
 
   62   node findActiveCNode(node, node, std::list<node>&);
 
   63   void preProcessing(Graph *);
 
   64   tlp::BmdLink<node>* searchRBC(
int,  tlp::BmdLink<node>*, node, std::list<node>&);
 
   65   bool isT0Edge(Graph *, edge);
 
   66   bool isBackEdge(Graph *, edge);
 
   68   void sortNodesIncreasingOrder(Graph *, MutableContainer<int>&, std::vector<node>&);
 
   69   node activeCNodeOf(
bool, node);
 
   70   void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node>&);
 
   71   void updateLabelB(node);
 
   72   void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node>&);
 
   73   node lastPNode(node, node);
 
   74   node lcaBetween(node, node,  
const MutableContainer<node>&);
 
   75   node lcaBetweenTermNodes(node, node);
 
   76   void calculateNewRBC(Graph *, node, node, std::list<node>&);
 
   77   node findNodeWithLabelBGreaterThanDfsN(
bool, Graph *, node, node);
 
   78   void setPossibleK33Obstruction(node, node, node, node);
 
   79   bool testCNodeCounter(Graph *, node, node, node, node, node&, node&);
 
   80   bool testObstructionFromTerminalNode(Graph *, node, node, node);
 
   83   bool listEdgesUpwardT0(node n1, node n2);
 
   84   void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge>& listEdges);
 
   86   void obstrEdgesTerminal(Graph* G, node w, node t, node u);
 
   87   void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3);
 
   88   void sortByLabelB(node &n1, node &n2, node &n3);
 
   89   void obstrEdgesPNode(Graph *sG, node p, node u);
 
   90   void calcInfo3Terminals(node &t1, node &t2, node &t3, 
int &countMin, 
int &countF, node &cNode, node &q);
 
   91   void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v);
 
   92   void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3);
 
   93   void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q, node v);
 
   95   void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3);
 
   96   void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v);
 
   97   void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1, node t2);
 
  100   void embedRoot(Graph *sG, 
int n);
 
  101   void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge>& listBackEdges, std::list<node>& terminalNodes);
 
  102   void markPathInT(node t, node w, std::map<node, node>& backEdgeRepresentant, std::list<node>& traversedNodes);
 
  103   std::map< node, std::list<edge> > groupBackEdgesByRepr(Graph *sG, std::list<edge>& listBackEdges,
 
  104       std::map<node, node>& backEdgeRepresentant,
 
  105       std::list<node>& traversedNodes,
 
  106       std::list<node>& listRepresentants);
 
  107   std::list<node> embedUpwardT(
bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
 
  108                                std::map< node, std::list<edge> > &bEdgesRepres,
 
  109                                std::list<node>& traversedNodes,
 
  110                                BmdList<edge>& embList);
 
  111   void addOldCNodeToEmbedding(
bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
 
  112                               std::map<node,std::list<edge> >& bEdgesRepres,
 
  113                               std::list<node>& traversedNodes,
 
  114                               std::list<node>& toEmbedLater,
 
  115                               BmdList<edge>& embList);
 
  116   void embedBackEdges(
bool embBackEdgesOutW, Graph *sG, node repr,
 
  117                       std::list<node>& traversedNodes,
 
  118                       std::list<edge>& listBackEdges,
 
  119                       BmdList<edge>& embList);
 
  120   int sortBackEdgesByDfs(Graph *sG, node w, node repr,
 
  121                          std::list<edge>& listBackEdges,
 
  122                          std::vector<edge>& backEdge);
 
  128   bool embed, biconnected;
 
  129   node lastNodeInQLinha;
 
  130   std::map<edge, edge> bidirectedEdges;
 
  131   std::map<edge, edge> reversalEdge;
 
  134   node cNodeOfPossibleK33Obstruction;
 
  141   std::map<node, std::list<node> > childrenInT0;
 
  148   std::map<node, std::list<edge> > listBackEdges;
 
  152   std::map<node, BmdList<node> > RBC;
 
  157   std::map<node, BmdList<edge> > embedList;
 
  160   std::map<tlp::BmdLink<node>*, node> activeCNode;
 
  164   BmdList<edge> listBackEdgesOutW;
 
  168   std::list<node> obstructionNodes;
 
  171   std::list<edge> obstructionEdges;
 
  177   MutableContainer< tlp::BmdLink<node>*> ptrItem;
 
  180   MutableContainer<int> dfsPosNum;
 
  183   MutableContainer<node> nodeWithDfsPos;
 
  187   MutableContainer<edge> T0EdgeIn;
 
  191   MutableContainer<node> parent;
 
  192   MutableContainer<node> p0;
 
  197   MutableContainer<int> largestNeighbor;
 
  203   MutableContainer<int> labelB;
 
  209   MutableContainer<node> nodeLabelB;
 
  213   MutableContainer<node> lastVisited;
 
  218   MutableContainer<node> neighborWTerminal;
 
  223   MutableContainer<int> state;
 
  227   MutableContainer<int> counter;
 
  231   MutableContainer<bool> hasBackEdge;
 
  232   unsigned int numberOfNodesInG;
 
  239 std::list<tlp::edge> posDFS(
tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);