A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d3/dec/cycle__check__directed__graph_8cpp_source.html below:

TheAlgorithms/C++: graph/cycle_check_directed_graph.cpp Source File

31

Edge(Edge&&) =

default

;

32

Edge& operator=(Edge&&) =

default

;

33

Edge(Edge

const

&) =

default

;

34

Edge& operator=(Edge

const

&) =

default

;

41 Edge

(

unsigned int

source,

unsigned int

destination)

42

: src(source), dest(destination) {}

45using

AdjList = std::map<unsigned int, std::vector<unsigned int>>;

57

Graph() : m_adjList({}) {}

59

Graph(Graph&&) =

default

;

60

Graph& operator=(Graph&&) =

default

;

61

Graph(Graph

const

&) =

default

;

62

Graph& operator=(Graph

const

&) =

default

;

69 Graph

(

unsigned int

vertices, AdjList adjList)

70

: m_vertices(vertices), m_adjList(std::move(adjList)) {}

77 Graph

(

unsigned int

vertices, AdjList&& adjList)

78

: m_vertices(vertices), m_adjList(std::move(adjList)) {}

89 Graph

(

unsigned int

vertices, std::vector<Edge>

const

& edges)

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"

);

96

m_adjList[edge.src].emplace_back(edge.dest);

104

std::remove_reference<AdjList>::type

const

&

getAdjList

()

const

{

126 if

(edge.src >= m_vertices || edge.dest >= m_vertices) {

127 throw

std::range_error(

"Either src or dest of edge out of range"

);

129

m_adjList[edge.src].emplace_back(edge.dest);

137 void addEdge

(

unsigned int

source,

unsigned int

destination) {

138 if

(source >= m_vertices || destination >= m_vertices) {

139 throw

std::range_error(

140 "Either source or destination of edge out of range"

);

142

m_adjList[source].emplace_back(destination);

146 unsigned int

m_vertices = 0;

161 enum

nodeStates : uint8_t { not_visited = 0, in_stack, visited };

172

std::vector<nodeStates>* state,

173 unsigned int node

) {

175

(*state)[

node

] = in_stack;

179 auto const

it = adjList.find(

node

);

180 if

(it != adjList.end()) {

181 for

(

auto

child : it->second) {

184 auto

state_of_child = (*state)[child];

185 if

(state_of_child == not_visited) {

189

}

else if

(state_of_child == in_stack) {

200

(*state)[

node

] = visited;

214 auto

vertices =

graph

.getVertices();

223

std::vector<nodeStates> state(vertices, not_visited);

226 for

(

unsigned int node

= 0;

node

< vertices;

node

++) {

230 if

(state[

node

] == not_visited) {

251 auto

graphAjdList =

graph

.getAdjList();

252 auto

vertices =

graph

.getVertices();

254

std::vector<unsigned int> indegree(vertices, 0);

256 for

(

auto const

&

list

: graphAjdList) {

257 auto

children =

list

.second;

258 for

(

auto const

& child : children) {

263

std::queue<unsigned int> can_be_solved;

264 for

(

unsigned int node

= 0;

node

< vertices;

node

++) {

267 if

(!indegree[

node

]) {

268

can_be_solved.emplace(

node

);

273 auto

remain = vertices;

275 while

(!can_be_solved.empty()) {

276 auto

solved = can_be_solved.front();

283 auto

it = graphAjdList.find(solved);

284 if

(it != graphAjdList.end()) {

285 for

(

auto

child : it->second) {

287 if

(--indegree[child] == 0) {

290

can_be_solved.emplace(child);

298 return

!(remain == 0);

307 Graph g

(7, std::vector<Edge>{{0, 1}, {1, 2}, {2, 0}, {2, 5}, {3, 5}});

static bool isCyclicDFSHelper(AdjList const &adjList, std::vector< nodeStates > *state, unsigned int node)

static bool isCyclicBFS(Graph const &graph)

static bool isCyclicDFS(Graph const &graph)

Edge(unsigned int source, unsigned int destination)

std::remove_reference< AdjList >::type const & getAdjList() const

Graph(unsigned int vertices, AdjList &&adjList)

unsigned int getVertices() const

Graph(unsigned int vertices, std::vector< Edge > const &edges)

void addVertices(unsigned int num=1)

void addEdge(unsigned int source, unsigned int destination)

Graph(unsigned int vertices, AdjList adjList)

void addEdge(Edge const &edge)

double g(double x)

Another test function.

int main()

Main function.

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