Tukukkk

I've implemented a graph for a course and i'd like to know what i could improve.
The graph is created from a adjacency list from a file with the following format per row:

node_name [neighbor_1_name[:edge_weight[:edge_flow]]]*

Nodes that do not have neighbors must not be declared in a own row (a node is created when the name is encountered for the first time).
The first row of the file can indicate whether the graph is directed or not and empty lines and lines starting with // are ignored when parsing the data.

An example file could look like this:

// Floyd-Warshall test graph.

1 3:-2

2 1:4 3:3

3 4:2

4 2:-1

The used compiler is the one shipped with Visual Studio 2017.

Node.h

#pragma once



#ifndef _NODE_

#define _NODE_



#include <string>



/// Defines a node of a graph.

class Node

{

private:

    const std::string name;



public:

    /// <summary>

    /// Initializes a new instance of the Node class with the given name.

    /// </summary>

    /// <param name="name">The name of the node.</param>

    Node(std::string name);



    /// <summary>

    /// Returns the name of the node.

    /// </summary>

    /// <returns>The name of the node.</returns>

    std::string GetName() const;



    /// <summary>

    /// Determines whether the node is equal to <paramref name="other"/>.

    /// </summary>

    /// <param name="other">The other node to compare this node to.</param>

    /// <returns>true, if the node's name equals the other node's name; false, otherwise.</returns>

    bool operator==(const Node& other) const;

};



#endif // !_NODE_

Node.cpp

#include "Node.h"



Node::Node(const std::string name)

    : name(name)

{ }



std::string Node::GetName() const

{

    return this->name;

}



bool Node::operator==(const Node& other) const

{

    if (this == &other)

    {

        return true;

    }



    return this->name.compare(other.name) == 0;

}

Edge.h

#pragma once



#ifndef _EDGE_

#define _EDGE_



#include <memory>

#include "Node.h"



/// Defines an edge of a graph.

class Edge

{

private:

    const std::shared_ptr<Node> source;

    const std::shared_ptr<Node> destination;



    double weight;

    double flow;



public:

    /// <summary>

    /// Initializes a new instance of the Edge class with

    /// the given source and destination nodes and a weight of 1.

    /// </summary>

    /// <param name="source">The source node of the edge.</param>

    /// <param name="destination">The source node of the edge.</param>

    Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination);



    /// <summary>

    /// Initializes a new instance of the Edge class with

    /// the given source and destination nodes and weight.

    /// </summary>

    /// <param name="source">The source node of the edge.</param>

    /// <param name="destination">The source node of the edge.</param>

    /// <param name="weight">The weight of the edge.</param>

    Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination, double weight);



    /// <summary>

    /// Initializes a new instance of the Edge class with

    /// the given source and destination nodes, weight and flow.

    /// </summary>

    /// <param name="source">The source node of the edge.</param>

    /// <param name="destination">The source node of the edge.</param>

    /// <param name="weight">The weight of the edge.</param>

    /// <param name="flow">The flow of the edge.</param>

    Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination, double weight, double flow);



    /// <summary>

    /// Gets a pointer to the source node of the edge.

    /// </summary>

    /// <returns>A pointer to the source node of the edge.</returns>

    const std::shared_ptr<Node> GetSourceNode() const;



    /// <summary>

    /// Gets a pointer to the destination node of the edge.

    /// </summary>

    /// <returns>A pointer to the destination node of the edge.</returns>

    const std::shared_ptr<Node> GetDestinationNode() const;



    /// <summary>

    /// Gets the weight of the edge.

    /// </summary>

    /// <returns>The weight of the edge.</returns>

    double GetWeight() const;



    /// <summary>

    /// Sets the weight of the edge. If the current flow of the node is

    /// greater than the new weight, the flow is set to the new weight.

    /// </summary>

    /// <param name="weight">The new weight of the edge.</param>

    void SetWeight(double weight);



    /// <summary>

    /// Gets the flow of the edge.

    /// </summary>

    /// <returns>The flow of the edge.</returns>

    double GetFlow() const;



    /// <summary>

    /// Sets the flow of the edge. Throws std::out_of_range when

    // <paramref name="flow"/> is greater than <see cref="weight"/>.

    /// </summary>

    /// <param name="flow">The new flow of the edge.</param>

    void SetFlow(double flow);

};



