make_dag.cpp

#include <utility>
#include <unordered_set>
#include <vector>
#include <stack>

using std::pair;
using std::make_pair;
using std::unordered_set;
using std::vector;
using std::stack;

typedef vector<vector<bool>> adj_matrix;
typedef stack<adj_matrix::size_type,
              vector<adj_matrix::size_type>> vertex_stack;
typedef pair<adj_matrix::size_type,
             adj_matrix::size_type> edge_type;
typedef stack<edge_type, vector<edge_type>> edges_stack;
typedef unordered_set<adj_matrix::size_type> unseen_set;


bool dfs_target(const adj_matrix& graph,
                adj_matrix::size_type source,
                const adj_matrix::size_type target = 0)
{
    vertex_stack s;
    vector<bool> discovered(graph.size(), false);
    s.push(source);

    while(!s.empty())
    {
        source = s.top();
        s.pop();
        if(!discovered[source])
        {
            discovered[source] = true;
            for(adj_matrix::size_type w = 0;
                w < graph[target].size(); w++)
            {
                if(graph[source][w])
                {
                    if (target == w) return true;
                    s.push(w);
                }
            }
        }
    }

    return false;
}


bool topological_visit(const adj_matrix& graph,
                       adj_matrix::size_type node,
                       vector<bool>& marks,
                       unseen_set& unseen)
{
    if (marks[node]) return false;

    auto it = unseen.find(node);
    if (it != unseen.end())
    {
        marks[node] = true;

        for (adj_matrix::size_type v = 0;
             v < graph[node].size(); v++)
        {
            if (graph[node][v])
            {
                if (!topological_visit(graph, v, marks, unseen))
                {
                    return false;
                }
            }
        }
        unseen.erase(it);
        marks[node] = false;
    }
    return true;
}


bool topological_sort_check(const adj_matrix& graph)
{
    vector<bool> visited(graph.size(), false);
    unseen_set unseen;
    for (adj_matrix::size_type i = 0; i < graph.size(); i++)
    {
        unseen.insert(i);
    }

    while(!unseen.empty())
    {
        if (!topological_visit(graph, *unseen.cbegin(),
                              visited, unseen))
        {
            return false;
        }
    }
    return true;
}


bool add_no_loop_edges(adj_matrix& graph, edges_stack& edges)
{
    if (edges.empty()) return true;

    auto edge = edges.top();
    edges.pop();

    bool paths[] = {
        dfs_target(graph, edge.first, edge.second),
        dfs_target(graph, edge.second, edge.first),
    };

    for (auto i: {0, 1})
    {
        if (!paths[i])
        {
            // (i, !i) is (0, 1) or (1, 0)
            graph[edge.first][edge.second] = i;
            graph[edge.second][edge.first] = !i;

            if (add_no_loop_edges(graph, edges))
            {
                // we have solution for this set of edges
                return true;
            }
        }
    }

    return false;
}


bool solve(const adj_matrix& in, adj_matrix& out)
{
    edges_stack double_edges;

    for(adj_matrix::size_type i = 0; i < in.size(); i++)
    {
        for(adj_matrix::size_type j = i; j < in.size(); j++)
        {
            if (in[i][j] && in[j][i])
            {
                double_edges.push(make_pair(i, j));
                out[i][j] = false;
                out[j][i] = false;
            }
            else
            {
                out[i][j] = in[i][j];
                out[j][i] = in[j][i];
            }
        }
    }

    if (!topological_sort_check(out)) return false;

    if (double_edges.empty()) return true;

    return add_no_loop_edges(out, double_edges);
}