Detailed Description

includes graph edge methods for Steiner problems

Author: Daniel Rehfeldt

Graph edge methods for Steiner problems

Definition in file graph_edge.c.

#include "graph.h"
#include "portab.h"

Functions
static void	removeEdge (GRAPH *g, int e)

int	graph_edge_redirect (SCIP scip, GRAPH g, int eki, int k, int j, SCIP_Real cost, SCIP_Bool forcedelete, SCIP_Bool checkexist)

SCIP_RETCODE	graph_edge_reinsert (SCIP scip, GRAPH g, int edge, int tail, int head, SCIP_Real cost, int ancestornode, SINGLETONANS ancestorsBackward, SINGLETONANS ancestorsForward, int insertedge, SCIP_Bool conflict)

void	graph_edge_add (SCIP scip, GRAPH g, int tail, int head, SCIP_Real cost1, SCIP_Real cost2)

void	graph_edge_addBi (SCIP scip, GRAPH g, int tail, int head, SCIP_Real cost)

void	graph_edge_addSubgraph (SCIP scip, const GRAPH orggraph, const int nodemapOrg2sub, int orgedge, GRAPH subgraph)

void	graph_edge_del (SCIP scip, GRAPH g, int e, SCIP_Bool freeancestors)

void	graph_edge_delFull (SCIP scip, GRAPH g, int e, SCIP_Bool freeancestors)

void	graph_edge_delBlocked (SCIP scip, GRAPH g, const SCIP_Bool *edge_deletable, SCIP_Bool freeancestors)

void	graph_edge_delHistory (SCIP scip, GRAPH g, int edge)

void	graph_edge_hide (GRAPH *g, int e)

Function Documentation

◆ removeEdge()

static void removeEdge	(	GRAPH *	g,
		int	e
	)

inlinestatic

Parameters

g	the graph
e	the edge to be removed

Definition at line 37 of file graph_edge.c.

References graph_edge_isInRange(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::rootedgeprevs, GRAPH::source, and GRAPH::tail.

Referenced by graph_edge_del(), and graph_edge_hide().

◆ graph_edge_redirect()

int graph_edge_redirect	(	SCIP *	scip,
		GRAPH *	g,
		int	eki,
		int	k,
		int	j,
		SCIP_Real	cost,
		SCIP_Bool	forcedelete,
		SCIP_Bool	checkexist
	)

redirects given edge eki

Parameters

scip	SCIP data structure
g	the graph
eki	the edge
k	new tail
j	new head
cost	new cost
forcedelete	delete edge eki if it is not used?
checkexist	check if there is already an edge kj

Definition at line 103 of file graph_edge.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), graph_edge_isInRange(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGE(), SCIPisGT(), and GRAPH::tail.

Referenced by delPseudoPath(), extractSubgraphAddEdge(), graph_edge_reinsert(), graph_knot_replaceDeg2(), graph_transPcGetRsap(), graph_transPcGetSap(), graph_transPcmw2rooted(), and mwTraverseChain().

◆ graph_edge_reinsert()

SCIP_RETCODE graph_edge_reinsert	(	SCIP *	scip,
		GRAPH *	g,
		int	edge,
		int	tail,
		int	head,
		SCIP_Real	cost,
		int	ancestornode,
		SINGLETONANS *	ancestorsBackward,
		SINGLETONANS *	ancestorsForward,
		int *	insertedge,
		SCIP_Bool *	conflict
	)

reinsert an edge to replace two other edges

Parameters

scip	SCIP data structure
g	the graph
edge	edge to reinsert
tail	new tail
head	new head
cost	new edge cost
ancestornode	node to copy ancestors from or -1
ancestorsBackward	backwards (edge) ancestors
ancestorsForward	forward (edge) ancestors
insertedge	pointer to inserted edge or -1
conflict	does the newly edge contain conflicts? (i.e. is redundant)

Definition at line 200 of file graph_edge.c.

References singleton_ancestors_edge::ancestors, GRAPH::ancestors, Edge_anti, Edge_even, FALSE, flipedge, graph_edge_delHistory(), graph_edge_redirect(), graph_pc_isPcMw(), graph_pseudoAncestors_appendCopyNodeToEdge(), graph_pseudoAncestors_appendCopySingToEdge(), graph_typeIsUndirected(), NULL, GRAPH::pcancestors, singleton_ancestors_edge::revancestors, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), and TRUE.

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), and pcReduceTermDeg2().

◆ graph_edge_add()

void graph_edge_add	(	SCIP *	scip,
		GRAPH *	g,
		int	tail,
		int	head,
		SCIP_Real	cost1,
		SCIP_Real	cost2
	)

add a new edge to the graph

Parameters

scip	SCIP data structure
g	the graph
tail	tail of the new edge
head	head of the new edge
cost1	tail to head cost
cost2	head to tail cost

Definition at line 278 of file graph_edge.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisEQ(), SCIPisGE(), GRAPH::tail, and UNKNOWN.

Referenced by graph_edge_addBi(), and graph_edge_addSubgraph().

◆ graph_edge_addBi()

void graph_edge_addBi	(	SCIP *	scip,
		GRAPH *	g,
		int	tail,
		int	head,
		SCIP_Real	cost
	)

add a bi-edge to the graph

Parameters

scip	SCIP data structure
g	the graph
tail	tail of the new edge
head	head of the new edge
cost	head to tail cost

Definition at line 328 of file graph_edge.c.

References graph_edge_add().

◆ graph_edge_addSubgraph()

void graph_edge_addSubgraph	(	SCIP *	scip,
		const GRAPH *	orggraph,
		const int *	nodemapOrg2sub,
		int	orgedge,
		GRAPH *	subgraph
	)

add a new edge to a subgraph

