The single web page application featured in this tutorial web page allows the user to generate a “randomized” graph consisting of five nodes and up to ten edges (which is drawn on an HTML5 graph with a labeled Cartesian grid). Each time the user clicks on the GENERATE button, a new “randomized” graph is depicted along with the following information about that graph: (0) each NODE whole-number coordinate pair and alphabetical label, (1) each EDGE end-point pair, alphanumeric label, and length, (2) each possible traversal path starting at the node labeled A, while visiting every edge-adjacent node in the graph, and while traversing cycles for exactly one loop, and (3) the length of each of such traversal paths. (Note that the traversal paths are listed in order of their traversal lengths such that the shortest paths are at the top of the list while the longest paths are at the bottom of the list).

Note that a live version of the RANDOM_GRAPH_GENERATOR application is available to try using immediately from your current web browser at the following web address: https://karlinarayberinger.github.io/KARBYTES_BLOG_APPS_github_hosted_website/RANDOM_GRAPH_GENERATOR/random_graph_generator.html

To view hidden text inside of the preformatted text boxes below, scroll horizontally.

The following Hyper-Text-Markup-Language (HTML) code defines the user interface component of the RANDOM_GRAPH_GENERATOR web page application. Copy the HTML code from the source code file which is linked below into a text editor and save that file as random_graph_generator.html. Use a web browser such as Firefox to open that HTML file (and ensure that the JavaScript and Cascading-Style-Sheet files are in the same file directory as the HTML file).

(Note that angle brackets which resemble HTML tags (i.e. an “is less than” symbol (i.e. ‘<‘) followed by an “is greater than” symbol (i.e. ‘>’)) displayed on this web page have been replaced (at the source code level of this web page) with the Unicode symbols U+003C (which is rendered by the web browser as ‘<‘) and U+003E (which is rendered by the web browser as ‘>’). That is because the WordPress web page editor or web browser interprets a plain-text version of an “is less than” symbol followed by an “is greater than” symbol as being an opening HTML tag (which means that the WordPress web page editor or web browser deletes or fails to display those (plain-text) inequality symbols and the content between those (plain-text) inequality symbols)).

If copy-pasting the following HTML code from the preformatted text box below into a text editor, remove the zero-width space Unicode character () which is located between the ‘s’ and the ‘r’ in the script tag(s) which each link to a JavaScript file.

<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>RANDOM_GRAPH_GENERATOR</title> <link rel="stylesheet" href="karbytes_aesthetic.css"> <script src="random_graph_generator.js"></script> <style> #graphCanvas { background: #ffffff; border-width: 0px; } div { padding-top: 10px; } #generate_button { color: #00ff00; border-color: #00ff00; } #generate_button:hover { background: #00ff00; color: #000000; } </style> </head> <body onload="initialize_web_page()"> <h1>RANDOM_GRAPH_GENERATOR</h1> <p>Click the GENERATE button to instantiate a randomized graph consisting of NODEs and EDGEs between NODEs.</p> <p><input type="button" id="generate_button" value="GENERATE" onclick="generate_random_graph_and_data_about_that_graph()"></p> <canvas id="graphCanvas" width="430" height="430"></canvas> <div id="graphInfo">This sentence will be replaced with graph data after the GENERATE button is clicked.</div> <div class="console" id="time_stamped_messages"><p>???</p></div> </body> </html>

The following Cascading-Style-Sheet (CSS) code defines a stylesheet which customizes the appearance of interface components of the RANDOM_GRAPH_GENERATOR web page application. Copy the CSS code from the preformatted text box below or from the source code file which is linked below into a text editor and save that file as karbytes_aesthetic.css.