#endif // !_EDGE_

Edge.cpp

#include "Edge.h"



Edge::Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination)

    : source(source), destination(destination), weight(1), flow(0)

{ }



Edge::Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination, double weight)

    : source(source), destination(destination), weight(weight), flow(0)

{ }



Edge::Edge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination, double weight, double flow)

    : source(source), destination(destination), weight(weight), flow(flow)

{ }



double Edge::GetWeight() const

{

    return this->weight;

}



void Edge::SetWeight(double weight)

{

    this->weight = weight;



    if (this->weight < this->flow)

    {

        this->flow = this->weight;

    }

}



double Edge::GetFlow() const

{

    return this->flow;

}



void Edge::SetFlow(double flow)

{

    if (this->weight < flow)

    {

        throw std::out_of_range("The flow of an edge cannot exceed it's capacity.");

    }



    this->flow = flow;

}



const std::shared_ptr<Node> Edge::GetSourceNode() const

{

    return this->source;

}



const std::shared_ptr<Node> Edge::GetDestinationNode() const

{

    return this->destination;

}

string_helper.h

#pragma once



#ifndef _STRING_HELPER_

#define _STRING_HELPER_



#define WHITESPACE " tfvrn"



#include <string>

#include <vector>



namespace string_helper

{

    /// Defines how to split a string.

    enum class string_split_options

    {

        None,

        RemoveEmptyEntries

    };



    /// <summary>

    /// Splits the given string using the given delimiter and returns a vector with

    /// the string's parts.

    /// </summary>

    /// <param name="str">The string to split.</param>

    /// <param name="delimiter">The delimiter to use when splitting the string.</param>

    /// <param name="splitOptions">Split options for the string to split.</param>

    /// <returns>A vector containing the string parts.</returns>

    const std::vector<std::string> split(std::string str, std::string delimiter, string_split_options splitOptions = string_split_options::None);



    /// <summary>

    /// Checks whether the given string consists only of whitespace

    // characters or whether the given string has a length of 0.

    /// </summary>

    /// <param name="str">The string to check.</param>

    /// <returns>true, if the string is empty; false, otherwise.</returns>

    bool is_empty(std::string str);



    /// <summary>

    /// Checks whether the given string starts with the given value.

    /// </summary>

    /// <param name="str">The string to check.</param>

    /// <param name="value">The value to check.</param>

    /// <returns>true, if the string starts with <paramref name="value"/>; false, otherwise.</returns>

    bool starts_with(std::string str, std::string value);

}



#endif // !_STRING_HELPER_

string_helper.cpp

#include "string_helper.h"



using split_options = string_helper::string_split_options;



const std::vector<std::string> string_helper::split(

    const std::string str,

    const std::string delimiter,

    string_helper::string_split_options splitOptions /* = None */

)

{

    std::vector<std::string> result;

    size_t delimiterIndex = -1;

    size_t oldDelimiterIndex = -1;



    while ((delimiterIndex = str.find(delimiter, delimiterIndex + 1)) != std::string::npos)

    {

        ++oldDelimiterIndex;



        std::string substr = str.substr(oldDelimiterIndex, delimiterIndex - oldDelimiterIndex);



        oldDelimiterIndex = delimiterIndex;



        if (splitOptions == split_options::RemoveEmptyEntries && substr.length() == 0)

        {

            continue;

        }



        result.push_back(substr);

    }



    // If there are more characters after the last index of the delimiter

    // add them to the result vector as well.

    ++oldDelimiterIndex;



    if (oldDelimiterIndex != str.length())

    {

        result.push_back(str.substr(oldDelimiterIndex));

    }



    return result;

}



bool string_helper::is_empty(const std::string str)

