seymour.h

Go to the documentation of this file.

#ifndef CMR_SEYMOUR_H
#define CMR_SEYMOUR_H
 
#include <cmr/env.h>
#include <cmr/matrix.h>
#include <cmr/matroid.h>
#include <cmr/graph.h>
#include <cmr/network.h>
#include <cmr/series_parallel.h>
 
#include <stdio.h>
#include <stdint.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef enum
{
  CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_MASK = 15,
  CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_PIVOT = 1,
  CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_DELTASUM = 2,
  CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_YSUM = 3,
  CMR_SEYMOUR_DECOMPOSE_FLAG_CONCENTRATED_MASK = 240,
  CMR_SEYMOUR_DECOMPOSE_FLAG_CONCENTRATED_PIVOT = 16,
  CMR_SEYMOUR_DECOMPOSE_FLAG_CONCENTRATED_THREESUM = 32,
  CMR_SEYMOUR_DECOMPOSE_FLAG_SEYMOUR = CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_DELTASUM
    | CMR_SEYMOUR_DECOMPOSE_FLAG_CONCENTRATED_PIVOT,
  CMR_SEYMOUR_DECOMPOSE_FLAG_TRUEMPER = CMR_SEYMOUR_DECOMPOSE_FLAG_DISTRIBUTED_PIVOT
    | CMR_SEYMOUR_DECOMPOSE_FLAG_CONCENTRATED_THREESUM,
} CMR_SEYMOUR_DECOMPOSE_FLAG;
 
typedef struct
{
  bool stopWhenIrregular;
  bool stopWhenNongraphic;
  bool stopWhenNoncographic;
  bool stopWhenNeitherGraphicNorCoGraphic;
  bool seriesParallel;
  bool planarityCheck;
  bool directGraphicness;
  bool preferGraphicness;
  int decomposeStrategy;
  bool constructLeafGraphs;
  bool constructAllGraphs;
} CMR_SEYMOUR_PARAMS;
 
CMR_EXPORT
CMR_ERROR CMRseymourParamsInit(
  CMR_SEYMOUR_PARAMS* params  
);
 
typedef struct
{
  uint32_t totalCount;                  
  double totalTime;                     
  CMR_SP_STATISTICS seriesParallel;     
  CMR_GRAPHIC_STATISTICS graphic;       
  CMR_NETWORK_STATISTICS network;       
  uint32_t sequenceExtensionCount;      
  double sequenceExtensionTime;         
  uint32_t sequenceGraphicCount;        
  double sequenceGraphicTime;           
  uint32_t enumerationCount;            
  double enumerationTime;               
  uint32_t enumerationCandidatesCount;  
} CMR_SEYMOUR_STATS;
 
 
CMR_EXPORT
CMR_ERROR CMRseymourStatsInit(
  CMR_SEYMOUR_STATS* stats 
);
 
CMR_EXPORT
CMR_ERROR CMRseymourStatsPrint(
  FILE* stream,             
  CMR_SEYMOUR_STATS* stats, 
  const char* prefix        
);
 
 
 
struct _CMR_SEYMOUR_NODE;
 
typedef struct _CMR_SEYMOUR_NODE CMR_SEYMOUR_NODE;
 
typedef enum
{
  CMR_SEYMOUR_NODE_TYPE_IRREGULAR = -1,
  CMR_SEYMOUR_NODE_TYPE_UNKNOWN = 0,
  CMR_SEYMOUR_NODE_TYPE_SERIES_PARALLEL = 1,
  CMR_SEYMOUR_NODE_TYPE_PIVOTS = 2,
  CMR_SEYMOUR_NODE_TYPE_GRAPH = 3,
  CMR_SEYMOUR_NODE_TYPE_COGRAPH = 4,
  CMR_SEYMOUR_NODE_TYPE_PLANAR = 5,
  CMR_SEYMOUR_NODE_TYPE_R10 = 6,
  CMR_SEYMOUR_NODE_TYPE_ONESUM = 7,
  CMR_SEYMOUR_NODE_TYPE_TWOSUM = 8,
  CMR_SEYMOUR_NODE_TYPE_DELTASUM = 9,
  CMR_SEYMOUR_NODE_TYPE_THREESUM = 10,
  CMR_SEYMOUR_NODE_TYPE_YSUM = 11
} CMR_SEYMOUR_NODE_TYPE;
 
