map<char *, int> dijkstra(graph g, char* source_node) {
	int MAX_INT = 63356  ;
	// build the heap
	heap nodes_heap;
	// create a map with not visited nodes

	map<char *, int> m_not_visited;
	graph::iterator it;
	for( it = g.begin(); it != g.end(); it++)
	{
		if( strcmp(it->first, source_node) ){
			nodes_heap.push(make_pair(MAX_INT, it->first));
			m_not_visited.insert(make_pair(it->first, MAX_INT));
		}
	}

	m_not_visited.insert(make_pair(source_node, 0));
	// initialize the map that will store the shortest paths.

	map<char *, int> m_shortest_path;
	m_shortest_path.insert( make_pair(source_node , 0) );

	while(nodes_heap.size() > 0){
		pair<int, char*> node = nodes_heap.top();
		if( m_not_visited.find( node.second ) == m_not_visited.end() )
			continue;
		m_shortest_path[node.second] = node.first;
		update_heap(nodes_heap, g, source_node, m_not_visited, node.first);
		m_not_visited.erase(node.second);
	}
	return m_shortest_path;
}

void kruskal(graph &g, graph &sf)
// from weighted graph g, set sf to minimum spanning forest
// uses a priority queue with edges sorted from large to min weight
// since top of queue is the back of underlying vector
// for every edge, add to sf, but if it creates cycle, then
// remove it and move to next edge
{
    g.clearMark();
    pqueue edges = getEdges(g);
    while (!edges.empty())
    {
        edgepair pair = edges.top();
        edges.pop();
        
        // add both edges to create undirected edges
        sf.addEdge(pair.i, pair.j, pair.cost);
        sf.addEdge(pair.j, pair.i, pair.cost);

        if (isCyclic(sf))
        {
            sf.removeEdge(pair.i, pair.j);
            sf.removeEdge(pair.j, pair.i);
        }
    }
}

void mst::kruskal(graph g) {
    int num = g.num_of_vertices();
    vector< vector<float> > edges;
    union_find explored;
    reset();

    // put all connected vertices in "edges"
    for(int i=0; i<num; ++i) {
        for(int j=0; j<num; ++j) {
            float c = g.cost(i, j);
            if (c!=0) {
                vector<float> temp;
                temp.push_back(i);
                temp.push_back(j);
                temp.push_back(c);
                edges.push_back(temp);
            }
        }
    }
    sort(edges.begin(), edges.end(), kruskal_compare);

    for(vector<vector<float> >::iterator  p=edges.begin(); p!=edges.end(); ++p) {
        // both nodes in the closed set ==> detecting a cycle
        vector<float> temp = *p;
        int f1 = explored.find(temp[0]);
        int f2 = explored.find(temp[1]);
        if(f1!=-1 && f2!=-1 && f1==f2) continue;
        path_cost += temp[2];
        explored.insert(temp[0], temp[1]);
        //cout <<"From "<<temp[0]<<" To "<<temp[1]<<" -- Cost "<<temp[2]<<endl;
    }
    // ckeck if there are isolated nodes
    if (explored.num_of_unions() != 1) path_cost=-1;
}

void findCities(graph<int>& g, LList<int>& cities, int cityId, int p){
	elem_link1<int>* start = g.point(cityId);
	int dist[100];	// 100???
	bool visited[100];	// 100??? - nikoi ne garantira, che id-tata na cities shte sa posledovatelni chisla pod 100
	memset(dist, -1, 100);
	memset(visited, 0, 100);

	if (start){
		visited[start->inf] = true;
		dist[start->inf] = 0;
		queue<int> q;
		q.push(start->inf);
		while (!q.empty()){
			int current = q.front();
			q.pop();
			elem_link1<int>* p = g.point(current);
			p = p->link;
			while (p){
				if (!visited[p->inf]){
					visited[p->inf] = true;
					dist[p->inf] = dist[current] + 1;
					q.push(p->inf);
				}
				p = p->link;
			}

		}

		for (int i = 0; i < 100; i++){
			if (dist[i] >= 0 && dist[i] <= p){
				cities.toEnd(i);
			}
		}
	}
}

// calculate the path using dijkstra's algo.
void dijkstra::path(graph g, int u, int v) {
    int num = g.num_of_vertices();
    minheap* candidates = new minheap(num);
    // reset the path_cost and clear the closed_set
    reset();

    // initialize the heap
    // the nodes in the heap are those of "open set"
    for (int i=0; i<num; ++i) {
        float c = g.cost(u, i);
        if (c!=0)
            candidates->update(c, i);
    }

    while (candidates->size()!=0) {
        heapitem t = candidates->pop();
        int node = t.get_node();
        // not record the duplicated probed nodes
        if (closed_set.find(node)!=closed_set.end())
            continue;
        closed_set.insert(node);
        path_cost = t.get_key();
        // terminated if arrives at the destination
        if (node == v)
            return;
        vector<int> n = g.neighbors(node);
        // update the heap with newly found nodes
        for(vector<int>::iterator i=n.begin(); i!=n.end(); ++i) {
            candidates->update(path_cost+g.cost(node,*i), *i);
        }
    }
    // after iteration, the v is not found
    path_cost = -1;
}

