Scippy

    SCIP

    Solving Constraint Integer Programs

    Data Structures | Macros | Typedefs | Functions
    dijkstra.h File Reference

    Detailed Description

    Definitions for Disjkstra's shortest path algorithm.

    Author
    Thorsten Koch
    Marc Pfetsch

    Definition in file dijkstra.h.

    Go to the source code of this file.

    Data Structures

    struct  DIJKSTRA_Graph
     

    Macros

    #define DIJKSTRA_Bool   unsigned int
     
    #define TRUE   1
     
    #define FALSE   0
     
    #define DIJKSTRA_FARAWAY   0xffffffffu
     
    #define DIJKSTRA_UNUSED   0xffffffffu
     

    Typedefs

    typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH
     

    Functions

    DIJKSTRA_Bool dijkstraGraphIsValid (const DIJKSTRA_GRAPH *G)
     
    unsigned int dijkstra (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
     
    unsigned int dijkstraPair (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
     
    unsigned int dijkstraPairCutoff (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
     
    unsigned int dijkstraPairCutoffIgnore (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned int *ignore, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
     

    Macro Definition Documentation

    ◆ DIJKSTRA_Bool

    #define DIJKSTRA_Bool   unsigned int

    type used for boolean values

    Definition at line 40 of file dijkstra.h.

    ◆ TRUE

    #define TRUE   1

    boolean value TRUE

    Definition at line 43 of file dijkstra.h.

    ◆ FALSE

    #define FALSE   0

    boolean value FALSE

    Definition at line 44 of file dijkstra.h.

    ◆ DIJKSTRA_FARAWAY

    #define DIJKSTRA_FARAWAY   0xffffffffu

    node has distance 'infinity'

    Definition at line 47 of file dijkstra.h.

    ◆ DIJKSTRA_UNUSED

    #define DIJKSTRA_UNUSED   0xffffffffu

    node is unused

    Definition at line 48 of file dijkstra.h.

    Typedef Documentation

    ◆ DIJKSTRA_GRAPH

    typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH

    graph structure - use consecutive storage for arcs

    Definition at line 65 of file dijkstra.h.

    Function Documentation

    ◆ dijkstraGraphIsValid()

    DIJKSTRA_Bool dijkstraGraphIsValid ( const DIJKSTRA_GRAPH *  G)

    Check whether the data structures of the graph are valid.

    Parameters
    Gdirected graph to be checked

    Definition at line 42 of file dijkstra.c.

    References DIJKSTRA_Graph::arcs, DIJKSTRA_UNUSED, DIJKSTRA_Graph::head, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, TRUE, and DIJKSTRA_Graph::weight.

    Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().

    ◆ dijkstra()

    unsigned int dijkstra ( const DIJKSTRA_GRAPH *  G,
    unsigned int  source,
    unsigned long long *  dist,
    unsigned int *  pred,
    unsigned int *  entry,
    unsigned int *  order 
    )

    Dijkstra's algorithm using binary heaps

    Dijkstra's algorithm for shortest paths from a single source using binary heaps

    Parameters
    Gdirected graph
    sourcesource node
    distnode distances (allocated by user)
    prednode predecessors in final shortest path tree (allocated by user)
    entrytemporary storage (for each node - must be allocated by user)
    ordertemporary storage (for each node - must be allocated by user)

    Definition at line 190 of file dijkstra.c.

    References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.

    ◆ dijkstraPair()

    unsigned int dijkstraPair ( const DIJKSTRA_GRAPH *  G,
    unsigned int  source,
    unsigned int  target,
    unsigned long long *  dist,
    unsigned int *  pred,
    unsigned int *  entry,
    unsigned int *  order 
    )

    Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps

    Parameters
    Gdirected graph
    sourcesource node
    targettarget node
    distnode distances (allocated by user)
    prednode predecessors in final shortest path tree (allocated by user)
    entrytemporary storage (for each node - must be allocated by user)
    ordertemporary storage (for each node - must be allocated by user)

    Definition at line 290 of file dijkstra.c.

    References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.

    ◆ dijkstraPairCutoff()

    unsigned int dijkstraPairCutoff ( const DIJKSTRA_GRAPH *  G,
    unsigned int  source,
    unsigned int  target,
    unsigned long long  cutoff,
    unsigned long long *  dist,
    unsigned int *  pred,
    unsigned int *  entry,
    unsigned int *  order 
    )

    Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff

    Parameters
    Gdirected graph
    sourcesource node
    targettarget node
    cutoffif the distance of a node reached this value, we truncate the search
    distnode distances (allocated by user)
    prednode predecessors in final shortest path tree (allocated by user)
    entrytemporary storage (for each node - must be allocated by user)
    ordertemporary storage (for each node - must be allocated by user)

    Definition at line 396 of file dijkstra.c.

    References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.

    Referenced by separateGLS().

    ◆ dijkstraPairCutoffIgnore()

    unsigned int dijkstraPairCutoffIgnore ( const DIJKSTRA_GRAPH *  G,
    unsigned int  source,
    unsigned int  target,
    unsigned int *  ignore,
    unsigned long long  cutoff,
    unsigned long long *  dist,
    unsigned int *  pred,
    unsigned int *  entry,
    unsigned int *  order 
    )

    Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff

    Parameters
    Gdirected graph
    sourcesource node
    targettarget node
    ignoremarking nodes to be ignored (if value is nonzero)
    cutoffif the distance of a node reached this value, we truncate the search
    distnode distances (allocated by user)
    prednode predecessors in final shortest path tree (allocated by user)
    entrytemporary storage (for each node - must be allocated by user)
    ordertemporary storage (for each node - must be allocated by user)

    Definition at line 507 of file dijkstra.c.

    References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.

    Referenced by separateGLS().