/**
* A Fibonacci heap, a graph with weighted edges, and dijkstra's algorithm
*
* Author: Erel Segal http://t...content-available-to-author-only...s.fm/rentabrain
* Date: 2010-11-11
*/
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned int uint;
/* ------ PART A: Fibonacci Heap -------- */
void maximize (uint& a, uint b) {
if (b>a)
a = b;
}
/**
* The heap is a min-heap sorted by Key.
*/
template <typename Data, typename Key> class FibonacciHeapNode {
Key myKey;
Data myData;
uint degree; // number of childern. used in the removeMinimum algorithm.
bool mark; // mark used in the decreaseKey algorithm.
FibonacciHeapNode<Data,Key>* previous; // pointers in a circular doubly linked list
FibonacciHeapNode<Data,Key>* next;
FibonacciHeapNode<Data,Key>* child; // pointer to the first child in the list of children
FibonacciHeapNode<Data,Key>* parent;
FibonacciHeapNode() {}
FibonacciHeapNode(Data d, Key k):
myKey(k),
myData(d),
degree(0),
mark(false),
child(NULL),
parent(NULL)
{
previous = next = this; // doubly linked circular list
}
bool isSingle() const {
return (this == this->next);
}
// inserts a new node after this node
void insert(FibonacciHeapNode<Data,Key>* other) {
if (!other)
return;
// For example: given 1->2->3->4->1, insert a->b->c->d->a after node 3:
// result: 1->2->3->a->b->c->d->4->1
this->next->previous = other->previous;
other->previous->next = this->next;
this->next = other;
other->previous = this;
}
void remove() {
this->previous->next = this->next;
this->next->previous = this->previous;
this->next = this->previous = this;
}
void addChild(FibonacciHeapNode<Data,Key>* other) { // Fibonacci-Heap-Link(other,current)
if (!child)
child = other;
else
child->insert(other);
other->parent = this;
other->mark = false;
degree++;
}
void removeChild(FibonacciHeapNode<Data,Key>* other) {
if (other->parent!=this)
throw string ("Trying to remove a child from a non-parent");
if (other->isSingle()) {
if (child != other)
throw string ("Trying to remove a non-child");
child = NULL;
} else {
if (child == other)
child = other->next;
other->remove(); // from list of children
}
other->parent=NULL;
other->mark = false;
degree--;
}
friend ostream& operator<< (ostream& out, const FibonacciHeapNode& n) {
return (out << n.myData << ":" << n.myKey);
}
void printTree(ostream& out) const {
out << myData << ":" << myKey << ":" << degree << ":" << mark;
if (child) {
out << "(";
const FibonacciHeapNode<Data,Key>* n=child;
do {
if (n==this)
throw string("Illegal pointer - node is child of itself");
n->printTree(out);
out << " ";
n = n->next;
} while (n!=child);
out << ")";
}
}
void printAll(ostream& out) const {
const FibonacciHeapNode<Data,Key>* n=this;
do {
n->printTree(out);
out << " ";
n = n->next;
} while (n!=this);
out << endl;
}
public:
Key key() const { return myKey; }
Data data() const { return myData; }
template <typename D, typename K> friend class FibonacciHeap;
}; // FibonacciHeapNode
template <typename Data, typename Key> class FibonacciHeap {
public:
typedef FibonacciHeapNode<Data,Key>* PNode;
private:
PNode rootWithMinKey; // a circular d-list of nodes
uint count; // total number of elements in heap
uint maxDegree; // maximum degree (=child count) of a root in the circular d-list
protected:
PNode insertNode(PNode newNode) {
//if (debug) cout << "insert " << (*newNode) << endl;
if (!rootWithMinKey) { // insert the first myKey to the heap:
rootWithMinKey = newNode;
} else {
rootWithMinKey->insert(newNode); // insert the root of new tree to the list of roots
if (newNode->key() < rootWithMinKey->key())
rootWithMinKey = newNode;
}
return newNode;
}
public:
bool debug, debugRemoveMin, debugDecreaseKey;
FibonacciHeap():
rootWithMinKey(NULL), count(0), maxDegree(0), debug(false), debugRemoveMin(false) {}
~FibonacciHeap() { /* TODO: remove all nodes */ }
bool empty() const {return count==0;}
PNode minimum() const {
if (!rootWithMinKey)
throw string("no minimum element");
return rootWithMinKey;
}
void printRoots(ostream& out) const {
out << "maxDegree=" << maxDegree << " count=" << count << " roots=";
if (rootWithMinKey)
rootWithMinKey->printAll(out);
else
out << endl;
}
void merge (const FibonacciHeap& other) { // Fibonacci-Heap-Union
rootWithMinKey->insert(other.rootWithMinKey);
if (!rootWithMinKey || (other.rootWithMinKey && other.rootWithMinKey->key() < rootWithMinKey->key()))
this->rootWithMinKey = other.rootWithMinKey;
count += other.count;
}
PNode insert (Data d, Key k) {
if (debug) cout << "insert " << d << ":" << k << endl;
count++;
// create a new tree with a single myKey:
return insertNode(new FibonacciHeapNode<Data,Key>(d,k));
}
void removeMinimum() { // Fibonacci-Heap-Extract-Min, CONSOLIDATE
if (!rootWithMinKey)
throw string("trying to remove from an empty heap");
if (debug) cout << "removeMinimum " << (*rootWithMinKey) << endl;
count--;
/// Phase 1: Make all the removed root's children new roots:
// Make all children of root new roots:
if (rootWithMinKey->child) {
if (debugRemoveMin) {
cout << " root's children: ";
rootWithMinKey->child->printAll(cout);
}
PNode c = rootWithMinKey->child;
do {
c->parent = NULL;
c = c->next;
} while (c!=rootWithMinKey->child);
rootWithMinKey->child = NULL; // removed all children
rootWithMinKey->insert(c);
}
if (debugRemoveMin) {
cout << " roots after inserting children: ";
printRoots(cout);
}
/// Phase 2-a: handle the case where we delete the last myKey:
if (rootWithMinKey->next == rootWithMinKey) {
if (debugRemoveMin) cout << " removed the last" << endl;
if (count!=0)
throw string ("Internal error: should have 0 keys");
rootWithMinKey = NULL;
return;
}
/// Phase 2: merge roots with the same degree:
vector<PNode> degreeRoots (maxDegree+1); // make room for a new degree
fill (degreeRoots.begin(), degreeRoots.end(), (PNode)NULL);
maxDegree = 0;
PNode currentPointer = rootWithMinKey->next;
uint currentDegree;
do {
currentDegree = currentPointer->degree;
if (debugRemoveMin) {
cout << " roots starting from currentPointer: ";
currentPointer->printAll(cout);
cout << " checking root " << *currentPointer << " with degree " << currentDegree << endl;
}
PNode current = currentPointer;
currentPointer = currentPointer->next;
while (degreeRoots[currentDegree]) { // merge the two roots with the same degree:
PNode other = degreeRoots[currentDegree]; // another root with the same degree
if (current->key() > other->key())
swap(other,current);
// now current->key() <= other->key() - make other a child of current:
other->remove(); // remove from list of roots
current->addChild(other);
if (debugRemoveMin) cout << " added " << *other << " as child of " << *current << endl;
degreeRoots[currentDegree]=NULL;
currentDegree++;
if (currentDegree >= degreeRoots.size())
degreeRoots.push_back((PNode)NULL);
}
// keep the current root as the first of its degree in the degrees array:
degreeRoots[currentDegree] = current;
} while (currentPointer != rootWithMinKey);
/// Phase 3: remove the current root, and calcualte the new rootWithMinKey:
delete rootWithMinKey;
rootWithMinKey = NULL;
uint newMaxDegree=0;
for (uint d=0; d<degreeRoots.size(); ++d) {
if (debugRemoveMin) cout << " degree " << d << ": ";
if (degreeRoots[d]) {
if (debugRemoveMin) cout << " " << *degreeRoots[d] << endl;
degreeRoots[d]->next = degreeRoots[d]->previous = degreeRoots[d];
insertNode(degreeRoots[d]);
maximize(newMaxDegree,d);
} else {
if (debugRemoveMin) cout << " no node" << endl;
}
}
maxDegree=newMaxDegree;
}
void decreaseKey(PNode node, Key newKey) {
if (newKey > node->myKey)
throw string("Trying to decrease key to a greater key");
else if (newKey == node->myKey)
return; // nothing to do
if (debug) cout << "decrease key of " << *node << " to " << newKey << endl;
// Update the key and possibly the min key:
node->myKey = newKey;
// Check if the new key violates the heap invariant:
PNode parent = node->parent;
if (!parent) { // root node - just make sure the minimum is correct
if (newKey < rootWithMinKey->key())
rootWithMinKey = node;
return; // heap invariant not violated - nothing more to do
} else if (parent->key() <= newKey) {
return; // heap invariant not violated - nothing more to do
}
for(;;) {
parent->removeChild(node);
insertNode(node);
if (debugDecreaseKey) {
cout << " removed " << *node << " as child of " << *parent << endl;
cout << " roots after remove: ";
rootWithMinKey->printAll(cout);
}
if (!parent->parent) { // parent is a root - nothing more to do
break;
} else if (!parent->mark) { // parent is not a root and is not marked - just mark it
parent->mark = true;
break;
} else {
node = parent;
parent = parent->parent;
continue;
}
};
}
void remove(PNode node, Key minusInfinity) {
if (minusInfinity >= minimum()->key())
throw string("2nd argument to remove must be a key that is smaller than all other keys");
decreaseKey(node, minusInfinity);
removeMinimum();
}
static int UnitTest() {
try {
typedef FibonacciHeap<string, uint> FibHeap;
FibHeap h;
h.debug=true;
h.debugRemoveMin=false;
h.debugDecreaseKey = false;
h.insert("a",4);
h.insert("b",2);
h.insert("c",7);
h.insert("d",5);
h.insert("e",1);
h.insert("f",8);
h.printRoots(cout);
while (!h.empty()) {
cout << "min=" << *h.minimum() << endl;
h.removeMinimum();
h.printRoots(cout);
}
cout << endl << endl;
vector <FibHeap::PNode> nodes(6);
nodes[0] =
h.insert("a",400);
nodes[1] =
h.insert("b",200);
nodes[2] =
h.insert("c",70);
nodes[3] =
h.insert("d",50);
nodes[4] =
h.insert("e",10);
nodes[5] =
h.insert("f",80);
h.printRoots(cout);
cout << "min=" << *h.minimum() << endl;
h.removeMinimum();
cout << "min=" << *h.minimum() << endl;
nodes[4]=NULL;
h.printRoots(cout);
for (uint i=0; i<nodes.size(); ++i) {
if (!nodes[i]) // minimum - already removed
continue;
h.decreaseKey(nodes[i], nodes[i]->key()/10);
cout << "min=" << *h.minimum() << endl;
h.printRoots(cout);
}
cout << endl << endl;
h.insert("AA",4);
h.insert("BB",2);
h.insert("CC",7);
h.insert("DD",5);
h.insert("EE",1);
h.insert("FF",8);
h.printRoots(cout);
while (!h.empty()) {
cout << "min=" << *h.minimum() << endl;
h.removeMinimum();
h.printRoots(cout);
}
cout << endl << endl;
return 0;
} catch (string s) {
cerr << endl << "ERROR: " << s << endl;
return 1;
}
}
}; // FibonacciHeap
/* ------ PART B: Graph with weighted edges -------- */
typedef map<uint,int> AdjacencyListWithWeights; // matches a target vertex to a weight.
const uint MAXINT = 999999999u;
template <class Iterator> ostream& print (Iterator iFrom, Iterator iTo) {
for (; iFrom!=iTo; ++iFrom) cout << *iFrom << " ";
return (cout << endl);
}
template <class T> ostream& operator<< (ostream& out, const vector<T>& theVector) {
return print (theVector.begin(), theVector.end());
}
template <class T> ostream& operator<< (ostream& out, const set<T>& theVector) {
return print (theVector.begin(), theVector.end());
}
/**
* A graph where the vertices are integers; stores edges in adjacency list.
*/
class GraphWithWeights {
vector<AdjacencyListWithWeights> myVertices;
public:
GraphWithWeights (uint nVertices): myVertices(nVertices) {}
uint size() const { return myVertices.size(); }
GraphWithWeights& addEdge (uint iFrom, uint iTo, uint weight) {
if (iFrom >= size()) {
throw string("trying to add an edge from a nonexisting vertex index");
}
if (iTo >= size()) {
throw string("trying to add an edge to a nonexisting vertex index");
}
myVertices[iFrom][iTo] = weight;
return *this;
}
void createClique() { // for testing
for (uint iFrom=0; iFrom<size(); ++iFrom) {
for (uint iTo=0; iTo<size(); ++iTo) {
if (iFrom!=iTo)
addEdge(iFrom,iTo, (iFrom-iTo)*(iFrom-iTo));
}
}
}
void printOutgoingEdges(uint iFrom, ostream& out) const {
out << iFrom << " -> ";
const AdjacencyListWithWeights& targets = myVertices[iFrom];
AdjacencyListWithWeights::const_iterator f;
for (f=targets.begin(); f!=targets.end(); ++f) {
out << " " << f->first << ":" << f->second;
}
out << endl;
}
void printIncomingEdges(uint iTo, ostream& out) {
out << iTo << " <- ";
for (uint iFrom=0; iFrom<myVertices.size(); ++iFrom) {
const AdjacencyListWithWeights& currentTargets = myVertices[iFrom];
AdjacencyListWithWeights::const_iterator it = currentTargets.find(iTo);
if (it != currentTargets.end()) {
out << " " << iFrom << ":" << it->second;
}
}
out << endl;
}
// Print the graph, using the vertex indices
void printIndices(ostream& out) const {
for (uint i=0; i<size(); ++i)
printOutgoingEdges (i, out);
}
friend ostream& operator<< (ostream& out, const GraphWithWeights& g) {
g.printIndices(out);
return out;
}
/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
void shortest_paths(uint source, vector<uint>& distances, vector<uint>& previous) const {
typedef FibonacciHeap<uint, uint> VertexQueue;
// Data=vertex, Key=distance from source
VertexQueue vertexQueue;
//vertexQueue.debug = true;
distances.resize(size());
previous.resize(size());
vector<VertexQueue::PNode> vertexData(size()); // pointers to the inside the vertex queue, for decrease-key
fill(distances.begin(), distances.end(), MAXINT);
fill(previous.begin(), previous.end(), MAXINT);
fill(vertexData.begin(), vertexData.end(), (VertexQueue::PNode)NULL);
// Initlaize source:
previous[source] = MAXINT;
distances[source] = 0;
vertexData[source] = vertexQueue.insert(source, 0);
// Loop over all vertices:
while (!vertexQueue.empty()) {
VertexQueue::PNode current = vertexQueue.minimum(); // finish a vertex
uint currentVertex = current->data();
uint currentDistance = current->key();
vertexQueue.removeMinimum();
// Loop over all outgoing edges of the current vertex:
const AdjacencyListWithWeights& nextTargets = myVertices[currentVertex];
AdjacencyListWithWeights::const_iterator iNeighbour;
for (iNeighbour=nextTargets.begin(); iNeighbour!=nextTargets.end(); ++iNeighbour) {
uint neighbour = iNeighbour->first;
uint distanceFromCurrentToNeighbour = iNeighbour->second;
uint newDistanceToNeighbour = currentDistance + distanceFromCurrentToNeighbour;
//cout << " visiting edge to " << neighbour << " with distance " << distanceFromCurrentToNeighbour
// << " new distance " << newDistanceToNeighbour << " old distance " << distances[neighbour] << endl;
if (newDistanceToNeighbour < distances[neighbour]) { // a tree edge
distances[neighbour] = newDistanceToNeighbour;
previous[neighbour] = currentVertex;
if (vertexData[neighbour]) {
vertexQueue.decreaseKey(vertexData[neighbour], newDistanceToNeighbour);
}
}
if (!vertexData[neighbour]) {
vertexData[neighbour] = vertexQueue.insert(neighbour, newDistanceToNeighbour);
}
}
}
}
void print_shortest_paths_from(uint iFrom) {
vector<uint> distances, previous;
shortest_paths(iFrom, distances, previous);
cout << "Dijkstra from " << iFrom << ": " << endl << "distances: " << distances << "previouses: " << previous << endl;
}
}; // end of class GraphWithWeights
int main() {
/*
GraphWithWeights g(12);
g.addEdge(0,1, 11).addEdge(1,2, 12).addEdge(0,2, 24);
g.addEdge(3,4, 11).addEdge(4,5, 12).addEdge(3,5, 22);
g.addEdge(8,7, 11).addEdge(7,6, 12).addEdge(8,6, 24);
g.addEdge(11,10, 11).addEdge(10,9, 12).addEdge(11,9, 22);
cout << g << endl;
g.printIncomingEdges(0,cout);
g.printIncomingEdges(1,cout);
g.printIncomingEdges(2,cout);
g.printIncomingEdges(3,cout);
g.printIncomingEdges(4,cout);
cout << endl;
g.print_shortest_paths_from(0); // shortest distance to 2 should be 23
g.print_shortest_paths_from(3); // shortest distance to 5 should be 22
g.print_shortest_paths_from(8); // shortest distance to 6 should be 23
g.print_shortest_paths_from(11); // shortest distance to 9 should be 23
return 1;
*/
cout << "Enter number of nodes: ";
uint nodeCount;
cin >> nodeCount;
GraphWithWeights clique(nodeCount);
clique.createClique();
if (nodeCount<=10)
cout << clique << endl;
//for (uint i=0; i<5; ++i)
// clique.print_shortest_paths_from(i);
time_t before = time(NULL);
clique.print_shortest_paths_from(clique.size()/4);
time_t after = time(NULL);
cout << "time for a single calculation = " << (after-before) << " seconds" << endl;
}