#include <cmr/graphic.h>
#include <cmr/network.h>
#include "seymour_internal.h"
#include "env_internal.h"
#include "hashtable.h"
#include <stdint.h>
#include <time.h>

Functions
static int	dfsArticulationPoint (CMR_GRAPH graph, bool edgesEnabled, CMR_GRAPH_NODE node, bool nodesVisited, int nodesDiscoveryTime, int ptime, CMR_GRAPH_NODE parentNode, size_t nodesArticulationPoint)
	Recursive DFS for finding all articulation points of a graph. More...

static CMR_ERROR	findArticulationPoints (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE columnEdges, size_t nodesArticulationPoint, size_t *nonzeroColumns, size_t numNonzeroColumns)

static void	dfsTree (CMR_GRAPH graph, bool edgesTree, bool nodesVisited, CMR_GRAPH_NODE nodesParent, CMR_GRAPH_NODE node)

static CMR_ERROR	findTreeParents (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, size_t numRows, CMR_GRAPH_NODE nodesParent)

static void	dfsComponents (CMR_GRAPH graph, bool edgesEnabled, size_t *nodesComponent, CMR_GRAPH_NODE node, size_t component)

static CMR_ERROR	findComponents (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE columnEdges, CMR_GRAPH_NODE removedNode, size_t nodesComponent, size_t pnumComponents, size_t nonzeroColumns, size_t numNonzeroColumns)

static bool	dfsBipartite (CMR_GRAPH graph, bool nodesVisited, int *bipartition, CMR_GRAPH_NODE node)
	DFS for searching for a bipartition. More...

static CMR_ERROR	findBipartition (CMR cmr, CMR_GRAPH graph, int bipartition, bool pisBipartite)
	Finds a bipartition of a graph. More...

static CMR_ERROR	addToGraph1Row (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges, size_t baseNumRows, size_t nonzeroColumns, size_t numNonzeroColumns, bool pisGraphic)
	Extends `graph` for a submatrix augmented by 1 row. More...

static CMR_ELEMENT	findParallel (CMR_CHRMAT matrix, size_t row, size_t numRows, size_t numColumns, long long rowHashValues, long long *hashVector)
	Find element in submatrix parallel to vector. More...

static CMR_ERROR	createHashVector (CMR cmr, long long *phashVector, size_t size)
	Creates a hash vector to speed-up recognition of parallel vectors. More...

static CMR_ERROR	updateHashValues (CMR_CHRMAT matrix, long long majorHashValues, long long minorHashValues, long long hashVector, size_t majorFirst, size_t majorBeyond, size_t minorSize)
	Update the hash values of rows/column of submatrix that is grown by a number of rows. More...

static bool	checkEdgesAdjacent (CMR_GRAPH graph, CMR_GRAPH_EDGE e, CMR_GRAPH_EDGE f, CMR_GRAPH_NODE pcommon, CMR_GRAPH_NODE peOther, CMR_GRAPH_NODE pfOther)
	Returns `true` if two edges `e` and `f` are adjacent. More...

static CMR_ERROR	addToGraph1Row1Column (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges, size_t baseNumRows, size_t baseNumColumns, CMR_ELEMENT rowParallel, CMR_ELEMENT columnParallel, bool *pisGraphic)
	Extends `graph` for a submatrix augmented by 1 row and 1 column. More...

static CMR_ERROR	addToGraph2Rows1Column (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges, size_t baseNumRows, size_t baseNumColumns, CMR_ELEMENT row1Parallel, CMR_ELEMENT row2Parallel, bool *pisGraphic)
	Extends `graph` for a submatrix augmented by 2 rows and 1 column. More...

static CMR_ERROR	addToGraph1Row2Columns (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges, size_t baseNumRows, size_t baseNumColumns, CMR_ELEMENT column1Parallel, CMR_ELEMENT column2Parallel, bool *pisGraphic)
	Extends `graph` for a submatrix augmented by 1 row and 2 columns. More...

static CMR_ERROR	addToGraph1Column (CMR cmr, CMR_GRAPH graph, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges, size_t baseNumColumns, size_t nonzeroRows, size_t numNonzeroRows, bool pisGraphic)
	Extends `graph` for a submatrix augmented by 1 column. More...

static CMR_ERROR	createWheel (CMR cmr, CMR_GRAPH graph, CMR_CHRMAT matrix, CMR_CHRMAT transpose, size_t wheelSize, CMR_GRAPH_EDGE rowEdges, CMR_GRAPH_EDGE columnEdges)
	Creates the wheel graph for a wheel submatrix. More...