vector<int> daiquistra(graph& g, int v){
	vector<int> dist(g.size(), INT_MAX);
	vector<int> prev(g.size(), -1);
	
	dist[v] = 0;
	set<pair<int, int> > q;
	for(int i = 0; i<g.size(); i++){
		q.insert(make_pair(dist[i], i));
	}
	
	while(!q.empty()){
		int u = q.begin()->second;
		int p = q.begin()->first;
		q.erase(q.begin());
		if(dist[u] == INT_MAX)
			break;
		
		for(int i = 0; i<g[u].size(); i++){
			int w = g[u][i].second;
			int alt = dist[u] + g[u][i].first;
			if(alt < dist[w]){
				q.erase(make_pair(dist[w], w));
				dist[w] = alt;
				prev[w] = u;
				q.insert(make_pair(dist[w], w));
			}
		}
	}
	
	return prev;	
}

bool CDLib::read_edgelist(graph& g, const string& filepath) {
    g.clear();
    ifstream ifs;
    ifs.open(filepath.c_str());
    if (ifs.is_open()) {
        vector<string> units;
        double weight;
        while (!ifs.eof()) {
            weight = 1;
            string line;
            getline(ifs, line);
            if ((line.size() > 0) && (line[0] != '#')) {
                split(line, units);
                if (units.size() != 0) {
                    if ((units.size() < 2) || (units.size() > 3)) return false;
                    if (units.size() == 3) weight = str2T<double>(units[2]);
                    g.add_node(units[0]);
                    g.add_node(units[1]);
                    g.add_edge(units[0], units[1], weight);
                }
            }
        }
        g.set_graph_name(filename(filepath));
        return true;
    }
    return false;
}

graph kruskal (graph &rede){

	graph result;
	int max_custo = 0;

	graph::iterator it;
	int no1, no2;
	vertice v;

	for (it = rede.begin(); it != rede.end(); it++){

		v = it->second;
		
		no1 = v.first;
		no2 = v.second;

		if (findset(no1) != findset(no2)){

			v = ordena (v.first, v.second);

			result.insert (make_pair (0, v));
			join (no1, no2);
			max_custo += it->first;
		}
		
		
	}

	cout << max_custo << endl;
	return result;
}

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;
}

bool circuit::goodCircuit()
{
    matrix<int> adj2 = circuit_graph.adjacency_matrix();
    adj2 = adj2*adj2;
    for(int i=0;i<circuit_graph.nVertices();i++) if(adj2(i,i)<2) return false;
    return circuit_graph.isConnected();
}

void path(town start, graph<town>& g, int p, LList<town> &visited){
	if (g.empty())return;
	int count = 0;
	queue<town> q;
	q.push(start);
	visited.toEnd(start);

	elem_link1<town> * f = g.point(start);
	f = f->link;
	while (!q.empty()){
		town t;
		q.pop(t);

		while (f){
			if (p == count)return;
			else if (!member(visited, f->inf)){

				q.push(f->inf);
				visited.toEnd(f->inf);
				count++;
			}

			f = f->link;
		}
	}
}

void findCycle(int curr, int start, bool &found, graph &g)
	// checks for cycles in a graph
{
	g.mark(curr);

	vector<int> lst = getNeighbors(curr, g);

	for (int i = 0; i < lst.size(); i++)
	{
		if (start == lst[i])
		{
			continue;
		}
		if (g.isMarked(lst[i]))
		{
			found = true;
		}
		else if (!g.isVisited(lst[i]))
		{
			findCycle(lst[i], curr, found, g);
		}
	} // for

	g.unMark(curr);
	g.visit(curr);

} // findCycle

void findSpanningForest(graph &g, graph &sf)
	// Create a graph sf that contains a spanning forest on the graph g.
{
	if (isConnected(g) && !isCyclic(g))
	{
		sf = g;
	}
	else
	{
		// add nodes to sf
		for (int i = 0; i < g.numNodes(); i++)
		{
			sf.addNode(g.getNode(i));
		}

		// build sf
		for (int i = 0; i < g.numNodes(); i++)
		{
			for (int j = 0; j < g.numNodes(); j++)
			{
				if (g.isEdge(i, j) && !sf.isEdge(i, j))
				{
					sf.addEdge(i, j, g.getEdgeWeight(i, j));
					sf.addEdge(j, i, g.getEdgeWeight(j, i));

					if(isCyclic(sf))
					{
						sf.removeEdge(j, i);
						sf.removeEdge(i, j);
					} // if
				} // if
			} // for
		} // for
	} // else
} // findSpanningForest

