FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
mage/cpp/bridges_module/algorithm/bridges.cpp at main · memgraph/mage · GitHub
This repository was archived by the owner on Jan 23, 2026. It is now read-only.
memgraph
/
mage
Public archive
Notifications
You must be signed in to change notification settings
Fork
35
Star
331
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
mage
/
cpp
/
bridges_module
/
algorithm
/
bridges.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
61 lines (48 loc) · 1.72 KB
Breadcrumbs
mage
/
cpp
/
bridges_module
/
algorithm
/
bridges.cpp
Copy path
File metadata and controls
61 lines (48 loc) · 1.72 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
#
include
<
algorithm
>
#
include
"
bridges.hpp
"
namespace
bridges_util
{
NodeState::NodeState
(std::
size_t
number_of_nodes) {
visited.
resize
(number_of_nodes,
false
);
discovery.
resize
(number_of_nodes,
0
);
low_link.
resize
(number_of_nodes,
0
);
counter =
0
;
}
void
NodeState::Update
(std::
uint64_t
node_id) {
counter++;
visited[node_id] =
true
;
discovery[node_id] = counter;
low_link[node_id] = counter;
}
void
BridgeDfs
(std::
uint64_t
node_id, std::
uint64_t
parent_id, NodeState *state, std::vector<mg_graph::Edge<>> *bridges,
const
mg_graph::GraphView<> &graph) {
state->
Update
(node_id);
for
(
const
auto
&neigh : graph.
Neighbours
(node_id)) {
auto
next_id = neigh.
node_id
;
if
(state->
visited
[next_id]) {
if
(next_id != parent_id) {
state->
low_link
[node_id] =
std::min
(state->
low_link
[node_id], state->
discovery
[next_id]);
}
continue
;
}
BridgeDfs
(next_id, node_id, state, bridges, graph);
state->
low_link
[node_id] =
std::min
(state->
low_link
[node_id], state->
low_link
[next_id]);
const
auto
&edge = graph.
GetEdge
(neigh.
edge_id
);
if
(state->
low_link
[next_id] > state->
discovery
[node_id]) {
if
(graph.
GetEdgesBetweenNodes
(edge.
from
, edge.
to
).
size
() ==
1
) bridges->
push_back
(edge);
}
}
}
}
//
namespace bridges_util
namespace
bridges_alg
{
std::vector<mg_graph::Edge<>>
GetBridges
(
const
mg_graph::GraphView<> &graph) {
auto
number_of_nodes = graph.
Nodes
().
size
();
bridges_util::NodeState
state
(number_of_nodes);
std::vector<mg_graph::Edge<>> bridges;
for
(
const
auto
&node : graph.
Nodes
()) {
if
(!state.
visited
[node.
id
]) {
bridges_util::BridgeDfs
(node.
id
, node.
id
, &state, &bridges, graph);
}
}
return
bridges;
}
}
//
namespace bridges_alg
Back
|
FazBrowse Home
|
New Git URL