#include <cmr/graphic.h>
#include "env_internal.h"
#include "matrix_internal.h"
#include "block_decomposition.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	CMRgraphicStatsInit (CMR_GRAPHIC_STATISTICS *stats)
	Initializes all statistics for graphicness computations. More...

CMR_ERROR	CMRgraphicStatsPrint (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	CMRgraphicComputeMatrix (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, ReducedMember *reducedMember, int numOneEnd, int numTwoEnds, int depth)
	Determines the type of a parallel member. More...

static CMR_ERROR	determineTypeSeries (Dec dec, DEC_NEWCOLUMN newcolumn, ReducedMember *reducedMember, int numOneEnd, int numTwoEnds, int depth)
	Determines the type of a series member. More...

static CMR_ERROR	determineTypeRigid (Dec dec, DEC_NEWCOLUMN newcolumn, 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	CMRcographicTestSupport (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 the support matrix \( M \) of the input matrix for being a cographic matrix. More...

CMR_ERROR	CMRgraphicTestTranspose (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	CMRgraphicTestMatrix (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...

Macro Definition Documentation

◆ SWAP_INTS

#define SWAP_INTS	(	a,
		b
	)

Value:

  do \
  { \
    int tmp = a; \
    a = b; \
    b = tmp; \
  } \
  while (false)

Typedef Documentation

◆ DEC_EDGE

typedef size_t DEC_EDGE

Type for refering to a decomposition edge.

◆ DEC_MEMBER

typedef size_t DEC_MEMBER

Type for refering to a decomposition member.

◆ DEC_NODE

typedef size_t DEC_NODE

Type for refering to a decomposition node.

◆ PathEdge

typedef struct _PathEdge PathEdge

Additional information specific to a path edge.

◆ ReducedComponent

typedef struct _ReducedComponent ReducedComponent

A component of the reduced decomposition.

◆ ReducedMember

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

◆ DEC_MEMBER_TYPE

enum DEC_MEMBER_TYPE

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.

◆ DIJKSTRA_STAGE

enum DIJKSTRA_STAGE

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.

◆ Type

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

◆ addColumnApply()

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

dec	Decomposition.
newcolumn	newcolumn.
column	Index of new column to be added.
rows	Array of rows with 1-entry in this column.
numRows	Length of `rows`.

◆ addColumnCheck()

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

dec	Decomposition.
newcolumn	newcolumn.
rows	Array of rows (with 1-entry in this column).
numRows	Length of `rows`.

◆ addColumnProcessComponent()

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

dec	Decomposition.
newcolumn	new-column structure.
reducedComponent	Reduced component.
reducedMember	Reduced member.
depth	Depth of member in reduced t-decomposition.

◆ addColumnProcessParallel()

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

dec	Decomposition.
newcolumn	new-column structure.
reducedComponent	Reduced component.
reducedMember	Reduced member.
depth	Depth of this member in reduced t-decomposition.

◆ addColumnProcessRigid()

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

dec	Decomposition.
newcolumn	newcolumn.
reducedComponent	Reduced component.
reducedMember	Reduced member.
depth	Depth of this member in reduced t-decomposition.

◆ addColumnProcessSeries()

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

dec	Decomposition.
newcolumn	newcolumn.
reducedComponent	Reduced component.
reducedMember	Reduced member.
depth	Depth of this member in reduced t-decomposition.

◆ addEdgeToMembersEdgeList()

static CMR_ERROR addEdgeToMembersEdgeList	(	Dec *	dec,
		DEC_EDGE	edge
	)

static

Adds edge to the edge list of its member.

Parameters

dec	Decomposition.
edge	Edge to be added.

◆ addTerminal()

static CMR_ERROR addTerminal	(	Dec *	dec,
		ReducedComponent *	reducedComponent,
		DEC_MEMBER	member,
		DEC_NODE	node
	)

static

Add a terminal of a reduced component.

Parameters

dec	Decomposition.
reducedComponent	Reduced component.
member	New terminal member.
node	New terminal node.

◆ CMRcographicTestSupport()

CMR_ERROR CMRcographicTestSupport	(	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 the support matrix \( M \) of the input matrix 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

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 non-graphic submatrix (if \( M \) is not graphic).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRcomputeRepresentationMatrix()

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

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`).

◆ CMRdecToDot()

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

dec	Decomposition.
stream	Stream to write to.
edgesHighlighted	Indicator for edges to be highlighted.

◆ CMRgraphicComputeMatrix()

CMR_ERROR CMRgraphicComputeMatrix	(	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

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`).

◆ CMRgraphicStatsInit()

CMR_ERROR CMRgraphicStatsInit ( CMR_GRAPHIC_STATISTICS * stats )

Initializes all statistics for graphicness computations.

Parameters

stats Pointer to statistics.

◆ CMRgraphicStatsPrint()

CMR_ERROR CMRgraphicStatsPrint	(	FILE *	stream,
		CMR_GRAPHIC_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for graphicness computations.

Parameters

stream	File stream to print to.
stats	Pointer to statistics.
prefix	Prefix string to prepend to each printed line (may be `NULL`).

◆ CMRgraphicTestMatrix()

CMR_ERROR CMRgraphicTestMatrix	(	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.

Note: If a column-wise representation of \( M \) is available, it is recommended to call CMRgraphicTestTranspose() 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

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 non-graphic submatrix (if \( M \) is not graphic).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRgraphicTestTranspose()

CMR_ERROR CMRgraphicTestTranspose	(	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.

Note: Retrieval of minimal non-cographic submatrices via *psubmatrix is not implemented, yet.

Parameters

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 non-graphic submatrix (if \( M \) is not graphic).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRtestBinaryGraphicColumnSubmatrixGreedy()

CMR_ERROR CMRtestBinaryGraphicColumnSubmatrixGreedy	(	CMR *	cmr,
		CMR_CHRMAT *	transpose,
		size_t *	orderedColumns,
		CMR_SUBMAT **	psubmatrix
	)

◆ cographicnessTest()

static CMR_ERROR cographicnessTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		void *	data,
		bool *	pisCographic,
		CMR_SUBMAT **	psubmatrix,
		double	timeLimit
	)

static

Parameters

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 non-cographic submatrix of `matrix`.
timeLimit	Time limit to impose.

◆ completeReducedDecomposition()

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

dec	Decomposition.
newcolumn	newcolumn.
rows	Array of rows (of new column's entries).
numRows	Length of `rows`.

◆ computeReducedDecomposition()

static CMR_ERROR computeReducedDecomposition	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn,
		size_t *	entryRows,
		size_t	numEntries
	)

static

Computes the reduced decomposition.

Parameters

dec	Decomposition.
newcolumn	newcolumn.
entryRows	Array of rows of new column's enries.
numEntries	Length of `entryRows`.

◆ countChildrenTypes()

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

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.

◆ createEdge()

static CMR_ERROR createEdge	(	Dec *	dec,
		DEC_MEMBER	member,
		DEC_EDGE *	pedge
	)

static

Creates a new edge in member.

Parameters

dec	Decomposition.
member	Member this edge belongs to.
pedge	Pointer for storing the new edge.

◆ createEdgeParallel()

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

dec	Decomposition.
edge	Edge to be replaced by a parallel containing that edge.
pNewParallel	Pointer for storing the new parallel.

◆ createMarkerEdgePair()

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

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`.

◆ createMember()

static CMR_ERROR createMember	(	Dec *	dec,
		DEC_MEMBER_TYPE	type,
		DEC_MEMBER *	pmember
	)

static

Creates a new member.

Parameters

dec	Decomposition.
type	Type of member.
pmember	Pointer for storing the new member.

◆ createNode()

static CMR_ERROR createNode	(	Dec *	dec,
		DEC_NODE *	pnode
	)

static

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

Parameters

dec	Decomposition.
pnode	Pointer for storing new node.

◆ createParallelNodes()

static CMR_ERROR createParallelNodes	(	Dec *	dec,
		DEC_MEMBER	member
	)

static

Create nodes of a parallel member.

Parameters

dec	Decomposition.
member	A parallel member.

◆ createPathEdge()

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

dec	Decomposition.
newcolumn	new column.
edge	The edge it refers to.
reducedMember	Reduced member this path edge belongs to.

◆ createReducedDecompositionPathEdges()

static CMR_ERROR createReducedDecompositionPathEdges	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn,
		size_t *	rows,
		size_t	numRows
	)

static

Creates path edges in reduced decomposition.

Parameters

dec	Decomposition.
newcolumn	newcolumn.
rows	Array of rows (of new column's enries).
numRows	Length of `rows`.

◆ createReducedMembers()

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

dec	Decomposition.
newcolumn	newcolumn.
member	Member to create reduced member for.
preducedMember	Pointer for storing the created reduced member.

◆ debugDot()

static void debugDot	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn
	)

inlinestatic

Parameters

dec	Decomposition.
newcolumn	new column.

◆ decCreate()

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

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.

◆ decFree()

CMR_ERROR decFree ( Dec ** pdec )

Frees the decomposition *pdec.

Parameters

pdec	Pointer to decomposition.

◆ decToGraph()

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

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 non-basis edges are stored here.
edgeElements	If not `NULL`, the elements for each edge are stored here.

◆ determineTypeParallel()

static CMR_ERROR determineTypeParallel	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn,
		ReducedMember *	reducedMember,
		int	numOneEnd,
		int	numTwoEnds,
		int	depth
	)

static

Determines the type of a parallel member.

Parameters

dec	Decomposition.
newcolumn	newcolumn.
reducedMember	Reduced member.
numOneEnd	Number of child markers containing one path end.
numTwoEnds	Number of child markers containing two path ends.
depth	Depth of member in reduced decomposition.

◆ determineTypeRigid()

static CMR_ERROR determineTypeRigid	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn,
		ReducedMember *	reducedMember,
		int	numOneEnd,
		int	numTwoEnds,
		DEC_EDGE	childMarkerEdges[2],
		int	depth
	)

static

Determines the type of a rigid member.

Parameters

dec	Decomposition.
newcolumn	newcolumn.
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 t-decomposition.

◆ determineTypes()

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

dec	Decomposition.
newcolumn	newcolumn.
reducedComponent	Reduced component.
reducedMember	Reduced member.
depth	Depth of member in reduced t-decomposition.

◆ determineTypeSeries()

static CMR_ERROR determineTypeSeries	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn,
		ReducedMember *	reducedMember,
		int	numOneEnd,
		int	numTwoEnds,
		int	depth
	)

static

Determines the type of a series member.

Parameters

dec	Decomposition.
newcolumn	newcolumn.
reducedMember	Reduced member.
numOneEnd	Number of child markers containing one path end.
numTwoEnds	Number of child markers containing two path ends.
depth	Depth of member in reduced t-decomposition.

◆ doReorderComponent()

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

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`.

◆ edgeToDot()

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

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.

◆ findEdgeHead()

static DEC_NODE findEdgeHead	(	Dec *	dec,
		DEC_EDGE	edge
	)

inlinestatic

Returns the representative node of the head of edge.

Parameters

dec	Decomposition.
edge	Edge.

◆ findEdgeMember()

static DEC_MEMBER findEdgeMember	(	Dec *	dec,
		DEC_EDGE	edge
	)

inlinestatic

Returns the representative member of edge.

Parameters

dec	Decomposition.
edge	Edge.

◆ findEdgeTail()

static DEC_NODE findEdgeTail	(	Dec *	dec,
		DEC_EDGE	edge
	)

inlinestatic

Returns the representative node of the tail of edge.

Parameters

dec	Decomposition.
edge	Edge.

◆ findMember()

static DEC_MEMBER findMember	(	Dec *	dec,
		DEC_MEMBER	member
	)

static

Returns the representative member of member.

Parameters

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

◆ findMemberParent()

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

dec	Decomposition.
member	Member whose parent shall be returned.

◆ findNode()

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.

◆ flipEdge()

static void flipEdge	(	Dec *	dec,
		DEC_EDGE	edge
	)

inlinestatic

Parameters

dec	t-decomposition.
edge	edge.

◆ initializeNewColumn()

static CMR_ERROR initializeNewColumn	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn
	)

static

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

Parameters

dec	Decomposition.
newcolumn	newcolumn.

◆ isRepresentativeMember()

static bool isRepresentativeMember	(	Dec *	dec,
		DEC_MEMBER	member
	)

inlinestatic

Returns true if and only member is a representative member.

Parameters

dec	Decomposition.
member	Member of `dec`.

◆ memberTypeString()

static const char* memberTypeString ( DEC_MEMBER_TYPE type )

inlinestatic

◆ mergeMemberIntoParent()

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

dec	Decomposition.
member	Reduced component.
headToHead	Whether the heads of the edges shall be joined.

◆ moveReducedRoot()

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

dec	Decomposition.
newcolumn	newcolumn.
reducedComponent	Reduced component.

◆ newcolumnCreate()

CMR_ERROR newcolumnCreate	(	CMR *	cmr,
		DEC_NEWCOLUMN **	pnewcolumn
	)

Creates a DEC_NEWCOLUMN structure.

Parameters

cmr	CMR environment.
pnewcolumn	Pointer for storing the newcolumn structure.

◆ newcolumnFree()

CMR_ERROR newcolumnFree	(	CMR *	cmr,
		DEC_NEWCOLUMN **	pnewcolumn
	)

Frees a DEC_NEWCOLUMN structure.

Parameters

cmr	CMR environment.
pnewcolumn	Pointer to newcolumn structure.

◆ parallelParentChildCheckMember()

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

dec	Decomposition.
member	Parent of `childMember`.
childMember	Child member of `member`.

◆ parallelParentChildCheckReducedMembers()

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

dec	Decomposition.
entryRows	Array of rows of new column's enries.
numEntries	Length of `entryRows`.

◆ removeAllPathEdges()

static CMR_ERROR removeAllPathEdges	(	Dec *	dec,
		DEC_NEWCOLUMN *	newcolumn
	)

static

Removes all path edges.

Parameters

dec	Decomposition.
newcolumn	new column.

◆ removeEdgeFromMembersEdgeList()

static CMR_ERROR removeEdgeFromMembersEdgeList	(	Dec *	dec,
		DEC_EDGE	edge
	)

static

Removes edge from the edge list of its member.

Parameters

dec	Decomposition.
edge	Edge to be added.

◆ reorderComponent()

static CMR_ERROR reorderComponent	(	Dec *	dec,
		DEC_MEMBER	newRoot
	)

static

Reorders a component, making newRoot the new root.

Parameters

dec	Decomposition.
newRoot	The new root of the component.

◆ replaceEdgeInMembersEdgeList()

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

dec	Decomposition.
oldEdge	Edge to be removed.
newEdge	Edge to be added.

◆ setEdgeNodes()

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

dec	Decomposition.
edge	Reduced component.
tail	New tail node.
head	New head node.

◆ splitParallel()

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

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.

◆ splitSeries()

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

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.

Classes

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ SWAP_INTS

Typedef Documentation

◆ DEC_EDGE

◆ DEC_MEMBER

◆ DEC_NODE

◆ PathEdge

◆ ReducedComponent

◆ ReducedMember

Enumeration Type Documentation

◆ DEC_MEMBER_TYPE

◆ DIJKSTRA_STAGE

◆ Type

Function Documentation

◆ addColumnApply()

◆ addColumnCheck()

◆ addColumnProcessComponent()

◆ addColumnProcessParallel()

◆ addColumnProcessRigid()

◆ addColumnProcessSeries()

◆ addEdgeToMembersEdgeList()

◆ addTerminal()

◆ CMRcographicTestSupport()

◆ CMRcomputeRepresentationMatrix()

◆ CMRdecToDot()

◆ CMRgraphicComputeMatrix()

◆ CMRgraphicStatsInit()

◆ CMRgraphicStatsPrint()

◆ CMRgraphicTestMatrix()

◆ CMRgraphicTestTranspose()

◆ CMRtestBinaryGraphicColumnSubmatrixGreedy()

◆ cographicnessTest()

◆ completeReducedDecomposition()

◆ computeReducedDecomposition()

◆ countChildrenTypes()

◆ createEdge()

◆ createEdgeParallel()

◆ createMarkerEdgePair()

◆ createMember()

◆ createNode()

◆ createParallelNodes()

◆ createPathEdge()

◆ createReducedDecompositionPathEdges()

◆ createReducedMembers()

◆ debugDot()

◆ decCreate()

◆ decFree()

◆ decToGraph()

◆ determineTypeParallel()

◆ determineTypeRigid()

◆ determineTypes()

◆ determineTypeSeries()

◆ doReorderComponent()

◆ edgeToDot()

◆ findEdgeHead()

◆ findEdgeMember()

◆ findEdgeTail()

◆ findMember()

◆ findMemberParent()

◆ findNode()

◆ flipEdge()

◆ initializeNewColumn()

◆ isRepresentativeMember()

◆ memberTypeString()

◆ mergeMemberIntoParent()

◆ moveReducedRoot()

◆ newcolumnCreate()

◆ newcolumnFree()

◆ parallelParentChildCheckMember()

◆ parallelParentChildCheckReducedMembers()

◆ removeAllPathEdges()

◆ removeEdgeFromMembersEdgeList()

◆ reorderComponent()

◆ replaceEdgeInMembersEdgeList()

◆ setEdgeNodes()