Scippy

SCIP

Solving Constraint Integer Programs

GraphNode Struct Reference

Detailed Description

a node in the graph

Definition at line 40 of file GomoryHuTree.h.

#include <GomoryHuTree.h>

Data Fields

int id
 
int dist
 
double x
 
double y
 
double excess
 
double mincap
 
SCIP_Bool unmarked
 
SCIP_Bool alive
 
struct GraphEdgefirst_edge
 
struct GraphEdgescan_ptr
 
struct GraphNodebfs_link
 
struct GraphNodestack_link
 
struct GraphNodeparent
 

Field Documentation

◆ id

int GraphNode::id

◆ dist

int GraphNode::dist

distances used in push-relabel

Definition at line 43 of file GomoryHuTree.h.

Referenced by global_relabel(), and maxflow().

◆ x

double GraphNode::x

2D-coordinate in some metric

Definition at line 45 of file GomoryHuTree.h.

Referenced by copy_graph(), and SCIP_DECL_EVENTEXEC().

◆ y

double GraphNode::y

second coordinate

Definition at line 46 of file GomoryHuTree.h.

Referenced by copy_graph(), and SCIP_DECL_EVENTEXEC().

◆ excess

double GraphNode::excess

excess of node used in push-relabel

Definition at line 47 of file GomoryHuTree.h.

Referenced by global_relabel(), and maxflow().

◆ mincap

double GraphNode::mincap

capacity of minimum cut between node and parent in GH cut tree

Definition at line 48 of file GomoryHuTree.h.

Referenced by constructCutList(), and ghc_tree().

◆ unmarked

SCIP_Bool GraphNode::unmarked

while BFS in progress

Definition at line 50 of file GomoryHuTree.h.

Referenced by constructSingleCut(), global_relabel(), and maxflow().

◆ alive

SCIP_Bool GraphNode::alive

marks alive (active) nodes in push-relabel

Definition at line 51 of file GomoryHuTree.h.

Referenced by ghc_tree(), global_relabel(), and maxflow().

◆ first_edge

struct GraphEdge* GraphNode::first_edge

◆ scan_ptr

struct GraphEdge* GraphNode::scan_ptr

next edge to be scanned when node will be visited again

Definition at line 54 of file GomoryHuTree.h.

Referenced by global_relabel(), and maxflow().

◆ bfs_link

struct GraphNode* GraphNode::bfs_link

for one way BFS working queue

Definition at line 56 of file GomoryHuTree.h.

Referenced by global_relabel(), and maxflow().

◆ stack_link

struct GraphNode* GraphNode::stack_link

for stack of active node

Definition at line 57 of file GomoryHuTree.h.

Referenced by global_relabel(), and maxflow().

◆ parent

struct GraphNode* GraphNode::parent

pointer of Gomory-Hu cut tree

Definition at line 58 of file GomoryHuTree.h.

Referenced by ghc_tree(), and nodeOnRootPath().