/** * file: karbytes_aesthetic.css * type: Cascading-Style-Sheet * date: 10_JULY_2023 * author: karbytes * license: PUBLIC_DOMAIN */ /** Make the page background BLACK, the text orange and monospace, and the page content width 800 pixels or less. */ body { background: #000000; color: #ff9000; font-family: monospace; font-size: 16px; padding: 10px; width: 800px; } /** Make input elements and select elements have an orange rounded border, a BLACK background, and orange monospace text. */ input, select { background: #000000; color: #ff9000; border-color: #ff9000; border-width: 1px; border-style: solid; border-radius: 5px; padding: 10px; appearance: none; font-family: monospace; font-size: 16px; } /** Invert the text color and background color of INPUT and SELECT elements when the cursor (i.e. mouse) hovers over them. */ input:hover, select:hover { background: #ff9000; color: #000000; } /** Make table data borders one pixel thick and CYAN. Give table data content 10 pixels in padding on all four sides. */ td { color: #00ffff; border-color: #00ffff; border-width: 1px; border-style: solid; padding: 10px; } /** Set the text color of elements whose identifier (id) is "output" to CYAN. */ #output { color: #00ffff; } /** Set the text color of elements whose class is "console" to GREEN and make the text background of those elements BLACK. */ .console { color: #00ff00; background: #000000; }

The following JavaScript (JS) code defines the functions which control the behavior of the RANDOM_GRAPH_GENERATOR web page application. Copy the JS code from the preformatted text box below or from the source code file which is linked below into a text editor and save that file as random_graph_generator.js.

/** * file: random_graph_generator.js * type: JavaScript * author: karbytes * date: 13_MARCH_2025 * license: PUBLIC_DOMAIN */ /** * Get the approximate integer Number of milliseconds which have elapsed since the Unix Epoch. * * The Unix Epoch is 01_JANUARY_1970 at 00:00 (Coordinated Universal Time (UTC)). * * @return {String} message displaying the time at which this function was called. */ function generate_time_stamp() { const approximate_number_of_milliseconds_elapsed_since_unix_epoch = Date.now(); return "approximately " + approximate_number_of_milliseconds_elapsed_since_unix_epoch + " milliseconds after 00:00 Coordinated Universal Time on 01_JANUARY_1970."; } /** * Display a time-stamped message at the bottom of the web page indicating the time at which that web page's source code file * (i.e. random_graph_generator.html) was most recently loaded by the web browser. * * Instantiate the appearance of a two-dimensional Cartesian grid on the web page's only canvas element. */ function initialize_web_page() { try { const time_stamped_message = "The initialize_web_page() function was called " + generate_time_stamp(), p0 = "<p>", p1 = "</p>"; console.log(time_stamped_message); document.getElementById("time_stamped_messages").innerHTML = p0 + time_stamped_message + p1; drawGrid(); } catch(e) { console.log("An exception to normal functioning occurred during the runtime of function initialize_web_page(): " + e); } } /** * Populate the (assumedly blank) canvas element (on the web page named random_graph_generator.html) * with grid lines (each separated by a 20-pixel width gap), horizontal (y) and vertical (x) axes * which intersect with each other at the center of the canvas (i.e. at x = 0, y = 0), * and numerical coordinate labels along each the x-axis and the y-axis. */ function drawGrid() { const canvas = document.getElementById('graphCanvas'); const ctx = canvas.getContext('2d'); const width = canvas.width; const height = canvas.height; const centerX = width / 2; const centerY = height / 2; const scale = 20; // pixels per grid unit ctx.strokeStyle = '#ddd'; ctx.lineWidth = 1; // Vertical lines for (let x = centerX % scale; x < width; x += scale) { ctx.beginPath(); ctx.moveTo(x, 0); ctx.lineTo(x, height); ctx.stroke(); } // Horizontal lines for (let y = centerY % scale; y < height; y += scale) { ctx.beginPath(); ctx.moveTo(0, y); ctx.lineTo(width, y); ctx.stroke(); } // Draw axes ctx.strokeStyle = '#000'; ctx.lineWidth = 2; // X-axis ctx.beginPath(); ctx.moveTo(0, centerY); ctx.lineTo(width, centerY); ctx.stroke(); // Y-axis ctx.beginPath(); ctx.moveTo(centerX, 0); ctx.lineTo(centerX, height); ctx.stroke(); // Tick marks and labels ctx.fillStyle = '#000'; ctx.font = '10px Arial'; for (let i = -10; i <= 10; i++) { // X-axis ticks ctx.beginPath(); ctx.moveTo(centerX + i * scale, centerY - 5); ctx.lineTo(centerX + i * scale, centerY + 5); ctx.stroke(); if (i !== 0) ctx.fillText(i, centerX + i * scale - 3, centerY + 15); // Y-axis ticks ctx.beginPath(); ctx.moveTo(centerX - 5, centerY + i * scale); ctx.lineTo(centerX + 5, centerY + i * scale); ctx.stroke(); if (i !== 0) ctx.fillText(-i, centerX + 8, centerY + i * scale + 3); } } /** * Generate a random integer within grid bounds (i.e. from -10 to 10). * * @return {Number} exactly one of the following twenty one values: * -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. */ function randomCoordinate() { return Math.floor(Math.random() * 21) - 10; } /** * Calculate the Euclidean distance between two points on a plane. * * @param {Object} a represents a graph NODE whose properties are the following: * exactly one x-axis value and exactly one y-axis value. * * @param {Object} b represents a graph NODE whose properties are the following: * exactly one x-axis value and exactly one y-axis value. */ function calculateDistance(a, b) { return Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2).toFixed(2); } /**-----------------------------------------------------------------------------------------------------------------------------------------------------*/ /** The following global variables store data which changes each time the GENERATE button is clicked on the web page named random_graph_generator.html. */ /**-----------------------------------------------------------------------------------------------------------------------------------------------------*/ // Generate five random non-identical NODE instances. let nodeLabels = ['A', 'B', 'C', 'D', 'E']; function generateUniqueNodes(count) { let uniqueNodes = []; let usedCoordinates = new Set(); while (uniqueNodes.length < count) { let x = randomCoordinate(); let y = randomCoordinate(); let coordinateKey = `${x},${y}`; // Create a unique key for the coordinate if (!usedCoordinates.has(coordinateKey)) { usedCoordinates.add(coordinateKey); uniqueNodes.push({ label: nodeLabels[uniqueNodes.length], x, y }); } } return uniqueNodes; } // Assign nodes using generateUniqueNodes let nodes = generateUniqueNodes(nodeLabels.length); // Generate up to ten random EDGE instances (which each represent two adjacent nodes of a graph). let edges = []; let numEdges = Math.floor(Math.random() * 6) + 5; // between 5 and 10 lines for (let i = 0; i < numEdges; i++) { let [n1, n2] = [nodes[Math.floor(Math.random() * nodes.length)], nodes[Math.floor(Math.random() * nodes.length)]]; while (n1 === n2 || edges.some(edge => (edge.node0 === n1 && edge.node1 === n2) || (edge.node0 === n2 && edge.node1 === n1))) { n1 = nodes[Math.floor(Math.random() * nodes.length)]; n2 = nodes[Math.floor(Math.random() * nodes.length)]; } edges.push({ node0: n1, node1: n2, length: calculateDistance(n1, n2) }); } // Global graph variable let graph = {}; function createGraph(nodes, edges) { graph = {}; // Reset global graph // Initialize graph with empty arrays for each node label nodes.forEach(node => { graph[node.label] = []; }); // Add edges ensuring bidirectionality and correctness edges.forEach(edge => { let from = edge.node0.label; let to = edge.node1.label; if (graph.hasOwnProperty(from) && graph.hasOwnProperty(to)) { if (!graph[from].includes(to)) { graph[from].push(to); } if (!graph[to].includes(from)) { graph[to].push(from); } } }); // Debugging: Log final adjacency list for verification // console.log("Final Adjacency List:", JSON.stringify(graph, null, 2)); } // Generate the graph from the global nodes and edges createGraph(nodes, edges); /**-----------------------------------------------------------------------------------------------------------------------------------------------------*/ /** End of global variables initialization (nodes, edges, graph) */ /**-----------------------------------------------------------------------------------------------------------------------------------------------------*/ /** * Draw Nodes and Edges * * The following function, drawGraph, renders a visual representation of a graph onto an HTML5 canvas element. * The function retrieves the canvas context, determines the center of the canvas, and applies a scaling factor to properly position nodes. * It first draws edges (lines) between connected nodes using the predefined edges array. * Then, it iterates through the 'nodes' array to render nodes as red circles, labeling them appropriately. * The y-axis is inverted to align with conventional Cartesian coordinates (positive y values appear above the center). * Dependencies: This function requires a global 'nodes' array containing labeled coordinate points and a 'lines' array defining connections between nodes. */ function drawGraph() { const canvas = document.getElementById('graphCanvas'); const ctx = canvas.getContext('2d'); const width = canvas.width; const height = canvas.height; const centerX = width / 2; const centerY = height / 2; const scale = 20; // pixels per grid unit // Adjust font settings for better readability ctx.font = '14px Arial'; ctx.textAlign = 'center'; ctx.textBaseline = 'middle'; // Draw Edges ctx.strokeStyle = 'blue'; ctx.lineWidth = 1.5; edges.forEach(edge => { ctx.beginPath(); ctx.moveTo(centerX + edge.node0.x * scale, centerY - edge.node0.y * scale); ctx.lineTo(centerX + edge.node1.x * scale, centerY - edge.node1.y * scale); ctx.stroke(); }); // Draw Nodes nodes.forEach(node => { ctx.fillStyle = 'red'; ctx.beginPath(); ctx.arc(centerX + node.x * scale, centerY - node.y * scale, 4, 0, 2 * Math.PI); ctx.fill(); // Adjust label positioning to prevent cutoff const labelOffsetX = node.x >= 0 ? 10 : -10; // Shift right for positive x, left for negative x const labelOffsetY = node.y >= 0 ? -10 : 10; // Shift up for positive y, down for negative y ctx.fillStyle = 'black'; ctx.fillText(node.label, centerX + node.x * scale + labelOffsetX, centerY - node.y * scale + labelOffsetY); }); } // Display Information Below Canvas (after the GENERATE button is clicked) function displayInfo() { const infoDiv = document.getElementById('graphInfo'); let html = '<h3>Graph Information</h3>'; html += '<strong>NODEs:</strong><ul>'; nodes.forEach(node => { html += `<li>${node.label}: X_POSITION = ${node.x}, Y_POSITION = ${node.y}</li>`; }); html += '</ul>'; html += '<strong>EDGEs:</strong><ul>'; edges.forEach((edge, idx) => { html += `<li>E${idx}: NODE_0 = ${edge.node0.label}, NODE_1 = ${edge.node1.label}, LENGTH = ${edge.length}</li>`; }); html += '</ul>'; // Generate adjacency list and display it let adjacencyArray = generateAdjacencyArray(graph); html += "<strong>Graph Representation:</strong><pre>"; adjacencyArray.forEach(entry => { html += entry[0] + ": " + entry.slice(1).join(", ") + "\n"; }); html += "</pre>"; if (graph['A']) { let traversalResults = calculateTraversalDistances(graph, edges, 'A'); html += '<strong>All Traversals Starting at A:</strong><ul>'; traversalResults.forEach((entry, index) => { let distanceText = (typeof entry.distance === 'number' && !isNaN(entry.distance)) ? entry.distance.toFixed(2) : "Unknown"; html += `<li>Traversal ${index + 1}: ${entry.path} (Total Distance: ${distanceText})</li>`; }); html += '</ul>'; } else { html += '<strong>All Traversals Starting at A:</strong> No valid paths found from A.'; } infoDiv.innerHTML = html; } /** * Append a time-stamped message to the bottom of the web page indicating when the function, generate_random_graph_and_data_about_that_graph(), was called. * * Assume this function was called in response to the GENERATE button on random_graph_generator.html getting clicked. * * Each time that button is clicked, a new instance of a randomized graph consisting of 5 nodes and up to 10 edges is drawn on the HTML5 canvas. * * Generate up to five randomized NODE instances such that each NODE instance is a software object consisting of two data attributes: * integers representing a horizontal and a vertical position on a Cartesian plane within 10 units of the Cartesian plane's center point. * * Generate randomized EDGE instances such that each EDGE instance is a software object consisting of two data attributes: * NODEs representing exactly two end-points to a edge segment. */ function generate_random_graph_and_data_about_that_graph() { const time_stamped_message = "The generate_random_graph_and_data_about_that_graph() function was called " + generate_time_stamp(), p0 = "<p>", p1 = "</p>"; console.log(time_stamped_message); document.getElementById("time_stamped_messages").innerHTML += p0 + time_stamped_message + p1; resetGraphData(); clearGraphElements(); drawGraph(); displayInfo(); } /** * Remove NODE and EDGE components from the HTML5 canvas on the web page whose source code file is named random_graph_generator.html. */ function clearGraphElements() { const canvas = document.getElementById('graphCanvas'); const ctx = canvas.getContext('2d'); // Define the area where nodes and edges exist const width = canvas.width; const height = canvas.height; // Use a composite operation to only clear nodes and lines while keeping the grid ctx.globalCompositeOperation = 'destination-out'; ctx.fillRect(0, 0, width, height); ctx.globalCompositeOperation = 'source-over'; // Redraw the grid after clearing nodes and edges drawGrid(ctx, width, height); } /** * Delete the data inside of the arrays named nodes and edges. * * Re-populate the canvas with a new randomized graph. */ function resetGraphData() { nodes = []; edges = []; console.log("Graph data has been reset."); generateNewGraphData(); // Reinitialize nodes and edges } /** * Generate EDGE instances which represent connections between NODE instances within the context of a graph. * * In the context of this software application, a graph consists of some natural number of point-sized nodes * and line-segment edges whose end-points are two non-identical nodes. */ function generateNewGraphData() { // Generate new nodes let nodeLabels = ['A', 'B', 'C', 'D', 'E']; nodes = nodeLabels.map(label => ({ label, x: randomCoordinate(), y: randomCoordinate() })); generateUniqueNodes(5); // Generate new random edges let numEdges = Math.floor(Math.random() * 6) + 5; // between 5 and 10 lines for (let i = 0; i < numEdges; i++) { let n1, n2; do { n1 = nodes[Math.floor(Math.random() * nodes.length)]; n2 = nodes[Math.floor(Math.random() * nodes.length)]; } while (n1 === n2 || edges.some(edge => (edge.node0 === n1 && edge.node1 === n2) || (edge.node0 === n2 && edge.node1 === n1))); edges.push({ node0: n1, node1: n2, length: calculateDistance(n1, n2) }); } // Generate the graph from the global nodes and edges createGraph(nodes, edges); } /** * This function converts the graph object into an adjacency array format. * Each element of the array represents a node and its connections. * The first element of each sub-array is the node itself, followed by its neighbors. * Example output: * [ * ["A", "B", "C", "D"], * ["B", "A", "C"], * ["C", "A", "B", "E"], * ["D", "A", "E"], * ["E", "C", "D"] * ] * @param {Object} graph - The adjacency list representation of the graph. * @returns {Array} adjacencyArray - The adjacency array representation of the graph. */ function generateAdjacencyArray(graph) { let adjacencyArray = []; Object.keys(graph).forEach(node => { adjacencyArray.push([node, ...graph[node]]); }); // console.log("Adjacency Array:", JSON.stringify(adjacencyArray, null, 2)); return adjacencyArray; } /** * This function finds all possible traversal paths in the graph * starting from a given node. It allows cycles and backtracking. * Each path follows edges between connected nodes and tracks visited edges. * * @param {Object} graph - The adjacency list representation of the graph. * @param {string} startNode - The node to start traversals from. * @returns {Array} paths - An array of all possible traversal paths. */ function findAllTraversals(graph, startNode) { let paths = []; function traverse(node, path, visitedEdges, cycleUsed) { path.push(node); let hasUnvisited = false; for (let neighbor of graph[node] || []) { let edgeKey = `${node}-${neighbor}`; let reverseEdgeKey = `${neighbor}-${node}`; if (!visitedEdges.has(edgeKey) || !cycleUsed) { hasUnvisited = true; let newVisitedEdges = new Set(visitedEdges); newVisitedEdges.add(edgeKey); newVisitedEdges.add(reverseEdgeKey); // Treat as an undirected graph traverse(neighbor, [...path], newVisitedEdges, cycleUsed || visitedEdges.has(edgeKey)); } } if (!hasUnvisited) { paths.push(path.join(" -> ")); } } traverse(startNode, [], new Set(), false); return paths; } /** * Sum the lengths of all edges in a given traversal. * Logs the traversal path and the total distance. * * @param {Array} traversal - An array of edges representing a path. * @return {Number} - The total sum of edge lengths. */ function sumEdgeLengths(traversal) { let totalLength = 0; let traversalPath = traversal.map(edge => `(${edge.node0.label} → ${edge.node1.label})`).join(" -> "); for (let edge of traversal) { totalLength += parseFloat(calculateDistance(edge.node0, edge.node1)); } console.log(`Traversal: ${traversalPath} | Total Distance: ${totalLength.toFixed(2)}`); return totalLength; } /** * Calculate the total distances for all traversals from a given start node. * Uses sumEdgeLengths(traversal) to compute distances and sorts them from shortest to longest. * * @param {Array} graph - The graph containing nodes. * @param {Array} edges - The list of edges with nodes. * @param {Object} startNode - The starting node for traversal. * @return {Array} - A sorted array of traversal paths and their respective distances. */ function calculateTraversalDistances(graph, edges, startNode) { let traversals = findAllTraversals(graph, startNode); let edgeMap = new Map(); console.log("Generating Edge Map..."); // Create a mapping of edges to their respective distances edges.forEach(edge => { let key = `${edge.node0.label}-${edge.node1.label}`; let reverseKey = `${edge.node1.label}-${edge.node0.label}`; let distance = Math.max(1, Math.ceil(parseFloat(calculateDistance(edge.node0, edge.node1)))); // Ensure nonzero integer edgeMap.set(key, { distance, edge }); edgeMap.set(reverseKey, { distance, edge }); console.log(`Mapped Edge: ${key} & ${reverseKey} → Distance: ${distance}`); }); console.log("Edge Map:", edgeMap); // Calculate the total minimum distance for each traversal using sumEdgeLengths let pathsWithDistances = traversals.map(pathStr => { let pathNodes = pathStr.split(" -> ").map(node => node.trim()); let traversalEdges = []; let validPath = true; console.log(`Processing Traversal: ${pathStr}`); for (let i = 0; i < pathNodes.length - 1; i++) { let node0 = pathNodes[i]; let node1 = pathNodes[i + 1]; let edgeKey = `${node0}-${node1}`; let reverseEdgeKey = `${node1}-${node0}`; console.log(`Checking Edge: ${edgeKey}`); if (edgeMap.has(edgeKey)) { let edgeObj = edgeMap.get(edgeKey); console.log(`Found Edge: ${edgeKey} → Distance: ${edgeObj.distance}`); traversalEdges.push(edgeObj.edge); } else { console.warn(`Edge Missing: ${edgeKey} or ${reverseEdgeKey} not found in Edge Map`); validPath = false; break; // Invalid path due to missing edge } } if (validPath && traversalEdges.length > 0) { let totalDistance = sumEdgeLengths(traversalEdges); console.log(`Traversal: ${pathStr} | Total Distance: ${totalDistance}`); return { path: pathStr, distance: totalDistance }; } else { console.warn(`Traversal: ${pathStr} | Total Distance: Unknown (Missing Edges)`); return { path: pathStr, distance: "Unknown (Missing Edges)" }; } }); // Sort traversals from shortest to longest distance let validPaths = pathsWithDistances.filter(traversal => traversal.distance !== "Unknown (Missing Edges)"); validPaths.sort((a, b) => a.distance - b.distance); console.log("Sorted Traversals (Shortest to Longest):"); validPaths.forEach(traversal => { console.log(`Traversal: ${traversal.path} | Total Distance: ${traversal.distance.toFixed(2)}`); }); return validPaths; }

Note that, in the image depicted below, the GENERATE button was clicked multiple times before the depicted graph was generated. That is because the prior graphs encompassed many more depicted traversal paths (and such a lengthy list of traversal paths would be difficult to encompass in a single screenshot image without risking being too big to upload and display on the (live and WayBack Machine backed up) web page and/or be too low resolution to be readable).

This web page was last updated on 12_JULY_2025. The content displayed on this web page is licensed as PUBLIC_DOMAIN intellectual property.