seymour.h File Reference

Functionality for Seymour decomposition. More...

#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>

Go to the source code of this file.

Classes
struct	CMR_SEYMOUR_PARAMS
	Parameters for Seymour decomposition algorithm. More...
struct	CMR_SEYMOUR_STATS
	Statistics for Seymour decomposition algorithm. More...

Typedefs
typedef struct _CMR_SEYMOUR_NODE	CMR_SEYMOUR_NODE

Enumerations
enum	CMR_SEYMOUR_THREESUM_FLAG {   CMR_SEYMOUR_THREESUM_FLAG_NO_PIVOTS = 0 , CMR_SEYMOUR_THREESUM_FLAG_DISTRIBUTED_RANKS = 1 , CMR_SEYMOUR_THREESUM_FLAG_CONCENTRATED_RANK = 2 , CMR_SEYMOUR_THREESUM_FLAG_FIRST_WIDE = 4 ,   CMR_SEYMOUR_THREESUM_FLAG_FIRST_TALL = 8 , CMR_SEYMOUR_THREESUM_FLAG_FIRST_MIXED = 64 , CMR_SEYMOUR_THREESUM_FLAG_FIRST_ALLREPR = 128 , CMR_SEYMOUR_THREESUM_FLAG_SECOND_WIDE = 16 ,   CMR_SEYMOUR_THREESUM_FLAG_SECOND_TALL = 32 , CMR_SEYMOUR_THREESUM_FLAG_SECOND_MIXED = 256 , CMR_SEYMOUR_THREESUM_FLAG_SECOND_ALLREPR = 512 , CMR_SEYMOUR_THREESUM_FLAG_SEYMOUR ,   CMR_SEYMOUR_THREESUM_FLAG_TRUEMPER }
	Flags that indicate the type of \( 3 \)-separation. More...
enum	CMR_SEYMOUR_NODE_TYPE {   CMR_SEYMOUR_NODE_TYPE_IRREGULAR = -1 , CMR_SEYMOUR_NODE_TYPE_UNKNOWN = 0 , CMR_SEYMOUR_NODE_TYPE_ONE_SUM = 1 , CMR_SEYMOUR_NODE_TYPE_TWO_SUM = 2 ,   CMR_SEYMOUR_NODE_TYPE_THREE_SUM = 3 , CMR_SEYMOUR_NODE_TYPE_SERIES_PARALLEL = 4 , CMR_SEYMOUR_NODE_TYPE_PIVOTS = 5 , CMR_SEYMOUR_NODE_TYPE_GRAPH = 6 ,   CMR_SEYMOUR_NODE_TYPE_COGRAPH = 7 , CMR_SEYMOUR_NODE_TYPE_PLANAR = 8 , CMR_SEYMOUR_NODE_TYPE_R10 = 9 }

Functions
CMR_EXPORT CMR_ERROR	CMRseymourParamsInit (CMR_SEYMOUR_PARAMS *params)
	Initializes the default parameters for regularity testing. More...
CMR_EXPORT CMR_ERROR	CMRseymourStatsInit (CMR_SEYMOUR_STATS *stats)
	Initializes all statistics for Seymour decomposition computations. More...
CMR_EXPORT CMR_ERROR	CMRseymourStatsPrint (FILE *stream, CMR_SEYMOUR_STATS *stats, const char *prefix)
	Prints statistics for Seymour decomposition computations. More...
CMR_EXPORT bool	CMRseymourIsTernary (CMR_SEYMOUR_NODE *node)
	Returns true iff the decomposition is over \( \mathbb{F}_3 \). More...
CMR_EXPORT bool	CMRseymourThreeSumDistributedRanks (CMR_SEYMOUR_NODE *node)
	Returns true iff the 3-sum decomposition node has \( 3 \)-separation with two rank-1 matrices. More...
CMR_EXPORT bool	CMRseymourThreeSumConcentratedRank (CMR_SEYMOUR_NODE *node)
	Returns true iff the 3-sum decomposition node has \( 3 \)-separation with one rank-2 matrix. More...
CMR_EXPORT bool	CMRseymourHasTranspose (CMR_SEYMOUR_NODE *node)
	Returns true iff the transposed matrix of the decomposition node dec is stored. More...
CMR_EXPORT CMR_CHRMAT *	CMRseymourGetMatrix (CMR_SEYMOUR_NODE *node)
	Returns the matrix of the decomposition node dec (or NULL if it is not stored). More...
CMR_EXPORT CMR_CHRMAT *	CMRseymourGetTranspose (CMR_SEYMOUR_NODE *node)
	Returns the transposed matrix of the decomposition node dec (or NULL if it is not stored). More...
CMR_EXPORT size_t	CMRseymourNumChildren (CMR_SEYMOUR_NODE *node)
	Returns the number of children of the decomposition node dec. More...
