int FindMinWeightBridge(const UndirectedGraph& graph) {

    vector<Color> colors(graph.Order(), WHITE);
    DFSVisitor visitor(graph.Order());
    Edge impossible_edge(0, 0, 0, -1);

    DepthFirstSearch(graph, 0, impossible_edge, &colors, &visitor);

    return visitor.MinWeight();
}

TEST(Graph, adjaent) {
  UndirectedGraph graph {20};
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(0, 5);
  Iterator<int>* iter = graph.adjacent(0);
  EXPECT_EQ(5, iter->next());
  EXPECT_EQ(2, iter->next());
  EXPECT_EQ(1, iter->next());
}

int main(int argc, char** argv) {
    int i;

    if (argc != 2) {
        cout << "Spatny pocet parametru" << endl;
        cout << "binarka nazev-souboru" << endl;
        cout << std::endl << "Arguments:" << endl;
        exit(EXIT_FAILURE);
    }

    UndirectedGraph *graph = readGraphFromFile(argv[1]);
    cout << "vertex count=" << graph->vertexCount() << endl;

    DFSSolver *solver = new DFSSolver(graph);

    //time start
    //time_t start = time(NULL);
    //TimeTool(time(NULL)) start;
    TimeTool start(time(NULL));
    //hledani reseni
    pair<vector<Edge> *, int>  *result = solver->findBestSolution();
    //time end
    //time_t end = time(NULL);
    TimeTool end(time(NULL));

    vector<Edge> *solution = result->first;
    int solutionPrice = result->second;
    if (solution != NULL) {
        cout << "Best solution:" << endl;
        for (i = 0; i < solution->size(); i++) {
            cout << (*solution)[i] << endl;
        }
		cout << "Spanning tree degree: " << solutionPrice << endl;
    }

    //Celkovy cas vypoctu
    //double dif = difftime(end, start);
    //int h = dif/3600;
    //int m = dif /60;
    //int s = dif - (h * 3600) - (m * 60);

    //cout << "DIFF:" << dif << "s" << endl;
    //cout << "TIME:" << h << ":" << m << ":" << s << " input file " << argv[1] << endl;

    TimeTool dif (difftime(end.time, start.time));
    //cout << "TIME: " << dif << " input file " << argv[1] << " START:" << start <<" END:" << end << endl;
    cout << "TIME: " << dif << " input file " << argv[1] << endl;

    delete graph;
    delete solution;
    delete result;
    delete solver; // tady to umre

    return 0;
}

TEST_F(UndirectedGraphFixture, canBeCopied)
{
    g_.addEdge(0, 1, 7);
    g_.addEdge(3, 2, 123);
    UndirectedGraph copy { g_ };
    ASSERT_EQ(g_.getWeightOfEdge(0, 1), copy.getWeightOfEdge(0, 1));
    ASSERT_EQ(g_.getWeightOfEdge(2, 3), copy.getWeightOfEdge(2, 3));
    ASSERT_EQ(g_.getNumberOfEdges(), copy.getNumberOfEdges());
    ASSERT_EQ(g_.getNumberOfVertices(), copy.getNumberOfVertices());
    ASSERT_EQ(g_.getSumOfWeights(), copy.getSumOfWeights());
}

UndirectedGraph* GreedyHeuristic::getICTree(UndirectedGraph* t1, UndirectedGraph* t2, list<Edge*>* iset, UndirectedGraph* ug) {

  int cardinality = ((*t1).vertices).size() - 1;
  UndirectedGraph* greedyTree = new UndirectedGraph();
  //cout << "iset size: " << iset->size() << endl;
  Edge* minE = getMinEdge(iset);
  greedyTree->addVertex(minE->fromVertex());
  greedyTree->addVertex(minE->toVertex());
  greedyTree->addEdge(minE);
  generateUCNeighborhoodFor(ug,minE);
  for (int k = 2; k < ((*ug).vertices).size(); k++) {
    Edge* newEdge = getICNeighbor(iset);
    Vertex* newVertex = NULL;
    if (greedyTree->contains(newEdge->fromVertex())) {
      newVertex = newEdge->toVertex();
    }
    else {
      newVertex = newEdge->fromVertex();
    }
    greedyTree->addVertex(newVertex);
    greedyTree->addEdge(newEdge);
    adaptUCNeighborhoodFor(newEdge,newVertex,greedyTree,ug);
  }
  if ((greedyTree->vertices).size() > (cardinality + 1)) {
    shrinkTree(greedyTree,cardinality);
  }
  greedyTree->setWeight(weightOfSolution(greedyTree));
  return greedyTree;
}

