##### swh:1:snp:818279ffd0c3c25a68d33cc2b97d007e1bdc7ed6
Tip revision: 39b1361
Graph.h
``````/* Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(C_Plus_Plus)?oldid=13422 */

#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <map>
#include <list>
#include <queue>
#include <set>

#undef min
#undef max
#include <limits>

#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))

template <typename VertexType = unsigned int, typename WeightType = double>
class Graph
{
private:
typedef VertexType vertex_t;
typedef WeightType weight_t;

public:
struct Edge {
vertex_t target;
weight_t weight;
unsigned int index;

Edge(vertex_t arg_target, weight_t arg_weight, unsigned int edge_index = -1)
: target(arg_target), weight(arg_weight), index(edge_index) { }

bool operator == (const Edge & rhs) const
{
return (target == rhs.target && weight == rhs.weight && index == rhs.index);
}
};

struct CompareEdge{
bool operator()(const Edge &a, const Edge &b){
if (a.target < b.target) return true;
if (a.target > b.target) return false;
return a.index < b.index;
}
};

typedef std::set<Edge,CompareEdge> EdgesSet;

private:
typedef std::set<vertex_t> vertices_set;

template <typename T1, typename T2>
struct pair_first_less
{
bool operator()(std::pair<T1,T2> p1, std::pair<T1,T2> p2) const {
if(p1.first == p2.first) {
return p1.second < p2.second;
}
return p1.first < p2.first;
}
};

void DijkstraComputePaths(vertex_t source)
{
if(source == lastStart)
return;
else
{
lastStart = source;
previous.clear();
}

vertex_iter++)
{
vertex_t v = vertex_iter->first;
min_distance[v] = std::numeric_limits< WeightType >::infinity();
}

min_distance[source] = 0;
std::set< std::pair<weight_t, vertex_t>,
pair_first_less<weight_t, vertex_t> > vertex_queue;
vertex_iter++){
vertex_t v = vertex_iter->first;
vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));
}

while (!vertex_queue.empty()) {
vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());

// Visit each edge exiting u
for (typename std::list<Edge>::iterator edge_iter = adjacency_map[u].begin();
edge_iter++)
{
vertex_t v = edge_iter->target;
weight_t weight = edge_iter->weight;
weight_t distance_through_u = min_distance[u] + weight;
if (distance_through_u < min_distance[v]) {
vertex_queue.erase(std::pair<weight_t, vertex_t>(min_distance[v], v));

min_distance[v] = distance_through_u;
previous[v] = u;
vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));
}

}
}
}

std::list<vertex_t> DijkstraGetShortestPathTo(vertex_t target)
{
std::list<vertex_t> path;
typename std::map<vertex_t, vertex_t>::iterator prev;
vertex_t vertex = target;

path.push_front(vertex);

while((prev = previous.find(vertex)) != previous.end())
{
vertex = prev->second;
path.push_front(vertex);
}

return path;
}

public:
std::list<vertex_t> DijkstraShortestPath(vertex_t start, vertex_t end)
{
this->DijkstraComputePaths(start);
return this->DijkstraGetShortestPathTo(end);
}

int NodeDistance(vertex_t n1, vertex_t n2)
{
if(!this->isConnected(n1, n2)) return -1;
return DijkstraShortestPath(n1, n2).size();
}

private:
// Graph Variables:
vertices_set vertices;

std::map<vertex_t, weight_t> min_distance;
std::map<vertex_t, vertex_t> previous;

vertex_t lastStart;

public:

Graph()
{
lastStart = std::numeric_limits<vertex_t>::max();
}

Graph(const Graph& from)
{
this->vertices = from.vertices;
this->min_distance = from.min_distance;
this->previous = from.previous;
this->lastStart = from.lastStart;
}

void AddEdge(vertex_t p1, vertex_t p2, weight_t weight, int index = -1)
{
}

{
vertices.insert(p);

return p;
}

void removeDirectedEdge(vertex_t p1, vertex_t p2)
{

{
Edge * e = &(*i);

if(e->target == p2)
{
return;
}
}
}

void removeEdge(vertex_t p1, vertex_t p2)
{
removeDirectedEdge(p1, p2);
removeDirectedEdge(p2, p1);
}

void SetDirectedEdgeWeight(vertex_t p1, vertex_t p2, weight_t newWeight)
{

{
Edge * e = &(*i);

if(e->target == p2)
{
e->weight = newWeight;
return;
}
}
}

void SetEdgeWeight(vertex_t p1, vertex_t p2, weight_t newWeight)
{
SetDirectedEdgeWeight(p1, p2, newWeight);
SetDirectedEdgeWeight(p2, p1, newWeight);
}

vertex_t GetRandomNeighbour(vertex_t p)
{
}

std::vector<vertex_t> GetNeighbours(vertex_t p)
{
std::vector<vertex_t> neighbours;

{
Edge * e = &(*i);

neighbours.push_back(e->target);
}

return neighbours;
}

vertex_t GetOtherNeighbour(vertex_t p, vertex_t q)
{
vertex_t n = p;

{
Edge * e = &(*i);

if(e->target != q)
{
n = e->target;
break;
}
}

return n;
}

bool isCircular(vertex_t p)
{
std::set<vertex_t> visited;

visited.insert(p);

bool hasMore = true;

vertex_t curr = p;
vertex_t prev = p;

while(hasMore)
{
vertex_t next = GetOtherNeighbour(curr, prev);

if(next == curr)
return false;

if(visited.find(next) != visited.end())
return true;

prev = curr;
curr = next;
}

return false;
}

