Implementation of graph class.
The graph will be represented using Adjacency List representation. This class contains 2 data members "m_vertices" & "m_adjList" used to represent the number of vertices and adjacency list of the graph respectively. The vertices are labelled 0 - (m_vertices - 1).
Definition at line 14 of file bellman_ford.cpp.
◆ Graph() [1/6] Graph::Graph ( int V, int E ) inlineDefinition at line 20 of file bellman_ford.cpp.
20 {
21 this->vertexNum = V;
22 this->edgeNum = E;
23 this->edges.reserve(E);
24 }
◆ Graph() [2/6]Definition at line 17 of file floyd_warshall.cpp.
17 {
18 this->vertexNum = V;
19 this->edges = new int *[V];
20 for (int i = 0; i < V; i++) {
21 this->edges[i] = new int[V];
22 for (int j = 0; j < V; j++) this->edges[i][j] = INT_MAX;
23 this->edges[i][i] = 0;
24 }
25 }
◆ ~Graph()Definition at line 27 of file floyd_warshall.cpp.
27 {
28 for (int i = 0; i < vertexNum; i++) {
29 delete[] edges[i];
30 }
31 delete[] edges;
32 }
◆ Graph() [3/6] ◆ Graph() [4/6] Graph::Graph ( unsigned int vertices, AdjList adjList ) inlineCreate a graph from vertices and adjacency list.
Definition at line 69 of file cycle_check_directed_graph.cpp.
70 : m_vertices(vertices), m_adjList(std::move(adjList)) {}
◆ Graph() [5/6] Graph::Graph ( unsigned int vertices, AdjList && adjList ) inlineCreate a graph from vertices and adjacency list.
Definition at line 77 of file cycle_check_directed_graph.cpp.
78 : m_vertices(vertices), m_adjList(std::move(adjList)) {}
◆ Graph() [6/6] Graph::Graph ( unsigned int vertices, std::vector< Edge > const & edges ) inlineCreate a graph from vertices and a set of edges.
Adjacency list of the graph would be created from the set of edges. If the source or destination of any edge has a value greater or equal to number of vertices, then it would throw a range_error.
Definition at line 89 of file cycle_check_directed_graph.cpp.
90 : m_vertices(vertices) {
91 for (auto const& edge : edges) {
92 if (edge.src >= vertices || edge.dest >= vertices) {
93 throw std::range_error(
94 "Either src or dest of edge out of range");
95 }
96 m_adjList[edge.src].emplace_back(edge.dest);
97 }
98 }
◆ addEdge() [1/4] void Graph::addEdge ( Edge const & edge ) inlineAdd an edge in the graph.
Definition at line 125 of file cycle_check_directed_graph.cpp.
125 {
126 if (edge.src >= m_vertices || edge.dest >= m_vertices) {
127 throw std::range_error("Either src or dest of edge out of range");
128 }
129 m_adjList[edge.src].emplace_back(edge.dest);
130 }
◆ addEdge() [2/4] void Graph::addEdge ( int src, int dst, int weight ) inlineDefinition at line 27 of file bellman_ford.cpp.
27 {
28 static int edgeInd = 0;
29 if (edgeInd < this->edgeNum) {
30 Edge newEdge;
31 newEdge.src = src;
32 newEdge.dst = dst;
33 newEdge.weight = weight;
34 this->edges[edgeInd++] = newEdge;
35 }
36 }
◆ addEdge() [3/4] void Graph::addEdge ( int src, int dst, int weight ) inline ◆ addEdge() [4/4] void Graph::addEdge ( unsigned int source, unsigned int destination ) inlineAdd an Edge in the graph
Definition at line 137 of file cycle_check_directed_graph.cpp.
137 {
138 if (source >= m_vertices || destination >= m_vertices) {
139 throw std::range_error(
140 "Either source or destination of edge out of range");
141 }
142 m_adjList[source].emplace_back(destination);
143 }
◆ addVertices() void Graph::addVertices ( unsigned int num = 1 ) inlineAdd vertices in the graph.
Definition at line 119 of file cycle_check_directed_graph.cpp.
119{ m_vertices += num; }
◆ bfs() bool Graph::bfs ( int source, int sink ) inlineprivateDefinition at line 26 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.
26 {
27 visited.reset();
28 std::queue<int> q;
29 q.push(source);
30 bool is_path_found = false;
31 while (q.empty() == false && is_path_found == false) {
32 int current_node = q.front();
33 visited.set(current_node);
34 q.pop();
35 for (int i = 0; i < total_nodes; ++i) {
36 if (residual_capacity[current_node][i] > 0 && !visited[i]) {
37 visited.set(i);
38 parent[i] = current_node;
39 if (i == sink) {
40 return true;
41 }
42 q.push(i);
43 }
44 }
45 }
46 return false;
47 }
◆ ford_fulkerson() void Graph::ford_fulkerson ( ) inlineDefinition at line 62 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.
62 {
63 while (bfs(source, sink)) {
64 int current_node = sink;
65 int flow = std::numeric_limits<int>::max();
66 while (current_node != source) {
67 int parent_ = parent[current_node];
68 flow = std::min(flow, residual_capacity[parent_][current_node]);
69 current_node = parent_;
70 }
71 current_node = sink;
72 max_flow += flow;
73 while (current_node != source) {
74 int parent_ = parent[current_node];
75 residual_capacity[parent_][current_node] -= flow;
76 residual_capacity[current_node][parent_] += flow;
77 current_node = parent_;
78 }
79 }
80 }
◆ getAdjList() std::remove_reference< AdjList >::type const & Graph::getAdjList ( ) const inlineReturn a const reference of the adjacency list.
Definition at line 104 of file cycle_check_directed_graph.cpp.
104 {
105 return m_adjList;
106 }
◆ getVertices() unsigned int Graph::getVertices ( ) const inline ◆ print_flow_info() void Graph::print_flow_info ( ) inlineDefinition at line 81 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.
81 {
82 for (int i = 0; i < total_nodes; ++i) {
83 for (int j = 0; j < total_nodes; ++j) {
84 if (capacity[i][j] &&
85 residual_capacity[i][j] < capacity[i][j]) {
86 edge_participated.emplace_back(std::make_tuple(
87 i, j, capacity[i][j] - residual_capacity[i][j]));
88 }
89 }
90 }
91 std::cout << "\nNodes : " << total_nodes << "\nMax flow: " << max_flow
92 << "\nEdge present in flow: " << edge_participated.size()
93 << '\n';
94 std::cout << "\nSource\tDestination\tCapacity\total_nodes";
95 for (auto& edge_data : edge_participated) {
96 int source = 0, destination = 0, capacity_ = 0;
97 std::tie(source, destination, capacity_) = edge_data;
98 std::cout << source << "\t" << destination << "\t\t" << capacity_
99 << '\t';
100 }
101 }
◆ set_graph() void Graph::set_graph ( ) inlineDefinition at line 50 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.
50 {
51 std::cin >> total_nodes >> total_edges >> source >> sink;
52 parent = std::vector<int>(total_nodes, -1);
53 capacity = residual_capacity = std::vector<std::vector<int> >(
54 total_nodes, std::vector<int>(total_nodes));
55 for (int start = 0, destination = 0, capacity_ = 0, i = 0;
56 i < total_edges; ++i) {
57 std::cin >> start >> destination >> capacity_;
58 residual_capacity[start][destination] = capacity_;
59 capacity[start][destination] = capacity_;
60 }
61 }
◆ capacity ◆ edge_participated ◆ edgeNum ◆ edges [1/2] ◆ edges [2/2] ◆ m_adjList ◆ m_vertices ◆ max_flow ◆ parent ◆ residual_capacity ◆ sink ◆ source ◆ total_edges ◆ total_nodes ◆ vertexNum ◆ visitedThe documentation for this class was generated from the following files:
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4