void order_subgraphs_wrapper(vector<subgraph*> &sgorder, subgraph *sg, 
                             graph &g) {
	// simplify the call to the above order subgraphs
	deque<vertex> order;
  	map<vertex,subgraph*> new_sub;
  	map<vertex,vertex> new_old;
  	
  	if (sg == 0) {
  		vector<vertex> verts;
	  	for (unsigned int i = 0; i != g.num_vertices(); ++i)
	    	if (g.find_parent(i) == 0 && (g.adj(i).size() > 0 || g.inv_adj(i).size() > 0))
	      		verts.push_back(i);
	  	
	  	order_subgraphs(order, new_sub, new_old, 0, verts, g.subgraphs, g);
  	}
  	else {
  		order_subgraphs(order, new_sub, new_old, sg, sg->vertices, sg->subs, g);
  	}
  	
  	map<vertex,subgraph*>::iterator itr = new_sub.begin();
  	for (unsigned int i = 0; i < order.size(); i++) {
        map<vertex,subgraph*>::iterator iter = new_sub.find(order[i]);
    	if (iter != new_sub.end()) {
            sgorder.push_back(iter->second);
        }
    }
}

void topo_sort(graph& g, deque<vertex>& order) 
{
    vector<bool> visited(g.num_vertices(), false);
    for (vertex i = 0; i != g.num_vertices(); ++i)
        if (! visited[i])
            topo_sort_r(i, g, order, visited);
}

vector<string> vertex_cover(const graph g) {
	vector<connection> list;
	copy(g.begin(), g.end(), back_inserter(list));

	sort(list.begin(), list.end(), [](connection a, connection b) {
		return a.second.size() > b.second.size();
	});

	vector<string> cover;
	while (list.size()) {
		connection max = list.at(0);
		cover.push_back(max.first);

		list.erase(list.begin());

		for (string conc : max.second) {
			if (!list.size())
				break;

			auto to_remove = find_if(list.begin(), list.end(), [conc](connection c) {
				return c.first == conc;
			});

			if (to_remove != list.end()) {
				list.erase(to_remove);
			}
		}
	}

	return cover;
}

void update_iters_sg(graph &g, subgraph *sg) {
	vector<iterOp_t>::iterator i;
	for (i = sg->sg_iterator.conditions.begin();
			i != sg->sg_iterator.conditions.end(); ++i) {

		vector<string> separate;
		boost::split(separate, i->right, boost::is_any_of("+"));

		string newString = g.get_iter_rep(separate[0]);
		for (unsigned int k=1; k < separate.size(); ++k) {
			newString += "+" + g.get_iter_rep(separate[k]);
		}
		i->right = newString;
	}

	for (i = sg->sg_iterator.updates.begin();
			i != sg->sg_iterator.updates.end(); ++i) {

		vector<string> separate;
		boost::split(separate, i->right, boost::is_any_of("+"));

		string newString = g.get_iter_rep(separate[0]);
		for (unsigned int k = 1; k < separate.size(); ++k) {
			newString += "+" + g.get_iter_rep(separate[k]);
		}
		i->right = newString;
	}

	for (auto i : sg->subs) {
		update_iters_sg(g, i);
	}
}

void recursiveDFS(int curId, int dstId, graph &g,
                  stack<int> &path, bool &done)
// depth first search that uses the mem stack to search the graph g
{

    if (curId == dstId)
    {
        done = true;
        path.push(curId);
    }
    else
    {
        g.mark(curId);
        g.visit(curId);

        vector<int> lst = getNeighbors(curId, g);

        while (!lst.empty())
        {
            int current =  lst.back();
            lst.pop_back();

            if (!g.isVisited(current))
            {
                recursiveDFS(current, dstId, g, path, done);
            }
            if (done)
                // if we found our node then construct our path
            {
                path.push(curId);
                break;
            }
        }
    }
}

    //------------------------------------------------------------------------
    void draw_dashes_draft()
    {
        pixfmt pixf(rbuf_window());
        base_renderer rb(pixf);
        primitives_renderer prim(rb);
        outline_rasterizer ras(prim);

        int i;
        for(i = 0; i < m_graph.get_num_edges(); i++)
        {
            graph::edge e  = m_graph.get_edge(i);
            graph::node n1 = m_graph.get_node(e.node1, width(), height());
            graph::node n2 = m_graph.get_node(e.node2, width(), height());
            curve c(n1.x, n1.y, n2.x, n2.y);
            dash_stroke_draft<curve> s(c, 6.0, 3.0, m_width.value());

            int r = rand() & 0x7F;
            int g = rand() & 0x7F;
            int b = rand() & 0x7F;
            int a = 255;
            if(m_translucent.status()) a = 80;
            prim.line_color(agg::srgba8(r, g, b, a));
            ras.add_path(s);
        }
    }

bool maze::findShortestPath1(graph &g)
//finds the shortest path in the given graph using DFS
{

    g.clearVisit();
    g.clearMark();
    int start = getMap(0, 0);
    int end = getMap(numRows() - 1, numCols() - 1);
    vector< stack<int> > rpaths = nonRecursiveDFS(start, end, g);

    stack<int> reverse_path;

    for(int i = 0; i < rpaths.size(); i++)
        if (rpaths[i].size() > reverse_path.size())
            reverse_path = rpaths[i];

    stack<int> path;

    while (!reverse_path.empty())
    {
        int top = reverse_path.top();
        reverse_path.pop();
        if (g.isVisited(top))
        {
            path.push(top);
        }
    }

    printPath(path);

}