{

    return str.length() == 0 || str.find_first_not_of(WHITESPACE) == std::string::npos;

}



bool string_helper::starts_with(const std::string str, const std::string value)

{

    return str.length() >= value.length() && str.substr(0, value.length()) == value;

}

Graph.h

#pragma once



#ifndef _GRAPH_

#define _GRAPH_



#include <memory>

#include <set>

#include <string>

#include <unordered_map>

#include <vector>



#include "Edge.h"

#include "Node.h"



/// Defines a graph with nodes and edges.

class Graph

{

private:

    bool directed;



    std::set<std::shared_ptr<Node>> nodes;

    std::vector<std::shared_ptr<Edge>> edges;



public:

    /// <summary>

    /// Initializes a new instance of the Graph class.

    /// </summary>

    Graph() { }



    /// <summary>

    /// Creates a graph from the adjacency list stored in the file with the given path.

    /// </summary>

    /// <param name="file">The path to the file that contains the adjacency list.</param>

    /// <returns>A shared pointer to the created graph.</returns>

    static std::shared_ptr<Graph> FromAdjacencyList(std::string file);



#pragma region Node stuff.



    /// <summary>

    /// Creates a new node with the given name and adds it to the graph.

    /// </summary>

    /// <param name="name">The name of the node to create.</param>

    /// <returns>A shared pointer to the created node.</returns>

    const std::shared_ptr<Node> AddNode(std::string name);



    /// <summary>

    /// Adds the given node to the graph.

    /// </summary>

    /// <param name="node">A pointer to the node to add.</param>

    void AddNode(const std::shared_ptr<Node> node);



    /// <summary>

    /// Adds a node with the given name to the graph, if there is no node with the name

    /// or returns a pointer to the node with the given name.

    /// </summary>

    /// <param name="name">The name of the node to create.</param>

    /// <returns>A shared pointer to the created or existent node.</returns>

    const std::shared_ptr<Node> AddNodeIfNotExist(std::string name);



    /// <summary>

    /// Returns a pointer to the node with the given name or a null pointer

    /// if no node with the given name exists.

    /// </summary>

    /// <param name="edge">The name of the node to which to return a pointer.</param>

    /// <returns>A pointer to the node with the given name.</returns>

    const std::shared_ptr<Node> GetNode(std::string name) const;



    /// <summary>

    /// Returns a set of the nodes of the graph.

    /// </summary>

    /// <returns>A set containing pointers to all nodes of the graph.</returns>

    const std::set<std::shared_ptr<Node>> GetNodes() const;



    /// <summary>

    /// Returns the number of nodes in the graph.

    /// </summary>

    /// <returns>The number of nodes in the graph.</returns>

    const size_t NodeCount() const;



#pragma endregion



#pragma region Edge stuff.



    /// <summary>

    /// Adds a new edge between the given nodes to the graph and returns the created edge or

    /// a null pointer if any of both nodes is not part of the graph.

    /// </summary>

    /// <param name="source">The source node of the edge.</param>

    /// <param name="destination">The destination node of the edge.</param>

    /// <returns>A shared pointer for the created edge or a null pointer if any of both nodes is not part of the graph.</returns>

    const std::shared_ptr<Edge> AddEdge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination);



    /// <summary>

    /// Returns a pointer to the egde with the given source and destination

    /// nodes or a null pointer if no such edge exists.

    /// </summary>

    /// <param name="source">The source node of the edge.</param>

    /// <param name="destination">The destination node of the edge.</param>

    /// <returns>A pointer to the edge with the given source and destination.</returns>

    const std::shared_ptr<Edge> GetEdge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination) const;



    /// <summary>

    /// Returns a vector of all edges of the graph.

    /// </summary>

    /// <returns>A vector containing pointers to all edges of the graph.</returns>

    const std::vector<std::shared_ptr<Edge>> GetEdges() const;



    /// <summary>

    /// Returns a vector containing all edges of the graph that have the given node as source node.

    /// </summary>

    /// <param name="source">The source node of the edges to fetch.</param>

    /// <returns>A vector of pointers to edges with the given node as source node.</returns>

    const std::vector<std::shared_ptr<Edge>> GetEdgesFrom(const std::shared_ptr<Node> source) const;



    /// <summary>

    /// Returns a vector containing all edges of the graph that have the given node as destination node.

    /// </summary>

    /// <param name="source">The destination node of the edges to fetch.</param>

    /// <returns>A vector of pointers to edges with the given node as destination node.</returns>

    const std::vector<std::shared_ptr<Edge>> GetEdgesTo(const std::shared_ptr<Node> destination) const;



