0

I have a project with structure:

CMakeLists.txt
src:
- graph_power.cpp
- graph_power.h
- main.cpp
- utils.cpp
- utils.h
- vertex_cover.cpp
- vertex_cover.h

main.cpp contains main() method and uses all other files. graph_power.cpp uses utils.cpp, so I've written #include "utils.h" there. vertex_cover.cpp also uses utils.cpp. Header files contain basically all methods from appropriate .cpp files.

utils.cpp implements set_contains(), set_union() and map_contains(), which are used by other files.

CMakeLists.txt:

cmake_minimum_required(VERSION 3.16)
project(project)

set(CMAKE_CXX_STANDARD 11)

add_executable(project src/main.cpp src/utils.cpp src/graph_power.cpp src/vertex_cover.cpp)

I'm getting LNK error for unrecognized external symbol for all three set_contains(), set_union() and map_contains(). What am I doing wrong? I though that including header files and listing all files for compilation should work? I'm using CLion and src is blue (source file directory), if that's important.

EDIT:

main.cpp:

#include <fstream>
#include <iostream>
#include <iterator>
#include <queue>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include "vertex_cover.h"
#include "utils.h"
#include "graph_power.h"


using namespace std;


void check_and_add_left(string& curr_line, unordered_map<int, unordered_set<int>>& graph, int vertex,
                        int row, int col, int W)
{
    if (col > 0 && (curr_line[col - 1] == '-' || curr_line[col - 1] == '+'))
    {
        int vertex_2 = index(row, col - 1, W);
        graph[vertex].insert(vertex_2);
        graph[vertex_2].insert(vertex);
    }
}


void check_and_add_right(string& curr_line, unordered_map<int, unordered_set<int>>& graph, int vertex,
                         int row, int col, int W)
{
    if (col < W - 1 && (curr_line[col + 1] == '-' || curr_line[col + 1] == '+'))
    {
        int vertex_2 = index(row, col + 1, W);
        graph[vertex].insert(vertex_2);
        graph[vertex_2].insert(vertex);
    }
}


void check_and_add_above(string& prev_line, string& curr_line, unordered_map<int, unordered_set<int>>& graph,
                         int vertex, int row, int col, int W)
{
    if (row > 0 && (prev_line[col] == '|' || prev_line[col] == '+'))
    {
        int vertex_2 = index(row - 1, col, W);
        graph[vertex].insert(vertex_2);
        graph[vertex_2].insert(vertex);
    }
}


void process_line_tokens(string& prev_line, string& curr_line,
                         unordered_map<int, unordered_set<int>>& graph, int row, int W)
{
    for (int col = 0; col < W; col++)
    {
        char tile = curr_line[col];
        int vertex = index(row, col, W);

        // add vertex to the graph, if it isn't there already and tile isn't empty
        if (graph.count(vertex) == 0 && tile != '.')
        {
            unordered_set<int> empty_set;
            graph[vertex] = empty_set;
        }

        if (tile == '-')  // vertex may be connected to the one to the left/right
        {
            check_and_add_left(curr_line, graph, vertex, row, col, W);
            check_and_add_right(curr_line, graph, vertex, row, col, W);
        }
        else if (tile == '|')
        {
            check_and_add_above(prev_line, curr_line, graph, vertex, row, col, W);
            // can't check below, but can check above while calling this for the next line
        }
        else if (tile == '+')
        {
            check_and_add_left(curr_line, graph, vertex, row, col, W);
            check_and_add_right(curr_line, graph, vertex, row, col, W);
            check_and_add_above(prev_line, curr_line, graph, vertex, row, col, W);
            // can't check below, but can check above while calling this for the next line
        }
        // ignore tile == "." (empty)
    }
}


unordered_map<int, unordered_set<int>> load_graph(ifstream &file, int W, int H)
{
    unordered_map<int, unordered_set<int>> graph;
    string prev_line, curr_line;
    for (int i = 0; i < H; i++)
    {
        getline(file, curr_line);
        process_line_tokens(prev_line, curr_line, graph, i, W);
        prev_line = curr_line;
    }
    return graph;
}


int W;


