seymour_internal.h

Go to the documentation of this file.

#ifndef CMR_SEYMOUR_INTERNAL_H
#define CMR_SEYMOUR_INTERNAL_H
 
#include <time.h>
 
#include "densematrix.h"
 
#include <cmr/matroid.h>
#include <cmr/seymour.h>
#include <cmr/series_parallel.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
 
struct _CMR_SEYMOUR_NODE
{
  size_t used;                                  
  CMR_SEYMOUR_NODE_TYPE type;                   
  bool isTernary;                               
  bool testedTwoConnected;                      
  int8_t regularity;                            
  int8_t graphicness;                           
  int8_t cographicness;                         
  bool testedR10;                               
  CMR_SEYMOUR_THREESUM_FLAG threesumFlags;      
  CMR_CHRMAT* matrix;                           
  CMR_CHRMAT* transpose;                        
  size_t numChildren;                           
  struct _CMR_SEYMOUR_NODE** children;          
  CMR_ELEMENT** childRowsToParent;              
  CMR_ELEMENT** childColumnsToParent;           
  size_t numRows;                               
  size_t* rowsToChild;                          
  size_t numColumns;                            
  size_t* columnsToChild;                       
  size_t memMinors;                             
  size_t numMinors;                             
  CMR_MINOR** minors;                           
  CMR_GRAPH* graph;                             
  CMR_GRAPH_EDGE* graphForest;                  
  CMR_GRAPH_EDGE* graphCoforest;                
  bool* graphArcsReversed;                      
  CMR_GRAPH* cograph;                           
  CMR_GRAPH_EDGE* cographForest;                
  CMR_GRAPH_EDGE* cographCoforest;              
  bool* cographArcsReversed;                    
  bool testedSeriesParallel;                    
  CMR_SP_REDUCTION* seriesParallelReductions;   
  size_t numSeriesParallelReductions;           
  size_t* pivotRows;                            
  size_t* pivotColumns;                         
  size_t numPivots;                             
  DenseBinaryMatrix* denseMatrix;               
  CMR_ELEMENT* denseRowsOriginal;               
  CMR_ELEMENT* denseColumnsOriginal;            
  size_t* nestedMinorsRowsDense;                
  size_t* nestedMinorsColumnsDense;             
  size_t nestedMinorsLength;                  
  size_t* nestedMinorsSequenceNumRows;        
  size_t* nestedMinorsSequenceNumColumns;     
  CMR_CHRMAT* nestedMinorsMatrix;             
  CMR_CHRMAT* nestedMinorsTranspose;          
  CMR_ELEMENT* nestedMinorsRowsOriginal;      
  CMR_ELEMENT* nestedMinorsColumnsOriginal;   
  size_t nestedMinorsLastGraphic;             
  size_t nestedMinorsLastCographic;           
};
 
typedef struct DecompositionTask
{
  CMR_SEYMOUR_NODE* node;         
  struct DecompositionTask* next; 
  CMR_SEYMOUR_PARAMS* params;     
  CMR_SEYMOUR_STATS* stats;       
  clock_t startClock;             
  double timeLimit;               
} DecompositionTask;
 
 
char* CMRseymourConsistency(
  CMR_SEYMOUR_NODE* node, 
  bool recurse            
);
 
CMR_EXPORT
CMR_ERROR CMRseymourPrintChild(
  CMR* cmr,                 
  CMR_SEYMOUR_NODE* child,  
  CMR_SEYMOUR_NODE* parent, 
  size_t childIndex,        
  FILE* stream,             
  size_t indent,            
  bool printChildren,       
  bool printParentElements, 
  bool printMatrices,       
  bool printGraphs,         
  bool printReductions,     
  bool printPivots          
);
 
CMR_ERROR CMRseymourAddMinor(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  CMR_MINOR* minor        
);
 
CMR_ERROR CMRseymourSetNumChildren(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  size_t numChildren      
);
 
CMR_ERROR CMRseymourUpdateOneSum(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  size_t numChildren      
);
 
CMR_ERROR CMRseymourCreateChildFromMatrices(
  CMR* cmr,                     
  CMR_SEYMOUR_NODE* parent,     
  size_t childIndex,            
  CMR_CHRMAT* matrix,           
  CMR_CHRMAT* transpose,        
  CMR_ELEMENT* rowsToParent,    
  CMR_ELEMENT* columnsToParent  
);
 
CMR_ERROR CMRseymourUpdateViolator(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  CMR_SUBMAT* violator    
);
 
CMR_ERROR CMRseymourUpdateSeriesParallel(
  CMR* cmr,                     
  CMR_SEYMOUR_NODE* node,       
  CMR_SUBMAT* reducedSubmatrix  
);
 
CMR_ERROR CMRseymourUpdateTwoSum(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  CMR_SEPA* separation    
);
 
CMR_ERROR CMRseymourUpdatePivots(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node, 
  size_t numPivots,       
  size_t* pivotRows,      
  size_t* pivotColumns,   
  CMR_CHRMAT* matrix,     
  CMR_CHRMAT* transpose   
);
 
CMR_ERROR CMRseymourUpdateThreeSumInit(
  CMR* cmr,               
  CMR_SEYMOUR_NODE* node  
);
 