#pragma endregion



    /// <summary>

    /// Gets whether the graph is directed.

    /// </summary>

    /// <returns>true, if the graph is directed; false, otherwise.</returns>

    bool IsDirected() const;



    /// <summary>

    /// Sets whether the graph is directed.

    /// </summary>

    /// <param name="directed">true, if the graph is directed; false, otherwise.</param>

    void SetIsDirected(bool directed);



#pragma region Functionality.



    /// <summary>

    /// Checks whether there is a path between <paramref name="root"/> and <paramref name="destination"/>

    /// in the current graph using a depth-first-search algorithm and returns the result.

    /// </summary>

    /// <param name="root">The root node of the search.</param>

    /// <param name="destination">The destination node of the search.</param>

    /// <returns>true, if there is a path from <paramref name="root"/> to <paramref name="destination"/>; false, otherwise.</returns>

    bool DepthFirstSearch(std::shared_ptr<Node> root, std::shared_ptr<Node> destination) const;



    /// <summary>

    /// Calculates the shortes distance for all nodes to all other nodes.

    /// </summary>

    /// <returns>An unordered map with the node as key and the distance to other nodes as value.</returns>

    const std::unordered_map<std::shared_ptr<Node>, std::unordered_map<std::shared_ptr<Node>, double>> FloydWarshall() const;



    // And some more...



#pragma endregion

};



#endif // !_GRAPH_

Graph.cpp

#include <experimental/filesystem>

#include <fstream>

#include <queue>

#include <regex>



#include "Graph.h"

#include "string_helper.h"

#include "UnionContainer.h"



using edge_ptr = std::shared_ptr<Edge>;

using node_ptr = std::shared_ptr<Node>;



///////////////////////////////////////////////////////////////////////

/// Helpers for implementing the functionality of the graph.

///////////////////////////////////////////////////////////////////////



namespace graph_helpers

{

    // Depth-first-search implementation.

    bool depth_first_search(

        const Graph* graph,

        const node_ptr root,

        const node_ptr destination,

        std::set<node_ptr>& visitedNodes,

        std::vector<node_ptr>& path

    )

    {

        path.push_back(root);



        if (root == destination)

        {

            return true;

        }



        visitedNodes.emplace(root);



        for (const auto edge : graph->GetEdgesFrom(root))

        {

            const auto edgeDestination = edge->GetDestinationNode();



            if (visitedNodes.find(edgeDestination) != visitedNodes.end())

            {

                // Node has already been visited.

                continue;

            }



            if (depth_first_search(graph, edgeDestination, destination, visitedNodes, path))

            {

                return true;

            }

        }



        path.pop_back();

        return false;

    }



    // Floyd-Warshall shortest path implementation.

    const std::unordered_map<node_ptr, std::unordered_map<node_ptr, double>> floyd_warshall(const Graph* graph)