int main()
{
    ifstream file("../example.txt");
    if (!file)
    {
        cout << "\nUnable to open file!";
        return -1;
    }

    string line;
    getline(file, line);
    istringstream buffer(line);
    vector<string> first_line_tokens{istream_iterator<string>(buffer), istream_iterator<string>()};

    W = stoi(first_line_tokens.at(0));  // grid width
    int H = stoi(first_line_tokens.at(1));  // grid height
    int L = stoi(first_line_tokens.at(2));  // distance between chosen vertices, number of edges
    int K = stoi(first_line_tokens.at(3));  // number of vertices to choose
    getline(file, line);  // ignore second line

    // load graph grid from standard input
    unordered_map<int, unordered_set<int>> graph = load_graph(file, W, H);

    // calculate G^L to solve Independent Set instead of L-distance Independent Set
    // vertices of degree 0 can be added to the solution here
    unordered_set<int> solution = raise_graph_to_power(graph, L);

    // k = V - K - size of already computed part of solution, for use in Vertex Cover
    unsigned int k = graph.size() - K - solution.size();
    k -= solution.size();

    // calculate graph kernel for efficiency
    bool solution_can_exist = kernelize(graph, solution, k);

    if (!solution_can_exist)
    {
        cout << "ERROR: solution can't exist!";
        exit(1);
    }

    if (k > 0)
    {
        // convert to edge list, since I can't manage to debug the hashmap-based Vertex Cover
        vector<pair<int, int>> edge_list = to_edge_list(graph);


    }

    print_solution(solution);

    return 0;
}

utils.cpp:

#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <iostream>
#include "utils.h"


int W;


int index(int row, int col, int W)
{
    return row * W + col;
}

void print_point(int point)
{
    int row = point / W;
    int col = point % W;
    cout << "(" << row << ", " << col << ")";
}

void print_solution(const unordered_set<int>& solution)
{
    for (auto const& point : solution)
    {
        int row = point / W;
        int col = point % W;
        cout << row << " " << col << "\n";
    }
}

template<class T>
void set_union(unordered_set<T>& add_to, unordered_set<T>& add_from)
{
    add_to.insert(add_from.begin(), add_from.end());
}

template<class T>
bool set_contains(const unordered_set<T>& s, const T& elem)
{
    return s.find(elem) != s.end();
}

template<typename Key, typename Value, typename Arg>
bool map_contains(const unordered_map< Key, Value > m, const Arg& key)
{
    return m.find(key) != m.end();
}

vector<pair<int, int>> to_edge_list(unordered_map<int, unordered_set<int>>& graph)
{
    unordered_set<pair<int, int>> edges;
    for (auto const& vertex : graph)
    {
        int v = vertex.first;
        for (auto const& u : vertex.second)
            v < u ? edges.insert(make_pair(v, u)) : edges.insert(make_pair(u, v));
    }

    vector<pair<int, int>> edge_list(edges.size());
    copy(edges.begin(), edges.end(), edge_list.begin());
    return edge_list;
}

utils.h:

#ifndef UTILS_H
#define UTILS_H

#include <unordered_map>
#include <unordered_set>

using namespace std;

int index(int row, int col, int W);

void print_point(int point);

void print_solution(const unordered_set<int>& solution);

template<class T>
void set_union(unordered_set<T>& add_to, unordered_set<T>& add_from);

template<class T>
bool set_contains(const unordered_set<T>& s, const T& elem);

template<typename Key, typename Value, typename Arg>
bool map_contains(unordered_map<Key, Value> m, const Arg& key);

namespace std
{
    // enables using pairs in sets
    template <> struct hash<pair<int, int>>
    {
        inline size_t operator()(const pair<int, int> &v) const
        {
            hash<int> int_hasher;
            return int_hasher(v.first) ^ int_hasher(v.second);
        }
    };
}

vector<pair<int, int>> to_edge_list(unordered_map<int, unordered_set<int>>& graph);


#endif //UTILS_H

graph_power.cpp:

#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include "utils.h"
#include "graph_power.h"


unordered_set<pair<int, int>> edge_adding_BFS(unordered_map<int, unordered_set<int>>& graph, int source, int power)
{
    unordered_set<pair<int, int>> edges_to_add;
    unordered_set<int> visited;
    unordered_map<int, int> distances;
    distances[source] = 0;
    queue<int> queue;
    queue.push(source);

    while (!queue.empty())
    {
        int u = queue.front();
        queue.pop();
        visited.insert(u);
        for (auto const& v : graph[u])
        {
            if (!set_contains(visited, v))
            {
                visited.insert(v);
                distances[v] = distances[u] + 1;
                edges_to_add.insert(make_pair(source, v));
                if (distances[v] < power)
                    queue.push(v);
            }
        }
    }

    return edges_to_add;
}

