acyclic_graph

acyclic_graph.cpp

class node{
  public:
    int id;
    short visited; // 0: not visited, 1: reached but not fully processed, 2: fully processed
    int parent;
    node(int idx) : id(idx), visited(0) {}
};
bool comp(const node & p, const node & q) {
  return (p.exit_time > q.exit_time);
}

vector<vector<int> > graph;

vector<node> node_order;

void topological_dfs(int root_idx, vector<node> & graph_nodes) {
  
  graph_nodes[root_idx].visited = 1;
  
  for(unsigned int i = 0; i < graph[root_idx].size(); i++) {
    
    int current_neighbor_idx = graph[root_idx][i];
    
    if(graph_nodes[current_neighbor_idx].visited == 0) {
      
      graph_nodes[current_neighbor_idx].parent = graph_nodes[root].id;
      topological_dfs(current_neighbor_idx, graph_nodes);

    } else if (graph_nodes[current_neighbor_idx].visited == 1) {
      // stop: there is a cycle in the graph
      // cycle: follow parent links from root until current neighbor is reached
      return 1;
    }
  }
  
  node_order.push_back(graph_nodes[root_idx]);
  graph_nodes[root_idx].visited = 2;
}

void fill_topological_node_order(vector<node> & graph_nodes) {
  
  for(unsigned int node_idx = 0; node_idx < graph_nodes.size(); node_idx++) {
      
      if(graph_nodes[node_idx].visited == 0) {
        topological_dfs(node_idx, graph_nodes);
      }
  }
  
  reverse(node_order.begin(), node_order.end());
}

int main()
{
    // 1. step: build graph and graph_nodes
    fill_topological_node_order(graph_nodes)
    return 0;
}