    {

        std::unordered_map<node_ptr, std::unordered_map<node_ptr, double>> distances;

        const auto nodes = graph->GetNodes();



        // Initialize the initial distances based on a edge between nodes.

        for (const auto n1 : nodes)

        {

            for (const auto n2 : nodes)

            {

                const auto edge = graph->GetEdge(n1, n2);



                if (n1 == n2)

                {

                    // Distance to itself is 0.

                    distances[n1][n2] = 0;

                }

                else

                {

                    if (edge)

                    {

                        distances[n1][n2] = edge->GetWeight();

                    }

                    else

                    {

                        distances[n1][n2] = DBL_MAX;

                    }

                }

            }

        }



        for (const auto n1 : nodes)

        {

            for (const auto n2 : nodes)

            {

                for (const auto n3 : nodes)

                {

                    if (distances[n2][n3] > distances[n2][n1] + distances[n1][n3])

                    {

                        distances[n2][n3] = distances[n2][n1] + distances[n1][n3];

                    }

                }

            }

        }



        return distances;

    };



///////////////////////////////////////////////////////////////////////

/// Graph parsing.

///////////////////////////////////////////////////////////////////////



std::shared_ptr<Graph> Graph::FromAdjacencyList(const std::string file)

{

    if (!std::experimental::filesystem::exists(file))

    {

        return nullptr;

    }



    const auto graph = std::make_shared<Graph>();

    std::ifstream fileStream(file);

    std::string line;

    int lineNumber = 0;



    while (std::getline(fileStream, line))

    {

        ++lineNumber;



        if (lineNumber == 1)

        {

            // First line can contain an indication for whether the graph is directed or not.

            // Example: directed=true, directed=t, directed=f, directed=false

            std::regex graphTypeRegex("^directed=(f|false|t|true)$");

            std::smatch match;



            if (std::regex_search(line, match, graphTypeRegex))

            {

                const bool directed = match[1] == "t" || match[1] == "true";

                graph->SetIsDirected(directed);

                continue;

            }

            else

            {

                // Graph is directed by default.

                graph->SetIsDirected(true);

            }

        }



        // Check if the string is empty or whitespace only or

        // if the line is a comment line (starts with //)

        if (string_helper::starts_with(line, "//") ||

            string_helper::is_empty(line))

        {

            continue;

        }



        // Create the node and its neighbors.

        const auto nodes = string_helper::split(line, " ", string_helper::string_split_options::RemoveEmptyEntries);



        // There is at least one node, because the string is neither empty nor a comment.

        const auto currentNode = graph->AddNodeIfNotExist(nodes[0]);



        for (size_t i = 1; i < nodes.size(); ++i)

        {

            // Format for a neighbor is name:edge_weight:egde_flow.

            // name should always be given, weight and flow are optional.

            const auto edgeData = string_helper::split(nodes[i], ":", string_helper::string_split_options::None);



            const auto edgeDestination = graph->AddNodeIfNotExist(edgeData[0]);

            const auto edge = graph->AddEdge(currentNode, edgeDestination);



            // Edge weight.

            if (edgeData.size() > 1 && edgeData[1] != "")

            {

                edge->SetWeight(std::stod(edgeData[1]));

            }



            // Edge flow.

            if (edgeData.size() > 2 && edgeData[2] != "")

            {

                edge->SetFlow(std::stod(edgeData[2]));

            }

        }

    }



    return graph;

}



///////////////////////////////////////////////////////////////////////

/// Node functions.

///////////////////////////////////////////////////////////////////////



const std::shared_ptr<Node> Graph::AddNode(const std::string name)

{

    auto node = std::make_shared<Node>(name);

    this->nodes.emplace(node);



    return node;

}



const std::shared_ptr<Node> Graph::AddNodeIfNotExist(const std::string name)

{

    const auto existentNode = GetNode(name);



    if (existentNode)

    {

        return existentNode;

    }



    auto node = std::make_shared<Node>(name);

    this->nodes.emplace(node);



    return node;

}



void Graph::AddNode(const std::shared_ptr<Node> node)

{

    this->nodes.emplace(node);

}



const std::set<std::shared_ptr<Node>> Graph::GetNodes() const

{

    return std::set<node_ptr>(this->nodes);

}



const std::shared_ptr<Node> Graph::GetNode(const std::string name) const

{

    for (auto node : this->nodes)

    {

        if (node->GetName() == name)

        {

            return node;

        }

    }



    return nullptr;

}



const size_t Graph::NodeCount() const

{

    return this->nodes.size();

}



///////////////////////////////////////////////////////////////////////

/// Edge functions.

///////////////////////////////////////////////////////////////////////



const std::shared_ptr<Edge> Graph::AddEdge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination)