CMR_ERROR	CMRregularSequenceGraphic (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, size_t lengthSequence, size_t sequenceNumRows, size_t sequenceNumColumns, size_t plastGraphicMinor, CMR_GRAPH pgraph, CMR_ELEMENT pedgeElements, CMR_SEYMOUR_STATS *stats, double timeLimit)

static CMR_ERROR	sequenceGraphicness (CMR cmr, DecompositionTask task, CMR_CHRMAT matrix, CMR_CHRMAT transpose, size_t length, size_t sequenceNumRows, size_t sequenceNumColumns, bool cographicness, CMR_GRAPH pgraph, CMR_ELEMENT pedgeElements, size_t *plastGraphicMinor)
	Tests each minor of the sequence of nested 3-connected minors for graphicness. More...

CMR_ERROR	CMRregularityNestedMinorSequenceGraphicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness. More...

CMR_ERROR	CMRregularityNestedMinorSequenceCographicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness. More...

CMR_ERROR	CMRregularityTestGraphicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests `matrix` for graphicness/network and stores it in `dec`. More...

CMR_ERROR	CMRregularityTestCographicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests `matrix` for cographicness/conetwork and stores it in `dec`. More...

Function Documentation

◆ addToGraph1Column()

static CMR_ERROR addToGraph1Column	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t	baseNumColumns,
		size_t *	nonzeroRows,
		size_t	numNonzeroRows,
		bool *	pisGraphic
	)

static

Extends graph for a submatrix augmented by 1 column.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.
baseNumColumns	Number of columns already processed.
nonzeroRows	Array with rows containing a nonzero.
numNonzeroRows	Length of `nonzeroRows`.
pisGraphic	Pointer for storing whether this extension was graphic.

◆ addToGraph1Row()

static CMR_ERROR addToGraph1Row	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t	baseNumRows,
		size_t *	nonzeroColumns,
		size_t	numNonzeroColumns,
		bool *	pisGraphic
	)

static

Extends graph for a submatrix augmented by 1 row.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.
baseNumRows	Number of rows already processed.
nonzeroColumns	Array with columns containing a nonzero.
numNonzeroColumns	Length of `nonzeroColumns`.
pisGraphic	Pointer for storing whether this extension was graphic.

◆ addToGraph1Row1Column()

static CMR_ERROR addToGraph1Row1Column	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t	baseNumRows,
		size_t	baseNumColumns,
		CMR_ELEMENT	rowParallel,
		CMR_ELEMENT	columnParallel,
		bool *	pisGraphic
	)

static

Extends graph for a submatrix augmented by 1 row and 1 column.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.
baseNumRows	Number of rows already processed.
baseNumColumns	Number of columns already processed.
rowParallel	Element to which the row is parallel.
columnParallel	Element to which the column is parallel.
pisGraphic	Pointer for storing whether this extension was graphic.

◆ addToGraph1Row2Columns()

static CMR_ERROR addToGraph1Row2Columns	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t	baseNumRows,
		size_t	baseNumColumns,
		CMR_ELEMENT	column1Parallel,
		CMR_ELEMENT	column2Parallel,
		bool *	pisGraphic
	)

static

Extends graph for a submatrix augmented by 1 row and 2 columns.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.
baseNumRows	Number of rows already processed.
baseNumColumns	Number of columns already processed.
column1Parallel	Element to which column1 is parallel.
column2Parallel	Element to which column2 is parallel.
pisGraphic	Pointer for storing whether this extension was graphic.

◆ addToGraph2Rows1Column()

static CMR_ERROR addToGraph2Rows1Column	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t	baseNumRows,
		size_t	baseNumColumns,
		CMR_ELEMENT	row1Parallel,
		CMR_ELEMENT	row2Parallel,
		bool *	pisGraphic
	)

static

Extends graph for a submatrix augmented by 2 rows and 1 column.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.
baseNumRows	Number of rows already processed.
baseNumColumns	Number of columns already processed.
row1Parallel	Element to which row1 is parallel.
row2Parallel	Element to which row2 is parallel.
pisGraphic	Pointer for storing whether this extension was graphic.

◆ checkEdgesAdjacent()

static bool checkEdgesAdjacent	(	CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE	e,
		CMR_GRAPH_EDGE	f,
		CMR_GRAPH_NODE *	pcommon,
		CMR_GRAPH_NODE *	peOther,
		CMR_GRAPH_NODE *	pfOther
	)

static

Returns true if two edges e and f are adjacent.

Parameters

graph	Graph.
e	First edge.
f	Second edge.
pcommon	Pointer for storing the common endnode.
peOther	Pointer for storing the endnode of `e` that is not common.
pfOther	Pointer for storing the endnode of `f` that is not common.

