dijkstra.cpp

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file dijkstra.cpp

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   dijkstra.cpp 
//
//==========================================================================
//$Id: dijkstra.cpp,v 1.6 2002/12/23 13:46:41 chris Exp $

#include <GTL/dijkstra.h>
#include <GTL/bin_heap.h>

#include <cstdlib>
#include <iostream>
#include <cassert>

#ifdef __GTL_MSVCC
#   ifdef _DEBUG
#       ifndef SEARCH_MEMORY_LEAKS_ENABLED
#       error SEARCH NOT ENABLED
#       endif
#       define new DEBUG_NEW
#       undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#   endif   // _DEBUG
#endif  // __GTL_MSVCC

__GTL_BEGIN_NAMESPACE

class less_dist : public binary_function<node, node, bool>
{
public:
    less_dist(const node_map<double>* dist, const node_map<int>* mark)
    {
        this->dist = dist;
        this->mark = mark;
    }

    bool operator()(const node n1, const node n2) const
    {
        if (((*mark)[n1] == dijkstra::black) &&
            ((*mark)[n2] == dijkstra::black))
        {
            return false;
        }
        else if ((*mark)[n1] == dijkstra::black)
        {
            return false;
        }
        else if ((*mark)[n2] == dijkstra::black)
        {
            return true;
        }
        return (*dist)[n1] < (*dist)[n2];
    }
private:
    const node_map<double>* dist;

    const node_map<int>* mark;
};


dijkstra::dijkstra()
{
    reset_algorithm();
}


dijkstra::~dijkstra()
{
}


void dijkstra::source(const node& n)
{
    s = n;
}


void dijkstra::target(const node& n)
{
    t = n;
}


void dijkstra::weights(const edge_map<double>& weight)
{
    this->weight = weight;
    weights_set = true;
}


void dijkstra::store_preds(bool set)
{
    preds_set = set;
}


int dijkstra::check(graph& G)
{
    if ((s == node()) || (!weights_set))
    {
        return GTL_ERROR;
    }

    bool source_found = false;
    graph::node_iterator node_it;
    graph::node_iterator nodes_end = G.nodes_end();
    for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
    {
        if (*node_it == s)
        {
            source_found = true;
            break;
        }
    }
    if (!source_found)
    {
        return(GTL_ERROR);
    }

    graph::edge_iterator edge_it;
    graph::edge_iterator edges_end = G.edges_end();
    for(edge_it = G.edges_begin(); edge_it != edges_end; ++edge_it)
    {
        if (weight[*edge_it] < 0.0)
        {
            return false;
        }
    }

    return GTL_OK;
}


int dijkstra::run(graph& G)
{
    init(G);

    less_dist prd(&dist, &mark);
    bin_heap<node, less_dist> node_heap(prd, G.number_of_nodes());
    mark[s] = grey;
    dist[s] = 0.0;
    node_heap.push(s);
    while (!node_heap.is_empty())
    {

        // debug:
        // node_heap.print_data_container();

        node cur_node = node_heap.top();
        node_heap.pop();

        // debug:
        // node_heap.print_data_container();

        mark[cur_node] = white;
        if (cur_node == t)
        {
            // if @a t is set through #target we are ready
            return GTL_OK;
        }

        node::adj_edges_iterator adj_edge_it;
        node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
        for (adj_edge_it = cur_node.adj_edges_begin();
             adj_edge_it != adj_edges_end;
             ++adj_edge_it)
        {
            node op_node = (*adj_edge_it).opposite(cur_node);
            if (mark[op_node] == black)
            {
                mark[op_node] = grey;
                dist[op_node] = dist[cur_node] + weight[*adj_edge_it];
                node_heap.push(op_node);

                // debug:
                // node_heap.print_data_container();

                if (preds_set)
                {
                    pred[op_node] = *adj_edge_it;
                }
            }
            else if (mark[op_node] == grey)
            {
                if (dist[op_node] > dist[cur_node] + weight[*adj_edge_it])
                {
                    dist[op_node] = dist[cur_node] + weight[*adj_edge_it];
                    node_heap.changeKey(op_node);

                    // debug:
                    // node_heap.print_data_container();

                    if (preds_set)
                    {
                        pred[op_node] = *adj_edge_it;
                    }
                }
            }
            else    // (mark[op_node] == white)
            {
                // nothing to do: shortest distance to op_node is already
                //                computed
            }
        }
    }

    return GTL_OK;
}


node dijkstra::source() const
{
    return s;
}


node dijkstra::target() const
{
    return t;
}


bool dijkstra::store_preds() const
{
    return preds_set;
}


bool dijkstra::reached(const node& n) const
{
    return mark[n] != black;
}


double dijkstra::distance(const node& n) const
{
    return dist[n];
}


node dijkstra::predecessor_node(const node& n) const
{
    assert(preds_set);
    if ((n == s) || (!reached(n)))
    {
        return node();
    }
    return pred[n].opposite(n);
}


edge dijkstra::predecessor_edge(const node& n) const
{
    assert(preds_set);
    return pred[n];
}


dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_begin(
    const node& dest)
{
    assert(preds_set);
    if ((shortest_path_node_list[dest].empty()) &&
        (dest != s) &&
        (reached(dest)))
    {
        fill_node_list(dest);
    }
    return shortest_path_node_list[dest].begin();
}


dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_end(
    const node& dest)
{
    assert(preds_set);
    if ((shortest_path_node_list[dest].empty()) &&
        (dest != s) &&
        (reached(dest)))
    {
        fill_node_list(dest);
    }
    return shortest_path_node_list[dest].end();
}


dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_begin(
    const node& dest)
{
    assert(preds_set);
    if ((shortest_path_edge_list[dest].empty()) &&
        (dest != s) &&
        (reached(dest)))
    {
        fill_edge_list(dest);
    }
    return shortest_path_edge_list[dest].begin();
}


dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_end(
    const node& dest)
{
    assert(preds_set);
    if ((shortest_path_edge_list[dest].empty()) &&
        (dest != s) &&
        (reached(dest)))
    {
        fill_edge_list(dest);
    }
    return shortest_path_edge_list[dest].end();
}


void dijkstra::reset()
{
    reset_algorithm();
}


void dijkstra::reset_algorithm()
{
    s = node();
    t = node();
    weights_set = false;
    preds_set = false;
}


void dijkstra::init(graph& G)
{
    dist.init(G, -1.0);
    mark.init(G, black);
    
    if (preds_set)
    {
        pred.init(G, edge());
        graph::node_iterator node_it;
        graph::node_iterator nodes_end = G.nodes_end();
        for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
        {
            shortest_path_node_list[(*node_it)].clear();
            shortest_path_edge_list[(*node_it)].clear();
        }
    }
}


void dijkstra::fill_node_list(const node& dest)
{
    if ((dest == s) || (!reached(dest)))
    {
        return;
    }

    node cur_node = dest;
    while (cur_node != node())
    {
        shortest_path_node_list[dest].push_front(cur_node);
        cur_node = predecessor_node(cur_node);
    }
}


void dijkstra::fill_edge_list(const node& dest)
{
    if ((dest == s) || (!reached(dest)))
    {
        return;
    }

    node cur_node = dest;
    edge cur_edge = predecessor_edge(dest);
    while (cur_edge != edge())
    {
        shortest_path_edge_list[dest].push_front(cur_edge);
        cur_node = predecessor_node(cur_node);
        cur_edge = predecessor_edge(cur_node);
    }
}

__GTL_END_NAMESPACE

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------