CMR  1.3.0
Classes | Macros | Typedefs | Enumerations | Functions
graphic.c File Reference
#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 shortest-path 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)
 
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)
 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)
 Tests a matrix \( M \) for being a graphic matrix. More...
 

Macro Definition Documentation

#define SWAP_INTS (   a,
 
)
Value:
do \
{ \
int tmp = a; \
a = b; \
b = tmp; \
} \
while (false)

Typedef Documentation

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 _PathEdge PathEdge

Additional information specific to a path edge.

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.

Enumeration Type Documentation

Enumerator
DEC_MEMBER_TYPE_INVALID 
DEC_MEMBER_TYPE_PARALLEL 

Indicate a parallel member, also known as a bond.

DEC_MEMBER_TYPE_SERIES 

Indicate a series member, also known as a polygon.

DEC_MEMBER_TYPE_RIGID 

Indicate a parallel member, also known as prime.

DEC_MEMBER_TYPE_LOOP 

Indicate a loop.

Enumerator
UNKNOWN 

The node was not considered by the shortest-path, yet.

SEEN 

Some path to the node is known.

COMPLETED 

The shortest path to the node is known.

BASIC 

The rootEdge of that node belongs to the spanning forest.

UNKNOWN 

The node was not considered by the shortest-path, yet.

SEEN 

Some path to the node is known.

COMPLETED 

The shortest path to the node is known.

BASIC 

The rootEdge of that node belongs to the spanning forest.

enum Type
Enumerator
TYPE_CYCLE_CHILD 

Parent marker edge plus path edges form a cycle. If graphic, this means we can replace the child by its child marker, adding the latter to the list of path edges.

TYPE_SINGLE_CHILD 

One node of the parent marker edge is a path end. If graphic, this means that one terminal node is in this member or its children.

TYPE_DOUBLE_CHILD 

Path edges form two cycles and adding the parent marker edge yields one. If graphic, this means that both terminal nodes are in this member or its children.

TYPE_ROOT 

Root member of reduced decomposition.

Function Documentation

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.

Parameters
decDecomposition.
newcolumnnewcolumn.
columnIndex of new column to be added.
rowsArray of rows with 1-entry in this column.
numRowsLength 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.

Parameters
decDecomposition.
newcolumnnewcolumn.
rowsArray of rows (with 1-entry in this column).
numRowsLength of rows.
static CMR_ERROR addColumnProcessComponent ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  depth 
)
static

Processes a component of a reduced decomposition before the actual modification.

Processes the reduced members in depth-first search manner and does the following:

  • Series members are squeezed.
  • Terminal nodes and (reduced) members are detected.
  • Marker edges along unique path between terminal nodes are merged.
Parameters
decDecomposition.
newcolumnnew-column structure.
reducedComponentReduced component.
reducedMemberReduced member.
depthDepth of member in reduced t-decomposition.
static CMR_ERROR addColumnProcessParallel ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  depth 
)
static

Processes a parallel member when adding a column.

Parameters
decDecomposition.
newcolumnnew-column structure.
reducedComponentReduced component.
reducedMemberReduced member.
depthDepth of this member in reduced t-decomposition.
static CMR_ERROR addColumnProcessRigid ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  depth 
)
static

Processes a rigid member when adding a column.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
depthDepth of this member in reduced t-decomposition.
static CMR_ERROR addColumnProcessSeries ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  depth 
)
static

Processes a series member when adding a column.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
depthDepth of this member in reduced t-decomposition.
static CMR_ERROR addEdgeToMembersEdgeList ( Dec dec,
DEC_EDGE  edge 
)
static

Adds edge to the edge list of its member.

Parameters
decDecomposition.
edgeEdge to be added.
static CMR_ERROR addTerminal ( Dec dec,
ReducedComponent reducedComponent,
DEC_MEMBER  member,
DEC_NODE  node 
)
static

Add a terminal of a reduced component.

Parameters
decDecomposition.
reducedComponentReduced component.
memberNew terminal member.
nodeNew 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.

Note
The function computes a graphic matrix of \( G \) (and \( T \)) regardless of whether forestEdges is a correct spanning forest. Whether this was the case is indicated via *pisCorrectForest.
Parameters
cmrCMR environment.
graphGraph \( G = (V,E) \).
pmatrixPointer for storing \( M \) (may be NULL).
ptransposePointer 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).
pisCorrectForestPointer 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.

