CMR
1.3.0

#include <cmr/graphic.h>
#include "env_internal.h"
#include "matrix_internal.h"
#include "one_sum.h"
#include "heap.h"
#include "sort.h"
#include "hereditary_property.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
Classes  
struct  DijkstraNodeData 
Node information for shortestpath computation in CMRcomputeRepresentationMatrix(). More...  
struct  DecNodeData 
struct  DecEdgeData 
struct  DEC_MEMBER_DATA 
struct  DecRowData 
struct  DecColumnData 
struct  Dec 
struct  _PathEdge 
Additional information specific to a path edge. More...  
struct  _ReducedMember 
Additional member information specfic to a given path. More...  
struct  _ReducedComponent 
A component of the reduced decomposition. More...  
struct  MemberInfo 
Additional information for each member (specific to a new column). More...  
struct  DEC_NEWCOLUMN 
Information for adding a new column. More...  
Macros  
#define  SWAP_INTS(a, b) 
Typedefs  
typedef size_t  DEC_EDGE 
Type for refering to a decomposition edge. More...  
typedef size_t  DEC_NODE 
Type for refering to a decomposition node. More...  
typedef size_t  DEC_MEMBER 
Type for refering to a decomposition member. More...  
typedef struct _PathEdge  PathEdge 
Additional information specific to a path edge. More...  
typedef struct _ReducedMember  ReducedMember 
Additional member information specfic to a given path. More...  
typedef struct _ReducedComponent  ReducedComponent 
A component of the reduced decomposition. More...  
Enumerations  
enum  DIJKSTRA_STAGE { UNKNOWN = 0 , SEEN = 1 , COMPLETED = 2 , BASIC = 3 , UNKNOWN = 0 , SEEN = 1 , COMPLETED = 2 , BASIC = 3 } 
enum  DEC_MEMBER_TYPE { DEC_MEMBER_TYPE_INVALID = 0 , DEC_MEMBER_TYPE_PARALLEL = 1 , DEC_MEMBER_TYPE_SERIES = 2 , DEC_MEMBER_TYPE_RIGID = 3 , DEC_MEMBER_TYPE_LOOP = 4 } 
enum  Type { TYPE_CYCLE_CHILD = 1 , TYPE_SINGLE_CHILD = 2 , TYPE_DOUBLE_CHILD = 3 , TYPE_ROOT = 4 } 
Functions  
CMR_ERROR  CMRstatsGraphicInit (CMR_GRAPHIC_STATISTICS *stats) 
Initializes all statistics for graphicness computations. More...  
CMR_ERROR  CMRstatsGraphicPrint (FILE *stream, CMR_GRAPHIC_STATISTICS *stats, const char *prefix) 
Prints statistics for graphicness computations. More...  
CMR_ERROR  CMRcomputeRepresentationMatrix (CMR *cmr, CMR_GRAPH *digraph, bool ternary, CMR_CHRMAT **ptranspose, bool *arcsReversed, int numForestArcs, CMR_GRAPH_EDGE *forestArcs, int numCoforestArcs, CMR_GRAPH_EDGE *coforestArcs, bool *pisCorrectForest) 
Computes the network or graphic matrix of a given (di)graph \( D = (V,A) \). More...  
CMR_ERROR  CMRcomputeGraphicMatrix (CMR *cmr, CMR_GRAPH *graph, CMR_CHRMAT **pmatrix, CMR_CHRMAT **ptranspose, int numForestEdges, CMR_GRAPH_EDGE *forestEdges, int numCoforestEdges, CMR_GRAPH_EDGE *coforestEdges, bool *pisCorrectForest) 
Computes the graphic matrix of a given graph \( G = (V,E) \). More...  
static const char *  memberTypeString (DEC_MEMBER_TYPE type) 
static bool  isRepresentativeMember (Dec *dec, DEC_MEMBER member) 
Returns true if and only member is a representative member. More...  
static DEC_MEMBER  findMember (Dec *dec, DEC_MEMBER member) 
Returns the representative member of member . More...  
static DEC_MEMBER  findMemberParent (Dec *dec, DEC_MEMBER member) 
Returns the representative of the parent member of member . More...  
static DEC_MEMBER  findEdgeMember (Dec *dec, DEC_EDGE edge) 
Returns the representative member of edge . More...  
static DEC_NODE  findNode (Dec *dec, DEC_NODE node) 
Returns the representative node of node . More...  
static DEC_NODE  findEdgeTail (Dec *dec, DEC_EDGE edge) 
Returns the representative node of the tail of edge . More...  
static DEC_NODE  findEdgeHead (Dec *dec, DEC_EDGE edge) 
Returns the representative node of the head of edge . More...  
static CMR_ERROR  createNode (Dec *dec, DEC_NODE *pnode) 
Creates a node for some rigid member of the decomposition dec . More...  
static CMR_ERROR  addEdgeToMembersEdgeList (Dec *dec, DEC_EDGE edge) 
Adds edge to the edge list of its member. More...  
static CMR_ERROR  removeEdgeFromMembersEdgeList (Dec *dec, DEC_EDGE edge) 
Removes edge from the edge list of its member. More...  
static CMR_ERROR  replaceEdgeInMembersEdgeList (Dec *dec, DEC_EDGE oldEdge, DEC_EDGE newEdge) 
Replaced oldEdge in its member by newEdge . More...  
static CMR_ERROR  createEdge (Dec *dec, DEC_MEMBER member, DEC_EDGE *pedge) 
Creates a new edge in member . More...  
static CMR_ERROR  createMarkerEdgePair (Dec *dec, DEC_MEMBER parentMember, DEC_EDGE *pMarkerOfParent, DEC_NODE markerOfParentTail, DEC_NODE markerOfParentHead, DEC_MEMBER childMember, DEC_EDGE *pMarkerToParent, DEC_NODE markerToParentTail, DEC_NODE markerToParentHead) 
Creates a pair of marker edges for linking parent parentMember to child childMember . More...  
static CMR_ERROR  createMember (Dec *dec, DEC_MEMBER_TYPE type, DEC_MEMBER *pmember) 
Creates a new member. More...  
CMR_ERROR  decCreate (CMR *cmr, Dec **pdec, size_t memEdges, size_t memNodes, size_t memMembers, size_t memRows, size_t memColumns) 
Creates an empty decomposition. More...  
CMR_ERROR  decFree (Dec **pdec) 
Frees the decomposition *pdec . More...  
static CMR_ERROR  decToGraph (Dec *dec, CMR_GRAPH *graph, bool merge, CMR_GRAPH_EDGE *forestEdges, CMR_GRAPH_EDGE *coforestEdges, CMR_ELEMENT *edgeElements) 
Creates a graph represented by given decomposition. More...  
static void  edgeToDot (FILE *stream, Dec *dec, DEC_MEMBER member, DEC_EDGE edge, int u, int v, bool red) 
CMR_ERROR  CMRdecToDot (Dec *dec, FILE *stream, bool *edgesHighlighted) 
Visualizes a decomposition in dot format. More...  
static void  debugDot (Dec *dec, DEC_NEWCOLUMN *newcolumn) 
CMR_ERROR  newcolumnCreate (CMR *cmr, DEC_NEWCOLUMN **pnewcolumn) 
Creates a DEC_NEWCOLUMN structure. More...  
CMR_ERROR  newcolumnFree (CMR *cmr, DEC_NEWCOLUMN **pnewcolumn) 
Frees a DEC_NEWCOLUMN structure. More...  
static CMR_ERROR  removeAllPathEdges (Dec *dec, DEC_NEWCOLUMN *newcolumn) 
Removes all path edges. More...  
static CMR_ERROR  initializeNewColumn (Dec *dec, DEC_NEWCOLUMN *newcolumn) 
Initializes a DEC_NEWCOLUMN structure in order to check for a column. More...  
static CMR_ERROR  parallelParentChildCheckMember (Dec *dec, DEC_MEMBER member, DEC_MEMBER childMember) 
Ensures that the child marker in member for childMember is not parallel to the parent marker of member . More...  
static CMR_ERROR  parallelParentChildCheckReducedMembers (Dec *dec, size_t *entryRows, size_t numEntries) 
Ensures that no child marker in the reduced decomposition is parallel to the parent marker. More...  
static CMR_ERROR  createReducedMembers (Dec *dec, DEC_NEWCOLUMN *newcolumn, DEC_MEMBER member, ReducedMember **preducedMember) 
Creates, if necessary, the reduced member for member and calls itself for the parent. More...  
static CMR_ERROR  computeReducedDecomposition (Dec *dec, DEC_NEWCOLUMN *newcolumn, size_t *entryRows, size_t numEntries) 
Computes the reduced decomposition. More...  
static CMR_ERROR  createPathEdge (Dec *dec, DEC_NEWCOLUMN *newcolumn, DEC_EDGE edge, ReducedMember *reducedMember) 
Creates a path edge structure. More...  
static CMR_ERROR  completeReducedDecomposition (Dec *dec, DEC_NEWCOLUMN *newcolumn, size_t *rows, size_t numRows) 
Creates members and reduced members of new edges. More...  
static CMR_ERROR  createReducedDecompositionPathEdges (Dec *dec, DEC_NEWCOLUMN *newcolumn, size_t *rows, size_t numRows) 
Creates path edges in reduced decomposition. More...  
static CMR_ERROR  countChildrenTypes (Dec *dec, ReducedMember *reducedMember, int *pNumOneEnd, int *pNumTwoEnds, DEC_EDGE childMarkerEdges[2]) 
Count the number of children of a reduced member having certain types. More...  
static CMR_ERROR  determineTypeParallel (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int numOneEnd, int numTwoEnds, DEC_EDGE childMarkerEdges[2], int depth) 
Determines the type of a parallel member. More...  
static CMR_ERROR  determineTypeSeries (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int numOneEnd, int numTwoEnds, DEC_EDGE childMarkerEdges[2], int depth) 
Determines the type of a series member. More...  
static CMR_ERROR  determineTypeRigid (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int numOneEnd, int numTwoEnds, DEC_EDGE childMarkerEdges[2], int depth) 
Determines the type of a rigid member. More...  
static CMR_ERROR  determineTypes (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int depth) 
Determines the type of a member and all its children in the reduced decomposition. More...  
CMR_ERROR  addColumnCheck (Dec *dec, DEC_NEWCOLUMN *newcolumn, size_t *rows, size_t numRows) 
Checks if a new column can be added to the decomposition. More...  
static CMR_ERROR  addTerminal (Dec *dec, ReducedComponent *reducedComponent, DEC_MEMBER member, DEC_NODE node) 
Add a terminal of a reduced component. More...  
static CMR_ERROR  moveReducedRoot (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent) 
Moves the reduced root upwards as long as it has a TYPE_DOUBLE_CHILD child. More...  
static CMR_ERROR  setEdgeNodes (Dec *dec, DEC_EDGE edge, DEC_NODE tail, DEC_NODE head) 
Sets the tail/head nodes of a edge to tail and head , respectively. More...  
static CMR_ERROR  mergeMemberIntoParent (Dec *dec, DEC_MEMBER member, bool headToHead) 
Merges member into its parent. More...  
static CMR_ERROR  createParallelNodes (Dec *dec, DEC_MEMBER member) 
Create nodes of a parallel member. More...  
static CMR_ERROR  splitParallel (Dec *dec, DEC_MEMBER parallel, DEC_EDGE edge1, DEC_EDGE edge2, DEC_MEMBER *pChildParallel) 
Splits a parallel member into two parallel members joined via a series member. More...  
static CMR_ERROR  addColumnProcessParallel (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int depth) 
Processes a parallel member when adding a column. More...  
static void  flipEdge (Dec *dec, DEC_EDGE edge) 
static CMR_ERROR  addColumnProcessRigid (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int depth) 
Processes a rigid member when adding a column. More...  
static CMR_ERROR  createEdgeParallel (Dec *dec, DEC_EDGE edge, DEC_MEMBER *pNewParallel) 
Replaces an edge by a parallel containing it. More...  
static CMR_ERROR  splitSeries (Dec *dec, DEC_MEMBER member, bool *edgesPredicate, bool predicateValue, DEC_EDGE *pRepresentativeEdge, DEC_MEMBER *pNewParallel, DEC_MEMBER *pNewSeries) 
Splits series member into two, connecting them via a parallel. More...  
static CMR_ERROR  addColumnProcessSeries (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int depth) 
Processes a series member when adding a column. More...  
static CMR_ERROR  addColumnProcessComponent (Dec *dec, DEC_NEWCOLUMN *newcolumn, ReducedComponent *reducedComponent, ReducedMember *reducedMember, int depth) 
Processes a component of a reduced decomposition before the actual modification. More...  
static CMR_ERROR  doReorderComponent (Dec *dec, DEC_MEMBER member, DEC_MEMBER newParent, DEC_EDGE newMarkerToParent, DEC_EDGE markerOfNewParent) 
Recursive method to reorder a member by making newParent the new parent. More...  
static CMR_ERROR  reorderComponent (Dec *dec, DEC_MEMBER newRoot) 
Reorders a component, making newRoot the new root. More...  
CMR_ERROR  addColumnApply (Dec *dec, DEC_NEWCOLUMN *newcolumn, size_t column, size_t *rows, size_t numRows) 
Actually adds a column with ones in rows , using information from newcolumn . More...  
static CMR_ERROR  cographicnessTest (CMR *cmr, CMR_CHRMAT *matrix, void *data, bool *pisCographic, CMR_SUBMAT **psubmatrix, double timeLimit) 
CMR_ERROR  CMRtestCographicMatrix (CMR *cmr, CMR_CHRMAT *matrix, bool *pisCographic, CMR_GRAPH **pgraph, CMR_GRAPH_EDGE **pforestEdges, CMR_GRAPH_EDGE **pcoforestEdges, CMR_SUBMAT **psubmatrix, CMR_GRAPHIC_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a cographic matrix. More...  
CMR_ERROR  CMRtestBinaryGraphicColumnSubmatrixGreedy (CMR *cmr, CMR_CHRMAT *transpose, size_t *orderedColumns, CMR_SUBMAT **psubmatrix) 
CMR_ERROR  CMRtestGraphicMatrix (CMR *cmr, CMR_CHRMAT *matrix, bool *pisGraphic, CMR_GRAPH **pgraph, CMR_GRAPH_EDGE **pforestEdges, CMR_GRAPH_EDGE **pcoforestEdges, CMR_SUBMAT **psubmatrix, CMR_GRAPHIC_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a graphic matrix. More...  
#define SWAP_INTS  (  a,  
b  
) 
typedef size_t DEC_EDGE 
Type for refering to a decomposition edge.
typedef size_t DEC_MEMBER 
Type for refering to a decomposition member.
typedef size_t DEC_NODE 
Type for refering to a decomposition node.
typedef struct _ReducedComponent ReducedComponent 
A component of the reduced decomposition.
typedef struct _ReducedMember ReducedMember 
Additional member information specfic to a given path.
TODO: Maybe add parent reduced member as well, so we don't have to go via the membersToReducedMembers array.
enum DEC_MEMBER_TYPE 
enum DIJKSTRA_STAGE 
enum Type 
CMR_ERROR addColumnApply  (  Dec *  dec, 
DEC_NEWCOLUMN *  newcolumn,  
size_t  column,  
size_t *  rows,  
size_t  numRows  
) 
Actually adds a column with ones in rows
, using information from newcolumn
.
dec  Decomposition. 
newcolumn  newcolumn. 
column  Index of new column to be added. 
rows  Array of rows with 1entry in this column. 
numRows  Length of rows . 
CMR_ERROR addColumnCheck  (  Dec *  dec, 
DEC_NEWCOLUMN *  newcolumn,  
size_t *  rows,  
size_t  numRows  
) 
Checks if a new column can be added to the decomposition.
Information necessary for carrying out the addition is stored in newcolumn
.
dec  Decomposition. 
newcolumn  newcolumn. 
rows  Array of rows (with 1entry in this column). 
numRows  Length of rows . 

static 
Processes a component of a reduced decomposition before the actual modification.
Processes the reduced members in depthfirst search manner and does the following:
dec  Decomposition. 
newcolumn  newcolumn structure. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
depth  Depth of member in reduced tdecomposition. 

static 
Processes a parallel member when adding a column.
dec  Decomposition. 
newcolumn  newcolumn structure. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
depth  Depth of this member in reduced tdecomposition. 

static 
Processes a rigid member when adding a column.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
depth  Depth of this member in reduced tdecomposition. 

static 
Processes a series member when adding a column.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
depth  Depth of this member in reduced tdecomposition. 
Adds edge
to the edge list of its member.
dec  Decomposition. 
edge  Edge to be added. 

static 
Add a terminal of a reduced component.
dec  Decomposition. 
reducedComponent  Reduced component. 
member  New terminal member. 
node  New terminal node. 
CMR_ERROR CMRcomputeGraphicMatrix  (  CMR *  cmr, 
CMR_GRAPH *  graph,  
CMR_CHRMAT **  pmatrix,  
CMR_CHRMAT **  ptranspose,  
int  numForestEdges,  
CMR_GRAPH_EDGE *  forestEdges,  
int  numCoforestEdges,  
CMR_GRAPH_EDGE *  coforestEdges,  
bool *  pisCorrectForest  
) 
Computes the graphic matrix of a given graph \( G = (V,E) \).
Computes the graphic matrix \( M := M(G,T) \) for given \( G \) and optionally given spanning forest \( T \subseteq E \). If \( T \) is not given, an arbitrary spanning forest of \( G \) is used. If forestEdges
is NULL
, an arbitrary spanning forest \( T \) of \( G \) is computed. The ordering of the columns can be specified via coforestEdges
.
forestEdges
is a correct spanning forest. Whether this was the case is indicated via *pisCorrectForest
. cmr  CMR environment. 
graph  Graph \( G = (V,E) \). 
pmatrix  Pointer for storing \( M \) (may be NULL ). 
ptranspose  Pointer for storing \( M^{\mathsf{T}} \) (may be NULL ). 
numForestEdges  \( T \) (0 if forestEdges is NULL ). 
forestEdges  \( T \), ordered by the rows of \( M \) (may be NULL ). 
numCoforestEdges  \( E \setminus T \) (0 if coforestEdges is NULL ). 
coforestEdges  \( E \setminus T \), ordered by the columns of \( M \) (may be NULL ). 
pisCorrectForest  Pointer for storing whether forestEdges is a spanning forest of \( G \) (may be NULL ). 
CMR_ERROR CMRcomputeRepresentationMatrix  (  CMR *  cmr, 
CMR_GRAPH *  digraph,  
bool  ternary,  
CMR_CHRMAT **  ptranspose,  
bool *  arcsReversed,  
int  numForestArcs,  
CMR_GRAPH_EDGE *  forestArcs,  
int  numCoforestArcs,  
CMR_GRAPH_EDGE *  coforestArcs,  
bool *  pisCorrectForest  
) 
Computes the network or graphic matrix of a given (di)graph \( D = (V,A) \).
Computes the network matrix \( M := M(D,T) \) for given \( D \) and optionally given (directed) spanning forest \( T \subseteq A \) or the support matrix of \( M(D,T) \). If \( T \) is not given, an arbitrary (directed) spanning forest of \( D \) is used. The direction of the edges is that of digraph
, but may be flipped by specifying arcsReversed
. If forestArcs
is NULL
, an arbitrary (directed) spanning forest \( T \) of \( D \) is computed. The ordering of the columns can be specified via coforestArcs
.
forestArcs
is a correct (directed) spanning forest. Whether this was the case is indicated via *pisCorrectForest
. cmr  CMR environment. 
digraph  Digraph \( D = (V,A) \). 
ternary  Whether we need to compute correct signs. 
ptranspose  Pointer for storing \( M^{\mathsf{T}} \) (may be NULL ). 
arcsReversed  Indicates, for each edge \( \{u, v\}\), whether we consider \( (u, v)\) (if false ) or \( (v,u)\) (if true ). 
numForestArcs  \( T \) (0 if forestArcs is NULL ). 
forestArcs  \( T \), ordered by the rows of \( M \) (may be NULL ). 
numCoforestArcs  \( A \setminus T \) (0 if coforestArcs is NULL ). 
coforestArcs  \( A \setminus T \), ordered by the columns of \( M \) (may be NULL ). 
pisCorrectForest  Pointer for storing whether forestArcs is a (directed) spanning forest of \( D \)'s underlying undirected graph (may be NULL ). 
Visualizes a decomposition in dot
format.
Writes decomposition to a dot file in the current directory.
The file name is decNUMBER.dot where NUMBER is increased for each call and reset for a new decomposition.
dec  Decomposition. 
stream  Stream to write to. 
edgesHighlighted  Indicator for edges to be highlighted. 
CMR_ERROR CMRstatsGraphicInit  (  CMR_GRAPHIC_STATISTICS *  stats  ) 
Initializes all statistics for graphicness computations.
stats  Pointer to statistics. 
CMR_ERROR CMRstatsGraphicPrint  (  FILE *  stream, 
CMR_GRAPHIC_STATISTICS *  stats,  
const char *  prefix  
) 
Prints statistics for graphicness computations.
stream  File stream to print to. 
stats  Pointer to statistics. 
prefix  Prefix string to prepend to each printed line (may be NULL ). 
CMR_ERROR CMRtestBinaryGraphicColumnSubmatrixGreedy  (  CMR *  cmr, 
CMR_CHRMAT *  transpose,  
size_t *  orderedColumns,  
CMR_SUBMAT **  psubmatrix  
) 
CMR_ERROR CMRtestCographicMatrix  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisCographic,  
CMR_GRAPH **  pgraph,  
CMR_GRAPH_EDGE **  pforestEdges,  
CMR_GRAPH_EDGE **  pcoforestEdges,  
CMR_SUBMAT **  psubmatrix,  
CMR_GRAPHIC_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a cographic matrix.
Tests if \( M = M(G,T)^{\mathsf{T}} \) for some graph \( G = (V,E) \) and some spanning forest \( T \subseteq E \) of \( G \) and sets *pisCographic
accordingly.
If \( M \) is a cographic matrix and pgraph
!= NULL
, then one possible graph \( G \) is computed and stored in *pgraph
. The caller must release its memory via CMRgraphFree. If in addition to pgraph
also pforestEdges
!= NULL
(resp. pcoforestEdges
!= NULL
), then a corresponding spanning forest \( T \) (resp. its complement \( E \setminus T \)) is stored in *pforestEdges
(resp. *pcoforestEdges
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \) 
pisCographic  Returns true if and only if \( M \) is a cographic matrix. 
pgraph  Pointer for storing the graph \( G \) (if \( M \) is graphic). 
pforestEdges  Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic). 
pcoforestEdges  Pointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic). 
psubmatrix  Pointer for storing a minimal nongraphic submatrix (if \( M \) is not graphic). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 
CMR_ERROR CMRtestGraphicMatrix  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisGraphic,  
CMR_GRAPH **  pgraph,  
CMR_GRAPH_EDGE **  pforestEdges,  
CMR_GRAPH_EDGE **  pcoforestEdges,  
CMR_SUBMAT **  psubmatrix,  
CMR_GRAPHIC_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a graphic matrix.
Tests if \( M = M(G,T) \) for some graph \( G = (V,E) \) and some spanning forest \( T \subseteq E \) of \( G \) and sets *pisGraphic
accordingly.
If \( M \) is a graphic matrix and pgraph
!= NULL
, then one possible graph \( G \) is computed and stored in *pgraph
. The caller must release its memory via CMRgraphFree. If in addition to pgraph
also pforestEdges
!= NULL
(resp. pcoforestEdges
!= NULL
), then a corresponding spanning forest \( T \) (resp. its complement \( E \setminus T \)) is stored in *pforestEdges
(resp. *pcoforestEdges
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \). 
pisGraphic  Pointer for storing true if and only if \( M \) is a graphic matrix. 
pgraph  Pointer for storing the graph \( G \) (if \( M \) is graphic). 
pforestEdges  Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic). 
pcoforestEdges  Pointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic). 
psubmatrix  Pointer for storing a minimal nongraphic submatrix (if \( M \) is not graphic). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 