CMR_ERROR CMRseymourUpdateThreeSumCreateWideFirstChild(
  CMR* cmr,                   
  CMR_SEYMOUR_NODE* node,     
  size_t* rowsToChild,        
  size_t* columnsToChild,     
  size_t numChildBaseRows,    
  size_t numChildBaseColumns, 
  size_t extraRow,            
  size_t extraColumn1,        
  size_t extraColumn2,        
  int8_t extraEntry           
);
 
CMR_ERROR CMRseymourUpdateThreeSumCreateWideSecondChild(
  CMR* cmr,                   
  CMR_SEYMOUR_NODE* node,     
  size_t* rowsToChild,        
  size_t* columnsToChild,     
  size_t numChildBaseRows,    
  size_t numChildBaseColumns, 
  size_t extraRow,            
  size_t extraColumn1,        
  size_t extraColumn2,        
  int8_t extraEntry           
);
 
CMR_ERROR CMRseymourUpdateThreeSumCreateMixedFirstChild(
  CMR* cmr,                   
  CMR_SEYMOUR_NODE* node,     
  size_t* rowsToChild,        
  size_t* columnsToChild,     
  size_t numChildBaseRows,    
  size_t numChildBaseColumns, 
  size_t extraRow1,           
  size_t extraRow2,           
  int8_t extraEntry           
);
 
CMR_ERROR CMRseymourUpdateThreeSumCreateMixedSecondChild(
  CMR* cmr,                   
  CMR_SEYMOUR_NODE* node,     
  size_t* rowsToChild,        
  size_t* columnsToChild,     
  size_t numChildBaseRows,    
  size_t numChildBaseColumns, 
  size_t extraColumn1,        
  size_t extraColumn2,        
  int8_t extraEntry           
);
 
CMR_ERROR CMRseymourSetAttributes(
  CMR_SEYMOUR_NODE* node  
);
 
 
CMR_ERROR CMRregularityTaskCreateRoot(
  CMR* cmr,                       
  CMR_SEYMOUR_NODE* dec,          
  DecompositionTask** ptask,      
  CMR_SEYMOUR_PARAMS* params,     
  CMR_SEYMOUR_STATS* stats,       
  clock_t startClock,             
  double timeLimit                
);
 
CMR_ERROR CMRregularityTaskFree(
  CMR* cmr,                       
  DecompositionTask** ptask       
);
 
typedef struct DecompositionQueue
{
  DecompositionTask* head;    
  bool foundIrregularity;     
  bool foundNongraphicness;   
  bool foundNoncographicness; 
} DecompositionQueue;
 
CMR_ERROR CMRregularityQueueCreate(
  CMR* cmr,                   
  DecompositionQueue** pqueue 
);
 
CMR_ERROR CMRregularityQueueFree(
  CMR* cmr,                   
  DecompositionQueue** pqueue 
);
 
bool CMRregularityQueueEmpty(
  DecompositionQueue* queue 
);
 
DecompositionTask* CMRregularityQueueRemove(
  DecompositionQueue* queue 
);
 
 
void CMRregularityQueueAdd(
  DecompositionQueue* queue,  
  DecompositionTask* task     
);
 
CMR_ERROR
CMRregularityDecomposeThreeSum(
  CMR* cmr,                   
  DecompositionTask* task,    
  DecompositionQueue* queue,  
  CMR_SEPA* separation        
);
 
CMR_ERROR
CMRregularityNestedMinorSequenceSearchThreeSeparation(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR
CMRregularityNestedMinorSequenceGraphicness(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR
CMRregularityNestedMinorSequenceCographicness(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR
CMRregularityExtendNestedMinorSequence(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRregularityTestR10(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRregularityInitNestedMinorSequence(
  CMR* cmr,                   
  DecompositionTask* task,    
  CMR_SUBMAT* wheelSubmatrix  
);
 
CMR_ERROR CMRregularityDecomposeSeriesParallel(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRregularityTestGraphicness(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRregularityTestCographicness(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRregularitySearchOneSum(
  CMR* cmr,                 
  DecompositionTask* task,  
  DecompositionQueue* queue 
);
 
CMR_ERROR CMRseymourDecompose(
  CMR* cmr,                   
  CMR_CHRMAT* matrix,         
  bool ternary,               
  CMR_SEYMOUR_NODE** proot,   
  CMR_SEYMOUR_PARAMS* params, 
  CMR_SEYMOUR_STATS* stats,   
  double timeLimit            
);
 
CMR_ERROR CMRregularityCompleteDecomposition(
  CMR* cmr,                   
    CMR_SEYMOUR_NODE* subtree,   
  CMR_SEYMOUR_PARAMS* params, 
  CMR_SEYMOUR_STATS* stats,   
  double timeLimit            
);
 
CMR_ERROR CMRregularityRefineDecomposition(
  CMR* cmr,                   
  size_t numNodes,            
    CMR_SEYMOUR_NODE** nodes,    
  CMR_SEYMOUR_PARAMS* params, 
  CMR_SEYMOUR_STATS* stats,   
  double timeLimit            
);
 
#ifdef __cplusplus
}
#endif
 
#endif /* CMR_SEYMOUR_INTERNAL_H */