Note
The function computes a network matrix of \( D \) (and \( T \)) regardless of whether forestArcs is a correct (directed) spanning forest. Whether this was the case is indicated via *pisCorrectForest.
Parameters
cmrCMR environment.
digraphDigraph \( D = (V,A) \).
ternaryWhether we need to compute correct signs.
ptransposePointer for storing \( M^{\mathsf{T}} \) (may be NULL).
arcsReversedIndicates, 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).
pisCorrectForestPointer for storing whether forestArcs is a (directed) spanning forest of \( D \)'s underlying undirected graph (may be NULL).
CMR_ERROR CMRdecToDot ( Dec dec,
FILE *  stream,
bool *  edgesHighlighted 
)

Visualizes a decomposition in dot format.

Writes decomposition to a dot file in the current directory.

The file name is dec-NUMBER.dot where NUMBER is increased for each call and reset for a new decomposition.

Parameters
decDecomposition.
streamStream to write to.
edgesHighlightedIndicator for edges to be highlighted.
CMR_ERROR CMRstatsGraphicInit ( CMR_GRAPHIC_STATISTICS stats)

Initializes all statistics for graphicness computations.

Parameters
statsPointer to statistics.
CMR_ERROR CMRstatsGraphicPrint ( FILE *  stream,
CMR_GRAPHIC_STATISTICS stats,
const char *  prefix 
)

Prints statistics for graphicness computations.

Parameters
streamFile stream to print to.
statsPointer to statistics.
prefixPrefix 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 
)

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.

Note
Retrieval of minimal non-cographic submatrices via *psubmatrix is not implemented, yet.
Parameters
cmrCMR environment.
matrixMatrix \( M \)
pisCographicReturns true if and only if \( M \) is a cographic matrix.
pgraphPointer for storing the graph \( G \) (if \( M \) is graphic).
pforestEdgesPointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic).
pcoforestEdgesPointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic).
psubmatrixPointer for storing a minimal non-graphic submatrix (if \( M \) is not graphic).
statsPointer to statistics (may be NULL).
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 
)

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.

Note
If a column-wise representation of \( M \) is available, it is recommended to call CMRtestCographicMatrix() for that. In fact, the implementation explicitly constructs \( M^{\mathsf{T}} \) before calling this function.

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.

Note
Retrieval of minimal non-graphic submatrices via *psubmatrix is not implemented, yet.
Parameters
cmrCMR environment.
matrixMatrix \( M \).
pisGraphicPointer for storing true if and only if \( M \) is a graphic matrix.
pgraphPointer for storing the graph \( G \) (if \( M \) is graphic).
pforestEdgesPointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic).
pcoforestEdgesPointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic).
psubmatrixPointer for storing a minimal non-graphic submatrix (if \( M \) is not graphic).
statsPointer to statistics (may be NULL).
static CMR_ERROR cographicnessTest ( CMR cmr,
CMR_CHRMAT matrix,
void *  data,
bool *  pisCographic,
CMR_SUBMAT **  psubmatrix 
)
static
Parameters
cmrCMR environment.
matrixSome matrix to be tested for cographicness.
dataAdditional data (must be NULL).
pisCographicPointer for storing whether matrix is cographic.
psubmatrixPointer for storing a proper non-cographic submatrix of matrix.
static CMR_ERROR completeReducedDecomposition ( Dec dec,
DEC_NEWCOLUMN newcolumn,
size_t *  rows,
size_t  numRows 
)
static

Creates members and reduced members of new edges.