static 
cmr  CMR environment. 
matrix  Some matrix to be tested for cographicness. 
data  Additional data (must be NULL ). 
pisCographic  Pointer for storing whether matrix is cographic. 
psubmatrix  Pointer for storing a proper noncographic submatrix of matrix . 
timeLimit  Time limit to impose. 

static 
Creates members and reduced members of new edges.
dec  Decomposition. 
newcolumn  newcolumn. 
rows  Array of rows (of new column's entries). 
numRows  Length of rows . 

static 
Computes the reduced decomposition.
dec  Decomposition. 
newcolumn  newcolumn. 
entryRows  Array of rows of new column's enries. 
numEntries  Length of entryRows . 

static 
Count the number of children of a reduced member having certain types.
dec  Decomposition. 
reducedMember  Reduced member. 
pNumOneEnd  Number of children that (recursively) must contain one path end. 
pNumTwoEnds  Number of children that (recursively) must contain two path ends. 
childMarkerEdges  Array for storing a child marker edges containing one/two path ends. 

static 
Creates a new edge in member
.
dec  Decomposition. 
member  Member this edge belongs to. 
pedge  Pointer for storing the new edge. 

static 
Replaces an edge by a parallel containing it.
The given member should have at least two edges.
dec  Decomposition. 
edge  Edge to be replaced by a parallel containing that edge. 
pNewParallel  Pointer for storing the new parallel. 

static 
Creates a pair of marker edges for linking parent parentMember
to child childMember
.
dec  Decomposition. 
parentMember  Parent member. 
pMarkerOfParent  Pointer for storing the new child marker in the parent. 
markerOfParentTail  Tail node of this *pChildMarker . 
markerOfParentHead  Head node of this *pChildMarker . 
childMember  Child member. 
pMarkerToParent  Pointer for storing the new parent marker in the child. 
markerToParentTail  Tail node of this *pParentMarker . 
markerToParentHead  Head node of this *pParentMarker . 

static 
Creates a new member.
dec  Decomposition. 
type  Type of member. 
pmember  Pointer for storing the new member. 
Creates a node for some rigid member of the decomposition dec
.
dec  Decomposition. 
pnode  Pointer for storing new node. 

static 
Create nodes of a parallel member.
dec  Decomposition. 
member  A parallel member. 

static 
Creates a path edge structure.
Adds it to the singlylinked path edge list of reducedMember
and to the overall singlylinked path edge list. The created PathEdge can be accessed via ReducedMember::firstPathEdge.
dec  Decomposition. 
newcolumn  new column. 
edge  The edge it refers to. 
reducedMember  Reduced member this path edge belongs to. 

static 
Creates path edges in reduced decomposition.
dec  Decomposition. 
newcolumn  newcolumn. 
rows  Array of rows (of new column's enries). 
numRows  Length of rows . 

static 
Creates, if necessary, the reduced member for member
and calls itself for the parent.
dec  Decomposition. 
newcolumn  newcolumn. 
member  Member to create reduced member for. 
preducedMember  Pointer for storing the created reduced member. 

inlinestatic 
dec  Decomposition. 
newcolumn  new column. 
CMR_ERROR decCreate  (  CMR *  cmr, 
Dec **  pdec,  
size_t  memEdges,  
size_t  memNodes,  
size_t  memMembers,  
size_t  memRows,  
size_t  memColumns  
) 
Creates an empty decomposition.
cmr  CMR environment. 
pdec  Pointer to new decomposition. . 
memEdges  Initial memory for edges of the decomposition. 
memNodes  Initial memory for nodes of the decomposition. 
memMembers  Initial memory for members of the decomposition. 
memRows  Initial memory for rows. 
memColumns  Initial memory for columns. 
Frees the decomposition *pdec
.
pdec  Pointer to decomposition. 

static 
Creates a graph represented by given decomposition.
dec  Decomposition. 
graph  Graph to be filled. 
merge  Merge and remove corresponding parent and child markers. 
forestEdges  If not NULL , the edges of a spanning tree are stored here. 
coforestEdges  If not NULL , the nonbasis edges are stored here. 
edgeElements  If not NULL , the elements for each edge are stored here. 

static 
Determines the type of a parallel member.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
numOneEnd  Number of child markers containing one path end. 
numTwoEnds  Number of child markers containing two path ends. 
childMarkerEdges  Marker edges of children containing one/two path ends. 
depth  Depth of member in reduced decomposition. 

static 
Determines the type of a rigid member.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
numOneEnd  Number of child markers containing one path end. 
numTwoEnds  Number of child markers containing two path ends. 
childMarkerEdges  Marker edges of children containing one/two path ends. 
depth  Depth of member in reduced tdecomposition. 

static 
Determines the type of a member and all its children in the reduced decomposition.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
depth  Depth of member in reduced tdecomposition. 

static 
Determines the type of a series member.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
reducedMember  Reduced member. 
numOneEnd  Number of child markers containing one path end. 
numTwoEnds  Number of child markers containing two path ends. 
childMarkerEdges  Marker edges of children containing one/two path ends. 
depth  Depth of member in reduced tdecomposition. 

static 
Recursive method to reorder a member by making newParent
the new parent.
dec  Decomposition. 
member  Member to be processed. 
newParent  New parent of member . 
newMarkerToParent  New marker edge linked to new parent of member . 
markerOfNewParent  Counterpart to newMarkerToParent . 

static 
Prints an edge in dot
format to stream
.
stream  File stream. 
dec  Decomposition. 
member  Member this edge belongs to. 
edge  Edge. 
u  First node. 
v  Second node. 
red  Whether to color it red. 
Returns the representative node of the head of edge
.
dec  Decomposition. 
edge  Edge. 

inlinestatic 
Returns the representative member of edge
.
dec  Decomposition. 
edge  Edge. 
Returns the representative node of the tail of edge
.
dec  Decomposition. 
edge  Edge. 

static 
Returns the representative member of member
.
dec  Decomposition. 
member  Member for which the representative shall be returned. 

inlinestatic 
Returns the representative of the parent member of member
.
Assumes that member
is a representative member.
dec  Decomposition. 
member  Member whose parent shall be returned. 
Returns the representative node of node
.
Assumes node
is indeed a node, i.e., not 1.
dec  tdecomposition. 
edge  edge. 

static 
Initializes a DEC_NEWCOLUMN structure in order to check for a column.
dec  Decomposition. 
newcolumn  newcolumn. 

inlinestatic 
Returns true
if and only member
is a representative member.
dec  Decomposition. 
member  Member of dec . 

inlinestatic 

static 
Merges member
into its parent.
If headToHead
is true
, then the two head nodes (and the two tail nodes) are identified with each other. Otherwise, a head is identified with a tail.
dec  Decomposition. 
member  Reduced component. 
headToHead  Whether the heads of the edges shall be joined. 

static 
Moves the reduced root upwards as long as it has a TYPE_DOUBLE_CHILD child.
dec  Decomposition. 
newcolumn  newcolumn. 
reducedComponent  Reduced component. 
CMR_ERROR newcolumnCreate  (  CMR *  cmr, 
DEC_NEWCOLUMN **  pnewcolumn  
) 
Creates a DEC_NEWCOLUMN structure.
cmr  CMR environment. 
pnewcolumn  Pointer for storing the newcolumn structure. 
CMR_ERROR newcolumnFree  (  CMR *  cmr, 
DEC_NEWCOLUMN **  pnewcolumn  
) 
Frees a DEC_NEWCOLUMN structure.
cmr  CMR environment. 
pnewcolumn  Pointer to newcolumn structure. 

static 
Ensures that the child marker in member
for childMember
is not parallel to the parent marker of member
.
Note that this can only happen when a component is reordered (receiving a new root) because reduced components shall be joined.
dec  Decomposition. 
member  Parent of childMember . 
childMember  Child member of member . 

static 
Ensures that no child marker in the reduced decomposition is parallel to the parent marker.
dec  Decomposition. 
entryRows  Array of rows of new column's enries. 
numEntries  Length of entryRows . 

static 
Removes all path edges.
dec  Decomposition. 
newcolumn  new column. 
Removes edge
from the edge list of its member.
dec  Decomposition. 
edge  Edge to be added. 

static 
Reorders a component, making newRoot
the new root.
dec  Decomposition. 
newRoot  The new root of the component. 

static 
Replaced oldEdge
in its member by newEdge
.
Assumes that newEdge
has the same member but is not in its edge list.
dec  Decomposition. 
oldEdge  Edge to be removed. 
newEdge  Edge to be added. 
Sets the tail/head nodes of a edge
to tail
and head
, respectively.
dec  Decomposition. 
edge  Reduced component. 
tail  New tail node. 
head  New head node. 

static 
Splits a parallel member into two parallel members joined via a series member.
dec  Decomposition. 
parallel  A parallel member. 
edge1  First edge to be moved into the child parallel. 
edge2  Second edge to be moved into the child parallel. 
pChildParallel  Pointer to storing the newly created child parallel. 

static 
Splits series member into two, connecting them via a parallel.
Takes all edges of the series member
for which edgesPredicate
is the same as predicateValue
.
dec  Decomposition. 
member  Series member to be split. 
edgesPredicate  Map from edges to predicate. 
predicateValue  Value of predicate. 
pRepresentativeEdge  Pointer for storing the child marker edge that links to new parallel. 
pNewParallel  Pointer for storing the new parallel. 
pNewSeries  Pointer for storing the new parallel. 