unordered_set<int> raise_graph_to_power(unordered_map<int, unordered_set<int>>& graph, int power)
{
    unordered_set<int> solution;
    unordered_set<pair<int, int>> edges_to_add;
    for (auto const& vertex : graph)
    {
        int source = vertex.first;
        // if we have a vertex of degree 0, we just add it to the solution and go on
        if (vertex.second.empty())
            solution.insert(source);
        else
        {
            unordered_set<pair<int, int>> new_edges = edge_adding_BFS(graph, source, power);
            set_union(edges_to_add, new_edges);
        }
    }

    // remove vertices of degree 0 from the graph (they're already in the solution)
    for (auto const& v : solution)
        graph.erase(v);

    for (auto const& edge : edges_to_add)
    {
        int u = edge.first;
        int v = edge.second;
        graph[v].insert(u);
        graph[u].insert(v);
    }

    return solution;
}

graph_power.h:

#ifndef GRAPH_POWER_H
#define GRAPH_POWER_H

unordered_set<pair<int, int>> edge_adding_BFS(unordered_map<int, unordered_set<int>>& graph, int source, int power);

unordered_set<int> raise_graph_to_power(unordered_map<int, unordered_set<int>>& graph, int power);

#endif //GRAPH_POWER_H

vertex_cover.cpp:

#include <vector>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include "utils.h"
#include "vertex_cover.h"

using namespace std;

bool kernelize(unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& solution, unsigned int& k)
{
    while (true)
    {
        unordered_set<int> to_remove;
        for (auto const& vertex : graph)
        {
            int v = vertex.first;
            if (vertex.second.size() == 1)
            {
                int u = *vertex.second.begin();
                solution.insert(u);

                to_remove.insert(u);
                to_remove.insert(v);

                k -= 1;
                break;
            }
            else if (vertex.second.size() > k)
            {
                solution.insert(v);
                to_remove.insert(v);
                k -= 1;
                break;
            }
        }

        if (!to_remove.empty())
        {
            for (auto const& v : to_remove)
            {
                unordered_set<int> neighbors;
                if (map_contains(graph, v))
                    neighbors = graph[v];
                else
                    continue;

                graph.erase(v);

                for (auto const& u : neighbors)
                {
                    if (!map_contains(graph, u) || !set_contains(graph[u], v))
                        continue;

                    graph[u].erase(v);

                    if (graph[u].empty())
                        graph.erase(u);
                }
            }
        }
        else
            break;
    }

    return graph.size() <= k * k;
}

bool vertex_cover(vector<pair<int, int>>& graph, unordered_set<int>& solution, unsigned int& k)
{
    return false;
}

vertex_cover.h:

#ifndef VERTEX_COVER_H
#define VERTEX_COVER_H

#include <unordered_set>

using namespace std;

bool kernelize(unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& solution, unsigned int& k);

bool vertex_cover(vector<pair<int, int>>& graph, unordered_set<int>& solution, unsigned int& k);


#endif //VERTEX_COVER_H
qalis
  • 1,314
  • 1
  • 16
  • 44
  • 1
    Try to add `taget_include_directories(project ${CMAKE_CURRENT_SOURCE_DIR}/src)` after the `add_executable` command. – vre May 06 '20 at 11:32
  • 1
    Edit: it must read `target_include_directories` – vre May 06 '20 at 11:44
  • @vre I'm getting "target_include_directories called with invalid arguments" error with your code – qalis May 06 '20 at 12:12
  • 1
    Then you should add either `PUBLIC` or `PRIVATE` keyword after `project` name. See https://cmake.org/cmake/help/latest/command/target_include_directories.html for the command documentation. – vre May 06 '20 at 12:13
  • @vre with this it compiles, but still throws the same error. I've provided the entire project code. – qalis May 06 '20 at 12:17
  • 3
    Aahh! A typical error. The templates `set_union` `set_contains` and `map_contains` need to be implemented in the header not in the source file. – vre May 06 '20 at 12:23
  • @vre thank you! I had no idea, I've read that header files are exclusively for interfaces, not implementations... please post an answer, so I can accept. – qalis May 06 '20 at 12:25

0 Answers0