
Security News
ESLint Adds Official Support for Linting HTML
ESLint now supports HTML linting with 48 new rules, expanding its language plugin system to cover more of the modern web development stack.
github.com/rajendraprasad7/map_reduce_mst
mrjob
)This project implements Borůvka’s algorithm for computing the Minimum Spanning Tree (MST) of a graph using MapReduce, facilitated via the mrjob
Python library. This approach is especially suitable for large-scale distributed environments.
Borůvka’s algorithm is an efficient greedy algorithm for MST computation. At each iteration, the algorithm:
This implementation simulates this iterative process using MapReduce, where each Map step identifies candidate edges and each Reduce step selects the lightest one.
boruvka_mr.py
: The main MapReduce job using mrjob
.dsu.py
: A helper module that implements the Disjoint Set Union (Union-Find) data structure, used to keep track of components.mrjob
(pip install mrjob
)pip install mrjob
The script expects three arguments:
--adjacency_list
: A stringified dictionary of the graph adjacency list.--dsu_rank
: A stringified list of the DSU ranks.--dsu_parent
: A stringified list of the DSU parent pointers.Each round of Borůvka corresponds to a single MapReduce job. Between iterations, the DSU state must be updated manually to reflect new merged components.
python boruvka_mr.py \
--adjacency_list="{0: [(1, 4), (2, 1)], 1: [(0, 4), (2, 3)], 2: [(0, 1), (1, 3)]}" \
--dsu_rank="[0, 0, 0]" \
--dsu_parent="[0, 1, 2]" \
-r inline
Each output line corresponds to the minimum edge chosen from each component in the current round.
Example output:
0 (0, 2, 1)
1 (1, 2, 3)
This means node 0
selected edge (0, 2, 1)
and node 1
selected (1, 2, 3)
for MST construction.
For each vertex and its adjacency list:
Borůvka’s algorithm is inherently iterative. This script runs a single phase of the algorithm. To complete the MST, you must:
parent
, rank
) and re-run until all nodes are in one component.mrjob
documentationRajendraprasad Saravanan
GitHub: @Rajendraprasad7
This project is licensed under the MIT License. See the LICENSE
file for details.
FAQs
Unknown package
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
ESLint now supports HTML linting with 48 new rules, expanding its language plugin system to cover more of the modern web development stack.
Security News
CISA is discontinuing official RSS support for KEV and cybersecurity alerts, shifting updates to email and social media, disrupting automation workflows.
Security News
The MCP community is launching an official registry to standardize AI tool discovery and let agents dynamically find and install MCP servers.