Parameters
decDecomposition.
newcolumnnewcolumn.
rowsArray of rows (of new column's entries).
numRowsLength of rows.
static CMR_ERROR computeReducedDecomposition ( Dec dec,
DEC_NEWCOLUMN newcolumn,
size_t *  entryRows,
size_t  numEntries 
)
static

Computes the reduced decomposition.

Parameters
decDecomposition.
newcolumnnewcolumn.
entryRowsArray of rows of new column's enries.
numEntriesLength of entryRows.
static CMR_ERROR countChildrenTypes ( Dec dec,
ReducedMember reducedMember,
int *  pNumOneEnd,
int *  pNumTwoEnds,
DEC_EDGE  childMarkerEdges[2] 
)
static

Count the number of children of a reduced member having certain types.

Parameters
decDecomposition.
reducedMemberReduced member.
pNumOneEndNumber of children that (recursively) must contain one path end.
pNumTwoEndsNumber of children that (recursively) must contain two path ends.
childMarkerEdgesArray for storing a child marker edges containing one/two path ends.
static CMR_ERROR createEdge ( Dec dec,
DEC_MEMBER  member,
DEC_EDGE pedge 
)
static

Creates a new edge in member.

Parameters
decDecomposition.
memberMember this edge belongs to.
pedgePointer for storing the new edge.
static CMR_ERROR createEdgeParallel ( Dec dec,
DEC_EDGE  edge,
DEC_MEMBER pNewParallel 
)
static

Replaces an edge by a parallel containing it.

The given member should have at least two edges.

Parameters
decDecomposition.
edgeEdge to be replaced by a parallel containing that edge.
pNewParallelPointer for storing the new parallel.
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 
)
static

Creates a pair of marker edges for linking parent parentMember to child childMember.

Parameters
decDecomposition.
parentMemberParent member.
pMarkerOfParentPointer for storing the new child marker in the parent.
markerOfParentTailTail node of this *pChildMarker.
markerOfParentHeadHead node of this *pChildMarker.
childMemberChild member.
pMarkerToParentPointer for storing the new parent marker in the child.
markerToParentTailTail node of this *pParentMarker.
markerToParentHeadHead node of this *pParentMarker.
static CMR_ERROR createMember ( Dec dec,
DEC_MEMBER_TYPE  type,
DEC_MEMBER pmember 
)
static

Creates a new member.

Parameters
decDecomposition.
typeType of member.
pmemberPointer for storing the new member.
static CMR_ERROR createNode ( Dec dec,
DEC_NODE pnode 
)
static

Creates a node for some rigid member of the decomposition dec.

Parameters
decDecomposition.
pnodePointer for storing new node.
static CMR_ERROR createParallelNodes ( Dec dec,
DEC_MEMBER  member 
)
static

Create nodes of a parallel member.

Parameters
decDecomposition.
memberA parallel member.
static CMR_ERROR createPathEdge ( Dec dec,
DEC_NEWCOLUMN newcolumn,
DEC_EDGE  edge,
ReducedMember reducedMember 
)
static

Creates a path edge structure.

Adds it to the singly-linked path edge list of reducedMember and to the overall singly-linked path edge list. The created PathEdge can be accessed via ReducedMember::firstPathEdge.

Parameters
decDecomposition.
newcolumnnew column.
edgeThe edge it refers to.
reducedMemberReduced member this path edge belongs to.
static CMR_ERROR createReducedDecompositionPathEdges ( Dec dec,
DEC_NEWCOLUMN newcolumn,
size_t *  rows,
size_t  numRows 
)
static

Creates path edges in reduced decomposition.

Parameters
decDecomposition.
newcolumnnewcolumn.
rowsArray of rows (of new column's enries).
numRowsLength of rows.
static CMR_ERROR createReducedMembers ( Dec dec,
DEC_NEWCOLUMN newcolumn,
DEC_MEMBER  member,
ReducedMember **  preducedMember 
)
static

Creates, if necessary, the reduced member for member and calls itself for the parent.

Parameters
decDecomposition.
newcolumnnewcolumn.
memberMember to create reduced member for.
preducedMemberPointer for storing the created reduced member.
static void debugDot ( Dec dec,
DEC_NEWCOLUMN newcolumn 
)
inlinestatic
Parameters
decDecomposition.
newcolumnnew 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.

Parameters
cmrCMR environment.
pdecPointer to new decomposition. .
memEdgesInitial memory for edges of the decomposition.
memNodesInitial memory for nodes of the decomposition.
memMembersInitial memory for members of the decomposition.
memRowsInitial memory for rows.
memColumnsInitial memory for columns.
CMR_ERROR decFree ( Dec **  pdec)

Frees the decomposition *pdec.

Parameters
pdecPointer to decomposition.
static CMR_ERROR decToGraph ( Dec dec,
CMR_GRAPH graph,
bool  merge,
CMR_GRAPH_EDGE forestEdges,
CMR_GRAPH_EDGE coforestEdges,
CMR_ELEMENT edgeElements 
)
static

Creates a graph represented by given decomposition.

Parameters
decDecomposition.
graphGraph to be filled.
mergeMerge and remove corresponding parent and child markers.
forestEdgesIf not NULL, the edges of a spanning tree are stored here.
coforestEdgesIf not NULL, the non-basis edges are stored here.
edgeElementsIf not NULL, the elements for each edge are stored here.
static CMR_ERROR determineTypeParallel ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  numOneEnd,
int  numTwoEnds,
DEC_EDGE  childMarkerEdges[2],
int  depth 
)
static

