Directed Acyclic Graph

[froufrouduck]

So I am studying graph data structures and I want to implement DAG but I am facing one problem, I want to make a DAG using randomly generated vertices and edges, for example if I want to make a DAG using randomly generated 100,000 vertices and 99,999 edges, how'd I check if they're not cyclic.

Also, if some one can help me understand concept of DAG betterly it'd be great, one doubt I had is , Is DAG always in topological order?

Thanks!

[nuderobmonkey]

I looked at the related wikipedia page, and if I have it correct understood, then the core assumption is, that a DAG has at least one predecessor vertex but not necessary a successor. And yes, the vertices are always in topological order.

So if you want to make a DAG, you must ensure that each vertex is connected to at least to one predecessor.

About how to implement:
You could hold all your vertices in a std::vector (or in a fixed size array). The array index determines the topological order. And each vertex needs to hold some (or none) links to some successors.

If you want to make some randomly generated links, you have at first to ensure that each vertex is connected to at least one predecessor (except the first vertex). If you have ensured this requirement, then you could make some further edges to your vertices. If you have connect every vertex to some predecessor, you can be sure that the graph is not cyclic.

[dhayden]

To create a random DAG you create a random proposed edge. Let's say it goes from node S to node D. Then
- tentatively insert the edge.
- Starting at node S, traverse the tree to see if you've created a cycle.
- If so, then remove the edge and pick another one.
- Otherwise you're good.

To see if you've created a cycle, you need to have a boolean "visited" member of each node. Then you recursively look for loops:

bool findCycle(Node &start)
{
    book result = false;    // assume that it's not on a loop
    if (start.visited) return true;  // you've seen this node before so you've looped around to it
    start.visited = true;  // indicate that this is on the current path
    for (const Edge &edge : node.edges) {
        if (findLoop(edge.dest)) {   // check each destination
            result = true;
            break;
        }
    }
    start.visited = false;  // back out of this node
    return result;
}