◆ CMRregularityNestedMinorSequenceCographicness()

CMR_ERROR CMRregularityNestedMinorSequenceCographicness	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

Tests each minor of the sequence of nested 3-connected minors for graphicness.

Sets task->dec->CMRregularityNestedMinorSequenceCographicness accordingly.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ CMRregularityNestedMinorSequenceGraphicness()

CMR_ERROR CMRregularityNestedMinorSequenceGraphicness	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

Tests each minor of the sequence of nested 3-connected minors for graphicness.

Sets task->dec->CMRregularityNestedMinorSequenceGraphicness accordingly.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ CMRregularityTestCographicness()

CMR_ERROR CMRregularityTestCographicness	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

Tests matrix for cographicness/conetwork and stores it in dec.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ CMRregularityTestGraphicness()

CMR_ERROR CMRregularityTestGraphicness	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

Tests matrix for graphicness/network and stores it in dec.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ CMRregularSequenceGraphic()

CMR_ERROR CMRregularSequenceGraphic	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		size_t	lengthSequence,
		size_t *	sequenceNumRows,
		size_t *	sequenceNumColumns,
		size_t *	plastGraphicMinor,
		CMR_GRAPH **	pgraph,
		CMR_ELEMENT **	pedgeElements,
		CMR_SEYMOUR_STATS *	stats,
		double	timeLimit
	)

◆ createHashVector()

static CMR_ERROR createHashVector	(	CMR *	cmr,
		long long **	phashVector,
		size_t	size
	)

static

Creates a hash vector to speed-up recognition of parallel vectors.

Parameters

cmr	CMR environment.
phashVector	Pointer for storing the hash vector.
size	Size of hash vector.

◆ createWheel()

static CMR_ERROR createWheel	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		size_t	wheelSize,
		CMR_GRAPH_EDGE *	rowEdges,
		CMR_GRAPH_EDGE *	columnEdges
	)

static

Creates the wheel graph for a wheel submatrix.

Parameters

cmr	CMR environment.
graph	Empty graph to be filled.
matrix	Matrix.
transpose	Transpose of `matrix`.
wheelSize	Size of wheel.
rowEdges	Array to be filled with map from rows to edges.
columnEdges	Array to be filled with map from columns to edges.

◆ dfsArticulationPoint()

static int dfsArticulationPoint	(	CMR_GRAPH *	graph,
		bool *	edgesEnabled,
		CMR_GRAPH_NODE	node,
		bool *	nodesVisited,
		int *	nodesDiscoveryTime,
		int *	ptime,
		CMR_GRAPH_NODE	parentNode,
		size_t *	nodesArticulationPoint
	)

static

Recursive DFS for finding all articulation points of a graph.

Parameters

graph	Graph.
edgesEnabled	Edge array indicating whether an edge is enabled.
node	Current node.
nodesVisited	Node array indicating whether a node was already visited.
nodesDiscoveryTime	Node array indicating at which time a node was visited.
ptime	Pointer to current time.
parentNode	Parent node in DFS arborescence.
nodesArticulationPoint	Node array indicating whether a node is an articulation point.

◆ dfsBipartite()

static bool dfsBipartite	(	CMR_GRAPH *	graph,
		bool *	nodesVisited,
		int *	bipartition,
		CMR_GRAPH_NODE	node
	)

static

DFS for searching for a bipartition.

Parameters

graph	Graph.
nodesVisited	Node array indicating whether a node was visited already.
bipartition	Node array for storing the bipartition.
node	Current node.

◆ dfsComponents()

static void dfsComponents	(	CMR_GRAPH *	graph,
		bool *	edgesEnabled,
		size_t *	nodesComponent,
		CMR_GRAPH_NODE	node,
		size_t	component
	)

static

◆ dfsTree()

static void dfsTree	(	CMR_GRAPH *	graph,
		bool *	edgesTree,
		bool *	nodesVisited,
		CMR_GRAPH_NODE *	nodesParent,
		CMR_GRAPH_NODE	node
	)

static

Parameters

graph	Graph.
edgesTree	Edge array indicating whether an edge is enabled.
nodesVisited	Node array indicating whether a node was already visited.
nodesParent	Node array indicating the parent node of each node.
node	Current node.

◆ findArticulationPoints()

static CMR_ERROR findArticulationPoints	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	columnEdges,
		size_t *	nodesArticulationPoint,
		size_t *	nonzeroColumns,
		size_t	numNonzeroColumns
	)

static

Parameters