bool dfs(int v, int c, UndirectedGraph& g, int* color){

    color[v] = c;

    for(vector<int>::iterator it=g.edge_list_begin(v); it !=g.edge_list_end(v); it++){
        int dst = *it;
        if(color[dst] == c)return false;
        if(color[dst] == 0)
        {
            if(!dfs(dst, -c, g, color))return false;
        }
    }

    return true;
}

int main(int argc, char **argv) {
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << "||||| Should be: <MAXIMUM_NUMBER_OF_VERTICES>" << std::endl;
        return 0;
    }
    std::cout << "The maximus number of vertices is " << argv[1] << std::endl;
    
    
    // Try to translate MAXIMUM_NUMBER_OF_VERTICES
    // to size_t in order to determine the number of vertices.
    try {
        long num_of_nodes = std::stoi(argv[1]);
        if (num_of_nodes < 0) {
            std::cout << "Invalid argument for MAXIMUM_NUMBER_OF_NODES::Must be a positive integer!::TERMINATING PROGRAM\n";
            exit(1);
        }
        
        const size_t max_val = num_of_nodes;
        UndirectedGraph<size_t> testGraph;
        DisjointSet<size_t> testDS;
        
        size_t counter = 1;
        while (counter <= num_of_nodes) {
            testGraph.AddVertex(counter);
            testDS.AddNewNode(counter);
            ++counter;
        }

        srand(time(0)); //use current time as seed for random generator
        while (testDS.Size() > 1) {
            int i1 = rand() % max_val + 1;
            int i2 = rand() % max_val + 1;
            if (testGraph.AddEdge(i1, i2)) {
                testDS.Union(i1, i2);
            }
        }
        
//        testGraph.printGraph();
        testGraph.PrintGraphStats();
        
    } catch (std::invalid_argument) {
        std::cout << "Invalid argument for MAXIMUM_NUMBER_OF_NODES::Must be a positive integer::TERMINATING PROGRAM\n";
        exit(1);
    }
    
    
    return 0;
}

int main(void)
{
	using namespace alg;
	srand(time(NULL));
	int NVERTEX = 10;
	UndirectedGraph * g = UndirectedGraph::randgraph(NVERTEX);
	g->printdot();
	printf("Generating Kruskal's Graph: \n");
	Kruskal pg(*g);
	pg.print();


	printf("Generating Minimal spanning tree: \n");
	Graph * mst = pg.run();
	mst->printdot();
	delete mst;
	delete g;
	return 0;
}

UndirectedGraph* DirectedGraph::convertToUndirectedGraph() {
	UndirectedGraph* result = new UndirectedGraph(maxNodeId);
	for (int i = 0; i != maxNodeId + 1; i++) {
		if (!hasNode(i))
			continue;
		ListType* neighborsList = inNeighborsTable[i];
		for (ListType::iterator neighbor = neighborsList->begin();
				neighbor != neighborsList->end(); neighbor++) {
			result->addEdge(*neighbor, i);
		}
		neighborsList = outNeighborsTable[i];
		for (ListType::iterator neighbor = neighborsList->begin();
				neighbor != neighborsList->end(); neighbor++) {
			result->addEdge(*neighbor, i);
		}
	}
	result->sort();
	return result;
}

int main( int argc, char **argv ) {

    if ( argc < 2 ) {
        print_help();
        exit(1);
    }
    else {
        read_parameters(argc,argv);
    }

    // initialize random number generator

    rnd = new Random((unsigned) time(&t));

    // initialize and read instance from file

    graph = new UndirectedGraph(i_file);
    GreedyHeuristic gho(graph);

    for (int i = cardb; i <= carde; i++) {
        cardinality = i;
        if ((cardinality == cardb) || (cardinality == carde) || ((cardinality % cardmod) == 0)) {
            Timer timer;

            UndirectedGraph* greedyTree = new UndirectedGraph();
            if (type == "edge_based") {
                gho.getGreedyHeuristicResult(greedyTree,cardinality,ls);
            }
            else {
                if (type == "vertex_based") {
                    gho.getVertexBasedGreedyHeuristicResult(greedyTree,cardinality,ls);
                }
            }

            printf("%d\t%f\t%f\n",cardinality,greedyTree->weight(),timer.elapsed_time(Timer::VIRTUAL));

            delete(greedyTree);
        }
    }
    delete(graph);
    delete rnd;
}

