#ifndef GRAPH_H

#define GRAPH_H

#include

#include

namespace Graphs{

template class Node{

public:

Node(T value): val(value){}

T val;

};

//no source -- used in adjacency list

template class DirectedEdge{

public:

T source;

T target;

W weight;

DirectedEdge(T s, T t, W w): source(s),target(t),weight(w){}

};

template

class DirectedWeightedGraph{

typedef DirectedEdge DE;

//std::map > > verts;

std::map > verts;

public:

void addVertex(T v){

verts[v]=std::vector >();

}

void addEdge(T source, T target, W weight){

DirectedEdge e(source,target,weight);

verts[source].push_back(e);

}

std::vector< DE > getEdges(T vert){

return verts[vert];

}

std::map< T, int> getIndexMap(){

std::map< T, int> im;

std::vector vs = getVertices();

for(int i = 0;i

im[vs[i]]=i;

}

return im;

}

std::vector getVertices(){

std::vector vs;

for(typename std::map >::iterator it = verts.begin();it!=verts.end();++it){

vs.push_back(it->first);

}

return vs;

}

/***************************************

*Returns adjacency matrix

*

****************************************/

std::vector > getAdjacencyMatrix(W non_adj_filler=W(0)){

std::vector > am;

std::vector vs = getVertices();

int n = vs.size();

for(int i =0;i

am.push_back(std::vector() );

for(int j =0;j

am[i].push_back(non_adj_filler);

}

}

std::map im = getIndexMap();

for(T v:vs){

for(int i =0; i

DE e = verts[v][i];

am[im[v]][im[e.target]] = e.weight;

}

}

return am;

}

std::vector > getBooleanAdjacencyMatrix(){

std::vector > bam;

std::vector vs = getVertices();

int n = vs.size();

for(int i =0;i

bam.push_back(std::vector() );

for(int j =0;j

bam[i].push_back(false);

}

}

std::map im = getIndexMap();

for(T v:vs){

for(int i =0; i

DE e = verts[v][i];

bam[im[e.source]][im[e.target]] = true;

}

}

return bam;

}

/***************************************

* Get Transitive closure

* define this with Warshall's

* careful: this is accessed like a regular matrix (row, then column)

********************************************/

std::vector > getTransitiveClosure(){

std::vector > R = getBooleanAdjacencyMatrix();

return R;

}

/***************************************

* Get All Pairs Shortests Paths

* define this with Floyd's

* careful: this is accessed like a regular matrix (row, then column)

********************************************/

std::vector > getAllPairsShortestPaths(){

//parameter is to indicate "filler"

std::vector > D = getAdjacencyMatrix(std::numeric_limits::infinity());

//Floyd's doesn't start with a regular adjacency matrix (look at diagonal)

return D;

}

};

template

std::string adjMatrix2String(const std::vector & vs, const std::vector > & am){

using std::endl;

std::stringstream ss;

int setwidth = 4;

ss<<"\t"/*setw(setwidth)*/<<" ";

for(T v:vs) {ss << "\t"/*setw(setwidth)*/ <

ss<<" ";

for(int i = 0;i

T v = vs[i];

ss<<"\t"/*setw(setwidth)*/<

for(W w:am[i]) {ss << "\t"/*setw(setwidth)*/<

ss<<" ";

}

return ss.str();

}

}

#endif