➕︎ Aa ➖︎ |Dark 1 ● Dark 2 ● Light|Hack ● Fira Code|Back to PT Mono✖
// CPCS 324 Algorithms & Data Structures 2
// First graph implementation - JSDOC3 demo
// 2020, Dr. Muhammad Al-Hashimi
// IMPORTANT NOTE - Don't use as starter or reference for code organization
// This file is only intended to demonstrate the use of JSDOC comments, and
// to generate the reference specs for the basic graph to use in 324.
/**
@fileOverview <p>An implementation of a simple graph data type with a basic
set of properties and operations; more may be added later as needed.</p>
<p>This is a JSDdoc3 demo to illustrate how javadoc-style documentation
comments and tags should be used within your source code. Every detail of the
design is published to provide an implementation guide for this course.</p>
@author 2020, Dr. Muhammad Al-Hashimi
@version Version 1.2 (Fall 2020), First Graph Implementation
*/
// -----------------------------------------------------------------------
/** @var {object[]} _v Input vertex objects (properties documented in {@link better_input}) */
/** @var {object[]} _e Input edge list (documented in {@link better_input}) */
var _v = [], _e = []; // 1-line comment style (also note 2 styles of documentation wording)
/**
Special global program startup function for the caller page, similar to
main() in C/C++/Java. Only function allowed to access global vars.
@author Muhammad Al-Hashimi
*/
function _main() // multiline comment style above
{
}
// -----------------------------------------------------------------------
/**
* Create a graph vertex using a special input object, also called a configuration
* object since it is used to configure the user properties of the vert.
*
* @author Muhammad Al-Hashimi
*
* @constructor
* @see {@link better_input} for details of config objects of the default internal input format.
* @param {object} v Input (configuration) object containing info used to initialize the vertex (such as a label)
* @param {string} v.label Required property (note how fields of input object are documented)
*/
function Vertex(v) // another conventional multiline style (not a fan personally)
{
// --------------------
// property fields
/** A text string to label a vertex, passed as arg to vertex constructor. */
this.label = v.label;
/**
Mark vertex visited or "seen" (useful for traversals and such).
@type {boolean}
@default false
*/
this.visit = false; // sometimes useful to document type
// marked as @private to hide by default in published documentation, show by using -p parameter on jsdoc command line
/**
Head pointer of a vertex adjacency list.
@private
*/
this.adjacent = new List();
// --------------------
// member methods
/**
Get id of adjacent vertices in an array.
@method
*/
this.adjacentByID = adjacentByIdImpl;
/**
Get information of incident edges in an array of custom objects (details
depend on implementation).
@method
@see {@link incidentEdgesImpl}
*/
this.incidentEdges = incidentEdgesImpl;
/**
Get printable vertex info strings, details depend on implementation.
@method
*/
this.vertexInfo = vertexInfoImpl;
/**
Insert an edge target vertex in adjacency list. An optional edge weight may
also be specified. This method hides adjacency implementation details (it
does the actual work on behalf of graph methods).
@method
@todo Left for students as exercise.
@see {@link addEdgeImpl2} (read description carefully)
*/
this.insertAdjacent = insertAdjacentImpl;
}
// -----------------------------------------------------------------------
/**
Create a graph edge object. Defaults to unweighted unless an optional weight
argument is passed
@author Muhammad Al-Hashimi
@constructor
@param {integer} vert_i Target vertex id
@param {number} [weight] Edge weight/cost, a number in general
*/
function Edge(vert_i,weight)
{
// --------------------
// property fields
/** Id of edge target vertex */
this.target_v = vert_i;
/**
Edge weight/cost, is null (for unweighted) unless an optional weight parameter
was specified when edge was created
@type {?number}
@default null
*/
this.weight; // note @type nullable (number or null)
// --------------------
// member methods
}
// -----------------------------------------------------------------------
/**
Create an empty graph object. Defaults to unlabeled, undirected, and
unweighted graph.
@author Muhammad Al-Hashimi
@constructor
*/
function Graph()
{
// --------------------
// property fields
/**
Vertex list
@type {Array<Vertex>}
@default [ ]
*/
this.verts = [];
/**
Number of vertices, initially 0
@default 0
*/
this.nv = 0; // no need to @type every var, only where needed (or adds value)
/**
Number of edges, initially 0
@default 0
*/
this.ne = 0;
/**
True if graph is directed (digraph), false otherwise
@type {boolean}
@default false
*/
this.digraph = false;
/**
True if graph is weighted, false otherwise
@type {boolean}
@default false
*/
this.weighted = false;
/**
Array of vertex id in DFS order. Stores output of last DFS and should be
reset or recreated after changes to vertex and edge sets.
@default [ ]
*/
this.dfs_push = [];
/**
Array of vertex id in BFS order. Stores output of last BFS and should be
reset or recreated after changes to vertex and edge sets.
@default [ ]
*/
this.bfs_order = [];
/**
An identification text string to label graph
@default empty string
*/
this.label = "";
/**
Number of connected components (0: no info), is set after a DFS/BFS
@default 0
@see {@link Graph#topoSearch}
*/
this.connectedComp = 0;
/**
Graph adjacency matrix, to be created on demand via {@link Graph#makeAdjMatrix}
method. Should be reset or recreated after changes to vertices and edges.
@default [ ]
*/
this.adjMatrix = [];
// --------------------
// member methods
/**
List graph vertices using info strings returned by Vertex methods
@method
@see {@link Vertex#vertexInfo}
*/
this.listVerts = listVertsImpl;
/**
Graph reader, defaults to internal format, details depend on implementation
@see better_input
@method
*/
this.readGraph = better_input;
/**
Insert an edge
@method
*/
this.addEdge = addEdgeImpl2;
/**
Print graph information. See implementing function for details.
@method
*/
this.printGraph = printGraphImpl;
/**
Create a random graph, details depend on implementation
@method
@todo <mark>Not part of Project 1</mark>. To be implemented in the Final Project.
@see makeGraphImpl
*/
this.makeGraph = makeGraphImpl;
/**
Visit connected vertices depth-first starting at some vertex
@method
*/
this.dfs = dfsImpl;
/**
Visit connected vertices breadth-first starting at some vertex
@method
*/
this.bfs = bfsImpl;
/**
Create adjacency (or weight, if graph weighted) matrix
@method
*/
this.makeAdjMatrix = makeAdjMatrixImpl2;
/**
Test if graph is connected returning true, otherwise false
@method
*/
this.isConnected = isConnectedImpl;
/**
Get printable connectivity info strings, details depend on implementation.
@method
*/
this.componentInfo = componentInfoImpl;
/**
Perform a search-like topological traversal of graph vertices. This method
iterates on connected components, calling a specified traversal method
(e.g., dfs) on each component, see implementing function for details.
@method
*/
this.topoSearch = topoSearchImpl;
}
// -----------------------------------------------------------------------
// Functions used by methods of Graph object. Similar to
// normal functions but use object member fields and
// methods, depending on which object is passed by the
// method call through the self variable: this.
// -----------------------------------------------------------------------
/**
Add an edge from a vertex pair (original pre Checkpoint 6).
@author Muhammad Al-Hashimi
@deprecated Obsolete first implementation. Use {@link addEdgeImpl3} instead.
@implements Graph#addEdge
@param {number} u_i Source vertex id
@param {number} v_i Target vertex id
*/
function addEdgeImpl(u_i,v_i)
{
}
/**
Add an edge from a vertex pair and optional weight (from Checkpoint 6).
@author Muhammad Al-Hashimi
@deprecated Obsolete, use {@link addEdgeImpl3} instead. It is tempting to
insert directly via .insert() method of underlying linked-list, which is
considered an encapsulation mistake. Graph and its methods should not see how
adjacency lists are implemented.
@implements Graph#addEdge
@see addEdgeImpl3
@see Vertex#insertAdjacent
@param {integer} u_i Source vertex id
@param {integer} v_i Target vertex id
@param {number} [weight] Edge weight/cost
*/
function addEdgeImpl2(u_i,v_i,weight)
{
}
/**
Add an edge from a vertex pair and an optional weight. A better implementation
which relies on a vertex method to handle adjacency details.
@author Muhammad Al-Hashimi
@implements Graph#addEdge
@see Vertex#insertAdjacent
@param {integer} u_i Source vertex id
@param {integer} v_i Target vertex id
@param {number} [weight] Edge weight/cost
*/
function addEdgeImpl3(u_i,v_i,weight)
{
}
/**
Output graph properties and list its vertices (replaces {@link
better_output}). This function depends on the vertex lister method of the
graph.
@author Muhammad Al-Hashimi
@implements Graph#printGraph
@see {@link Graph#listVerts}
*/
function printGraphImpl()
{
}
/**
Output a vertex list using descriptive strings returned by the Vertex object
@author Muhammad Al-Hashimi
@implements Graph#listVerts
@see Vertex#vertexInfo
*/
function listVertsImpl()
{
}
/**
Input graph data based on default internal format, see parameters for
details. Create vertices and corresponding adjacency lists, and set number of
vertices and edges accordingly. Set a weighted property of graph if an
optional weight is specified in input edge list (based on the first pair).
Vertices are auto assigned a numeric id starting from 0 based on position in
the input vertex list. Will interpret input edge list as undirected unless
the directed property of the graph was set. Only function allowed to break
naming convention of method- implementing functions (no Impl suffix).
@author Muhammad Al-Hashimi
@implements Graph#readGraph
@param {object[]} v Vertex input (configuration) objects
@param {string} v.label Vertex label
@param {object} e Array of edge input (configuration) objects
@param {integer} e.u Source vertex id
@param {integer} e.v Target vertex id
@param {number} [e.w] Edge weight
*/
function better_input(v,e)
{
}
/**
Output graph data
@author Muhammad Al-Hashimi
@deprecated Replaced by {@link printGraphImpl}
@implements Graph#printGraph
@see {@link printGraphImpl}
*/
function better_output()
{
}
/**
Implement a versatile caller for search-like topological traversals of
vertices (initially support DFS and BFS). Updates and returns the number of
connected components {@link Graph#connectedComp}. Stores the id of vertices
in visit order in {@link Graph#dfs_push} or {@link Graph#bfs_order} depending
on requested search.
@author Muhammad Al-Hashimi
@implements Graph#topoSearch
@param fun Design left for students
@return {integer} Number of connected components
*/
function topoSearchImpl()
{
}
/**
Recursively traverse a connected component depth-first starting at passed
vertex. Inserts visited vertex id in visit order in {@link #dfs_push}.
@implements Graph#dfs
@param {number} v_i Starting vertex id
*/
function dfsImpl(v_i)
{
}
/**
Traverse a connected component breadth-first starting at passed vertex.
Inserts visited vertex id in visit order in {@link #bfs_order}.
@author Muhammad Al-Hashimi
@implements Graph#bfs
@param {number} v_i Starting vertex id
*/
function bfsImpl(v_i)
{
}
/**
Generate adjacency matrix representation of graph - obsolete naïve
implementation, see notes below.
@author Muhammad Al-Hashimi
@deprecated Use {@link Graph#makeAdjMatrixImpl3} instead. This function
doesn't support weighted edges, and is not coded optimally.
@implements Graph#makeAdjMatrix
*/
function makeAdjMatrixImpl()
{
}
/**
Generate adjacency matrix representation of graph - obsolete first weighted
implementation, see notes below.
@author Sandy Bridge
@deprecated Use {@link Graph#makeAdjMatrixImpl3} instead. This version illustrates
a point about better object-oriented design consistent with principles of
encapsulation and proper hiding of implementation details.
@implements Graph#makeAdjMatrix
*/
function makeAdjMatrixImpl2()
{
}
/**
Generate an adjacency matrix from internal adjacency lists. A weight (or
weighted adjacency) matrix is produced if graph is weighted. This is a better
implementation which relies on vertex methods to obtain incident edges
information.
@author Muhammad Al-Hashimi
@implements Graph#makeAdjMatrix
*/
function makeAdjMatrixImpl3()
{
}
/**
Return connected status based on internal connectivity field
@implements Graph#isConnected
@returns {boolean} True if graph is connected
*/
function isConnectedImpl()
{
}
/**
Report connectivity information if available
@implements Graph#componentInfo
@returns {string} Connectivity report including number of connected
components if disconnected. One of following strings is returned: "no
information available", "CONNECTED", or "DISCONNECTED (n)" where n is number of
connected components
*/
function componentInfoImpl()
{
}
/**
Get id of adjacent vertices in an array
@implements {Vertex#adjacentById}
@returns {integer[]} Array containing id of adjacent vertices in edge input order by default
*/
function adjacentByIdImpl()
{
}
/**
@typedef {object} enode - Workaround to document a literal object returned by function
@property {integer} adjVert_i - id of target vertex
@property {string} edgeLabel - a text label (not implemented, always "" for now)
@property {number} [edgeWeight] - weight/cost, if any
@see incidentEdgesImpl
*/
// a @typedef as work-around to specify fields of a return object, otherwise
// multiple @returns show fields as separate values with different types;
// this is a weakness in the package (@returns should work similar to @param
// for object properties, but it does not as of v3.6.3)
/**
Get information of edges incident to a vertex, to be returned in an array of
special output objects each of which contains information from an edge node
in the vertex adjacency list. This function implements a general, extensible
interface to the adjacency lists which may replace {@link
Vertex#adjacentByID}.
@author Muhammad Al-Hashimi
@author Sandy Bridge
@implements {Vertex#incidentEdges}
@returns {enode[]} Array of custom objects containing edge information, in
input order by default.
*/
function incidentEdgesImpl()
{
}
/**
Get vertex details in a printable string
@implements {Vertex#vertexInfo}
@example <caption>Sample output.</caption>
VERTEX: 0 {a} - VISIT: false - ADJACENCY: 3,2,4
@returns {string} Formatted vertex information
*/
function vertexInfoImpl()
{
}
/**
Insert a new edge node in the adjacency list of vertex. Currently only
updates the internal adjacency list representation.
@implements {Vertex#insertAdjacent}
@param {number} v_i Edge target vertex id
@param {number} [weight] Edge weight (for weighted graphs), if specified
*/
function insertAdjacentImpl(v_i,weight)
{
}
/**
Create a random graph using vertex id as label. If weighted generate random
weights between 1 and 50000. Digraph property should be set before this
method otherwise the graph will be undirected by default. Suggestion: can you
utilize the graph reader method to create the graph for you?
@implements {Graph#makeGraph}
@param {number} n Number of vertices
@param {number} m Number of edges
@param {boolean} w Weighted if true
*/
function makeGraphImpl()
{
}