UndirectedGraph * readGraphFromFile(char * filename) {
    char token;
    int x=0, y=0, i=0;
    int nodes_count = 0;
    UndirectedGraph *graph;
    
    FILE *file = fopen(filename, (const char *)"r");
    if (file == NULL) {
        std::cout << "Neexistujici soubor:" << filename << endl;
        exit(EXIT_FAILURE);
    }

    if (fscanf(file, "%d", &nodes_count) != 1) {
        std:cout << "Nelze nacist prvni radek vstupniho souboru" <<endl;
        exit(EXIT_FAILURE);
    }
    
    graph = new UndirectedGraph(nodes_count);
    while (fscanf(file, "%c", &token) == 1) {
        if (token == '\r') {
            continue;
        }
        if (token == '\n') {
            //printf("\n");
            if (i > 0) {
                x=0;
                y++;
            }
            
            continue;
        }
        if(token == '1') {
            graph->addEdge(x,y);
        }
        x++;
        i++;
    }
	fclose(file);
    return graph;
}

/**
 * Removes all edges from the graph except those necessary to
 * form a minimum cost spanning tree of all vertices using Prim's
 * algorithm.
 *
 * The graph must be in a state where such a spanning tree
 * is possible. To call this method when a spanning tree is
 * impossible is undefined behavior.
 */
UndirectedGraph UndirectedGraph::minSpanningTree() {
  // Define based on the Wikipedia Pseudocode
  UndirectedGraph nug;
  
  std::priority_queue<Edge> edges;

  for (vertexmap::iterator vi = this->vertices.begin();
       vi != this->vertices.end();
       vi++)
    vi->second->setVisited(false);

  Vertex *cur = this->vertices.begin()->second;
  cur->setVisited(true);
  for (Vertex::edgemap::iterator ei = cur->edges.begin();
       ei != cur->edges.end();
       ei++)
    edges.push(ei->second);
  
  while (!edges.empty() && nug.vertices.size() < this->vertices.size()) {
    Edge small = edges.top();
    edges.pop();
    Vertex *to = small.getTo();
    
    if (to->wasVisited())
      continue;
    else {
      to->setVisited(true);
      nug.addEdge(small);
      for (Vertex::edgemap::iterator ei = to->edges.begin();
	   ei != to->edges.end();
	   ei++)
	if (!ei->second.getTo()->wasVisited())
	  edges.push(ei->second);
    }
  } // END WHILE

  return nug;
}

void DepthFirstSearch(const UndirectedGraph& graph, int vertex, const Edge& incoming_edge,
        vector<Color>* colors, DFSVisitor* visitor) {

    colors->at(vertex) = GREY;
    visitor->EnterVertex(vertex);

    UndirectedGraph::EdgeIterator edge;
    for (edge = graph.EdgesBegin(vertex); edge != graph.EdgesEnd(vertex); ++edge) {
        if (edge->id == incoming_edge.id) {
            continue;
        }

        if (colors->at(edge->head) == GREY) {
            visitor->BackEdge(*edge);
        }

        if (colors->at(edge->head) == WHITE) {
            DepthFirstSearch(graph, edge->head, *edge, colors, visitor);
            visitor->TreeEdge(*edge);
        }
    }
    colors->at(vertex) = BLACK;
}

      explicit ConnectedComponentsDecomposer(const UndirectedGraph<>& g) {
        int nVertices = g.num_vertices();
        vertexToComponent_.clear();
        vertexToComponent_.resize(nVertices);
        fill(begin(vertexToComponent_), end(vertexToComponent_), -1);

        int iComponent = 0;
        for (int i = 0; i < nVertices; ++i) {
            if (vertexToComponent_[i] >= 0)
                continue;  // Lies in processed component

            components_.push_back(std::vector<int>());
            dfs(g, {i}, [&](const GraphTraversalState& state, int index) {
                components_.back().push_back(index);
                vertexToComponent_[index] = iComponent;
                return IterationControl::Proceed;
            });
            iComponent++;
        }
    }