bool isConnected(vertex_t v1, vertex_t v2)
{
this->DijkstraComputePaths(v1);

if(min_distance[v2] != std::numeric_limits< WeightType >::infinity())
return true;

return false;
}

vertices_set GetNodes()
{
return vertices;
}

// the 'index' of the edge will be replaced with index of a vertex
std::vector<Edge> GetEdges()
{
std::vector<Edge> result;

{
vertex_t v1 = it->first;

{
Edge e = *i;

result.push_back(Edge(Min(e.target, v1), e.weight, Max(e.target, v1)));
}
}

return result;
}

EdgesSet GetEdgesSet()
{
std::vector<Edge> allEdges = GetEdges();

EdgesSet result;

for(typename std::vector<Edge>::iterator it = allEdges.begin(); it != allEdges.end(); it++)
result.insert(*it);

return result;
}

std::vector<vertex_t> GetLeaves() const
{
std::vector<vertex_t> leaves;

{
if(it->second.size() < 2)
leaves.push_back(it->first);
}

return leaves;
}

void explore(vertex_t seed, std::set<vertex_t> & explored)
{
std::queue<vertex_t> q;

q.push(seed);
explored.insert(seed);

while(!q.empty())
{
vertex_t i = q.front();
q.pop();

{
vertex_t j = it->target;

// Check: not visited
if(explored.find(j) == explored.end())
{
explored.insert(j);
q.push(j);
}
}
}
}

vertex_t getNodeLargestConnected()
{
std::vector< std::set<vertex_t> > connectedComponents;
std::set<vertex_t> unvisited;

if(vertices.size() == 0)
return -1;

// fill unvisited set
for(typename vertices_set::const_iterator it = vertices.begin(); it != vertices.end(); it++)
unvisited.insert(*it);

while(unvisited.size() > 1)
{
// Take first unvisited node
vertex_t firstNode = *(unvisited.begin());

// Explore its tree
std::set<vertex_t> currVisit;
currVisit.insert(firstNode);
explore(firstNode, currVisit);

// Add as a connected component
connectedComponents.push_back(currVisit);

// Remove from unvisited set
for(typename std::set<vertex_t>::iterator it = currVisit.begin(); it != currVisit.end(); it++)
unvisited.erase(*it);
}

// Find set with maximum number of nodes
int maxConnectSize = -1, max_i = 0;
for(int i = 0; i < (int)connectedComponents.size(); i++)
{
int currSize = connectedComponents[i].size();

if(currSize > maxConnectSize){
maxConnectSize = currSize;
max_i = i;
}
}

// Return first node of that maximum set
return *(connectedComponents[max_i].begin());
}

std::set<vertex_t> GetLargestConnectedComponent()
{
std::vector<std::set<vertex_t> > connectedComponents;
std::set<vertex_t> unvisited;

// fill unvisited set
for(typename vertices_set::const_iterator it = vertices.begin(); it != vertices.end(); it++)
unvisited.insert(*it);

while(unvisited.size() > 1)
{
// Take first unvisited node
vertex_t firstNode = *(unvisited.begin());

// Explore its tree
std::set<vertex_t> currVisit;
currVisit.insert(firstNode);
explore(firstNode, currVisit);

// Add as a connected component
connectedComponents.push_back(currVisit);

// Remove from unvisited set
for(typename std::set<vertex_t>::iterator it = currVisit.begin(); it != currVisit.end(); it++)
unvisited.erase(*it);
}

// Find set with maximum number of nodes
int maxConnectSize = -1, max_i = 0;
for(int i = 0; i < (int)connectedComponents.size(); i++)
{
int currSize = connectedComponents[i].size();

if(currSize > maxConnectSize){
maxConnectSize = currSize;
max_i = i;
}
}

// Return first node of that maximum set
return connectedComponents[max_i];
}

void subGraph(Graph & g, const std::set<vertex_t> & explored)
{
for(typename std::set<vertex_t>::const_iterator vi = explored.begin(); vi != explored.end(); vi++)
{

}
}

std::vector< Graph <vertex_t,weight_t> > toConnectedParts()
{
std::vector< Graph <vertex_t,weight_t> > result;

// Make a 'bitmap' of visited nodes
std::map<vertex_t, bool> isVisited;
for(typename std::set<vertex_t>::iterator it = vertices.begin(); it != vertices.end(); it++)
isVisited[*it] = false;

for(typename std::map<vertex_t,bool>::iterator i = isVisited.begin(); i != isVisited.end(); i++)
{
// Check if visited
if(i->second)
continue;

vertex_t seed = i->first;

std::set<vertex_t> explored;
explore(seed, explored);

// Add this new connected sub graph from exploration
result.push_back(Graph<vertex_t, weight_t>());
result.back().subGraph(*this, explored);

// mark as visited the explored
for(typename std::set<vertex_t>::iterator vi = explored.begin(); vi != explored.end(); vi++)
isVisited[*vi] = true;
}

return result;
}

std::list<vertex_t> GetLargestConnectedPath()
{
std::list<vertex_t> longestPath;

std::set<vertex_t> seedSet = GetLargestConnectedComponent();
std::vector<vertex_t> leaves = GetLeaves();

if(!leaves.size())
{
leaves.push_back(*this->vertices.begin());
}

vertex_t seed = leaves.front();

DijkstraComputePaths(seed);

for(typename std::set<vertex_t>::iterator it = seedSet.begin(); it != seedSet.end(); it++)
{
std::list<vertex_t> curPath = DijkstraGetShortestPathTo(*it);

if(curPath.size() > longestPath.size())
longestPath = curPath;
}

return longestPath;
}