Algorithm-TimelinePacking
view release on metacpan or search on metacpan
# NAME
Algorithm::TimelinePacking - Arrange time intervals into non-overlapping lines
## Example Output
The module arranges overlapping time intervals into non-overlapping rows,
perfect for Gantt-style visualizations:
*75 Hadoop MapReduce jobs arranged into 11 parallel execution lanes.
See `examples/hadoop-jobs.html` for the full demo.*
# SYNOPSIS
use Algorithm::TimelinePacking;
# $lines is an arrayref of arrayrefs, each containing non-overlapping slices
# $latest is the normalized end timestamp
# DESCRIPTION
Algorithm::TimelinePacking solves the interval graph coloring problem: given a
set of potentially overlapping time intervals, it assigns them to the minimum
number of "lines" (rows) such that no two intervals on the same line overlap.
Originally developed to visualize Hadoop MapReduce job execution timelines,
the algorithm is completely generic and works for any Gantt-style visualization:
conference schedules, meeting room allocation, project timelines, TV programming,
resource booking systems, or any scenario with overlapping time ranges.
The algorithm uses a greedy first-fit approach, placing each interval on the
first available line where it fits without overlap.
# EXAMPLES
## Conference Schedule
examples/conference.html view on Meta::CPAN
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>TinfoilConf 2024 - Timeline Demo</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
* { box-sizing: border-box; }
body {
font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, sans-serif;
margin: 0; padding: 20px; background: #f8f9fa; color: #333;
}
h1 { margin-top: 0; color: #2c3e50; }
.subtitle { color: #666; margin-bottom: 20px; }
.container { max-width: 1200px; margin: 0 auto; }
#chart {
background: white; border-radius: 8px; padding: 20px;
examples/conference.html view on Meta::CPAN
.legend-color { width: 16px; height: 16px; border-radius: 3px; }
.tooltip {
position: absolute; background: rgba(0,0,0,0.9); color: #fff;
padding: 12px; border-radius: 6px; font-size: 13px;
pointer-events: none; z-index: 1000; max-width: 280px; line-height: 1.4;
display: none;
}
.tooltip-title { font-weight: bold; font-size: 14px; margin-bottom: 6px; }
.tooltip-time { color: #aaa; margin-bottom: 4px; }
.stats { margin-top: 15px; font-size: 13px; color: #666; }
</style>
</head>
<body>
<div class="container">
<h1>TinfoilConf 2024</h1>
<p class="subtitle">The premier conference for developers who do their own research. Wake up, sheeple! Hover over sessions for details.</p>
<div id="chart"></div>
<div class="legend" id="legend"></div>
<div class="stats" id="stats"></div>
</div>
<div class="tooltip" id="tooltip">
examples/conference.html view on Meta::CPAN
var w = Math.max(30, (d[1] - d[0]) * SCALE);
var maxChars = Math.floor(w / 7);
return d[2].length > maxChars ? d[2].substring(0, maxChars - 1) + '...' : d[2];
});
talks.on("mouseover", function(event, d) {
d3.select("#tooltip-title").text(d[2]);
d3.select("#tooltip-time").text(fmt(d[0] + EARLIEST) + ' - ' + fmt(d[1] + EARLIEST));
d3.select("#tooltip-speaker").text(d[3] ? 'Speaker: ' + d[3] : '');
d3.select("#tooltip-track").text('Track: ' + LABELS[d[4]]);
tooltip.style("display", "block")
.style("left", (event.pageX + 10) + "px")
.style("top", (event.pageY - 10) + "px");
})
.on("mousemove", function(event) {
tooltip.style("left", (event.pageX + 10) + "px")
.style("top", (event.pageY - 10) + "px");
})
.on("mouseout", function() {
tooltip.style("display", "none");
});
});
// Legend
var legend = d3.select("#legend");
Object.keys(COLORS).forEach(function(track) {
var item = legend.append("div").attr("class", "legend-item");
item.append("div").attr("class", "legend-color").style("background", COLORS[track]);
item.append("span").text(LABELS[track]);
});
// Stats
d3.select("#stats").text(INPUT.length + ' sessions arranged in ' + lines.length + ' rooms | Conference runs ' + fmt(EARLIEST) + ' - ' + fmt(EARLIEST + LATEST));
</script>
</body>
</html>
examples/generate_demo.pl view on Meta::CPAN
my $width = 1200;
# Generate complete HTML document
print <<"HTML";
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Timeline Demo</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
body {
font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, sans-serif;
margin: 20px;
background: #f5f5f5;
}
h1 {
color: #333;
}
.info {
margin-bottom: 20px;
examples/generate_demo.pl view on Meta::CPAN
overflow: visible;
}
rect {
stroke: #fff;
stroke-width: 0.5;
}
rect:hover {
stroke: #000;
stroke-width: 2;
}
</style>
</head>
<body>
<h1>Timeline Visualization Demo</h1>
<div class="info">
<p>50 simulated Hadoop jobs arranged on ${\(scalar @$lines)} lines.
Hover over bars to see job details.</p>
<p>Color intensity represents map task count (gray → red = few → many).</p>
</div>
<div id="chart">
<svg id="timeline" width="$width"></svg>
examples/generate_demo.pl view on Meta::CPAN
myData.forEach(function(line, idx) {
const lineGroup = d3.select("#timeline")
.append("g")
.attr("id", "line_" + idx)
.attr("transform", "translate(0," + (idx * LINE_HEIGHT) + ")");
lineGroup.selectAll("rect")
.data(line)
.enter()
.append("rect")
.style("fill", function(d) {
if (d[4] > INTENSITY_MAX) return "#f00";
return d3.interpolateLab("#eee", "#f00")(levelColor(d[4]));
})
.attr("height", BAR_HEIGHT)
.attr("width", function(d) {
return Math.max(2, d[1] / SCALE_DIVISOR - d[0] / SCALE_DIVISOR);
})
.attr("x", function(d) {
return d[0] / SCALE_DIVISOR;
})
examples/hadoop-jobs.html view on Meta::CPAN
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Hadoop Jobs Timeline - Demo</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
* { box-sizing: border-box; }
body {
font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, sans-serif;
margin: 0; padding: 20px; background: #f8f9fa; color: #333;
}
h1 { margin-top: 0; color: #2c3e50; }
.subtitle { color: #666; margin-bottom: 20px; }
.container { max-width: 1400px; margin: 0 auto; }
#chart {
background: #fff; border-radius: 8px; padding: 20px;
examples/hadoop-jobs.html view on Meta::CPAN
.stats { margin-top: 15px; font-size: 13px; color: #666; }
.tooltip {
position: absolute; background: rgba(0,0,0,0.9); color: #fff;
padding: 10px; border-radius: 4px; font-size: 12px;
pointer-events: none; z-index: 1000; line-height: 1.5; display: none;
}
.tooltip-title { font-weight: bold; margin-bottom: 5px; }
.legend { display: flex; gap: 20px; margin-top: 15px; font-size: 12px; }
.legend-item { display: flex; align-items: center; gap: 5px; }
.legend-color { width: 20px; height: 12px; border-radius: 2px; }
</style>
</head>
<body>
<div class="container">
<h1>Hadoop MapReduce Timeline</h1>
<p class="subtitle">75 jobs arranged into parallel execution lanes. Color intensity indicates map task count. Hover for details.</p>
<div id="chart">
<svg id="timeline" width="1200"></svg>
</div>
examples/hadoop-jobs.html view on Meta::CPAN
// =============================================================================
// RENDERING: Display the pre-computed layout (no algorithm, just visualization)
// =============================================================================
var LINE_HEIGHT = 22;
var BAR_HEIGHT = 18;
var SCALE = 1100 / LATEST;
var colorFn = function(d) { return d3.interpolateLab("#eee", "#f00")(d); };
document.getElementById('legend-low').style.background = colorFn(0);
document.getElementById('legend-high').style.background = colorFn(1);
var svg = d3.select("#timeline");
svg.attr("height", lines.length * LINE_HEIGHT);
var tooltip = document.getElementById('tooltip');
lines.forEach(function(line, idx) {
var lineGroup = svg.append("g")
.attr("transform", "translate(0, " + (idx * LINE_HEIGHT) + ")");
lineGroup.selectAll("rect")
.data(line)
.enter()
.append("rect")
.style("fill", function(d) { return colorFn(Math.min(d[4] / 5000, 1)); })
.attr("height", BAR_HEIGHT)
.attr("width", function(d) { return Math.max(3, (d[1] - d[0]) * SCALE); })
.attr("x", function(d) { return d[0] * SCALE; })
.attr("y", 0)
.attr("rx", 2)
.attr("ry", 2)
.on("mouseover", function(event, d) {
document.getElementById('tooltip-title').textContent = d[2];
document.getElementById('tooltip-user').textContent = 'User: ' + d[3];
document.getElementById('tooltip-maps').textContent = 'Maps: ' + d[4].toLocaleString();
document.getElementById('tooltip-reduces').textContent = 'Reduces: ' + d[5].toLocaleString();
document.getElementById('tooltip-duration').textContent = 'Duration: ' + (d[1] - d[0]) + 's';
tooltip.style.display = 'block';
tooltip.style.left = (event.pageX + 10) + 'px';
tooltip.style.top = (event.pageY - 10) + 'px';
})
.on("mousemove", function(event) {
tooltip.style.left = (event.pageX + 10) + 'px';
tooltip.style.top = (event.pageY - 10) + 'px';
})
.on("mouseout", function() {
tooltip.style.display = 'none';
});
});
document.getElementById('stats').textContent = INPUT.length + ' jobs arranged on ' + lines.length + ' lines | Timeline span: ' + LATEST + 's | Avg jobs per line: ' + (INPUT.length / lines.length).toFixed(1);
</script>
</body>
</html>
lib/Algorithm/TimelinePacking.pm view on Meta::CPAN
=head1 NAME
Algorithm::TimelinePacking - Arrange time intervals into non-overlapping lines
=begin markdown
## Example Output
The module arranges overlapping time intervals into non-overlapping rows,
perfect for Gantt-style visualizations:
*75 Hadoop MapReduce jobs arranged into 11 parallel execution lanes.
See `examples/hadoop-jobs.html` for the full demo.*
=end markdown
=head1 SYNOPSIS
lib/Algorithm/TimelinePacking.pm view on Meta::CPAN
# $lines is an arrayref of arrayrefs, each containing non-overlapping slices
# $latest is the normalized end timestamp
=head1 DESCRIPTION
Algorithm::TimelinePacking solves the interval graph coloring problem: given a
set of potentially overlapping time intervals, it assigns them to the minimum
number of "lines" (rows) such that no two intervals on the same line overlap.
Originally developed to visualize Hadoop MapReduce job execution timelines,
the algorithm is completely generic and works for any Gantt-style visualization:
conference schedules, meeting room allocation, project timelines, TV programming,
resource booking systems, or any scenario with overlapping time ranges.
The algorithm uses a greedy first-fit approach, placing each interval on the
first available line where it fits without overlap.
=head1 EXAMPLES
=head2 Conference Schedule
( run in 1.716 second using v1.01-cache-2.11-cpan-e1769b4cff6 )