depthFirstTraverse полностью в C++?


Интересно, если это полностью в C++, и если не может кто-то поможет мне рассказать различия. Это был представлен мне в прошлом семестре, и получил хорошую оценку. Я в настоящее время пытаюсь убедиться, что я могу сказать C++ и C врозь.

#include <fstream>
#include <stack>
#include <stdlib.h>  //Not neccessary in C++
#define swap(type, a, b) {type t = a; a = b; b = t;}
using namespace std;

typedef struct {
    int degree, *adjList, //arraySize = degree
        nextToVisit, //0 <=nextToVisit < degree
        parent, dfLabel, nodeName;
} GraphNode;

int numNodes, startNode = 1;
GraphNode *nodes;

void readGraph();
void depthFirstTraverse(int startNode);

int main() {
    readGraph();
    depthFirstTraverse(startNode);
}

void depthFirstTraverse(int startNode) {
    int nextNode, dfLabels[numNodes], nextToVisit[numNodes], parents[numNodes], lastDFLabel = 0;
    stack<int> stackArray;
    for (int i = 0; i < numNodes; i++) dfLabels[i] = nextToVisit[i] = 0;
    stackArray.push(startNode);
    printf("startNode = %d, dfLabel(%d) = %d\n",startNode,startNode,1);
    while (!stackArray.empty()) {
        if (0 == dfLabels[stackArray.top()]) {
            lastDFLabel++;
            dfLabels[stackArray.top()] = lastDFLabel; }
        if (nextToVisit[stackArray.top()] == nodes[stackArray.top()].degree) {
            if (lastDFLabel < numNodes) {
                printf("backtracking %d", stackArray.top());
                stackArray.pop();
                printf(" -> %d\n", stackArray.top()); }
            else { printf("backtracking %d -> %d\n", stackArray.top(), startNode);
                stackArray.pop(); }
        }
        else { nextNode = nodes[stackArray.top()].adjList[nextToVisit[stackArray.top()]];
            nextToVisit[stackArray.top()]++;
            if (0 == dfLabels[nextNode]) {
                parents[nextNode] = stackArray.top();
                printf("processing (%d, %d): tree-edge, dfLabel(%d) = %d\n",
                    stackArray.top(), nextNode, nextNode, lastDFLabel+1);
                stackArray.push(nextNode); }
            else if (dfLabels[nextNode] < dfLabels[stackArray.top()]) {
                if (nextNode != parents[stackArray.top()])
                    printf("processing (%d, %d): back-edge\n", stackArray.top(), nextNode);
                else printf("processing (%d, %d): tree-edge 2nd-visit\n", stackArray.top(), nextNode); }
            else printf("processing (%d, %d): back-edge 2nd-visit\n", stackArray.top(), nextNode);
        }
    } for (int i = 0; i < 30; i++) printf("-");
}

void readGraph() {
    char ignore;
    ifstream digraph("digraph.data");
    digraph >> numNodes;
    nodes = new GraphNode[numNodes];
    for (int i = 0; i < numNodes; i++) {
        digraph >> nodes[i].nodeName >> ignore >> nodes[i].degree >> ignore;
        nodes[i].adjList = new int[nodes[i].degree];
        for (int j = 0; j < nodes[i].degree; j++) digraph >> nodes[i].adjList[j];
    } digraph.close();
    printf ("Input Graph:\nnumNodes = %d\n", numNodes);
    for (int i = 0; i< numNodes; i++) {
        printf("%d (%d): ", nodes[i].nodeName, nodes[i].degree);
        for (int j = 0; j < nodes[i].degree; j++)
            for (int k = 0; k < j; k++)
                if (nodes[i].adjList[j] < nodes[i].adjList[k]) 
                    swap(int, nodes[i].adjList[j], nodes[i].adjList[k]);
        for (int j = 0; j < nodes[i].degree; j++) printf("%d ", nodes[i].adjList[j]);
        printf("\n");
    } for (int i = 0; i < 30; i++) printf("-");
    printf ("\n");
}


442
4
задан 14 августа 2011 в 11:08 Источник Поделиться
Комментарии
2 ответа

Это все-таки ближе к C, чем c++ ИМО.

Первые два номера C++ проблем:


  1. Вы не инкапсулировать свои классы. Весь ваш интерфейс общественности. Таким образом, вы теперь обречены вечно поддерживать этот интерфейс для вечности. Кроме того, он позволяет другим людям, чтобы случайно не изменить свою структуру. Использовать системы класса C++ для инкапсуляции объектов и по крайней мере защитить ваши объекты от случайного Мисс использовании.

  2. Ваше дерево-обход на самом деле зависит от объекта узел, чтобы отслеживать перемещения. Теперь это плохая дизайнерская вещь. Вы связываете себя на реализацию и ограничения использования код. Вы должны демонстративно посмотреть на посетителя шаблон.

Остальные c++ проблем:

Вы делаете управление ресурсами вручную:

nodes = new GraphNode[numNodes];             
// STUFF
nodes[i].adjList = new int[nodes[i].degree];