cmr	CMR environment.
graph	Graph.
columnEdges	Array with with map from columns to edges.
nodesArticulationPoint	Node array indicating whether a node is an articulation point.
nonzeroColumns	Array with columns containing a nonzero.
numNonzeroColumns	Length of `nonzeroColumns`.

◆ findBipartition()

static CMR_ERROR findBipartition	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		int *	bipartition,
		bool *	pisBipartite
	)

static

Finds a bipartition of a graph.

Parameters

cmr	CMR environment.
graph	Graph.
bipartition	Node array indicating color class.
pisBipartite	Pointer for storing whether `is` bipartite.

◆ findComponents()

static CMR_ERROR findComponents	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	columnEdges,
		CMR_GRAPH_NODE	removedNode,
		size_t *	nodesComponent,
		size_t *	pnumComponents,
		size_t *	nonzeroColumns,
		size_t	numNonzeroColumns
	)

static

Parameters

cmr	CMR environment.
graph	Graph.
columnEdges	Array with with map from columns to edges.
removedNode	Node that shall be considered as removed.
nodesComponent	Node array indicating the components.
pnumComponents	Pointer for storing the number of connected components.
nonzeroColumns	Array with columns containing a nonzero.
numNonzeroColumns	Length of `nonzeroColumns`.

◆ findParallel()

static CMR_ELEMENT findParallel	(	CMR_CHRMAT *	matrix,
		size_t	row,
		size_t	numRows,
		size_t	numColumns,
		long long *	rowHashValues,
		long long *	hashVector
	)

static

Find element in submatrix parallel to vector.

◆ findTreeParents()

static CMR_ERROR findTreeParents	(	CMR *	cmr,
		CMR_GRAPH *	graph,
		CMR_GRAPH_EDGE *	rowEdges,
		size_t	numRows,
		CMR_GRAPH_NODE *	nodesParent
	)

static

Parameters

cmr	CMR environment.
graph	Graph.
rowEdges	Array with with map from rows to edges.
numRows	Number of rows.
nodesParent	Array to be filled with map from nodes to parent nodes.

◆ sequenceGraphicness()

static CMR_ERROR sequenceGraphicness	(	CMR *	cmr,
		DecompositionTask *	task,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		size_t	length,
		size_t *	sequenceNumRows,
		size_t *	sequenceNumColumns,
		bool	cographicness,
		CMR_GRAPH **	pgraph,
		CMR_ELEMENT **	pedgeElements,
		size_t *	plastGraphicMinor
	)

static

Tests each minor of the sequence of nested 3-connected minors for graphicness.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
matrix	Matrix that displays the nested minor sequences.
transpose	Transpose of `matrix`.
length	Length of sequence of nested minors.
sequenceNumRows	Number of rows of sequence of nested minors.
sequenceNumColumns	Number of columns of sequence of nested minors.
cographicness	Whether we actually received the transpose as input.
pgraph	Pointer for storing the constructed graph.
pedgeElements	Pointer for storing the mapping from edges to elements.
plastGraphicMinor	Pointer for storing the last graphic minor.

◆ updateHashValues()

static CMR_ERROR updateHashValues	(	CMR_CHRMAT *	matrix,
		long long *	majorHashValues,
		long long *	minorHashValues,
		long long *	hashVector,
		size_t	majorFirst,
		size_t	majorBeyond,
		size_t	minorSize
	)

static

Update the hash values of rows/column of submatrix that is grown by a number of rows.

Parameters

matrix	Matrix.
majorHashValues	Map for hash values of major indices.
minorHashValues	Map for hash values of minor indices.
hashVector	Hash vector.
majorFirst	First new major index.
majorBeyond	Last new major index plus 1.
minorSize	Number of minor indices in submatrix.

Functions

Function Documentation

◆ addToGraph1Column()

◆ addToGraph1Row()

◆ addToGraph1Row1Column()

◆ addToGraph1Row2Columns()

◆ addToGraph2Rows1Column()

◆ checkEdgesAdjacent()

◆ CMRregularityNestedMinorSequenceCographicness()

◆ CMRregularityNestedMinorSequenceGraphicness()

◆ CMRregularityTestCographicness()

◆ CMRregularityTestGraphicness()

◆ CMRregularSequenceGraphic()

◆ createHashVector()

◆ createWheel()

◆ dfsArticulationPoint()

◆ dfsBipartite()

◆ dfsComponents()

◆ dfsTree()

◆ findArticulationPoints()

◆ findBipartition()

◆ findComponents()

◆ findParallel()

◆ findTreeParents()

◆ sequenceGraphicness()

◆ updateHashValues()