CMR_EXPORT CMR_SEYMOUR_NODE *	CMRseymourChild (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns a child of the decomposition node dec. More...
CMR_EXPORT CMR_SEYMOUR_NODE_TYPE	CMRseymourType (CMR_SEYMOUR_NODE *node)
	Returns the type of a decomposition node dec. More...
CMR_EXPORT size_t	CMRseymourNumMinors (CMR_SEYMOUR_NODE *node)
	Returns the number of minors of the decomposition node. More...
CMR_EXPORT CMR_MINOR *	CMRseymourMinor (CMR_SEYMOUR_NODE *node, size_t minorIndex)
	Returns a minor of the decomposition node. More...
CMR_EXPORT int8_t	CMRseymourGraphicness (CMR_SEYMOUR_NODE *node)
	Indicates graphicness/being network. More...
CMR_EXPORT int8_t	CMRseymourCographicness (CMR_SEYMOUR_NODE *node)
	Indicates cographicness/being conetwork. More...
CMR_EXPORT int8_t	CMRseymourRegularity (CMR_SEYMOUR_NODE *node)
	Indicates regularity/total unimodularity. More...
CMR_EXPORT size_t	CMRseymourNumRows (CMR_SEYMOUR_NODE *node)
	Returns the number of rows. More...
CMR_EXPORT size_t	CMRseymourNumColumns (CMR_SEYMOUR_NODE *node)
	Returns the number of columns. More...
CMR_EXPORT CMR_ELEMENT *	CMRseymourChildRowsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of rows of child childIndex to this node's elements. More...
CMR_EXPORT CMR_ELEMENT *	CMRseymourChildColumnsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of columns of child childIndex to this node's elements. More...
CMR_EXPORT CMR_GRAPH *	CMRseymourGraph (CMR_SEYMOUR_NODE *node)
	Returns the graph (if available). More...
CMR_EXPORT CMR_GRAPH_EDGE *	CMRseymourGraphForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the graph (if available). More...
CMR_EXPORT size_t	CMRseymourGraphSizeForest (CMR_SEYMOUR_NODE *dec)
	Returns the number of edges of the graph's forest (if available). More...
CMR_EXPORT CMR_GRAPH_EDGE *	CMRseymourGraphCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the graph (if available). More...
CMR_EXPORT size_t	CMRseymourGraphSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the graph's coforest (if available). More...
CMR_EXPORT bool *	CMRseymourGraphArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the graph's edges whether they must be reversed (if available). More...
CMR_EXPORT CMR_GRAPH *	CMRseymourCograph (CMR_SEYMOUR_NODE *node)
	Returns the cograph (if available). More...
CMR_EXPORT size_t	CMRseymourCographSizeForest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's forest (if available). More...
CMR_EXPORT CMR_GRAPH_EDGE *	CMRseymourCographForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the cograph (if available). More...
CMR_EXPORT size_t	CMRseymourCographSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's coforest (if available). More...
CMR_EXPORT CMR_GRAPH_EDGE *	CMRseymourCographCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the cograph (if available). More...
CMR_EXPORT bool *	CMRseymourCographArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the cograph's edges whether they must be reversed (if available). More...
CMR_EXPORT size_t	CMRseymourNumPivots (CMR_SEYMOUR_NODE *node)
	Returns the number of pivots (if available). More...
CMR_EXPORT size_t *	CMRseymourPivotRows (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot rows (if available). More...
CMR_EXPORT size_t *	CMRseymourPivotColumns (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot columns (if available). More...
CMR_EXPORT size_t	CMRseymourGetUsed (CMR_SEYMOUR_NODE *node)
	Returns node's reference counter. More...
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)
	Prints the decomposition dec to stream. More...
CMR_EXPORT CMR_ERROR	CMRseymourCapture (CMR *cmr, CMR_SEYMOUR_NODE *node)
	Increases the reference counter by 1. More...
CMR_EXPORT CMR_ERROR	CMRseymourRelease (CMR *cmr, CMR_SEYMOUR_NODE **pnode)
	Releases a decomposition node, freeing it if this was the last reference. More...
CMR_EXPORT CMR_ERROR	CMRseymourCreate (CMR *cmr, CMR_SEYMOUR_NODE **pnode, bool isTernary, CMR_CHRMAT *matrix)
	Creates an unknown decomposition node as a root. More...
CMR_EXPORT CMR_ERROR	CMRseymourCloneUnknown (CMR *cmr, CMR_SEYMOUR_NODE *node, CMR_SEYMOUR_NODE **pclone)
	Clones a decomposition node node into *pclone which represents the same matrix but has type CMR_SEYMOUR_NODE_TYPE_UNKNOWN type and no child nodes. More...
CMR_EXPORT CMR_ERROR	CMRseymourCloneSubtrees (CMR *cmr, size_t numSubtrees, CMR_SEYMOUR_NODE **subtreeRoots, CMR_SEYMOUR_NODE **clonedSubtrees)
	Clones the union of subtrees of a Seymour decomposition, returning the copies. More...

Detailed Description

Functionality for Seymour decomposition.

Author

Matthias Walter