CMR_EXPORT
bool CMRseymourIsTernary(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
bool CMRseymourThreeSumDistributedRanks(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
bool CMRseymourThreeSumConcentratedRank(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
bool CMRseymourHasTranspose(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_CHRMAT* CMRseymourGetMatrix(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_CHRMAT* CMRseymourGetTranspose(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourNumChildren(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_SEYMOUR_NODE* CMRseymourChild(
  CMR_SEYMOUR_NODE* node, 
  size_t childIndex         
);
 
CMR_EXPORT
CMR_SEYMOUR_NODE_TYPE CMRseymourType(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourNumMinors(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_MINOR* CMRseymourMinor(
  CMR_SEYMOUR_NODE* node, 
  size_t minorIndex         
);
 
CMR_EXPORT
int8_t CMRseymourGraphicness(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
int8_t CMRseymourCographicness(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
int8_t CMRseymourRegularity(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourNumRows(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourNumColumns(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_ELEMENT* CMRseymourChildRowsToParent(
  CMR_SEYMOUR_NODE* node, 
  size_t childIndex       
);
 
CMR_EXPORT
CMR_ELEMENT* CMRseymourChildColumnsToParent(
  CMR_SEYMOUR_NODE* node, 
  size_t childIndex       
);
 
CMR_EXPORT
size_t* CMRseymourChildSpecialRows(
  CMR_SEYMOUR_NODE* node, 
  size_t childIndex       
);
 
CMR_EXPORT
size_t* CMRseymourChildSpecialColumns(
  CMR_SEYMOUR_NODE* node, 
  size_t childIndex       
);
 
CMR_EXPORT
CMR_GRAPH* CMRseymourGraph(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_GRAPH_EDGE* CMRseymourGraphForest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourGraphSizeForest(
    CMR_SEYMOUR_NODE* dec  
);
 
CMR_EXPORT
CMR_GRAPH_EDGE* CMRseymourGraphCoforest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourGraphSizeCoforest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
bool* CMRseymourGraphArcsReversed(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_GRAPH* CMRseymourCograph(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourCographSizeForest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_GRAPH_EDGE* CMRseymourCographForest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourCographSizeCoforest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_GRAPH_EDGE* CMRseymourCographCoforest(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
bool* CMRseymourCographArcsReversed(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourNumPivots(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t* CMRseymourPivotRows(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t* CMRseymourPivotColumns(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
size_t CMRseymourGetUsed(
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_ERROR CMRseymourPrint(
  CMR* cmr,                 
  CMR_SEYMOUR_NODE* node,   
  FILE* stream,             
  bool printChildren,       
  bool printParentElements, 
  bool printMatrices,       
  bool printGraphs,         
  bool printReductions,     
  bool printPivots          
);
 
CMR_EXPORT
CMR_ERROR CMRseymourCapture(
  CMR* cmr,             
  CMR_SEYMOUR_NODE* node  
);
 
CMR_EXPORT
CMR_ERROR CMRseymourRelease(
  CMR* cmr,                 
  CMR_SEYMOUR_NODE** pnode  
);
 
CMR_EXPORT
CMR_ERROR CMRseymourCreate(
  CMR* cmr,                 
  CMR_SEYMOUR_NODE** pnode, 
  bool isTernary,           
  CMR_CHRMAT* matrix,       
  bool copyMatrix           
);
 
CMR_EXPORT
CMR_ERROR CMRseymourCloneUnknown(
  CMR* cmr,                 
  CMR_SEYMOUR_NODE* node,   
  CMR_SEYMOUR_NODE** pclone 
);
 
CMR_EXPORT
CMR_ERROR CMRseymourCloneSubtrees(CMR* cmr, size_t numSubtrees, CMR_SEYMOUR_NODE** subtreeRoots,
  CMR_SEYMOUR_NODE** clonedSubtrees);
 
#ifdef __cplusplus
}
#endif
 
#endif /* CMR_SEYMOUR_H */