Было бы лучше использовать std::вектор, по крайней мере, что бы быть исключением, безопасный в управлении ресурсами:

std::vector<GraphNode>   nodes(numNodes);

Вы вручную загрузки узлов. Если узел не знают, как себя потока на поток?

    digraph >> nodes[i].nodeName >> ignore >> nodes[i].degree >> ignore;

Я бы ожидал, чтобы она выглядела так:

    digraph >> nodes[i];

Или еще лучше создавать предметы и толкать их в вектор:
Поскольку единственное, что кажется в файле "диграф.данных", кажется, GraphNodes тогда вы могли бы сделать что-то вроде этого:

std::copy(std::istream_iterator<GraphNode>(digraph),
std::istream_iterator<GraphNode>(),
std::back_inserter(nodes) // Assuming nodes is a vector described above.
);

Это не c++

    printf("%d (%d): ", nodes[i].nodeName, nodes[i].degree);

Проблема с стиля printf является то, что он не является типобезопасным. Основное преимущество С++ над C-это исключительная безопасность тип языка. Используйте это в ваших интересах.

Это так плохо, я чуть не проглотил свой язык.:

                swap(int, nodes[i].adjList[j], nodes[i].adjList[k]);

У вас есть #определенными своп.


  1. Используйте все крышки для макросов.
    Причина в том, чтобы убедиться, что макросы не конфликтуют с другими идентификаторами.

  2. Макросы не типобезопасным.
    Если было преобразование этого объекта в int компилятор будет счастливо сделать это.

  3. Есть уже типа безопасный макрос в качестве части стандартной библиотеки.
    Если вы хотите переопределить поведение по умолчанию, подкачки нужно просто переписать конкретного типа версии и объектов Koenig автоматически найти его.

Не большое дело, но предпочитают пре-инкремент. Причина не имеет значения для Pod типов, но для пользовательских типов это делает (или потенциально делает) материи. Если сопровождающий на последнем этапе меняется тип переменной цикла, то вы не должны пойти и изменить код префиксный инкремент-это уже правильный тип.

 for (int i = 0; i < 30; ++i)
// ^^^^ Prefer pre-increment here

Не объявить несколько переменных в одной строке:

int nextNode, dfLabels[numNodes], nextToVisit[numNodes], parents[numNodes], lastDFLabel = 0;

Каждый стандарт кодирования расскажет вам не делать этого. Так что привыкай. Технически есть несколько случаев, которые будут бить тебя и класть каждую переменную на отдельной строке делает его более удобным для чтения. Также обратите внимание, похоже, вы не инициализировать все значения на ноль. Это не происходит так что все эти (кроме последней) не определены.

Также определение массивов с Тип затрат технически не допускается.

dfLabels[numNodes],

Некоторые компиляторы позволяют это, потому что это расширение С90. Но ее не очень портативный. Использовать std::вектор (или std::массив) вместо.

Не ставьте код в той же строке, как закрыть скобки.
Я dobt кто-нибудь нравится даже людей, которые хотят сохранить вертикальные линии пространства.

} for (int i = 0; i < 30; i++) printf("-");

И я предпочитаю, чтобы положить заявление на цикл for будет выполняться в следующей строке, так что очевидно, что происходит (но я не волнует, что многое о нем).

typedefing структуры не требуется в C++

typedef struct {
// BLAH
} GraphNode;

Это просто

struct GraphNode
{
// BLAH
};

Когда вы петли над вашим контейнеров используется стиль C (т. е. вы используете индекс). Обычно это более условно, чтобы использовать итератор стиль показателя за контейнер (даже простой массив). Таким образом, если вы решите переехать к себе другой стиль контейнер код не должен быть изменен. Итератор стиль делает контейнер код агностик.

Лично я не думаю, что это большое дело. В этом ограниченном контексте.

    for (int j = 0; j < nodes[i].degree; j++)

Вы реализуете (плохо) функция сортировки:

    for (int j = 0; j < nodes[i].degree; j++)
for (int k = 0; k < j; k++)
if (nodes[i].adjList[j] < nodes[i].adjList[k])
swap(int, nodes[i].adjList[j], nodes[i].adjList[k]);

Позволяет, просто говорят на языках C/C++ вы должны, вероятно, использовать встроенные алгоритмы сортировки:

std::sort(&nodes[i].adjList[0], &nodes[i].adjList[nodes[i].degree]);

Или я читая твои намерения здесь неправильно? Это какая-то случайная особенность? В любом случае вы должны, вероятно, документально это объяснить, что вы пытаетесь достичь!

Вот это больше на C++, как вариант

#include <vector>
#include <map>
#include <iterator>
#include <stdexcept>
#include <fstream>
#include <iostream>

