GraphsLib/graphalgorithms.hpp at master · onyazuka/GraphsLib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#pragma once
#include <list>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include "graphs.hpp"
#include "DataStructures/disjointset.hpp"
#include "graphalgorithmstopologicalsort.h"
#include "grapharticulationpointssearcher.hpp"
#include "DataStructures/heap.hpp"
#include "utils.hpp"

void BFS(Graph& graph, Vertex::Number s);

class DFS
{
public:
    enum EdgeTypes {NoType = -1, Tree, Back, Direct, Cross};
    DFS(Graph& graph);
protected:
    void DFS_Visit(Graph& graph, Vertex::Number vNum);

    const Vertex::AttributeId ColorAttributeId;
    const Vertex::AttributeId ParentAttributeId;
    const Vertex::AttributeId DistanceAttributeId;
    const Vertex::AttributeId FinishAttributeId;
    const Edge::AttributeId TypeAttributeId;
    enum Colors{White, Gray, Black};
    enum {NoParent=-1};
    int time;       // vertex visit time
};

template<typename Container>
class TopologicalSort;

bool hasCycle(Graph& graph);

class UndirectedComponentsSplitter
{
public:
    typedef std::vector<Vertex::Number> Component;
    typedef std::vector<Component> Components;
    UndirectedComponentsSplitter(UndirectedGraph& graph, Components& components);
private:
    const Vertex::AttributeId ColorAttributeId;

    void visit(UndirectedGraph& graph, Vertex::Number vNum, Components& components);
    enum Colors{White, Gray};
};

class StronglyConnectedComponents
{
public:
    typedef std::vector<Graph::VertexNumbers> Components;
    StronglyConnectedComponents(DirectedGraph& graph, Components& components);
protected:
    void StrongDFS(DirectedGraph& graph);
    void visit(DirectedGraph& graph, Vertex::Number vNum);
    size_t time;
    const Vertex::AttributeId ColorAttributeId;
    const Vertex::AttributeId DistanceAttributeId;
    const Vertex::AttributeId FinishAttributeId;
    enum Colors{White, Gray};
};

class EulerianBuilder
{
    enum {Unvisited, Visited};
public:
    typedef std::vector<Vertex> Vertices;
    typedef std::vector<Vertex::Number> Eulerian;
    EulerianBuilder(UndirectedGraph graphCopy);
    EulerianBuilder(DirectedGraph graphCopy);
    bool hasEulerianCircuit() const {return eulerianCircuitFound;}
    bool hasEulerianPath() const {return eulerianPathFound;}
    Eulerian getEulerianCircuit() const {return eulerian;}
    Eulerian getEulerianPath() const {return eulerian;}
private:
    Vertex::Number checkEulerianConditions(UndirectedGraph& graph);
    Vertex::Number checkEulerianConditions(DirectedGraph& graph);
    void buildEulerian(Graph& graph, Vertex::Number startVertexNumber);
    Eulerian eulerian;
    std::stack<Vertex::Number> walkingStack;
    bool eulerianCircuitFound;
    bool eulerianPathFound;
};

UndirectedGraph minimalSpanningTreeKruskal(UndirectedGraph& graph);
UndirectedGraph minimalSpanningTreePrim(UndirectedGraph& graph, Vertex::Number v = 0);

class ShortestPathSearcher
{
public:
    enum {NoParent = -1, WeightInf = std::numeric_limits<Vertex::AttributeType>::max()};
    typedef std::vector<std::vector<Vertex::AttributeType>> Matrix;
    enum class BellmanFordReturnCode {HasNegativeCycle, Ok};

    ShortestPathSearcher(DirectedGraph* graph);

    BellmanFordReturnCode bellmanFord(Vertex::Number source);
    void dagShortestPaths(Vertex::Number source);
    void dijkstra(Vertex::Number source);
    void floydWarshall(Matrix& weights, Matrix& parents);
private:
    const Vertex::AttributeId ParentAttributeId;
    const Vertex::AttributeId DistanceAttributeId;
    const Edge::AttributeId WeightAttributeId;
    DirectedGraph* graph;

    void doAdjacencyWeightMatrix(Matrix& weightMatrix);
    void fillParentsMatrixFromWeightsMatrix(Matrix& weightsMatrix, Matrix& parentsMatrix);
    void initializeSingleSource(Vertex::Number source);
    void relax(Vertex::Number v1, Vertex::Number v2);
};

class FordFulkerson
{
public:
    FordFulkerson(DirectedGraph& graph, Vertex::Number source, Vertex::Number to);
private:
    typedef std::vector<Edge*> pEdges;
    bool isCorrectNetwork(DirectedGraph& graph, Vertex::Number source, Vertex::Number to);
    size_t findPathCost(DirectedGraph& graph, Vertex::Number source, Vertex::Number to);
    void updateFlows(DirectedGraph& graph, Vertex::Number source, Vertex::Number to, size_t pathCost);
    DirectedGraph makeResidualGraph(DirectedGraph& graph);
    const Vertex::AttributeId ColorAttributeId;
    const Vertex::AttributeId ParentAttributeId;
    const Edge::AttributeId FlowAttributeId;
    const Edge::AttributeId CurrentAttributeId;
    enum Colors{White, Gray};
    enum {NoParent=-1};
    Edge::AttributeId ResidualCurrentAttributeId;
    Edge::AttributeId ResidualColorAttributeId;
    Edge::AttributeId ResidualParentAttributeId;
    Edge::AttributeId ResidualDistanceAttributeId;
};