{

    if (this->nodes.find(source) == this->nodes.end() ||

        this->nodes.find(destination) == this->nodes.end())

    {

        return nullptr;

    }



    auto edge = std::make_shared<Edge>(source, destination);

    this->edges.push_back(edge);



    return edge;

}



const std::shared_ptr<Edge> Graph::GetEdge(const std::shared_ptr<Node> source, const std::shared_ptr<Node> destination) const

{

    for (auto edge : this->edges)

    {

        if (edge->GetSourceNode() == source && edge->GetDestinationNode() == destination)

        {

            return edge;

        }

    }



    return nullptr;

}



const std::vector<std::shared_ptr<Edge>> Graph::GetEdges() const

{

    return std::vector<edge_ptr>(this->edges);

}



const std::vector<std::shared_ptr<Edge>> Graph::GetEdgesFrom(const std::shared_ptr<Node> source) const

{

    std::vector<edge_ptr> edgesWithSource;



    for (auto edge : this->edges)

    {

        if (edge->GetSourceNode() == source)

        {

            edgesWithSource.push_back(edge);

        }

    }



    return edgesWithSource;

}



const std::vector<std::shared_ptr<Edge>> Graph::GetEdgesTo(const std::shared_ptr<Node> destination) const

{

    std::vector<edge_ptr> edgesWithDestination;



    for (auto edge : this->edges)

    {

        if (edge->GetDestinationNode() == destination)

        {

            edgesWithDestination.push_back(edge);

        }

    }



    return edgesWithDestination;

}



///////////////////////////////////////////////////////////////////////

/// Traits.

///////////////////////////////////////////////////////////////////////



bool Graph::IsDirected() const

{

    return this->directed;

}



void Graph::SetIsDirected(bool directed)

{

    this->directed = directed;

}



///////////////////////////////////////////////////////////////////////

/// Functionality.

///////////////////////////////////////////////////////////////////////



bool Graph::DepthFirstSearch(std::shared_ptr<Node> root, std::shared_ptr<Node> destination) const

{

    std::set<node_ptr> visitedNodes;

    std::vector<node_ptr> path;

    return graph_helpers::depth_first_search(this, root, destination, visitedNodes, path);

}



const std::unordered_map<std::shared_ptr<Node>, std::unordered_map<std::shared_ptr<Node>, double>> Graph::FloydWarshall() const

{

    return graph_helpers::floyd_warshall(this);

}

main.cpp

#include <iostream>

#include <vector>



#include "Graph.h"



void print_edge(const std::shared_ptr<Edge>& edge)

{

    std::cout << edge->GetSourceNode()->GetName() << " -> " << edge->GetDestinationNode()->GetName() << ", " << edge->GetWeight() << "[" << edge->GetFlow() << "]" << std::endl;

}



void print_node(const std::shared_ptr<Node>& node)

{

    std::cout << node->GetName() << std::endl;

}



void print_graph(const std::shared_ptr<Graph>& g)

{

    std::cout << "Directed: " << g->IsDirected() << std::endl;

    std::cout << "Nodes" << std::endl;



    for (auto node : g->GetNodes())

    {

        print_node(node);

    }



    std::cout << std::endl << "Edges" << std::endl;



    for (auto edge : g->GetEdges())

    {

        print_edge(edge);

    }

}



int main()

{

    const auto g = Graph::FromAdjacencyList("SampleGraph_5.txt");

    print_graph(g);



    std::cout << std::endl;



    const auto distances = g->FloydWarshall();



    for (const auto source : distances)

    {

        for (const auto destination : source.second)

        {

            std::cout << "Distance from '" << source.first->GetName() << "' to '" << destination.first->GetName() << "': " << destination.second << std::endl;

        }

    }



    std::cin.get();

    return 0;

}