class GraphVisitor; // We will implement the `Visitor Pattern`
class Graph
{
public:
class GraphNode
{
public:
// Allows us to visit each node.
// Don't need to track progress via modifying the node
void accept(GraphVisitor& visitor);
private:
// The streaming operators are defined so we can freeze and thaw data to a stream
friend std::istream& operator>>(std::istream& stream, Graph::GraphNode& node);
friend std::ostream& operator<<(std::ostream& stream, Graph::GraphNode const& node);

// The data is private nobody actually needs to see this
int nodeName;
std::vector<int> link;
};

// Graph knows how to implement depth first traversal.
// External entities can't do this because that requires knowledge of the implementation
void DepthFirstTraversal(size_t startNode);

private:
// The streaming operators are defined so we can freeze and thaw data to a stream
friend std::istream& operator>>(std::istream& stream, Graph& node);
friend std::ostream& operator<<(std::ostream& stream, Graph const & node);

// The data is just the nodes
std::vector<GraphNode> nodes;

};
// A visitor is easy
// When you only have one node type.
// So we just have one visit method.
class GraphVisitor
{
public:
virtual ~GraphVisitor() {}
virtual void visit(Graph::GraphNode& node, int name, std::vector<int> const& links) = 0;
};

// All the node does with the visitor is tell it that it can visit.
void Graph::GraphNode::accept(GraphVisitor& visitor)
{
visitor.visit(*this, nodeName, link);
}

// Stream Nodes
std::ostream& operator<<(std::ostream& stream, Graph::GraphNode const& node)
{
stream << node.nodeName << ":" << node.link.size() << ":";
std::copy(node.link.begin(), node.link.end(), std::ostream_iterator<int>(stream, " "));
return stream;
}
std::istream& operator>>(std::istream& stream, Graph::GraphNode& node)
{
char ignore;
int count;

stream >> node.nodeName >> ignore >> count >> ignore;

for(std::istream_iterator<int> loop(stream); count != 0; --count, ++loop)
{ node.link.push_back(*loop);
}
// For some reason you sort your nodes so I am sorting them here.
// Or I am reading your original code incorrectly.
std::sort(node.link.begin(), node.link.end());
return stream;
}
// Stream the whole graph.
// This is simply the number of nodes followed by a list of nodes.
std::ostream& operator<<(std::ostream& stream, Graph const & graph)
{
stream << graph.nodes.size() << " ";
std::copy(graph.nodes.begin(), graph.nodes.end(), std::ostream_iterator<Graph::GraphNode>(stream, " "));
return stream;
}
std::istream& operator>>(std::istream& stream, Graph& graph)
{
int nodeCount;
stream >> nodeCount;

// We could implement it like this.
// As this would match your current file format nicely and if their
// is anything after the nodes it still works.
/*
for(int loop=0;loop < nodeCount; ++loop) // I implemented it like this becuase
{
Graph::GraphNode node;
stream >> node;
graph.nodes.push_back(node);
}
*/
// But if there is nothing after the nodes it could be implemented like this:
std::copy(std::istream_iterator<Graph::GraphNode>(stream),
std::istream_iterator<Graph::GraphNode>(),
std::back_inserter(graph.nodes)
);
}

// A visitor object used by Graph::DepthFirstTraversal
// It tracks which nodes it has already seen.
// So you do not need to visit them again.
// When a node says it can visit then just visit all the linked nodes.
// If you get a call from a node that has already visited then just exit.
class DepthFirstVisitor: public GraphVisitor
{
public:
DepthFirstVisitor(std::vector<Graph::GraphNode>& n)
: nodes(n)
{}
private:
virtual void visit(Graph::GraphNode& node, int name, std::vector<int> const& links)
{
if (visited[&node])
{ return;
}

visited[&node] = true;
std::cout << "Visiting Node: " << name << "\n";

for(std::vector<int>::const_iterator loop = links.begin();loop != links.end();++loop)
{
nodes[*loop].accept(*this);
}
}
std::map<Graph::GraphNode const*, bool> visited;
std::vector<Graph::GraphNode>& nodes;
};

// Implementing the Depth First traversal is easy as calling the first node with the
// the correct visitor object
void Graph::DepthFirstTraversal(size_t startNode)
{
if (startNode >= nodes.size())
{ throw std::runtime_error("Failed");
}
DepthFirstVisitor visitor(nodes);
nodes[startNode].accept(visitor);
};

int main()
{
Graph graph;

std::ifstream digraph("digraph.data");
digraph >> graph; // Very easy to load a graph.
std::cout << graph << "\n\n\n"; // Printing it out is also easy

graph.DepthFirstTraversal(1); // start at node one instead of zero for some reason!!!!!.
}

13
ответ дан 15 августа 2011 в 02:08 Источник Поделиться

используя printf работает с как.

используя функцию как readGraph, что делает много магии, а также печатать вещи с как.

Для такого рода вещи, чтобы быть как C++, то ты думаешь о том, как писать обобщенно эти функции. Давая свой график в стл, как чувствую.

Этот код здесь является больше о ваших попытках обучения обход, чем написать хорошую полезную функцию. Например, весь смысл обход делать что-то с каждым узлом посетили, здесь у вас нет номера / удобства для функциональности инъекций, как вы достигнете каждого узла.

Так что на C++ подход, в смысле современный подход, выглядел бы совсем иначе. Это будет шаблонный, он согласится с лямбдами или функторы, он будет использовать/обеспечить итераторы и т. д.

6
ответ дан 15 августа 2011 в 01:08 Источник Поделиться