abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaEmbed.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [giaEmbed.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Scalable AIG package.]
8 
9  Synopsis [Logic network derived from AIG.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: giaEmbed.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include <math.h>
22 #include "gia.h"
23 #include "aig/ioa/ioa.h"
24 
25 ABC_NAMESPACE_IMPL_START
26 
27 
28 /*
29  The code is based on the paper by D. Harel and Y. Koren,
30  "Graph drawing by high-dimensional embedding",
31  J. Graph Algs & Apps, Vol 8(2), pp. 195-217 (2004).
32  http://www.emis.de/journals/JGAA/accepted/2004/HarelKoren2004.8.2.pdf
33 
34  Iterative refinement is described in the paper: F. A. Aloul, I. L. Markov, and K. A. Sakallah.
35  "FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic", Proc. GLSVLSI’03.
36  http://www.eecs.umich.edu/~imarkov/pubs/conf/glsvlsi03-force.pdf
37 */
38 
39 ////////////////////////////////////////////////////////////////////////
40 /// DECLARATIONS ///
41 ////////////////////////////////////////////////////////////////////////
42 
43 #define GIA_PLACE_SIZE 0x7fff
44 // objects will be placed in box [0, GIA_PLACE_SIZE] x [0, GIA_PLACE_SIZE]
45 
46 typedef float Emb_Dat_t;
47 
48 typedef struct Emb_Obj_t_ Emb_Obj_t;
49 struct Emb_Obj_t_
50 {
51  unsigned fCi : 1; // terminal node CI
52  unsigned fCo : 1; // terminal node CO
53  unsigned fMark0 : 1; // first user-controlled mark
54  unsigned fMark1 : 1; // second user-controlled mark
55  unsigned nFanins : 28; // the number of fanins
56  unsigned nFanouts; // the number of fanouts
57  int hHandle; // the handle of the node
58  union {
59  unsigned TravId; // user-specified value
60  unsigned iFanin;
61  };
62  union {
63  unsigned Value; // user-specified value
64  unsigned iFanout;
65  };
66  int Fanios[0]; // the array of fanins/fanouts
67 };
68 
69 typedef struct Emb_Man_t_ Emb_Man_t;
70 struct Emb_Man_t_
71 {
72  Gia_Man_t * pGia; // the original AIG manager
73  Vec_Int_t * vCis; // the vector of CIs (PIs + LOs)
74  Vec_Int_t * vCos; // the vector of COs (POs + LIs)
75  int nObjs; // the number of objects
76  int nRegs; // the number of registers
77  int nTravIds; // traversal ID of the network
78  int * pObjData; // the array containing data for objects
79  int nObjData; // the size of array to store the logic network
80  int fVerbose; // verbose output flag
81  Emb_Dat_t * pVecs; // array of vectors of size nObjs * nDims
82  int nReached; // the number of nodes reachable from the pivot
83  int nDistMax; // the maximum distance from the node
84  float ** pMatr; // covariance matrix nDims * nDims
85  float ** pEigen; // the first several eigen values of the matrix
86  float * pSols; // solutions to the problem nObjs * nSols;
87  unsigned short*pPlacement; // (x,y) coordinates for each cell
88 };
89 
90 static inline int Emb_ManRegNum( Emb_Man_t * p ) { return p->nRegs; }
91 static inline int Emb_ManCiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis); }
92 static inline int Emb_ManCoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos); }
93 static inline int Emb_ManPiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; }
94 static inline int Emb_ManPoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; }
95 static inline int Emb_ManObjNum( Emb_Man_t * p ) { return p->nObjs; }
96 static inline int Emb_ManNodeNum( Emb_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); }
97 
98 static inline Emb_Obj_t * Emb_ManObj( Emb_Man_t * p, unsigned hHandle ) { return (Emb_Obj_t *)(p->pObjData + hHandle); }
99 static inline Emb_Obj_t * Emb_ManCi( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCis,i) ); }
100 static inline Emb_Obj_t * Emb_ManCo( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCos,i) ); }
101 
102 static inline int Emb_ObjIsTerm( Emb_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; }
103 static inline int Emb_ObjIsCi( Emb_Obj_t * pObj ) { return pObj->fCi; }
104 static inline int Emb_ObjIsCo( Emb_Obj_t * pObj ) { return pObj->fCo; }
105 //static inline int Emb_ObjIsPi( Emb_Obj_t * pObj ) { return pObj->fCi && pObj->nFanins == 0; }
106 //static inline int Emb_ObjIsPo( Emb_Obj_t * pObj ) { return pObj->fCo && pObj->nFanouts == 0; }
107 static inline int Emb_ObjIsNode( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins > 0; }
108 //static inline int Emb_ObjIsConst0( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins == 0; }
109 
110 static inline int Emb_ObjSize( Emb_Obj_t * pObj ) { return sizeof(Emb_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
111 static inline int Emb_ObjFaninNum( Emb_Obj_t * pObj ) { return pObj->nFanins; }
112 static inline int Emb_ObjFanoutNum( Emb_Obj_t * pObj ) { return pObj->nFanouts; }
113 static inline Emb_Obj_t * Emb_ObjFanin( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); }
114 static inline Emb_Obj_t * Emb_ObjFanout( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); }
115 
116 static inline void Emb_ManResetTravId( Emb_Man_t * p ) { extern void Emb_ManCleanTravId( Emb_Man_t * p ); Emb_ManCleanTravId( p ); p->nTravIds = 1; }
117 static inline void Emb_ManIncrementTravId( Emb_Man_t * p ) { p->nTravIds++; }
118 static inline void Emb_ObjSetTravId( Emb_Obj_t * pObj, int TravId ) { pObj->TravId = TravId; }
119 static inline void Emb_ObjSetTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds; }
120 static inline void Emb_ObjSetTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds - 1; }
121 static inline int Emb_ObjIsTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds); }
122 static inline int Emb_ObjIsTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds - 1); }
123 
124 static inline Emb_Dat_t * Emb_ManVec( Emb_Man_t * p, int v ) { return p->pVecs + v * p->nObjs; }
125 static inline float * Emb_ManSol( Emb_Man_t * p, int v ) { return p->pSols + v * p->nObjs; }
126 
127 #define Emb_ManForEachObj( p, pObj, i ) \
128  for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) )
129 #define Emb_ManForEachNode( p, pObj, i ) \
130  for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) ) if ( Emb_ObjIsTerm(pObj) ) {} else
131 #define Emb_ManForEachObjVec( vVec, p, pObj, i ) \
132  for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Emb_ManObj(p, Vec_IntEntry(vVec,i))); i++ )
133 #define Emb_ObjForEachFanin( pObj, pNext, i ) \
134  for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Emb_ObjFanin(pObj,i)); i++ )
135 #define Emb_ObjForEachFanout( pObj, pNext, i ) \
136  for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Emb_ObjFanout(pObj,i)); i++ )
137 
138 ////////////////////////////////////////////////////////////////////////
139 /// FUNCTION DEFINITIONS ///
140 ////////////////////////////////////////////////////////////////////////
141 
142 /**Function*************************************************************
143 
144  Synopsis [Creates fanin/fanout pair.]
145 
146  Description []
147 
148  SideEffects []
149 
150  SeeAlso []
151 
152 ***********************************************************************/
153 void Emb_ObjAddFanin( Emb_Obj_t * pObj, Emb_Obj_t * pFanin )
154 {
155  assert( pObj->iFanin < pObj->nFanins );
156  assert( pFanin->iFanout < pFanin->nFanouts );
157  pFanin->Fanios[pFanin->nFanins + pFanin->iFanout++] =
158  pObj->Fanios[pObj->iFanin++] = pObj->hHandle - pFanin->hHandle;
159 }
160 
161 /**Function*************************************************************
162 
163  Synopsis [Creates logic network isomorphic to the given AIG.]
164 
165  Description []
166 
167  SideEffects []
168 
169  SeeAlso []
170 
171 ***********************************************************************/
172 Emb_Man_t * Emb_ManStartSimple( Gia_Man_t * pGia )
173 {
174  Emb_Man_t * p;
175  Emb_Obj_t * pObjLog, * pFanLog;
176  Gia_Obj_t * pObj, * pObjRi, * pObjRo;
177  int i, nNodes, hHandle = 0;
178  // prepare the AIG
179  Gia_ManCreateRefs( pGia );
180  // create logic network
181  p = ABC_CALLOC( Emb_Man_t, 1 );
182  p->pGia = pGia;
183  p->nRegs = Gia_ManRegNum(pGia);
184  p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
185  p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
186  p->nObjData = (sizeof(Emb_Obj_t) / 4) * Gia_ManObjNum(pGia) + 2 * (2 * Gia_ManAndNum(pGia) + Gia_ManCoNum(pGia) + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
187  p->pObjData = ABC_CALLOC( int, p->nObjData );
188  // create constant node
189  Gia_ManConst0(pGia)->Value = hHandle;
190  pObjLog = Emb_ManObj( p, hHandle );
191  pObjLog->hHandle = hHandle;
192  pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
193  pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
194  // count objects
195  hHandle += Emb_ObjSize( pObjLog );
196  nNodes = 1;
197  p->nObjs++;
198  // create the PIs
199  Gia_ManForEachCi( pGia, pObj, i )
200  {
201  // create PI object
202  pObj->Value = hHandle;
203  Vec_IntPush( p->vCis, hHandle );
204  pObjLog = Emb_ManObj( p, hHandle );
205  pObjLog->hHandle = hHandle;
206  pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
207  pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
208  pObjLog->fCi = 1;
209  // count objects
210  hHandle += Emb_ObjSize( pObjLog );
211  p->nObjs++;
212  }
213  // create internal nodes
214  Gia_ManForEachAnd( pGia, pObj, i )
215  {
216  assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
217  // create node object
218  pObj->Value = hHandle;
219  pObjLog = Emb_ManObj( p, hHandle );
220  pObjLog->hHandle = hHandle;
221  pObjLog->nFanins = 2;
222  pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
223  // add fanins
224  pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
225  Emb_ObjAddFanin( pObjLog, pFanLog );
226  pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin1(pObj)) );
227  Emb_ObjAddFanin( pObjLog, pFanLog );
228  // count objects
229  hHandle += Emb_ObjSize( pObjLog );
230  nNodes++;
231  p->nObjs++;
232  }
233  // create the POs
234  Gia_ManForEachCo( pGia, pObj, i )
235  {
236  // create PO object
237  pObj->Value = hHandle;
238  Vec_IntPush( p->vCos, hHandle );
239  pObjLog = Emb_ManObj( p, hHandle );
240  pObjLog->hHandle = hHandle;
241  pObjLog->nFanins = 1;
242  pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
243  pObjLog->fCo = 1;
244  // add fanins
245  pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
246  Emb_ObjAddFanin( pObjLog, pFanLog );
247  // count objects
248  hHandle += Emb_ObjSize( pObjLog );
249  p->nObjs++;
250  }
251  // connect registers
252  Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
253  Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
254  assert( nNodes == Emb_ManNodeNum(p) );
255  assert( hHandle == p->nObjData );
256  assert( p->nObjs == Gia_ManObjNum(pGia) );
257  if ( hHandle != p->nObjData )
258  printf( "Emb_ManStartSimple(): Fatal error in internal representation.\n" );
259  // make sure the fanin/fanout counters are correct
260  Gia_ManForEachObj( pGia, pObj, i )
261  {
262  if ( !~Gia_ObjValue(pObj) )
263  continue;
264  pObjLog = Emb_ManObj( p, Gia_ObjValue(pObj) );
265  assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
266  assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
267  pObjLog->iFanin = pObjLog->iFanout = 0;
268  }
269  ABC_FREE( pGia->pRefs );
270  return p;
271 }
272 
273 /**Function*************************************************************
274 
275  Synopsis [Collect the fanin IDs.]
276 
277  Description []
278 
279  SideEffects []
280 
281  SeeAlso []
282 
283 ***********************************************************************/
284 void Emb_ManCollectSuper_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
285 {
286  if ( pObj->fMark1 )
287  return;
288  pObj->fMark1 = 1;
289  Vec_IntPush( vVisit, Gia_ObjId(p, pObj) );
290  if ( pObj->fMark0 )
291  {
292  Vec_IntPush( vSuper, Gia_ObjId(p, pObj) );
293  return;
294  }
295  assert( Gia_ObjIsAnd(pObj) );
296  Emb_ManCollectSuper_rec( p, Gia_ObjFanin0(pObj), vSuper, vVisit );
297  Emb_ManCollectSuper_rec( p, Gia_ObjFanin1(pObj), vSuper, vVisit );
298 
299 }
300 
301 /**Function*************************************************************
302 
303  Synopsis [Collect the fanin IDs.]
304 
305  Description []
306 
307  SideEffects []
308 
309  SeeAlso []
310 
311 ***********************************************************************/
312 void Emb_ManCollectSuper( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
313 {
314  int Entry, i;
315  Vec_IntClear( vSuper );
316  Vec_IntClear( vVisit );
317  assert( pObj->fMark0 == 1 );
318  pObj->fMark0 = 0;
319  Emb_ManCollectSuper_rec( p, pObj, vSuper, vVisit );
320  pObj->fMark0 = 1;
321  Vec_IntForEachEntry( vVisit, Entry, i )
322  Gia_ManObj(p, Entry)->fMark1 = 0;
323 }
324 
325 /**Function*************************************************************
326 
327  Synopsis [Assigns references while removing the MUX/XOR ones.]
328 
329  Description []
330 
331  SideEffects []
332 
333  SeeAlso []
334 
335 ***********************************************************************/
336 void Emb_ManCreateRefsSpecial( Gia_Man_t * p )
337 {
338  Gia_Obj_t * pObj, * pFan0, * pFan1;
339  Gia_Obj_t * pObjC, * pObjD0, * pObjD1;
340  int i;
341  assert( p->pRefs == NULL );
342  Gia_ManCleanMark0( p );
343  Gia_ManCreateRefs( p );
344  Gia_ManForEachAnd( p, pObj, i )
345  {
346  assert( pObj->fMark0 == 0 );
347  pFan0 = Gia_ObjFanin0(pObj);
348  pFan1 = Gia_ObjFanin1(pObj);
349  // skip nodes whose fanins are PIs or are already marked
350  if ( Gia_ObjIsCi(pFan0) || pFan0->fMark0 ||
351  Gia_ObjIsCi(pFan1) || pFan1->fMark0 )
352  continue;
353  // skip nodes that are not MUX type
354  if ( !Gia_ObjIsMuxType(pObj) )
355  continue;
356  // the node is MUX type, mark it and its fanins
357  pObj->fMark0 = 1;
358  pFan0->fMark0 = 1;
359  pFan1->fMark0 = 1;
360  // deref the control
361  pObjC = Gia_ObjRecognizeMux( pObj, &pObjD1, &pObjD0 );
362  Gia_ObjRefDec( p, Gia_Regular(pObjC) );
363  if ( Gia_Regular(pObjD0) == Gia_Regular(pObjD1) )
364  Gia_ObjRefDec( p, Gia_Regular(pObjD0) );
365  }
366  Gia_ManForEachAnd( p, pObj, i )
367  assert( Gia_ObjRefNum(p, pObj) > 0 );
368  Gia_ManCleanMark0( p );
369 }
370 
371 /**Function*************************************************************
372 
373  Synopsis [Assigns references while removing the MUX/XOR ones.]
374 
375  Description []
376 
377  SideEffects []
378 
379  SeeAlso []
380 
381 ***********************************************************************/
382 void Emb_ManTransformRefs( Gia_Man_t * p, int * pnObjs, int * pnFanios )
383 {
384  Vec_Int_t * vSuper, * vVisit;
385  Gia_Obj_t * pObj, * pFanin;
386  int i, k, Counter;
387  assert( p->pRefs != NULL );
388 
389  // mark nodes to be used in the logic network
390  Gia_ManCleanMark0( p );
391  Gia_ManConst0(p)->fMark0 = 1;
392  // mark the inputs
393  Gia_ManForEachCi( p, pObj, i )
394  pObj->fMark0 = 1;
395  // mark those nodes that have ref count more than 1
396  Gia_ManForEachAnd( p, pObj, i )
397  pObj->fMark0 = (Gia_ObjRefNum(p, pObj) > 1);
398  // mark the output drivers
399  Gia_ManForEachCoDriver( p, pObj, i )
400  pObj->fMark0 = 1;
401 
402  // count the number of nodes
403  Counter = 0;
404  Gia_ManForEachObj( p, pObj, i )
405  Counter += pObj->fMark0;
406  *pnObjs = Counter + Gia_ManCoNum(p);
407 
408  // reset the references
409  ABC_FREE( p->pRefs );
410  p->pRefs = ABC_CALLOC( int, Gia_ManObjNum(p) );
411  // reference from internal nodes
412  Counter = 0;
413  vSuper = Vec_IntAlloc( 100 );
414  vVisit = Vec_IntAlloc( 100 );
415  Gia_ManCleanMark1( p );
416  Gia_ManForEachAnd( p, pObj, i )
417  {
418  if ( pObj->fMark0 == 0 )
419  continue;
420  Emb_ManCollectSuper( p, pObj, vSuper, vVisit );
421  Gia_ManForEachObjVec( vSuper, p, pFanin, k )
422  {
423  assert( pFanin->fMark0 );
424  Gia_ObjRefInc( p, pFanin );
425  }
426  Counter += Vec_IntSize( vSuper );
427  }
428  Gia_ManCheckMark1( p );
429  Vec_IntFree( vSuper );
430  Vec_IntFree( vVisit );
431  // reference from outputs
432  Gia_ManForEachCoDriver( p, pObj, i )
433  {
434  assert( pObj->fMark0 );
435  Gia_ObjRefInc( p, pObj );
436  }
437  *pnFanios = Counter + Gia_ManCoNum(p);
438 }
439 
440 /**Function*************************************************************
441 
442  Synopsis [Cleans the value.]
443 
444  Description []
445 
446  SideEffects []
447 
448  SeeAlso []
449 
450 ***********************************************************************/
451 void Emb_ManCleanTravId( Emb_Man_t * p )
452 {
453  Emb_Obj_t * pObj;
454  int i;
455  Emb_ManForEachObj( p, pObj, i )
456  pObj->TravId = 0;
457 }
458 
459 /**Function*************************************************************
460 
461  Synopsis [Cleans the value.]
462 
463  Description []
464 
465  SideEffects []
466 
467  SeeAlso []
468 
469 ***********************************************************************/
470 void Emb_ManSetValue( Emb_Man_t * p )
471 {
472  Emb_Obj_t * pObj;
473  int i, Counter = 0;
474  Emb_ManForEachObj( p, pObj, i )
475  {
476  pObj->Value = Counter++;
477 // if ( pObj->fCi && pObj->nFanins == 0 )
478 // printf( "CI: Handle = %8d. Value = %6d. Fanins = %d.\n", pObj->hHandle, pObj->Value, pObj->nFanins );
479  }
480 }
481 
482 /**Function*************************************************************
483 
484  Synopsis [Creates logic network isomorphic to the given AIG.]
485 
486  Description []
487 
488  SideEffects []
489 
490  SeeAlso []
491 
492 ***********************************************************************/
493 Emb_Man_t * Emb_ManStart( Gia_Man_t * pGia )
494 {
495  Emb_Man_t * p;
496  Emb_Obj_t * pObjLog, * pFanLog;
497  Gia_Obj_t * pObj, * pObjRi, * pObjRo, * pFanin;
498  Vec_Int_t * vSuper, * vVisit;
499  int nObjs, nFanios, nNodes = 0;
500  int i, k, hHandle = 0;
501  // prepare the AIG
502 // Gia_ManCreateRefs( pGia );
503  Emb_ManCreateRefsSpecial( pGia );
504  Emb_ManTransformRefs( pGia, &nObjs, &nFanios );
505  Gia_ManFillValue( pGia );
506  // create logic network
507  p = ABC_CALLOC( Emb_Man_t, 1 );
508  p->pGia = pGia;
509  p->nRegs = Gia_ManRegNum(pGia);
510  p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
511  p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
512  p->nObjData = (sizeof(Emb_Obj_t) / 4) * nObjs + 2 * (nFanios + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
513  p->pObjData = ABC_CALLOC( int, p->nObjData );
514  // create constant node
515  Gia_ManConst0(pGia)->Value = hHandle;
516  pObjLog = Emb_ManObj( p, hHandle );
517  pObjLog->hHandle = hHandle;
518  pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
519  pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
520  // count objects
521  hHandle += Emb_ObjSize( pObjLog );
522  nNodes++;
523  p->nObjs++;
524  // create the PIs
525  Gia_ManForEachCi( pGia, pObj, i )
526  {
527  // create PI object
528  pObj->Value = hHandle;
529  Vec_IntPush( p->vCis, hHandle );
530  pObjLog = Emb_ManObj( p, hHandle );
531  pObjLog->hHandle = hHandle;
532  pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
533  pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
534  pObjLog->fCi = 1;
535  // count objects
536  hHandle += Emb_ObjSize( pObjLog );
537  p->nObjs++;
538  }
539  // create internal nodes
540  vSuper = Vec_IntAlloc( 100 );
541  vVisit = Vec_IntAlloc( 100 );
542  Gia_ManForEachAnd( pGia, pObj, i )
543  {
544  if ( pObj->fMark0 == 0 )
545  {
546  assert( Gia_ObjRefNum( pGia, pObj ) == 0 );
547  continue;
548  }
549  assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
550  Emb_ManCollectSuper( pGia, pObj, vSuper, vVisit );
551  // create node object
552  pObj->Value = hHandle;
553  pObjLog = Emb_ManObj( p, hHandle );
554  pObjLog->hHandle = hHandle;
555  pObjLog->nFanins = Vec_IntSize( vSuper );
556  pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
557  // add fanins
558  Gia_ManForEachObjVec( vSuper, pGia, pFanin, k )
559  {
560  pFanLog = Emb_ManObj( p, Gia_ObjValue(pFanin) );
561  Emb_ObjAddFanin( pObjLog, pFanLog );
562  }
563  // count objects
564  hHandle += Emb_ObjSize( pObjLog );
565  nNodes++;
566  p->nObjs++;
567  }
568  Vec_IntFree( vSuper );
569  Vec_IntFree( vVisit );
570  // create the POs
571  Gia_ManForEachCo( pGia, pObj, i )
572  {
573  // create PO object
574  pObj->Value = hHandle;
575  Vec_IntPush( p->vCos, hHandle );
576  pObjLog = Emb_ManObj( p, hHandle );
577  pObjLog->hHandle = hHandle;
578  pObjLog->nFanins = 1;
579  pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
580  pObjLog->fCo = 1;
581  // add fanins
582  pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
583  Emb_ObjAddFanin( pObjLog, pFanLog );
584  // count objects
585  hHandle += Emb_ObjSize( pObjLog );
586  p->nObjs++;
587  }
588  // connect registers
589  Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
590  Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
591  Gia_ManCleanMark0( pGia );
592  assert( nNodes == Emb_ManNodeNum(p) );
593  assert( nObjs == p->nObjs );
594  assert( hHandle == p->nObjData );
595  if ( hHandle != p->nObjData )
596  printf( "Emb_ManStart(): Fatal error in internal representation.\n" );
597  // make sure the fanin/fanout counters are correct
598  Gia_ManForEachObj( pGia, pObj, i )
599  {
600  if ( !~Gia_ObjValue(pObj) )
601  continue;
602  pObjLog = Emb_ManObj( p, Gia_ObjValue(pObj) );
603  assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
604  assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
605  pObjLog->iFanin = pObjLog->iFanout = 0;
606  }
607  ABC_FREE( pGia->pRefs );
608  return p;
609 }
610 
611 /**Function*************************************************************
612 
613  Synopsis [Creates logic network isomorphic to the given AIG.]
614 
615  Description []
616 
617  SideEffects []
618 
619  SeeAlso []
620 
621 ***********************************************************************/
622 void Emb_ManPrintStats( Emb_Man_t * p )
623 {
624 // if ( p->pName )
625 // printf( "%8s : ", p->pName );
626  printf( "i/o =%7d/%7d ", Emb_ManPiNum(p), Emb_ManPoNum(p) );
627  if ( Emb_ManRegNum(p) )
628  printf( "ff =%7d ", Emb_ManRegNum(p) );
629  printf( "node =%8d ", Emb_ManNodeNum(p) );
630  printf( "obj =%8d ", Emb_ManObjNum(p) );
631 // printf( "lev =%5d ", Emb_ManLevelNum(p) );
632 // printf( "cut =%5d ", Emb_ManCrossCut(p) );
633  printf( "mem =%5.2f MB", 4.0*p->nObjData/(1<<20) );
634 // printf( "obj =%5d ", Emb_ManObjNum(p) );
635  printf( "\n" );
636 
637 // Emb_ManSatExperiment( p );
638 }
639 
640 /**Function*************************************************************
641 
642  Synopsis [Creates logic network isomorphic to the given AIG.]
643 
644  Description []
645 
646  SideEffects []
647 
648  SeeAlso []
649 
650 ***********************************************************************/
651 void Emb_ManStop( Emb_Man_t * p )
652 {
653  Vec_IntFree( p->vCis );
654  Vec_IntFree( p->vCos );
655  ABC_FREE( p->pPlacement );
656  ABC_FREE( p->pVecs );
657  ABC_FREE( p->pSols );
658  ABC_FREE( p->pMatr );
659  ABC_FREE( p->pEigen );
660  ABC_FREE( p->pObjData );
661  ABC_FREE( p );
662 }
663 
664 /**Function*************************************************************
665 
666  Synopsis [Prints the distribution of fanins/fanouts in the network.]
667 
668  Description []
669 
670  SideEffects []
671 
672  SeeAlso []
673 
674 ***********************************************************************/
675 void Emb_ManPrintFanio( Emb_Man_t * p )
676 {
677  char Buffer[100];
678  Emb_Obj_t * pNode;
679  Vec_Int_t * vFanins, * vFanouts;
680  int nFanins, nFanouts, nFaninsMax, nFanoutsMax, nFaninsAll, nFanoutsAll;
681  int i, k, nSizeMax;
682 
683  // determine the largest fanin and fanout
684  nFaninsMax = nFanoutsMax = 0;
685  nFaninsAll = nFanoutsAll = 0;
686  Emb_ManForEachNode( p, pNode, i )
687  {
688  if ( i == 0 ) continue; // skip const 0 obj
689  nFanins = Emb_ObjFaninNum(pNode);
690  nFanouts = Emb_ObjFanoutNum(pNode);
691  nFaninsAll += nFanins;
692  nFanoutsAll += nFanouts;
693  nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins );
694  nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts );
695  }
696 
697  // allocate storage for fanin/fanout numbers
698  nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
699  vFanins = Vec_IntStart( nSizeMax );
700  vFanouts = Vec_IntStart( nSizeMax );
701 
702  // count the number of fanins and fanouts
703  Emb_ManForEachNode( p, pNode, i )
704  {
705  if ( i == 0 ) continue; // skip const 0 obj
706  nFanins = Emb_ObjFaninNum(pNode);
707  nFanouts = Emb_ObjFanoutNum(pNode);
708 
709  if ( nFanins < 10 )
710  Vec_IntAddToEntry( vFanins, nFanins, 1 );
711  else if ( nFanins < 100 )
712  Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
713  else if ( nFanins < 1000 )
714  Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
715  else if ( nFanins < 10000 )
716  Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
717  else if ( nFanins < 100000 )
718  Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
719  else if ( nFanins < 1000000 )
720  Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
721  else if ( nFanins < 10000000 )
722  Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );
723 
724  if ( nFanouts < 10 )
725  Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
726  else if ( nFanouts < 100 )
727  Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
728  else if ( nFanouts < 1000 )
729  Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
730  else if ( nFanouts < 10000 )
731  Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
732  else if ( nFanouts < 100000 )
733  Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
734  else if ( nFanouts < 1000000 )
735  Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
736  else if ( nFanouts < 10000000 )
737  Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
738  }
739 
740  printf( "The distribution of fanins and fanouts in the network:\n" );
741  printf( " Number Nodes with fanin Nodes with fanout\n" );
742  for ( k = 0; k < nSizeMax; k++ )
743  {
744  if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 )
745  continue;
746  if ( k < 10 )
747  printf( "%15d : ", k );
748  else
749  {
750  sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 );
751  printf( "%15s : ", Buffer );
752  }
753  if ( vFanins->pArray[k] == 0 )
754  printf( " " );
755  else
756  printf( "%12d ", vFanins->pArray[k] );
757  printf( " " );
758  if ( vFanouts->pArray[k] == 0 )
759  printf( " " );
760  else
761  printf( "%12d ", vFanouts->pArray[k] );
762  printf( "\n" );
763  }
764  Vec_IntFree( vFanins );
765  Vec_IntFree( vFanouts );
766 
767  printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f.\n",
768  nFaninsMax, 1.0*nFaninsAll/Emb_ManNodeNum(p),
769  nFanoutsMax, 1.0*nFanoutsAll/Emb_ManNodeNum(p) );
770 }
771 
772 /**Function*************************************************************
773 
774  Synopsis [Computes the distance from the given object]
775 
776  Description []
777 
778  SideEffects []
779 
780  SeeAlso []
781 
782 ***********************************************************************/
783 int Emb_ManComputeDistance_old( Emb_Man_t * p, Emb_Obj_t * pPivot )
784 {
785  Vec_Int_t * vThis, * vNext, * vTemp;
786  Emb_Obj_t * pThis, * pNext;
787  int i, k, d, nVisited = 0;
788 // assert( Emb_ObjIsTerm(pPivot) );
789  vThis = Vec_IntAlloc( 1000 );
790  vNext = Vec_IntAlloc( 1000 );
791  Emb_ManIncrementTravId( p );
792  Emb_ObjSetTravIdCurrent( p, pPivot );
793  Vec_IntPush( vThis, pPivot->hHandle );
794  for ( d = 0; Vec_IntSize(vThis) > 0; d++ )
795  {
796  nVisited += Vec_IntSize(vThis);
797  Vec_IntClear( vNext );
798  Emb_ManForEachObjVec( vThis, p, pThis, i )
799  {
800  Emb_ObjForEachFanin( pThis, pNext, k )
801  {
802  if ( Emb_ObjIsTravIdCurrent(p, pNext) )
803  continue;
804  Emb_ObjSetTravIdCurrent(p, pNext);
805  Vec_IntPush( vNext, pNext->hHandle );
806  nVisited += !Emb_ObjIsTerm(pNext);
807  }
808  Emb_ObjForEachFanout( pThis, pNext, k )
809  {
810  if ( Emb_ObjIsTravIdCurrent(p, pNext) )
811  continue;
812  Emb_ObjSetTravIdCurrent(p, pNext);
813  Vec_IntPush( vNext, pNext->hHandle );
814  nVisited += !Emb_ObjIsTerm(pNext);
815  }
816  }
817  vTemp = vThis; vThis = vNext; vNext = vTemp;
818  }
819  Vec_IntFree( vThis );
820  Vec_IntFree( vNext );
821  // check if there are several strongly connected components
822 // if ( nVisited < Emb_ManNodeNum(p) )
823 // printf( "Visited less nodes (%d) than present (%d).\n", nVisited, Emb_ManNodeNum(p) );
824  return d;
825 }
826 
827 /**Function*************************************************************
828 
829  Synopsis [Traverses from the given node.]
830 
831  Description []
832 
833  SideEffects []
834 
835  SeeAlso []
836 
837 ***********************************************************************/
838 void Gia_ManTestDistanceInternal( Emb_Man_t * p )
839 {
840  int nAttempts = 20;
841  int i, iNode, Dist;
842  abctime clk;
843  Emb_Obj_t * pPivot, * pNext;
844  Gia_ManRandom( 1 );
845  Emb_ManResetTravId( p );
846  // compute distances from several randomly selected PIs
847  clk = Abc_Clock();
848  printf( "From inputs: " );
849  for ( i = 0; i < nAttempts; i++ )
850  {
851  iNode = Gia_ManRandom( 0 ) % Emb_ManCiNum(p);
852  pPivot = Emb_ManCi( p, iNode );
853  if ( Emb_ObjFanoutNum(pPivot) == 0 )
854  { i--; continue; }
855  pNext = Emb_ObjFanout( pPivot, 0 );
856  if ( !Emb_ObjIsNode(pNext) )
857  { i--; continue; }
858  Dist = Emb_ManComputeDistance_old( p, pPivot );
859  printf( "%d ", Dist );
860  }
861  ABC_PRT( "Time", Abc_Clock() - clk );
862  // compute distances from several randomly selected POs
863  clk = Abc_Clock();
864  printf( "From outputs: " );
865  for ( i = 0; i < nAttempts; i++ )
866  {
867  iNode = Gia_ManRandom( 0 ) % Emb_ManCoNum(p);
868  pPivot = Emb_ManCo( p, iNode );
869  pNext = Emb_ObjFanin( pPivot, 0 );
870  if ( !Emb_ObjIsNode(pNext) )
871  { i--; continue; }
872  Dist = Emb_ManComputeDistance_old( p, pPivot );
873  printf( "%d ", Dist );
874  }
875  ABC_PRT( "Time", Abc_Clock() - clk );
876  // compute distances from several randomly selected nodes
877  clk = Abc_Clock();
878  printf( "From nodes: " );
879  for ( i = 0; i < nAttempts; i++ )
880  {
881  iNode = Gia_ManRandom( 0 ) % Gia_ManObjNum(p->pGia);
882  if ( !~Gia_ManObj(p->pGia, iNode)->Value )
883  { i--; continue; }
884  pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
885  if ( !Emb_ObjIsNode(pPivot) )
886  { i--; continue; }
887  Dist = Emb_ManComputeDistance_old( p, pPivot );
888  printf( "%d ", Dist );
889  }
890  ABC_PRT( "Time", Abc_Clock() - clk );
891 }
892 
893 /**Function*************************************************************
894 
895  Synopsis [Returns sorted array of node handles with largest fanout.]
896 
897  Description []
898 
899  SideEffects []
900 
901  SeeAlso []
902 
903 ***********************************************************************/
904 void Gia_ManTestDistance( Gia_Man_t * pGia )
905 {
906  Emb_Man_t * p;
907  abctime clk = Abc_Clock();
908  p = Emb_ManStart( pGia );
909 // Emb_ManPrintFanio( p );
910  Emb_ManPrintStats( p );
911 ABC_PRT( "Time", Abc_Clock() - clk );
912  Gia_ManTestDistanceInternal( p );
913  Emb_ManStop( p );
914 }
915 
916 
917 
918 
919 /**Function*************************************************************
920 
921  Synopsis [Perform BFS from the set of nodes.]
922 
923  Description [Returns one of the most distant objects.]
924 
925  SideEffects []
926 
927  SeeAlso []
928 
929 ***********************************************************************/
930 Emb_Obj_t * Emb_ManPerformBfs( Emb_Man_t * p, Vec_Int_t * vThis, Vec_Int_t * vNext, Emb_Dat_t * pDist )
931 {
932  Vec_Int_t * vTemp;
933  Emb_Obj_t * pThis, * pNext, * pResult;
934  int i, k;
935  assert( Vec_IntSize(vThis) > 0 );
936  for ( p->nDistMax = 0; Vec_IntSize(vThis) > 0; p->nDistMax++ )
937  {
938  p->nReached += Vec_IntSize(vThis);
939  Vec_IntClear( vNext );
940  Emb_ManForEachObjVec( vThis, p, pThis, i )
941  {
942  if ( pDist ) pDist[pThis->Value] = p->nDistMax;
943  Emb_ObjForEachFanin( pThis, pNext, k )
944  {
945  if ( Emb_ObjIsTravIdCurrent(p, pNext) )
946  continue;
947  Emb_ObjSetTravIdCurrent(p, pNext);
948  Vec_IntPush( vNext, pNext->hHandle );
949  }
950  Emb_ObjForEachFanout( pThis, pNext, k )
951  {
952  if ( Emb_ObjIsTravIdCurrent(p, pNext) )
953  continue;
954  Emb_ObjSetTravIdCurrent(p, pNext);
955  Vec_IntPush( vNext, pNext->hHandle );
956  }
957  }
958  vTemp = vThis; vThis = vNext; vNext = vTemp;
959  }
960  assert( Vec_IntSize(vNext) > 0 );
961  pResult = Emb_ManObj( p, Vec_IntEntry(vNext, 0) );
962  assert( pDist == NULL || pDist[pResult->Value] == p->nDistMax - 1 );
963  return pResult;
964 }
965 
966 /**Function*************************************************************
967 
968  Synopsis [Computes the distances from the given set of objects.]
969 
970  Description [Returns one of the most distant objects.]
971 
972  SideEffects []
973 
974  SeeAlso []
975 
976 ***********************************************************************/
977 Vec_Int_t * Emb_ManConnectedComponents( Emb_Man_t * p )
978 {
979  Gia_Obj_t * pObj;
980  Vec_Int_t * vThis, * vNext, * vResult;
981  Emb_Obj_t * pThis;
982  int i;
983  vResult = Vec_IntAlloc( 1000 );
984  vThis = Vec_IntAlloc( 1000 );
985  vNext = Vec_IntAlloc( 1000 );
986  p->nReached = 0;
987  Emb_ManIncrementTravId( p );
988  Gia_ManForEachCo( p->pGia, pObj, i )
989  {
990  pThis = Emb_ManObj( p, Gia_ObjValue(pObj) );
991  if ( Emb_ObjIsTravIdCurrent(p, pThis) )
992  continue;
993  Emb_ObjSetTravIdCurrent( p, pThis );
994  Vec_IntPush( vResult, pThis->hHandle );
995  // perform BFS from this node
996  Vec_IntClear( vThis );
997  Vec_IntPush( vThis, pThis->hHandle );
998  Emb_ManPerformBfs( p, vThis, vNext, NULL );
999  }
1000  Vec_IntFree( vThis );
1001  Vec_IntFree( vNext );
1002  return vResult;
1003 }
1004 
1005 /**Function*************************************************************
1006 
1007  Synopsis [Computes the distances from the given set of objects.]
1008 
1009  Description [Returns one of the most distant objects.]
1010 
1011  SideEffects []
1012 
1013  SeeAlso []
1014 
1015 ***********************************************************************/
1016 Emb_Obj_t * Emb_ManFindDistances( Emb_Man_t * p, Vec_Int_t * vStart, Emb_Dat_t * pDist )
1017 {
1018  Vec_Int_t * vThis, * vNext;
1019  Emb_Obj_t * pThis, * pResult;
1020  int i;
1021  p->nReached = p->nDistMax = 0;
1022  vThis = Vec_IntAlloc( 1000 );
1023  vNext = Vec_IntAlloc( 1000 );
1024  Emb_ManIncrementTravId( p );
1025  Emb_ManForEachObjVec( vStart, p, pThis, i )
1026  {
1027  Emb_ObjSetTravIdCurrent( p, pThis );
1028  Vec_IntPush( vThis, pThis->hHandle );
1029  }
1030  pResult = Emb_ManPerformBfs( p, vThis, vNext, pDist );
1031  Vec_IntFree( vThis );
1032  Vec_IntFree( vNext );
1033  return pResult;
1034 }
1035 
1036 /**Function*************************************************************
1037 
1038  Synopsis [Traverses from the given node.]
1039 
1040  Description []
1041 
1042  SideEffects []
1043 
1044  SeeAlso []
1045 
1046 ***********************************************************************/
1047 Emb_Obj_t * Emb_ManRandomVertex( Emb_Man_t * p )
1048 {
1049  Emb_Obj_t * pPivot;
1050  do {
1051  int iNode = (911 * Gia_ManRandom(0)) % Gia_ManObjNum(p->pGia);
1052  if ( ~Gia_ManObj(p->pGia, iNode)->Value )
1053  pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
1054  else
1055  pPivot = NULL;
1056  }
1057  while ( pPivot == NULL || !Emb_ObjIsNode(pPivot) );
1058  return pPivot;
1059 }
1060 
1061 /**Function*************************************************************
1062 
1063  Synopsis [Computes the distances from the given set of objects.]
1064 
1065  Description [Returns one of the most distant objects.]
1066 
1067  SideEffects []
1068 
1069  SeeAlso []
1070 
1071 ***********************************************************************/
1072 void Emb_DumpGraphIntoFile( Emb_Man_t * p )
1073 {
1074  FILE * pFile;
1075  Emb_Obj_t * pThis, * pNext;
1076  int i, k;
1077  pFile = fopen( "1.g", "w" );
1078  Emb_ManForEachObj( p, pThis, i )
1079  {
1080  if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
1081  continue;
1082  Emb_ObjForEachFanout( pThis, pNext, k )
1083  {
1084  assert( Emb_ObjIsTravIdCurrent(p, pNext) );
1085  fprintf( pFile, "%d %d\n", pThis->Value, pNext->Value );
1086  }
1087  }
1088  fclose( pFile );
1089 }
1090 
1091 /**Function*************************************************************
1092 
1093  Synopsis [Computes dimentions of the graph.]
1094 
1095  Description []
1096 
1097  SideEffects []
1098 
1099  SeeAlso []
1100 
1101 ***********************************************************************/
1102 void Emb_ManComputeDimensions( Emb_Man_t * p, int nDims )
1103 {
1104  Emb_Obj_t * pRandom, * pPivot;
1105  Vec_Int_t * vStart, * vComps;
1106  int d, nReached;
1107  int i;//, Counter;
1108  // connect unconnected components
1109  vComps = Emb_ManConnectedComponents( p );
1110 // printf( "Components = %d. Considered %d objects (out of %d).\n", Vec_IntSize(vComps), p->nReached, Emb_ManObjNum(p) );
1111  if ( Vec_IntSize(vComps) > 1 )
1112  {
1113  Emb_Obj_t * pFanin, * pObj = Emb_ManObj( p, 0 );
1114  Emb_ManForEachObjVec( vComps, p, pFanin, i )
1115  {
1116  assert( Emb_ObjIsCo(pFanin) );
1117  pFanin->Fanios[pFanin->nFanins + pFanin->nFanouts-1] =
1118  pObj->Fanios[i] = pObj->hHandle - pFanin->hHandle;
1119  }
1120  }
1121  Vec_IntFree( vComps );
1122  // allocate memory for vectors
1123  assert( p->pVecs == NULL );
1124  p->pVecs = ABC_CALLOC( Emb_Dat_t, p->nObjs * nDims );
1125 // for ( i = 0; i < p->nObjs * nDims; i++ )
1126 // p->pVecs[i] = ABC_INFINITY;
1127  vStart = Vec_IntAlloc( nDims );
1128  // get the pivot vertex
1129  pRandom = Emb_ManRandomVertex( p );
1130  Vec_IntPush( vStart, pRandom->hHandle );
1131  // get the most distant vertex from the pivot
1132  pPivot = Emb_ManFindDistances( p, vStart, NULL );
1133 // Emb_DumpGraphIntoFile( p );
1134  nReached = p->nReached;
1135  if ( nReached < Emb_ManObjNum(p) )
1136  {
1137 // printf( "Considering a connected component with %d objects (out of %d).\n", p->nReached, Emb_ManObjNum(p) );
1138  }
1139  // start dimensions with this vertex
1140  Vec_IntClear( vStart );
1141  for ( d = 0; d < nDims; d++ )
1142  {
1143 // printf( "%3d : Adding vertex %7d with distance %3d.\n", d+1, pPivot->Value, p->nDistMax );
1144  Vec_IntPush( vStart, pPivot->hHandle );
1145  if ( d+1 == nReached )
1146  break;
1147  pPivot = Emb_ManFindDistances( p, vStart, Emb_ManVec(p, d) );
1148  assert( nReached == p->nReached );
1149  }
1150  Vec_IntFree( vStart );
1151  // make sure the number of reached objects is correct
1152 // Counter = 0;
1153 // for ( i = 0; i < p->nObjs; i++ )
1154 // if ( p->pVecs[i] < ABC_INFINITY )
1155 // Counter++;
1156 // assert( Counter == nReached );
1157 }
1158 
1159 /**Function*************************************************************
1160 
1161  Synopsis [Allocated square matrix of floats.]
1162 
1163  Description []
1164 
1165  SideEffects []
1166 
1167  SeeAlso []
1168 
1169 ***********************************************************************/
1170 float ** Emb_ManMatrAlloc( int nDims )
1171 {
1172  int i;
1173  float ** pMatr = (float **)ABC_ALLOC( char, sizeof(float *) * nDims + sizeof(float) * nDims * nDims );
1174  pMatr[0] = (float *)(pMatr + nDims);
1175  for ( i = 1; i < nDims; i++ )
1176  pMatr[i] = pMatr[i-1] + nDims;
1177  return pMatr;
1178 }
1179 
1180 /**Function*************************************************************
1181 
1182  Synopsis [Computes covariance matrix.]
1183 
1184  Description []
1185 
1186  SideEffects []
1187 
1188  SeeAlso []
1189 
1190 ***********************************************************************/
1191 void Emb_ManComputeCovariance( Emb_Man_t * p, int nDims )
1192 {
1193  Emb_Dat_t * pOne, * pTwo;
1194  double Ave;
1195  float * pRow;
1196  int d, i, k, v;
1197  // average vectors
1198  for ( d = 0; d < nDims; d++ )
1199  {
1200  // compute average
1201  Ave = 0.0;
1202  pOne = Emb_ManVec( p, d );
1203  for ( v = 0; v < p->nObjs; v++ )
1204  if ( pOne[v] < ABC_INFINITY )
1205  Ave += pOne[v];
1206  Ave /= p->nReached;
1207  // update the vector
1208  for ( v = 0; v < p->nObjs; v++ )
1209  if ( pOne[v] < ABC_INFINITY )
1210  pOne[v] -= Ave;
1211  else
1212  pOne[v] = 0.0;
1213  }
1214  // compute the matrix
1215  assert( p->pMatr == NULL );
1216  assert( p->pEigen == NULL );
1217  p->pMatr = Emb_ManMatrAlloc( nDims );
1218  p->pEigen = Emb_ManMatrAlloc( nDims );
1219  for ( i = 0; i < nDims; i++ )
1220  {
1221  pOne = Emb_ManVec( p, i );
1222  pRow = p->pMatr[i];
1223  for ( k = 0; k < nDims; k++ )
1224  {
1225  pTwo = Emb_ManVec( p, k );
1226  pRow[k] = 0.0;
1227  for ( v = 0; v < p->nObjs; v++ )
1228  pRow[k] += pOne[v]*pTwo[v];
1229  }
1230  }
1231 }
1232 
1233 /**Function*************************************************************
1234 
1235  Synopsis [Returns random vector.]
1236 
1237  Description []
1238 
1239  SideEffects []
1240 
1241  SeeAlso []
1242 
1243 ***********************************************************************/
1244 void Emb_ManVecRandom( float * pVec, int nDims )
1245 {
1246  int i;
1247  for ( i = 0; i < nDims; i++ )
1248  pVec[i] = Gia_ManRandom( 0 );
1249 }
1250 
1251 /**Function*************************************************************
1252 
1253  Synopsis [Returns normalized vector.]
1254 
1255  Description []
1256 
1257  SideEffects []
1258 
1259  SeeAlso []
1260 
1261 ***********************************************************************/
1262 void Emb_ManVecNormal( float * pVec, int nDims )
1263 {
1264  int i;
1265  double Norm = 0.0;
1266  for ( i = 0; i < nDims; i++ )
1267  Norm += pVec[i] * pVec[i];
1268  Norm = pow( Norm, 0.5 );
1269  for ( i = 0; i < nDims; i++ )
1270  pVec[i] /= Norm;
1271 }
1272 
1273 /**Function*************************************************************
1274 
1275  Synopsis [Multiplies vector by vector.]
1276 
1277  Description []
1278 
1279  SideEffects []
1280 
1281  SeeAlso []
1282 
1283 ***********************************************************************/
1284 float Emb_ManVecMultiplyOne( float * pVec0, float * pVec1, int nDims )
1285 {
1286  float Res = 0.0;
1287  int i;
1288  for ( i = 0; i < nDims; i++ )
1289  Res += pVec0[i] * pVec1[i];
1290  return Res;
1291 }
1292 
1293 /**Function*************************************************************
1294 
1295  Synopsis [Copies the vector.]
1296 
1297  Description []
1298 
1299  SideEffects []
1300 
1301  SeeAlso []
1302 
1303 ***********************************************************************/
1304 void Emb_ManVecCopyOne( float * pVecDest, float * pVecSour, int nDims )
1305 {
1306  int i;
1307  for ( i = 0; i < nDims; i++ )
1308  pVecDest[i] = pVecSour[i];
1309 }
1310 
1311 /**Function*************************************************************
1312 
1313  Synopsis [Multiplies matrix by vector.]
1314 
1315  Description []
1316 
1317  SideEffects []
1318 
1319  SeeAlso []
1320 
1321 ***********************************************************************/
1322 void Emb_ManVecMultiply( float ** pMatr, float * pVec, int nDims, float * pRes )
1323 {
1324  int k;
1325  for ( k = 0; k < nDims; k++ )
1326  pRes[k] = Emb_ManVecMultiplyOne( pMatr[k], pVec, nDims );
1327 }
1328 
1329 /**Function*************************************************************
1330 
1331  Synopsis [Multiplies vector by matrix.]
1332 
1333  Description []
1334 
1335  SideEffects []
1336 
1337  SeeAlso []
1338 
1339 ***********************************************************************/
1340 void Emb_ManVecOrthogonolizeOne( float * pEigen, float * pVecI, int nDims, float * pVecRes )
1341 {
1342  int k;
1343  for ( k = 0; k < nDims; k++ )
1344  pVecRes[k] = pVecI[k] - pEigen[k] * Emb_ManVecMultiplyOne( pVecI, pEigen, nDims );
1345 }
1346 
1347 /**Function*************************************************************
1348 
1349  Synopsis [Computes the first nSols eigen-vectors.]
1350 
1351  Description []
1352 
1353  SideEffects []
1354 
1355  SeeAlso []
1356 
1357 ***********************************************************************/
1358 void Emb_ManComputeEigenvectors( Emb_Man_t * p, int nDims, int nSols )
1359 {
1360  float * pVecUiHat, * pVecUi;
1361  int i, j, k;
1362  assert( nSols < nDims );
1363  pVecUiHat = p->pEigen[nSols];
1364  for ( i = 0; i < nSols; i++ )
1365  {
1366  pVecUi = p->pEigen[i];
1367  Emb_ManVecRandom( pVecUiHat, nDims );
1368  Emb_ManVecNormal( pVecUiHat, nDims );
1369  k = 0;
1370  do {
1371  k++;
1372  Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1373  for ( j = 0; j < i; j++ )
1374  {
1375  Emb_ManVecOrthogonolizeOne( p->pEigen[j], pVecUi, nDims, pVecUiHat );
1376  Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1377  }
1378  Emb_ManVecMultiply( p->pMatr, pVecUi, nDims, pVecUiHat );
1379  Emb_ManVecNormal( pVecUiHat, nDims );
1380  } while ( Emb_ManVecMultiplyOne( pVecUiHat, pVecUi, nDims ) < 0.999 && k < 100 );
1381  Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1382 // printf( "Converged after %d iterations.\n", k );
1383  }
1384 }
1385 
1386 /**Function*************************************************************
1387 
1388  Synopsis [Derives solutions from original vectors and eigenvectors.]
1389 
1390  Description []
1391 
1392  SideEffects []
1393 
1394  SeeAlso []
1395 
1396 ***********************************************************************/
1397 void Emb_ManComputeSolutions( Emb_Man_t * p, int nDims, int nSols )
1398 {
1399  Emb_Dat_t * pX;
1400  float * pY;
1401  int i, j, k;
1402  assert( p->pSols == NULL );
1403  p->pSols = ABC_CALLOC( float, p->nObjs * nSols );
1404  for ( i = 0; i < nDims; i++ )
1405  {
1406  pX = Emb_ManVec( p, i );
1407  for ( j = 0; j < nSols; j++ )
1408  {
1409  pY = Emb_ManSol( p, j );
1410  for ( k = 0; k < p->nObjs; k++ )
1411  pY[k] += pX[k] * p->pEigen[j][i];
1412  }
1413  }
1414 }
1415 
1416 /**Function*************************************************************
1417 
1418  Synopsis [Projects into square of size [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE].]
1419 
1420  Description []
1421 
1422  SideEffects []
1423 
1424  SeeAlso []
1425 
1426 ***********************************************************************/
1427 void Emb_ManDerivePlacement( Emb_Man_t * p, int nSols )
1428 {
1429  float * pY0, * pY1, Max0, Max1, Min0, Min1, Str0, Str1;
1430  int * pPerm0, * pPerm1;
1431  int k;
1432  if ( nSols != 2 )
1433  return;
1434  // compute intervals
1435  Min0 = ABC_INFINITY;
1436  Max0 = -ABC_INFINITY;
1437  pY0 = Emb_ManSol( p, 0 );
1438  for ( k = 0; k < p->nObjs; k++ )
1439  {
1440  Min0 = Abc_MinInt( Min0, pY0[k] );
1441  Max0 = Abc_MaxInt( Max0, pY0[k] );
1442  }
1443  Str0 = 1.0*GIA_PLACE_SIZE/(Max0 - Min0);
1444  // update the coordinates
1445  for ( k = 0; k < p->nObjs; k++ )
1446  pY0[k] = (pY0[k] != 0.0) ? ((pY0[k] - Min0) * Str0) : 0.0;
1447 
1448  // compute intervals
1449  Min1 = ABC_INFINITY;
1450  Max1 = -ABC_INFINITY;
1451  pY1 = Emb_ManSol( p, 1 );
1452  for ( k = 0; k < p->nObjs; k++ )
1453  {
1454  Min1 = Abc_MinInt( Min1, pY1[k] );
1455  Max1 = Abc_MaxInt( Max1, pY1[k] );
1456  }
1457  Str1 = 1.0*GIA_PLACE_SIZE/(Max1 - Min1);
1458  // update the coordinates
1459  for ( k = 0; k < p->nObjs; k++ )
1460  pY1[k] = (pY1[k] != 0.0) ? ((pY1[k] - Min1) * Str1) : 0.0;
1461 
1462  // derive the order of these numbers
1463  pPerm0 = Gia_SortFloats( pY0, NULL, p->nObjs );
1464  pPerm1 = Gia_SortFloats( pY1, NULL, p->nObjs );
1465 
1466  // average solutions and project them into square [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE]
1467  p->pPlacement = ABC_ALLOC( unsigned short, 2 * p->nObjs );
1468  for ( k = 0; k < p->nObjs; k++ )
1469  {
1470  p->pPlacement[2*pPerm0[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1471  p->pPlacement[2*pPerm1[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1472  }
1473  ABC_FREE( pPerm0 );
1474  ABC_FREE( pPerm1 );
1475 }
1476 
1477 
1478 /**Function*************************************************************
1479 
1480  Synopsis [Computes wire-length.]
1481 
1482  Description []
1483 
1484  SideEffects []
1485 
1486  SeeAlso []
1487 
1488 ***********************************************************************/
1489 double Emb_ManComputeHPWL( Emb_Man_t * p )
1490 {
1491  double Result = 0.0;
1492  Emb_Obj_t * pThis, * pNext;
1493  int i, k, iMinX, iMaxX, iMinY, iMaxY;
1494  if ( p->pPlacement == NULL )
1495  return 0.0;
1496  Emb_ManForEachObj( p, pThis, i )
1497  {
1498  iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
1499  iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
1500  Emb_ObjForEachFanout( pThis, pNext, k )
1501  {
1502  iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
1503  iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
1504  iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
1505  iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
1506  }
1507  Result += (iMaxX - iMinX) + (iMaxY - iMinY);
1508  }
1509  return Result;
1510 }
1511 
1512 
1513 /**Function*************************************************************
1514 
1515  Synopsis [Performs iterative refinement of the given placement.]
1516 
1517  Description []
1518 
1519  SideEffects []
1520 
1521  SeeAlso []
1522 
1523 ***********************************************************************/
1524 void Emb_ManPlacementRefine( Emb_Man_t * p, int nIters, int fVerbose )
1525 {
1526  Emb_Obj_t * pThis, * pNext;
1527  double CostThis, CostPrev;
1528  float * pEdgeX, * pEdgeY;
1529  float * pVertX, * pVertY;
1530  float VertX, VertY;
1531  int * pPermX, * pPermY;
1532  int i, k, Iter, iMinX, iMaxX, iMinY, iMaxY;
1533  abctime clk = Abc_Clock();
1534  if ( p->pPlacement == NULL )
1535  return;
1536  pEdgeX = ABC_ALLOC( float, p->nObjs );
1537  pEdgeY = ABC_ALLOC( float, p->nObjs );
1538  pVertX = ABC_ALLOC( float, p->nObjs );
1539  pVertY = ABC_ALLOC( float, p->nObjs );
1540  // refine placement
1541  CostPrev = 0.0;
1542  for ( Iter = 0; Iter < nIters; Iter++ )
1543  {
1544  // compute centers of hyperedges
1545  CostThis = 0.0;
1546  Emb_ManForEachObj( p, pThis, i )
1547  {
1548  iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
1549  iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
1550  Emb_ObjForEachFanout( pThis, pNext, k )
1551  {
1552  iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
1553  iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
1554  iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
1555  iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
1556  }
1557  pEdgeX[pThis->Value] = 0.5 * (iMaxX + iMinX);
1558  pEdgeY[pThis->Value] = 0.5 * (iMaxY + iMinY);
1559  CostThis += (iMaxX - iMinX) + (iMaxY - iMinY);
1560  }
1561  // compute new centers of objects
1562  Emb_ManForEachObj( p, pThis, i )
1563  {
1564  VertX = pEdgeX[pThis->Value];
1565  VertY = pEdgeY[pThis->Value];
1566  Emb_ObjForEachFanin( pThis, pNext, k )
1567  {
1568  VertX += pEdgeX[pNext->Value];
1569  VertY += pEdgeY[pNext->Value];
1570  }
1571  pVertX[pThis->Value] = VertX / (Emb_ObjFaninNum(pThis) + 1);
1572  pVertY[pThis->Value] = VertY / (Emb_ObjFaninNum(pThis) + 1);
1573  }
1574  // sort these numbers
1575  pPermX = Gia_SortFloats( pVertX, NULL, p->nObjs );
1576  pPermY = Gia_SortFloats( pVertY, NULL, p->nObjs );
1577  for ( k = 0; k < p->nObjs; k++ )
1578  {
1579  p->pPlacement[2*pPermX[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1580  p->pPlacement[2*pPermY[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1581  }
1582  ABC_FREE( pPermX );
1583  ABC_FREE( pPermY );
1584  // evaluate cost
1585  if ( fVerbose )
1586  {
1587  printf( "%2d : HPWL = %e ", Iter+1, CostThis );
1588  ABC_PRT( "Time", Abc_Clock() - clk );
1589  }
1590  }
1591  ABC_FREE( pEdgeX );
1592  ABC_FREE( pEdgeY );
1593  ABC_FREE( pVertX );
1594  ABC_FREE( pVertY );
1595 }
1596 
1597 
1598 /**Function*************************************************************
1599 
1600  Synopsis [Derives solutions from original vectors and eigenvectors.]
1601 
1602  Description []
1603 
1604  SideEffects []
1605 
1606  SeeAlso []
1607 
1608 ***********************************************************************/
1609 void Emb_ManPrintSolutions( Emb_Man_t * p, int nSols )
1610 {
1611  float * pSol;
1612  int i, k;
1613  for ( i = 0; i < nSols; i++ )
1614  {
1615  pSol = Emb_ManSol( p, i );
1616  for ( k = 0; k < p->nObjs; k++ )
1617  printf( "%4d ", (int)(100 * pSol[k]) );
1618  printf( "\n" );
1619  }
1620 }
1621 
1622 /**Function*************************************************************
1623 
1624  Synopsis [Prepares image for dumping.]
1625 
1626  Description []
1627 
1628  SideEffects []
1629 
1630  SeeAlso []
1631 
1632 ***********************************************************************/
1633 Vec_Int_t * Emb_ManDumpGnuplotPrepare( Emb_Man_t * p )
1634 {
1635 // int nRows = 496;
1636 // int nCols = 710;
1637  int nRows = 500;
1638  int nCols = 700;
1639  Vec_Int_t * vLines;
1640  Emb_Obj_t * pThis;
1641  char * pBuffer, ** ppRows;
1642  int i, k, placeX, placeY;
1643  int fStart;
1644  // alloc memory
1645  pBuffer = ABC_CALLOC( char, nRows * (nCols+1) );
1646  ppRows = ABC_ALLOC( char *, nRows );
1647  for ( i = 0; i < nRows; i++ )
1648  ppRows[i] = pBuffer + i*(nCols+1);
1649  // put data into them
1650  Emb_ManForEachObj( p, pThis, i )
1651  {
1652  placeX = p->pPlacement[2*pThis->Value+0] * nCols / (1<<16);
1653  placeY = p->pPlacement[2*pThis->Value+1] * nRows / (1<<16);
1654  assert( placeX < nCols && placeY < nRows );
1655  ppRows[placeY][placeX] = 1;
1656  }
1657  // select lines
1658  vLines = Vec_IntAlloc( 1000 );
1659  for ( i = 0; i < nRows; i++ )
1660  {
1661  fStart = 0;
1662  for ( k = 0; k <= nCols; k++ )
1663  {
1664  if ( ppRows[i][k] && !fStart )
1665  {
1666  Vec_IntPush( vLines, k );
1667  Vec_IntPush( vLines, i );
1668  fStart = 1;
1669  }
1670  if ( !ppRows[i][k] && fStart )
1671  {
1672  Vec_IntPush( vLines, k-1 );
1673  Vec_IntPush( vLines, i );
1674  fStart = 0;
1675  }
1676  }
1677  assert( fStart == 0 );
1678  }
1679  ABC_FREE( pBuffer );
1680  ABC_FREE( ppRows );
1681  return vLines;
1682 }
1683 
1684 /**Function*************************************************************
1685 
1686  Synopsis [Derives solutions from original vectors and eigenvectors.]
1687 
1688  Description []
1689 
1690  SideEffects []
1691 
1692  SeeAlso []
1693 
1694 ***********************************************************************/
1695 void Emb_ManDumpGnuplot( Emb_Man_t * p, char * pName, int fDumpLarge, int fShowImage )
1696 {
1697  extern void Gia_ManGnuplotShow( char * pPlotFileName );
1698 // char * pDirectory = "place\\";
1699  char * pDirectory = "";
1700 // extern char * Ioa_TimeStamp();
1701  FILE * pFile;
1702  char Buffer[1000];
1703  Emb_Obj_t * pThis, * pNext;
1704  int i, k;
1705  if ( p->pPlacement == NULL )
1706  {
1707  printf( "Emb_ManDumpGnuplot(): Placement is not available.\n" );
1708  return;
1709  }
1710  sprintf( Buffer, "%s%s", pDirectory, Gia_FileNameGenericAppend(pName, ".plt") );
1711  pFile = fopen( Buffer, "w" );
1712  fprintf( pFile, "# This Gnuplot file was produced by ABC on %s\n", Ioa_TimeStamp() );
1713  fprintf( pFile, "\n" );
1714  fprintf( pFile, "set nokey\n" );
1715  fprintf( pFile, "\n" );
1716  if ( !fShowImage )
1717  {
1718 // fprintf( pFile, "set terminal postscript\n" );
1719  fprintf( pFile, "set terminal gif font \'arial\' 10 size 800,600 xffffff x000000 x000000 x000000\n" );
1720  fprintf( pFile, "set output \'%s\'\n", Gia_FileNameGenericAppend(pName, ".gif") );
1721  fprintf( pFile, "\n" );
1722  }
1723  fprintf( pFile, "set title \"%s : PI = %d PO = %d FF = %d Node = %d Obj = %d HPWL = %.2e\\n",
1724  pName, Emb_ManPiNum(p), Emb_ManPoNum(p), Emb_ManRegNum(p), Emb_ManNodeNum(p), Emb_ManObjNum(p), Emb_ManComputeHPWL(p) );
1725  fprintf( pFile, "(image generated by ABC and Gnuplot on %s)\"", Ioa_TimeStamp() );
1726  fprintf( pFile, "font \"Times, 12\"\n" );
1727  fprintf( pFile, "\n" );
1728  fprintf( pFile, "plot [:] '-' w l\n" );
1729  fprintf( pFile, "\n" );
1730  if ( fDumpLarge )
1731  {
1732  int begX, begY, endX, endY;
1733  Vec_Int_t * vLines = Emb_ManDumpGnuplotPrepare( p );
1734  Vec_IntForEachEntry( vLines, begX, i )
1735  {
1736  begY = Vec_IntEntry( vLines, i+1 );
1737  endX = Vec_IntEntry( vLines, i+2 );
1738  endY = Vec_IntEntry( vLines, i+3 );
1739  i += 3;
1740  fprintf( pFile, "%5d %5d\n", begX, begY );
1741  fprintf( pFile, "%5d %5d\n", endX, endY );
1742  fprintf( pFile, "\n" );
1743  }
1744  Vec_IntFree( vLines );
1745  }
1746  else
1747  {
1748  Emb_ManForEachObj( p, pThis, i )
1749  {
1750  if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
1751  continue;
1752  Emb_ObjForEachFanout( pThis, pNext, k )
1753  {
1754  assert( Emb_ObjIsTravIdCurrent(p, pNext) );
1755  fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pThis->Value+0], p->pPlacement[2*pThis->Value+1] );
1756  fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pNext->Value+0], p->pPlacement[2*pNext->Value+1] );
1757  fprintf( pFile, "\n" );
1758  }
1759  }
1760  }
1761  fprintf( pFile, "EOF\n" );
1762  fprintf( pFile, "\n" );
1763  if ( fShowImage )
1764  {
1765  fprintf( pFile, "pause -1 \"Close window\"\n" ); // Hit return to continue
1766  fprintf( pFile, "reset\n" );
1767  fprintf( pFile, "\n" );
1768  }
1769  else
1770  {
1771  fprintf( pFile, "# pause -1 \"Close window\"\n" ); // Hit return to continue
1772  fprintf( pFile, "# reset\n" );
1773  fprintf( pFile, "\n" );
1774  }
1775  fclose( pFile );
1776  if ( fShowImage )
1777  Gia_ManGnuplotShow( Buffer );
1778 }
1779 
1780 /**Function*************************************************************
1781 
1782  Synopsis [Computes dimentions of the graph.]
1783 
1784  Description []
1785 
1786  SideEffects []
1787 
1788  SeeAlso []
1789 
1790 ***********************************************************************/
1791 void Gia_ManSolveProblem( Gia_Man_t * pGia, Emb_Par_t * pPars )
1792 {
1793  Emb_Man_t * p;
1794  int i;
1795  abctime clkSetup;
1796  abctime clk;
1797 // Gia_ManTestDistance( pGia );
1798 
1799  // transform AIG into internal data-structure
1800 clk = Abc_Clock();
1801  if ( pPars->fCluster )
1802  {
1803  p = Emb_ManStart( pGia );
1804  if ( pPars->fVerbose )
1805  {
1806  printf( "Clustered: " );
1807  Emb_ManPrintStats( p );
1808  }
1809  }
1810  else
1811  p = Emb_ManStartSimple( pGia );
1812  p->fVerbose = pPars->fVerbose;
1813 // Emb_ManPrintFanio( p );
1814 
1815  // prepare data-structure
1816  Gia_ManRandom( 1 ); // reset random numbers for deterministic behavior
1817  Emb_ManResetTravId( p );
1818  Emb_ManSetValue( p );
1819 clkSetup = Abc_Clock() - clk;
1820 
1821 clk = Abc_Clock();
1822  Emb_ManComputeDimensions( p, pPars->nDims );
1823 if ( pPars->fVerbose )
1824 ABC_PRT( "Setup ", clkSetup );
1825 if ( pPars->fVerbose )
1826 ABC_PRT( "Dimensions", Abc_Clock() - clk );
1827 
1828 clk = Abc_Clock();
1829  Emb_ManComputeCovariance( p, pPars->nDims );
1830 if ( pPars->fVerbose )
1831 ABC_PRT( "Matrix ", Abc_Clock() - clk );
1832 
1833 clk = Abc_Clock();
1834  Emb_ManComputeEigenvectors( p, pPars->nDims, pPars->nSols );
1835  Emb_ManComputeSolutions( p, pPars->nDims, pPars->nSols );
1836  Emb_ManDerivePlacement( p, pPars->nSols );
1837 if ( pPars->fVerbose )
1838 ABC_PRT( "Eigenvecs ", Abc_Clock() - clk );
1839 
1840  if ( pPars->fRefine )
1841  {
1842 clk = Abc_Clock();
1843  Emb_ManPlacementRefine( p, pPars->nIters, pPars->fVerbose );
1844 if ( pPars->fVerbose )
1845 ABC_PRT( "Refinement", Abc_Clock() - clk );
1846  }
1847 
1848  if ( (pPars->fDump || pPars->fDumpLarge) && pPars->nSols == 2 )
1849  {
1850 clk = Abc_Clock();
1851  Emb_ManDumpGnuplot( p, pGia->pName, pPars->fDumpLarge, pPars->fShowImage );
1852 if ( pPars->fVerbose )
1853 ABC_PRT( "Image dump", Abc_Clock() - clk );
1854  }
1855 
1856  // transfer placement
1857  if ( Gia_ManObjNum(pGia) == p->nObjs )
1858  {
1859  // assuming normalized ordering of the AIG
1860  pGia->pPlacement = ABC_CALLOC( Gia_Plc_t, p->nObjs );
1861  for ( i = 0; i < p->nObjs; i++ )
1862  {
1863  pGia->pPlacement[i].xCoord = p->pPlacement[2*i+0];
1864  pGia->pPlacement[i].yCoord = p->pPlacement[2*i+1];
1865  }
1866  }
1867  Emb_ManStop( p );
1868 }
1869 
1870 ////////////////////////////////////////////////////////////////////////
1871 /// END OF FILE ///
1872 ////////////////////////////////////////////////////////////////////////
1873 
1874 
1875 ABC_NAMESPACE_IMPL_END
1876 
Emb_ObjSetTravIdCurrent
static void Emb_ObjSetTravIdCurrent(Emb_Man_t *p, Emb_Obj_t *pObj)
Definition: giaEmbed.c:119
Emb_ManMatrAlloc
float ** Emb_ManMatrAlloc(int nDims)
Definition: giaEmbed.c:1170
Emb_Man_t_::nRegs
int nRegs
Definition: giaEmbed.c:76
Gia_ManCreateRefs
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition: giaUtil.c:715
Emb_Obj_t_::hHandle
int hHandle
Definition: giaEmbed.c:57
Emb_ManVecRandom
void Emb_ManVecRandom(float *pVec, int nDims)
Definition: giaEmbed.c:1244
Emb_ManVec
static Emb_Dat_t * Emb_ManVec(Emb_Man_t *p, int v)
Definition: giaEmbed.c:124
Emb_ObjSize
static int Emb_ObjSize(Emb_Obj_t *pObj)
Definition: giaEmbed.c:110
Emb_Man_t_::pObjData
int * pObjData
Definition: giaEmbed.c:78
Emb_Par_t_::nDims
int nDims
Definition: gia.h:211
Emb_Man_t_::pSols
float * pSols
Definition: giaEmbed.c:86
Emb_ManNodeNum
static int Emb_ManNodeNum(Emb_Man_t *p)
Definition: giaEmbed.c:96
Gia_ManSolveProblem
void Gia_ManSolveProblem(Gia_Man_t *pGia, Emb_Par_t *pPars)
Definition: giaEmbed.c:1791
Emb_ManDerivePlacement
void Emb_ManDerivePlacement(Emb_Man_t *p, int nSols)
Definition: giaEmbed.c:1427
Emb_Obj_t_::Value
unsigned Value
Definition: giaEmbed.c:63
Emb_ManPlacementRefine
void Emb_ManPlacementRefine(Emb_Man_t *p, int nIters, int fVerbose)
Definition: giaEmbed.c:1524
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition: gia.h:1022
Emb_ManCoNum
static int Emb_ManCoNum(Emb_Man_t *p)
Definition: giaEmbed.c:92
Emb_ManComputeDistance_old
int Emb_ManComputeDistance_old(Emb_Man_t *p, Emb_Obj_t *pPivot)
Definition: giaEmbed.c:783
Emb_Par_t_::nIters
int nIters
Definition: gia.h:213
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Emb_Obj_t_::fMark0
unsigned fMark0
Definition: giaEmbed.c:53
Emb_ManVecMultiply
void Emb_ManVecMultiply(float **pMatr, float *pVec, int nDims, float *pRes)
Definition: giaEmbed.c:1322
Emb_ObjFanoutNum
static int Emb_ObjFanoutNum(Emb_Obj_t *pObj)
Definition: giaEmbed.c:112
Gia_Regular
static Gia_Obj_t * Gia_Regular(Gia_Obj_t *p)
Definition: gia.h:377
Emb_ManStop
void Emb_ManStop(Emb_Man_t *p)
Definition: giaEmbed.c:651
Emb_ManPerformBfs
Emb_Obj_t * Emb_ManPerformBfs(Emb_Man_t *p, Vec_Int_t *vThis, Vec_Int_t *vNext, Emb_Dat_t *pDist)
Definition: giaEmbed.c:930
Emb_ObjIsCi
static int Emb_ObjIsCi(Emb_Obj_t *pObj)
Definition: giaEmbed.c:103
Emb_ManFindDistances
Emb_Obj_t * Emb_ManFindDistances(Emb_Man_t *p, Vec_Int_t *vStart, Emb_Dat_t *pDist)
Definition: giaEmbed.c:1016
Gia_ManGnuplotShow
void Gia_ManGnuplotShow(char *pPlotFileName)
Definition: cmd.c:2134
Emb_ManCollectSuper
void Emb_ManCollectSuper(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
Definition: giaEmbed.c:312
Emb_ManPoNum
static int Emb_ManPoNum(Emb_Man_t *p)
Definition: giaEmbed.c:94
Gia_ManCleanMark0
void Gia_ManCleanMark0(Gia_Man_t *p)
Definition: giaUtil.c:215
Gia_ObjIsConst0
static int Gia_ObjIsConst0(Gia_Obj_t *pObj)
Definition: gia.h:430
Emb_Par_t_::fVerbose
int fVerbose
Definition: gia.h:219
Emb_Par_t_::fDumpLarge
int fDumpLarge
Definition: gia.h:217
Gia_ObjValue
static int Gia_ObjValue(Gia_Obj_t *pObj)
Definition: gia.h:413
Emb_Dat_t
float Emb_Dat_t
Definition: giaEmbed.c:46
Gia_ManTestDistanceInternal
void Gia_ManTestDistanceInternal(Emb_Man_t *p)
Definition: giaEmbed.c:838
Emb_Par_t_::nSols
int nSols
Definition: gia.h:212
Emb_ObjForEachFanout
#define Emb_ObjForEachFanout(pObj, pNext, i)
Definition: giaEmbed.c:135
Gia_ObjRefNum
static int Gia_ObjRefNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:521
Emb_ObjIsTravIdPrevious
static int Emb_ObjIsTravIdPrevious(Emb_Man_t *p, Emb_Obj_t *pObj)
Definition: giaEmbed.c:122
Emb_ManPiNum
static int Emb_ManPiNum(Emb_Man_t *p)
Definition: giaEmbed.c:93
Emb_Obj_t_::fCo
unsigned fCo
Definition: giaEmbed.c:52
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Emb_Obj_t_::fMark1
unsigned fMark1
Definition: giaEmbed.c:54
Emb_ManCi
static Emb_Obj_t * Emb_ManCi(Emb_Man_t *p, int i)
Definition: giaEmbed.c:99
Gia_Obj_t_::fMark1
unsigned fMark1
Definition: gia.h:84
Emb_Obj_t_::iFanout
unsigned iFanout
Definition: giaEmbed.c:64
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Gia_ManForEachCoDriver
#define Gia_ManForEachCoDriver(p, pObj, i)
Definition: gia.h:1030
Emb_ManRegNum
static int Emb_ManRegNum(Emb_Man_t *p)
Definition: giaEmbed.c:90
Gia_ManObj
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
Gia_Man_t_::pRefs
int * pRefs
Definition: gia.h:114
Gia_Obj_t_
Definition: gia.h:75
Gia_ManCleanMark1
void Gia_ManCleanMark1(Gia_Man_t *p)
Definition: giaUtil.c:272
Emb_Man_t_::vCis
Vec_Int_t * vCis
Definition: giaEmbed.c:73
Emb_ManStartSimple
Emb_Man_t * Emb_ManStartSimple(Gia_Man_t *pGia)
Definition: giaEmbed.c:172
Emb_Par_t_
Definition: gia.h:209
Emb_Man_t_::pGia
Gia_Man_t * pGia
Definition: giaEmbed.c:72
Emb_ManCleanTravId
void Emb_ManCleanTravId(Emb_Man_t *p)
Definition: giaEmbed.c:451
Emb_ManPrintStats
void Emb_ManPrintStats(Emb_Man_t *p)
Definition: giaEmbed.c:622
Gia_ManRandom
unsigned Gia_ManRandom(int fReset)
FUNCTION DEFINITIONS ///.
Definition: giaUtil.c:49
Emb_ManCreateRefsSpecial
void Emb_ManCreateRefsSpecial(Gia_Man_t *p)
Definition: giaEmbed.c:336
Gia_Plc_t_::yCoord
unsigned yCoord
Definition: gia.h:71
Gia_ManForEachCi
#define Gia_ManForEachCi(p, pObj, i)
Definition: gia.h:1016
Emb_Man_t_
Definition: giaEmbed.c:70
Gia_ManForEachRiRo
#define Gia_ManForEachRiRo(p, pObjRi, pObjRo, i)
Definition: gia.h:1042
Gia_ManAndNum
static int Gia_ManAndNum(Gia_Man_t *p)
Definition: gia.h:389
Emb_ManCollectSuper_rec
void Emb_ManCollectSuper_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
Definition: giaEmbed.c:284
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
Emb_ManVecNormal
void Emb_ManVecNormal(float *pVec, int nDims)
Definition: giaEmbed.c:1262
Emb_ManPrintFanio
void Emb_ManPrintFanio(Emb_Man_t *p)
Definition: giaEmbed.c:675
Emb_ManCo
static Emb_Obj_t * Emb_ManCo(Emb_Man_t *p, int i)
Definition: giaEmbed.c:100
Vec_IntStart
static Vec_Int_t * Vec_IntStart(int nSize)
Definition: bblif.c:172
Gia_ManCheckMark1
void Gia_ManCheckMark1(Gia_Man_t *p)
Definition: giaUtil.c:291
Emb_ObjForEachFanin
#define Emb_ObjForEachFanin(pObj, pNext, i)
Definition: giaEmbed.c:133
Emb_Man_t_::pPlacement
unsigned short * pPlacement
Definition: giaEmbed.c:87
Gia_ObjFanin0
static Gia_Obj_t * Gia_ObjFanin0(Gia_Obj_t *pObj)
Definition: gia.h:454
Ioa_TimeStamp
char * Ioa_TimeStamp()
Definition: ioaUtil.c:127
Gia_Man_t_::pName
char * pName
Definition: gia.h:97
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Emb_ManTransformRefs
void Emb_ManTransformRefs(Gia_Man_t *p, int *pnObjs, int *pnFanios)
Definition: giaEmbed.c:382
Emb_ManObjNum
static int Emb_ManObjNum(Emb_Man_t *p)
Definition: giaEmbed.c:95
Emb_Man_t_::nTravIds
int nTravIds
Definition: giaEmbed.c:77
Emb_Par_t_::fShowImage
int fShowImage
Definition: gia.h:218
Emb_Obj_t_::TravId
unsigned TravId
Definition: giaEmbed.c:59
Vec_IntAddToEntry
static void Vec_IntAddToEntry(Vec_Int_t *p, int i, int Addition)
Definition: bblif.c:302
Gia_ObjIsRo
static int Gia_ObjIsRo(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:443
Emb_ManDumpGnuplot
void Emb_ManDumpGnuplot(Emb_Man_t *p, char *pName, int fDumpLarge, int fShowImage)
Definition: giaEmbed.c:1695
Emb_Obj_t_::nFanouts
unsigned nFanouts
Definition: giaEmbed.c:56
Emb_ManForEachObj
#define Emb_ManForEachObj(p, pObj, i)
Definition: giaEmbed.c:127
Emb_Obj_t_::fCi
unsigned fCi
Definition: giaEmbed.c:51
Emb_ManPrintSolutions
void Emb_ManPrintSolutions(Emb_Man_t *p, int nSols)
Definition: giaEmbed.c:1609
Gia_ObjIsRi
static int Gia_ObjIsRi(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:444
Emb_Obj_t_
Definition: giaEmbed.c:49
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Abc_Base10Log
static int Abc_Base10Log(unsigned n)
Definition: abc_global.h:252
Gia_ObjRefInc
static int Gia_ObjRefInc(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:522
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Emb_ObjIsNode
static int Emb_ObjIsNode(Emb_Obj_t *pObj)
Definition: giaEmbed.c:107
Emb_ObjSetTravIdPrevious
static void Emb_ObjSetTravIdPrevious(Emb_Man_t *p, Emb_Obj_t *pObj)
Definition: giaEmbed.c:120
Emb_Obj_t_::Fanios
int Fanios[0]
Definition: giaEmbed.c:66
Gia_ManForEachAnd
#define Gia_ManForEachAnd(p, pObj, i)
Definition: gia.h:1002
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Emb_ManComputeCovariance
void Emb_ManComputeCovariance(Emb_Man_t *p, int nDims)
Definition: giaEmbed.c:1191
sprintf
char * sprintf()
Gia_ObjId
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
Counter
static int Counter
Definition: extraBddMisc.c:1877
Gia_ManFillValue
void Gia_ManFillValue(Gia_Man_t *p)
Definition: giaUtil.c:328
Emb_Par_t_::fRefine
int fRefine
Definition: gia.h:214
Emb_ManObj
static Emb_Obj_t * Emb_ManObj(Emb_Man_t *p, unsigned hHandle)
Definition: giaEmbed.c:98
Emb_ObjSetTravId
static void Emb_ObjSetTravId(Emb_Obj_t *pObj, int TravId)
Definition: giaEmbed.c:118
Emb_ManForEachNode
#define Emb_ManForEachNode(p, pObj, i)
Definition: giaEmbed.c:129
Gia_FileNameGenericAppend
char * Gia_FileNameGenericAppend(char *pBase, char *pSuffix)
Definition: giaUtil.c:125
Emb_ManComputeDimensions
void Emb_ManComputeDimensions(Emb_Man_t *p, int nDims)
Definition: giaEmbed.c:1102
Emb_DumpGraphIntoFile
void Emb_DumpGraphIntoFile(Emb_Man_t *p)
Definition: giaEmbed.c:1072
Emb_Man_t_::pMatr
float ** pMatr
Definition: giaEmbed.c:84
Emb_ManForEachObjVec
#define Emb_ManForEachObjVec(vVec, p, pObj, i)
Definition: giaEmbed.c:131
Emb_Obj_t_::iFanin
unsigned iFanin
Definition: giaEmbed.c:60
Gia_ObjIsCo
static int Gia_ObjIsCo(Gia_Obj_t *pObj)
Definition: gia.h:421
Emb_ObjFaninNum
static int Emb_ObjFaninNum(Emb_Obj_t *pObj)
Definition: giaEmbed.c:111
Emb_ManResetTravId
static void Emb_ManResetTravId(Emb_Man_t *p)
Definition: giaEmbed.c:116
Gia_ManForEachObjVec
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition: gia.h:988
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Emb_Man_t_::nDistMax
int nDistMax
Definition: giaEmbed.c:83
Gia_ObjRefDec
static int Gia_ObjRefDec(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:523
Gia_ObjIsMuxType
int Gia_ObjIsMuxType(Gia_Obj_t *pNode)
Definition: giaUtil.c:885
Gia_ManCiNum
static int Gia_ManCiNum(Gia_Man_t *p)
Definition: gia.h:383
Emb_ObjIsCo
static int Emb_ObjIsCo(Emb_Obj_t *pObj)
Definition: giaEmbed.c:104
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Emb_ManIncrementTravId
static void Emb_ManIncrementTravId(Emb_Man_t *p)
Definition: giaEmbed.c:117
Gia_Obj_t_::fMark0
unsigned fMark0
Definition: gia.h:79
Emb_ObjFanin
static Emb_Obj_t * Emb_ObjFanin(Emb_Obj_t *pObj, int i)
Definition: giaEmbed.c:113
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Gia_ObjRecognizeMux
Gia_Obj_t * Gia_ObjRecognizeMux(Gia_Obj_t *pNode, Gia_Obj_t **ppNodeT, Gia_Obj_t **ppNodeE)
Definition: giaUtil.c:959
Gia_Plc_t_::xCoord
unsigned xCoord
Definition: gia.h:69
Gia_Man_t_
Definition: gia.h:95
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
Emb_ManSol
static float * Emb_ManSol(Emb_Man_t *p, int v)
Definition: giaEmbed.c:125
Gia_ObjIsAnd
static int Gia_ObjIsAnd(Gia_Obj_t *pObj)
Definition: gia.h:422
Emb_ManSetValue
void Emb_ManSetValue(Emb_Man_t *p)
Definition: giaEmbed.c:470
Emb_ManComputeHPWL
double Emb_ManComputeHPWL(Emb_Man_t *p)
Definition: giaEmbed.c:1489
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition: gia.h:984
Gia_ManConst0
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
Emb_ManRandomVertex
Emb_Obj_t * Emb_ManRandomVertex(Emb_Man_t *p)
Definition: giaEmbed.c:1047
Gia_ManTestDistance
void Gia_ManTestDistance(Gia_Man_t *pGia)
Definition: giaEmbed.c:904
Gia_Man_t_::pPlacement
Gia_Plc_t * pPlacement
Definition: gia.h:148
Emb_ManVecOrthogonolizeOne
void Emb_ManVecOrthogonolizeOne(float *pEigen, float *pVecI, int nDims, float *pVecRes)
Definition: giaEmbed.c:1340
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
Emb_Man_t_::pEigen
float ** pEigen
Definition: giaEmbed.c:85
Emb_ManStart
Emb_Man_t * Emb_ManStart(Gia_Man_t *pGia)
Definition: giaEmbed.c:493
Gia_ObjFanin1
static Gia_Obj_t * Gia_ObjFanin1(Gia_Obj_t *pObj)
Definition: gia.h:455
Emb_ObjAddFanin
void Emb_ObjAddFanin(Emb_Obj_t *pObj, Emb_Obj_t *pFanin)
FUNCTION DEFINITIONS ///.
Definition: giaEmbed.c:153
Emb_Par_t_::fCluster
int fCluster
Definition: gia.h:215
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
Gia_SortFloats
int * Gia_SortFloats(float *pArray, int *pPerm, int nSize)
Definition: giaSort.c:251
assert
#define assert(ex)
Definition: util_old.h:213
Emb_Man_t_::pVecs
Emb_Dat_t * pVecs
Definition: giaEmbed.c:81
Emb_Obj_t_::nFanins
unsigned nFanins
Definition: giaEmbed.c:55
Gia_Obj_t_::Value
unsigned Value
Definition: gia.h:87
Emb_ManCiNum
static int Emb_ManCiNum(Emb_Man_t *p)
Definition: giaEmbed.c:91
Gia_Plc_t_
Definition: gia.h:66
Emb_Man_t_::vCos
Vec_Int_t * vCos
Definition: giaEmbed.c:74
GIA_PLACE_SIZE
#define GIA_PLACE_SIZE
DECLARATIONS ///.
Definition: giaEmbed.c:43
Emb_ManConnectedComponents
Vec_Int_t * Emb_ManConnectedComponents(Emb_Man_t *p)
Definition: giaEmbed.c:977
Emb_ManDumpGnuplotPrepare
Vec_Int_t * Emb_ManDumpGnuplotPrepare(Emb_Man_t *p)
Definition: giaEmbed.c:1633
Emb_ManComputeSolutions
void Emb_ManComputeSolutions(Emb_Man_t *p, int nDims, int nSols)
Definition: giaEmbed.c:1397
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Emb_Obj_t
struct Emb_Obj_t_ Emb_Obj_t
Definition: giaEmbed.c:48
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Gia_ObjIsCi
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Emb_ManVecCopyOne
void Emb_ManVecCopyOne(float *pVecDest, float *pVecSour, int nDims)
Definition: giaEmbed.c:1304
Emb_Man_t_::nObjs
int nObjs
Definition: giaEmbed.c:75
Emb_ObjIsTerm
static int Emb_ObjIsTerm(Emb_Obj_t *pObj)
Definition: giaEmbed.c:102
Emb_Par_t_::fDump
int fDump
Definition: gia.h:216
Emb_ManVecMultiplyOne
float Emb_ManVecMultiplyOne(float *pVec0, float *pVec1, int nDims)
Definition: giaEmbed.c:1284
Gia_ManObjNum
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
Emb_Man_t_::fVerbose
int fVerbose
Definition: giaEmbed.c:80
Emb_ManComputeEigenvectors
void Emb_ManComputeEigenvectors(Emb_Man_t *p, int nDims, int nSols)
Definition: giaEmbed.c:1358
Emb_Man_t_::nObjData
int nObjData
Definition: giaEmbed.c:79
Gia_ManCoNum
static int Gia_ManCoNum(Gia_Man_t *p)
Definition: gia.h:384
Emb_ObjIsTravIdCurrent
static int Emb_ObjIsTravIdCurrent(Emb_Man_t *p, Emb_Obj_t *pObj)
Definition: giaEmbed.c:121
Emb_Man_t_::nReached
int nReached
Definition: giaEmbed.c:82
Emb_ObjFanout
static Emb_Obj_t * Emb_ObjFanout(Emb_Obj_t *pObj, int i)
Definition: giaEmbed.c:114
Gia_ManRegNum
static int Gia_ManRegNum(Gia_Man_t *p)
Definition: gia.h:387