Parameters

scip	SCIP data structure
orggraph	original graph
nodemapOrg2sub	node mapping from original to subgraph
orgedge	original edge
subgraph	the subgraph

Definition at line 341 of file graph_edge.c.

References GRAPH::cost, GRAPH::extended, flipedge, graph_edge_add(), graph_pc_isPcMw(), graph_pc_updateSubgraphEdge(), GRAPH::head, and GRAPH::tail.

Referenced by buildsolgraph(), packEdges(), redcostGraphBuild(), and SCIPStpHeurRecExclude().

◆ graph_edge_del()

void graph_edge_del	(	SCIP *	scip,
		GRAPH *	g,
		int	e,
		SCIP_Bool	freeancestors
	)

delete an edge from standard data structure

Parameters

scip	SCIP data structure
g	the graph
e	the edge
freeancestors	free edge ancestors?

Definition at line 368 of file graph_edge.c.

References GRAPH::ancestors, EAT_FREE, EAT_HIDE, GRAPH::grad, graph_edge_delHistory(), GRAPH::head, GRAPH::ieat, GRAPH::knots, GRAPH::oeat, removeEdge(), and GRAPH::tail.

Referenced by ansProcessCandidateWithBridge(), boundPruneHeur(), boundPruneHeurMw(), cutEdgePrune(), daRpcmwDeleteTermIncidents(), decomposeExactFixSol(), delPseudoEdgeDeleteEdge(), graph_edge_delBlocked(), graph_edge_delFull(), graph_edge_redirect(), graph_knot_contract(), graph_knot_del(), graph_knot_delFull(), graph_knot_replaceDeg2(), graph_pc_deleteTerm(), graph_transPcGetRsap(), ledgeFromNetgraph(), mwContractNonPositiveChain(), mwTraverseChain(), pcmwDeleteNonSolEdges(), pcmwReduceKnotDeg1(), pcmwReduceTerm0Prize(), pcReduceTermDeg2(), propgraphDeleteEdge(), pseudoDelDouble(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_chain2(), reduce_cnsAdv(), reduce_daSlackPrune(), reduce_deleteConflictEdges(), reduce_deleteMultiedges(), reduce_fixedConflicts(), reduce_impliedProfitBasedRpc(), reduce_nnp(), reduce_npv(), reduce_nvAdv(), reduce_sd(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdImpLongEdge(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_sdWalk(), reduce_sdWalkExt(), reduce_sdWalkExt2(), reduce_simple(), reduce_simple_dc(), reduce_simple_hc(), reduce_simple_sap(), reduce_unconnectedInfeas(), reduce_unconnectedRpcRmwInfeas(), reduceFixedVars(), reduceLurk(), reducePcMw(), reduceRootedProb(), reduceWithEdgeFixingBounds(), reinsertSubgraphDeleteOldEdges(), removeEdge(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), sepafullReduceFromSols(), termcompDeleteEdges(), termDeleteExtension(), testBLCworksFor3StarAfterReduction(), testSdRepair(), testTerminalPathsRepair2(), and testTerminalPathsRepair3().

◆ graph_edge_delFull()

void graph_edge_delFull	(	SCIP *	scip,
		GRAPH *	g,
		int	e,
		SCIP_Bool	freeancestors
	)

delete an edge from standard, DCSR (if existent) and CSR (if existent) data structures

Parameters

scip	SCIP data structure
g	the graph
e	the edge
freeancestors	free edge ancestors?

Definition at line 418 of file graph_edge.c.

References GRAPH::csr_storage, GRAPH::dcsr_storage, FALSE, graph_dcsr_deleteEdgeBi(), graph_edge_del(), graph_valid_dcsr(), and dynamic_csr_storage::id2csredge.

Referenced by deleteEdge(), graph_knot_delFull(), removeEdge(), and testDistDistancesAreValid().

◆ graph_edge_delBlocked()

void graph_edge_delBlocked	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Bool *	edge_deletable,
		SCIP_Bool	freeancestors
	)

deletes edges marked by given array

Parameters

scip	SCIP data structure
g	the graph
edge_deletable	marks edges to delete (of size nedges / 2)
freeancestors	free edge ancestors?

Definition at line 448 of file graph_edge.c.

References GRAPH::edges, and graph_edge_del().

Referenced by reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), and sdStarFinalize().

◆ graph_edge_delHistory()

void graph_edge_delHistory	(	SCIP *	scip,
		GRAPH *	g,
		int	edge
	)

free the history of an edge

Parameters

scip	SCIP data
g	graph data
edge	edge for which to free the history

Definition at line 466 of file graph_edge.c.

References GRAPH::ancestors, flipedge_Uint, graph_edge_delPseudoAncestors(), and SCIPintListNodeFree().

Referenced by graph_edge_del(), graph_edge_reinsert(), graph_knot_replaceDeg2(), mwTraverseChain(), and packEdges().

◆ graph_edge_hide()

void graph_edge_hide	(	GRAPH *	g,
		int	e
	)

hide edge

Parameters

g	the graph
e	the edge

Definition at line 483 of file graph_edge.c.

References EAT_FREE, EAT_HIDE, GRAPH::grad, GRAPH::head, GRAPH::ieat, NULL, GRAPH::oeat, removeEdge(), and GRAPH::tail.

SCIP

Detailed Description

Functions

Function Documentation

◆ removeEdge()

◆ graph_edge_redirect()

◆ graph_edge_reinsert()

◆ graph_edge_add()

◆ graph_edge_addBi()

◆ graph_edge_addSubgraph()

◆ graph_edge_del()

◆ graph_edge_delFull()

◆ graph_edge_delBlocked()

◆ graph_edge_delHistory()

◆ graph_edge_hide()