CODEWITHSUNDEEP
c++algorithm
Sol
Sol

Reputation: 47

A C++ implementation of topological ordering

This morning I was doing my C++ class assignment, an implementation of topological ordering. There's no error while compiling, but simply can't run. Since I'm not quite familiar with pointers or STL, nor the VS debugger...I just can't figure out where went wrong. It would help me a lot if someone can point out my errors. Tons of thanks!

Here's my code:

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef struct Vertex{
    int index;
    int indegree;  // indegree of vertex v is the total num of edges like(u,v)
    vector<Vertex>adjacent;
    int topoNum;    // topological order of this vertex.
}Vertex;
typedef struct Edge{
    Vertex start;
    Vertex in;
}Edge;

Vertex*InDegrees(int numVertex,int numEdge,Edge*edges) // calculate indegrees of all vertices.
{
    Vertex*vertices=new Vertex[numVertex];
    for(int i=0;i<numVertex;i++){   vertices[i].index=i;    vertices[i].indegree=0;}
    for(int i=0;i<numEdge;i++)
    {
        int j=edges[i].in.index;
        vertices[j].indegree++;
        vertices[j].adjacent.push_back(edges[i].start);
    }
    return vertices;
}

int*topoSort(int numVertex,int numEdge,Edge*edges)
{
    edges=new Edge[numEdge];
    Vertex*Vertices=new Vertex[numVertex];
    Vertices=InDegrees(numVertex,numEdge,edges);

    queue<Vertex>q;
    for(int i=0;i<numVertex;i++)
    {
        if(Vertices[i].indegree==0)
            q.push(Vertices[i]);
    }

    int count=0;
    while(!q.empty())   // Ordering completed when queue is empty.
    {
        Vertex v=q.front();    // get the vertex whose indegree==0
        q.pop();
        v.topoNum=++count;
        vector<Vertex>::iterator iter;
        for(iter=v.adjacent.begin();iter!=v.adjacent.end();iter++)
        {
            Vertex w=*iter;
            if(--w.indegree==0)
                q.push(w);
        }
    }
    int*topoOrder=new int[numVertex];
    for(int i=0;i<numVertex;i++)
    {
        int j=Vertices[i].topoNum;
        topoOrder[j]=-1;    // initial value, in case cycle existed.
        topoOrder[j]=Vertices[i].index;
    }
    delete[]Vertices;
    delete[]edges;
    return topoOrder;
}

int main()
{
    int numVertex,numEdge;
    cin>>numVertex>>numEdge;
    Edge*Edges=new Edge[numEdge];
    int indexStart,indexIn;
    for(int i=0;i<numEdge;i++)
    {
        cin>>indexStart>>indexIn;
        Edges[i].in.index=--indexIn;
        Edges[i].start.index=--indexStart;
    }

    int*topoOrder=new int[numVertex];
    topoOrder=topoSort(numVertex,numEdge,Edges);
    for(int i=0;i<numVertex-1;i++)
    {
        if(topoOrder[i]==-1)
        {
            cout<<"Cycle exists, not a DAG!";
            return 0;
        }
        cout<<topoOrder[i]<<",";
    }
    cout<<topoOrder[numVertex-1]<<endl;

    delete[]Edges;
    return 0;
}

Upvotes: 1

Views: 3111

Answers (1)

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153955

An obvious starting point for your problems is the allocation for Edges: the allocation uses the uninitialized value numEdge which is likely to be zero. That is, you'll get a pointer to no elements. You probably want to allocate Edges only after having read numEdge. I didn't really had a look at what happens in the actual algorithm.

I also strongly recommend that you verify that the input operations were successful:

if (std::cin >> numVertex >> numEdge) {
    use_successfully_read(numVertex, numEdge);
}

If inputs fail the variable remain unchanged and the values will also lead to interesting behavior.

Upvotes: 2

Related Questions