Determines the type of a parallel member.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
numOneEndNumber of child markers containing one path end.
numTwoEndsNumber of child markers containing two path ends.
childMarkerEdgesMarker edges of children containing one/two path ends.
depthDepth of member in reduced decomposition.
static CMR_ERROR determineTypeRigid ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  numOneEnd,
int  numTwoEnds,
DEC_EDGE  childMarkerEdges[2],
int  depth 
)
static

Determines the type of a rigid member.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
numOneEndNumber of child markers containing one path end.
numTwoEndsNumber of child markers containing two path ends.
childMarkerEdgesMarker edges of children containing one/two path ends.
depthDepth of member in reduced t-decomposition.
static CMR_ERROR determineTypes ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  depth 
)
static

Determines the type of a member and all its children in the reduced decomposition.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
depthDepth of member in reduced t-decomposition.
static CMR_ERROR determineTypeSeries ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent,
ReducedMember reducedMember,
int  numOneEnd,
int  numTwoEnds,
DEC_EDGE  childMarkerEdges[2],
int  depth 
)
static

Determines the type of a series member.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
reducedMemberReduced member.
numOneEndNumber of child markers containing one path end.
numTwoEndsNumber of child markers containing two path ends.
childMarkerEdgesMarker edges of children containing one/two path ends.
depthDepth of member in reduced t-decomposition.
static CMR_ERROR doReorderComponent ( Dec dec,
DEC_MEMBER  member,
DEC_MEMBER  newParent,
DEC_EDGE  newMarkerToParent,
DEC_EDGE  markerOfNewParent 
)
static

Recursive method to reorder a member by making newParent the new parent.

Parameters
decDecomposition.
memberMember to be processed.
newParentNew parent of member.
newMarkerToParentNew marker edge linked to new parent of member.
markerOfNewParentCounterpart to newMarkerToParent.
static void edgeToDot ( FILE *  stream,
Dec dec,
DEC_MEMBER  member,
DEC_EDGE  edge,
int  u,
int  v,
bool  red 
)
static

Prints an edge in dot format to stream.

Parameters
streamFile stream.
decDecomposition.
memberMember this edge belongs to.
edgeEdge.
uFirst node.
vSecond node.
redWhether to color it red.
static DEC_NODE findEdgeHead ( Dec dec,
DEC_EDGE  edge 
)
inlinestatic

Returns the representative node of the head of edge.

Parameters
decDecomposition.
edgeEdge.
static DEC_MEMBER findEdgeMember ( Dec dec,
DEC_EDGE  edge 
)
inlinestatic

Returns the representative member of edge.

Parameters
decDecomposition.
edgeEdge.
static DEC_NODE findEdgeTail ( Dec dec,
DEC_EDGE  edge 
)
inlinestatic

Returns the representative node of the tail of edge.

Parameters
decDecomposition.
edgeEdge.
static DEC_MEMBER findMember ( Dec dec,
DEC_MEMBER  member 
)
static

Returns the representative member of member.

Parameters
decDecomposition.
memberMember for which the representative shall be returned.
static DEC_MEMBER findMemberParent ( Dec dec,
DEC_MEMBER  member 
)
inlinestatic

Returns the representative of the parent member of member.

Assumes that member is a representative member.

Parameters
decDecomposition.
memberMember whose parent shall be returned.
static DEC_NODE findNode ( Dec dec,
DEC_NODE  node 
)
static

Returns the representative node of node.

Assumes node is indeed a node, i.e., not -1.

static void flipEdge ( Dec dec,
DEC_EDGE  edge 
)
inlinestatic
Parameters
dect-decomposition.
edgeedge.
static CMR_ERROR initializeNewColumn ( Dec dec,
DEC_NEWCOLUMN newcolumn 
)
static

Initializes a DEC_NEWCOLUMN structure in order to check for a column.

Parameters
decDecomposition.
newcolumnnewcolumn.
static bool isRepresentativeMember ( Dec dec,
DEC_MEMBER  member 
)
inlinestatic