// check whether graph is a bigraph or not with dfs
bool bigraph(UndirectedGraph& g){
    int num_vertex = g.get_num_vertex();
    int* color = (int *)malloc(sizeof(int)*num_vertex);
    memset(color, 0, num_vertex*sizeof(int));

    bool result = true;

    for(int i=0;i<num_vertex;i++){
        if(color[i]==0){
            if(!dfs(i, 1, g, color)){
                result = false;
                break;
            }
        }
    }

    free(color);

    return result;
}

/**
 * Entry point into the netplan program.
 *
 * -Reads a file from the filesystem according to the specification for
 *  PA3, creating an UndirectedGraph.
 * -Finds the total cost & ping time of the graph as presented in the input
 *  file.
 * -Determines the minimum cost graph from the original graph.
 * -Finds the total cost & ping time of the minimum cost graph.
 * -Finds the change of cost & ping time from the original graph to the
 *  minimum cost graph.
 * -Prints the results to stdout.
 *
 * Usage:
 *   ./netplan infile
 *
 */
int main(int argc, char **argv) {
    // Data Structs to hold the variables
    vector<string> to;
    vector<string> from;
    vector<unsigned int> cost;
    vector<unsigned int> length;

    // if number of arguments passed in is not 2, print usage
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " infile" << std::endl;
        return EXIT_FAILURE;
    }
    
    std::ifstream in(argv[1]);
    if (!in) {
        std::cerr << "Unable to open file for reading." << std::endl;
        return EXIT_FAILURE;
    }

    // string and int variables for adding to the vectors
    string str;
    unsigned int i;

    /**
     * while file is not empty, parse input so that we can make a graph from
     * the input
     */
    while(true){
        in >> str;
        if(in.eof()) break;
        to.push_back(str);

        in >> str;
        from.push_back(str);

        in >> i;
        cost.push_back(i);

        in >> i;
        length.push_back(i);
    }

    /**
     * create undirected graph from the input file
     */
    UndirectedGraph *bob = new UndirectedGraph();
    for(unsigned int j = 0; j < to.size(); j++){
        bob->addEdge(to[j], from[j], cost[j], length[j]);
    }

    // get total edge cost of inital graph
    unsigned int totalCost = bob->totalEdgeCost();

    // get total distance of inital graph, by using Dijkstra's algorithm on 
    // all the vertices
    unsigned int totalTime = bob->totalDistance();

    // create minimum spanning tree of the inital graph, using Prim's algorithm
    bob->minSpanningTree();

    // get total edge cost of minimum spanning tree
    unsigned int mstCost = bob->totalEdgeCost();

    // get total distance of minimum spanning tree, using Dijkstra's algorithm
    // on all the vertices
    unsigned int mstTime = bob->totalDistance();

    // print out all the costs and distances
    cout << totalCost << endl;
    cout << mstCost << endl;
    cout << totalCost - mstCost << endl;
    cout << totalTime << endl;
    cout << mstTime << endl;
    cout << mstTime - totalTime << endl;

    // delete graph
    delete(bob);

    return EXIT_SUCCESS;
}

int main() {
    cout << "--------------GRAPHTESTERFILE-----------------" << endl;

    cout << "CREATING GRAPH" << endl;
    UndirectedGraph testG = UndirectedGraph();

    cout << "ADDING EDGE WITHOUT ANY VERTICES EXISTING" << endl;
    testG.addEdge("Yahoo","Google",13,13);

    cout << "total edge cost: ";
    cout << testG.totalEdgeCost() << endl;

    cout << "ADDING DUPLICATE" << endl;
    testG.addEdge("Yahoo","Google",9,9);

    cout << "total edge cost: ";
    cout << testG.totalEdgeCost() << endl;

    cout << "ADDING REVERSED DUPLICATE" << endl;
    testG.addEdge("Google","Yahoo",7,7);

    cout << "total edge cost: ";
    cout << testG.totalEdgeCost() << endl;    

    cout << "ADDING EDGE" << endl;
    testG.addEdge("Yahoo","Microsoft",71,71);
    cout << "total edge cost: ";    
    cout << testG.totalEdgeCost() << endl;

    cout << "ADDING UNCONNECTED EDGE" << endl;
    testG.addEdge("Netflix","Yelp",21,21);
    cout << "total edge cost: ";    
    cout << testG.totalEdgeCost() << endl;

    cout << "SETTING UP NON-MST" << endl;
    testG.addEdge("Google","Yahoo",2,2);
    testG.addEdge("Yahoo","Microsoft",3,3);
    testG.addEdge("Microsoft","Netflix",5,5);
    testG.addEdge("Netflix","Yelp",7,7);
    testG.addEdge("Yelp","Google",11,11);
    testG.addEdge("Netflix","Google",13,13);
    testG.addEdge("Google","Microsoft",17,17);

    cout << "total edge cost: ";    
    cout << testG.totalEdgeCost() << endl;

    cout << "CREATING MST" << endl;
    testG.minSpanningTree();
    cout << "total edge cost: ";        
    cout << testG.totalEdgeCost() << endl;

    cout << "TEST TOTAL DISTANCE" << endl;
    cout << "total distance: ";
    cout << testG.totalDistance("Google") << endl;

    cout << "TEST TOTAL DISTANCE NEW GRAPH" << endl;
    UndirectedGraph graphTwo = UndirectedGraph();
    graphTwo.addEdge("Google","Yahoo",2,2);
    graphTwo.addEdge("Yahoo","Microsoft",3,3);    
    cout << graphTwo.totalDistance("Google") << endl;
    cout << graphTwo.totalDistance("Yahoo") << endl;
    cout << graphTwo.totalDistance("Microsoft") << endl;
    cout << graphTwo.totalDistance() << endl;

    return 1;
}

