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 GraphEdge *	first_edge
struct GraphEdge *	scan_ptr
struct GraphNode *	bfs_link
struct GraphNode *	stack_link
struct GraphNode *	parent

Field Documentation

id

int GraphNode::id

number of the node

Definition at line 42 of file GomoryHuTree.h.

Referenced by copy_graph(), findEdge(), getToken(), nodeOnRootPath(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_READERREAD(), sepaSubtour(), and updateDistances().

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(), getToken(), and SCIP_DECL_EVENTEXEC().

y

double GraphNode::y

second coordinate

Definition at line 46 of file GomoryHuTree.h.

Referenced by copy_graph(), getToken(), 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

in list of incident edges

Definition at line 53 of file GomoryHuTree.h.

Referenced by copy_graph(), findEdge(), findSubtour(), getToken(), global_relabel(), maxflow(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_READERREAD(), sepaSubtour(), and updateDistances().

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