00001
00002
00003
00004
00005
00006
00007
00008 #ifndef POWERCIRCUITGRAPH_H_
00009 #define POWERCIRCUITGRAPH_H_
00010
00011
00012 namespace PC
00013 {
00014
00015 class PowerCircuitGraph : public PowerCircuit
00016 {
00017 private:
00018
00019
00020
00021
00022
00023 struct IntNode
00024 {
00025 bool BV;
00026 unsigned int indexInOrder;
00027 bool deleted;
00028 int nextDeleted;
00029 std::list< std::pair<Node,Sign> > successors;
00030 };
00031
00032 struct IntMarking
00033 {
00034 bool deleted;
00035 bool reduced;
00036 int nextDeleted;
00037 int refCount;
00038 std::list< std::pair<Node,Sign> > nodes;
00039 };
00040
00041 struct NodeUsedByType
00042 {
00043 std::list< std::pair<Node,Sign> >* nodeList;
00044 std::list< std::pair<Node,Sign> >::iterator position;
00045 int id;
00046 NodeUsedByType(std::list< std::pair<Node,Sign> >* l, std::list< std::pair<Node,Sign> >::iterator iter, int i )
00047 :nodeList(l), position(iter), id(i){}
00048
00049 bool operator== (const NodeUsedByType& t2)
00050 {
00051 return (id==t2.id);
00052 }
00053 };
00054
00055
00056
00057 unsigned int numNodes;
00058 unsigned int numMarkings;
00059 unsigned int numReducedNodes;
00060 std::vector<Node> nodeOrder;
00061
00062 std::vector<IntNode> nodes;
00063 std::vector<IntMarking> markings;
00064
00065 int firstDeletedNode;
00066 int firstDeletedMarking;
00067
00068
00069
00070
00071
00072 static bool compareNodesLessThan(const std::pair<Node,Sign>& n1, const std::pair<Node,Sign>& n2)
00073 {
00074 assert(n1.first.pc==n2.first.pc);
00075 PowerCircuitGraph* pc = (PowerCircuitGraph*) n1.first.pc;
00076 return (pc->nodes[n1.first.id].indexInOrder < pc->nodes[n2.first.id].indexInOrder);
00077 }
00078
00079
00080
00081
00082 bool checkMarkingValid(const Marking& m) const;
00083 bool checkNodeValid(Node n) const;
00084
00085 void deleteNode(Node node);
00086 void deleteMarking(Marking& mark);
00087
00088 Marking newMarking(std::list< std::pair<Node,Sign> > nodeList );
00089 Node newNode(std::list< std::pair<Node,Sign> > nodeList );
00090
00091 Node newOneNode();
00092
00093 Marking newOneMarking();
00094 Marking newZeroMarking();
00095 Marking newUnitMarking(int onePos);
00096 Marking newCopyMarking(const Marking& mark);
00097
00098 std::list< std::pair<Node,Sign> > inc(const std::list< std::pair<Node,Sign> >& nodeList);
00099
00100 void moveNodeIntoReducedPart(Node node, int newPos);
00101
00102 int compare(std::list< std::pair<Node,Sign> >& l1, std::list< std::pair<Node,Sign> >& l2);
00103 void sortNodeList(std::list< std::pair<Node,Sign> >& l);
00104
00105 void insertNewPowerOfTwoNode(unsigned int power);
00106 std::list< std::pair<Node,Sign> > calculateCompactRepresentation(int n);
00107
00108 void markSucessors(std::vector<bool> marked, std::list< std::pair<Node,Sign> >& nodeList);
00109 void setBV(Node node);
00110 Node newDoubleNode(Node node);
00111
00112 std::list< std::pair<Node,Sign> >::iterator findNodeInList(unsigned int nodeIndex, std::list< std::pair<Node,Sign> >& nodeList);
00113 void removeDoubleNodesFromMarkings(Node oldNode, Node newNode, std::list<NodeUsedByType>* nodeUsedBy);
00114
00115 int findNewPosOfReducedNode(Node node, bool& equal);
00116 int insertNodeIntoReduced(Node node, std::list<NodeUsedByType>* nodeUsedBy);
00117 void topSortNode(Node node, std::vector<bool>& visited, std::vector<Node>& topSortPerm);
00118
00119 void extendTree(std::vector<Node>& nodeList, std::vector<Marking>& markingList);
00120
00121
00122
00123 virtual void incMarkingRefCount(const Marking& mark);
00124 virtual void decMarkingRefCount(Marking& mark);
00125 virtual Marking addMarkings(const Marking& m1, const Marking& m2) ;
00126 virtual Marking invMarking(const Marking& m);
00127 virtual Marking incMarking(const Marking& mark);
00128 virtual Marking intersectMarkings(const Marking& m1, const Marking& m2);
00129 virtual Marking cloneMarking(const Marking& mark);
00130 virtual Node cloneNode(Node n);
00131 virtual Marking copyMarking(const Marking& m);
00132 virtual bool isMarkingReduced(const Marking& m) const;
00133 virtual int compareMarkings(const Marking& m1, const Marking& m2);
00134 virtual int getRedNodeOrd(Node n);
00135 virtual int getNodeSignInMarking(Node n, const Marking& m) const;
00136 virtual bool isSuccessorMarking(const Marking& m) const;
00137 virtual Node getIncidentNode(const Marking& m);
00138 virtual Node getSmallestNodeInMarking(const Marking& m);
00139 virtual Marking getSuccMarking(Node n);
00140
00141 public:
00142
00143 PowerCircuitGraph();
00144 virtual ~PowerCircuitGraph();
00145
00146
00147 virtual void reduce();
00148 void reduce(std::list<Marking> markingList);
00149 virtual void reduce(std::vector<Node>& nodeVector, std::vector<Marking>& markingVector);
00150 virtual Marking createMarking(int i = 0);
00151 virtual Marking createMarking(const std::list<Node>& nodes);
00152 virtual Marking createMarking(const std::list<Node>& nodeList, const std::list<int>& signList);
00153 virtual Marking createMarking(const std::list< std::pair<Node,Sign> >& nodeList );
00154 virtual Node createNode(const Marking& succ) ;
00155 virtual void connect(const Marking& m, const Marking& p) ;
00156 virtual void connectInv(const Marking& m, const Marking& q);
00157 virtual void remove(const Marking& m) ;
00158 virtual Node getReducedNode(unsigned int ord);
00159 virtual std::list<Node> getNodes();
00160 virtual std::list<Marking> getMarkings();
00161 virtual std::list<Node> getMarkingNodes(const Marking& m);
00162 virtual PowerCircuit* clone(std::vector<Marking>& markingsToKeep);
00163
00164
00165 virtual void print(std::ostream& os= std::cout);
00166 void printMarking(const Marking& m, std::ostream& os= std::cout);
00167 void printMarking(const std::list< std::pair<Node, Sign> >& l ,std::ostream& os= std::cout);
00168 double getMatrixUsage();
00169 virtual void printStatistics(std::ostream& os = std::cout);
00170
00171 bool checkCyclesRecursive(int n, std::vector<bool> & visited);
00172 bool checkCycles();
00173 bool checkConsistency();
00174 };
00175
00176 }
00177
00178 #endif
1.6.1