int main( int argc, char **argv ) {

    if ( argc < 2 ) {
        cout << "something wrong" << endl;
        exit(1);
    }
    else {
        read_parameters(argc,argv);
    }
    Timer initialization_timer;

    rnd = new Random((unsigned) time(&t));

    graph = new UndirectedGraph(i_file);

    init_pheromone_trail();

    register int i = 0;
    register int j = 0;
    register int k = 0;
    register int b = 0;

    cout << endl;
    for (int card_counter = cardb; card_counter <= carde; card_counter++) {
        cardinality = card_counter;
        if ((cardinality == cardb) || (cardinality == carde) || ((cardinality % cardmod) == 0)) {
            printf("begin cardinality %d\n",cardinality);

            if (tfile_is_given) {
                if (times.count(cardinality) == 1) {
                    time_limit = times[cardinality];
                }
            }
            vector<double> results;
            vector<double> times_best_found;
            double biar = 0.0;

            int n_of_ants = (int)(((double)((*graph).edges).size()) / ((double)cardinality));
            if (n_of_ants < 15) {
                n_of_ants = 15;
            }
            if (n_of_ants > 50) {
                n_of_ants = 50;
            }

            if (ants.size() > 0) {
                for (list<KCT_Ant*>::iterator anAnt = ants.begin(); anAnt != ants.end(); anAnt++) {
                    delete(*anAnt);
                }
            }
            ants.clear();

            for (i = 0; i < n_of_ants; i++) {
                KCT_Ant* ant = new KCT_Ant();
                ant->initialize(graph,rnd,pheromone,daemon_action);
                ants.push_back(ant);
            }

            for (int trial_counter = 1; trial_counter <= n_of_trials; trial_counter++) {
                printf("begin try %d\n",trial_counter);

                UndirectedGraph* best = NULL;
                UndirectedGraph* newSol = NULL;
                UndirectedGraph* restartBest = NULL;

                double ib_weight = 0.0;
                double rb_weight = 0.0;
                double gb_weight = 0.0;

                Timer timer;

                if ((!(card_counter == cardb)) || (!(trial_counter == 1))) {
                    reset_pheromone_trail();
                    for (list<KCT_Ant*>::iterator ant = ants.begin(); ant != ants.end(); ant++) {
                        (*ant)->restart_reset();
                    }
                }

                int iter = 1;
                double cf = 0.0;
                bool restart = false;
                bool program_stop = false;
                bool bs_update = false;

                while (program_stop == false) {

                    for (list<KCT_Ant*>::iterator ant = ants.begin(); ant != ants.end(); ant++) {
                        for (k = 0; k < cardinality; k++) {
                            (*ant)->step(0.8);
                        }
                        (*ant)->evaluate();
                    }

                    if (!(newSol == NULL)) {
                        delete(newSol);
                    }
                    if (elite_action == "no") {
                        newSol = getBestDaemonSolutionInIteration();
                    }
                    else {
//.........这里部分代码省略.........

inline void HexBoard::getNeighbors(const int index, vector<int> &neighbors)
{
  board.getNeighbors(index, neighbors);
}

inline HexBoardPiece HexBoard::get(const int index)
{
  return board.getNodeValue(index);
}