Returns true if and only member is a representative member.

Parameters
decDecomposition.
memberMember of dec.
static const char* memberTypeString ( DEC_MEMBER_TYPE  type)
inlinestatic
static CMR_ERROR mergeMemberIntoParent ( Dec dec,
DEC_MEMBER  member,
bool  headToHead 
)
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.

Parameters
decDecomposition.
memberReduced component.
headToHeadWhether the heads of the edges shall be joined.
static CMR_ERROR moveReducedRoot ( Dec dec,
DEC_NEWCOLUMN newcolumn,
ReducedComponent reducedComponent 
)
static

Moves the reduced root upwards as long as it has a TYPE_DOUBLE_CHILD child.

Parameters
decDecomposition.
newcolumnnewcolumn.
reducedComponentReduced component.
CMR_ERROR newcolumnCreate ( CMR cmr,
DEC_NEWCOLUMN **  pnewcolumn 
)

Creates a DEC_NEWCOLUMN structure.

Parameters
cmrCMR environment.
pnewcolumnPointer for storing the newcolumn structure.
CMR_ERROR newcolumnFree ( CMR cmr,
DEC_NEWCOLUMN **  pnewcolumn 
)

Frees a DEC_NEWCOLUMN structure.

Parameters
cmrCMR environment.
pnewcolumnPointer to newcolumn structure.
static CMR_ERROR parallelParentChildCheckMember ( Dec dec,
DEC_MEMBER  member,
DEC_MEMBER  childMember 
)
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.

Parameters
decDecomposition.
memberParent of childMember.
childMemberChild member of member.
static CMR_ERROR parallelParentChildCheckReducedMembers ( Dec dec,
size_t *  entryRows,
size_t  numEntries 
)
static

Ensures that no child marker in the reduced decomposition is parallel to the parent marker.

Parameters
decDecomposition.
entryRowsArray of rows of new column's enries.
numEntriesLength of entryRows.
static CMR_ERROR removeAllPathEdges ( Dec dec,
DEC_NEWCOLUMN newcolumn 
)
static

Removes all path edges.

Parameters
decDecomposition.
newcolumnnew column.
static CMR_ERROR removeEdgeFromMembersEdgeList ( Dec dec,
DEC_EDGE  edge 
)
static

Removes edge from the edge list of its member.

Parameters
decDecomposition.
edgeEdge to be added.
static CMR_ERROR reorderComponent ( Dec dec,
DEC_MEMBER  newRoot 
)
static

Reorders a component, making newRoot the new root.

Parameters
decDecomposition.
newRootThe new root of the component.
static CMR_ERROR replaceEdgeInMembersEdgeList ( Dec dec,
DEC_EDGE  oldEdge,
DEC_EDGE  newEdge 
)
static

Replaced oldEdge in its member by newEdge.

Assumes that newEdge has the same member but is not in its edge list.

Parameters
decDecomposition.
oldEdgeEdge to be removed.
newEdgeEdge to be added.
static CMR_ERROR setEdgeNodes ( Dec dec,
DEC_EDGE  edge,
DEC_NODE  tail,
DEC_NODE  head 
)
static

Sets the tail/head nodes of a edge to tail and head, respectively.

Parameters
decDecomposition.
edgeReduced component.
tailNew tail node.
headNew head node.
static CMR_ERROR splitParallel ( Dec dec,
DEC_MEMBER  parallel,
DEC_EDGE  edge1,
DEC_EDGE  edge2,
DEC_MEMBER pChildParallel 
)
static

Splits a parallel member into two parallel members joined via a series member.

Parameters
decDecomposition.
parallelA parallel member.
edge1First edge to be moved into the child parallel.
edge2Second edge to be moved into the child parallel.
pChildParallelPointer to storing the newly created child parallel.
static CMR_ERROR splitSeries ( Dec dec,
DEC_MEMBER  member,
bool *  edgesPredicate,
bool  predicateValue,
DEC_EDGE pRepresentativeEdge,
DEC_MEMBER pNewParallel,
DEC_MEMBER pNewSeries 
)
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.

Parameters
decDecomposition.
memberSeries member to be split.
edgesPredicateMap from edges to predicate.
predicateValueValue of predicate.
pRepresentativeEdgePointer for storing the child marker edge that links to new parallel.
pNewParallelPointer for storing the new parallel.
pNewSeriesPointer for storing the new parallel.