Global

Members

_e :Array.<object>

Input edge list (documented in better_input)
Type ▸ Array.<object>
Source:

_v :Array.<object>

Input vertex objects (properties documented in better_input)
Type ▸ Array.<object>
Source:

Methods

_main()

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
Source:

addEdgeImpl(u_i, v_i)

Add an edge from a vertex pair (original pre Checkpoint 6).
Parameters:
Name Type Description
u_i number Source vertex id
v_i number Target vertex id
Implements:
Deprecated:
Author:
  • Muhammad Al-Hashimi
Source:

addEdgeImpl2(u_i, v_i, weightopt)

Add an edge from a vertex pair and optional weight (from Checkpoint 6).
Parameters:
Name Type Attributes Description
u_i integer Source vertex id
v_i integer Target vertex id
weight number <optional>
 Edge weight/cost
Implements:
Deprecated:
  • Obsolete, use 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.
Author:
  • Muhammad Al-Hashimi
Source:
See:

addEdgeImpl3(u_i, v_i, weightopt)

Add an edge from a vertex pair and an optional weight. A better implementation which relies on a vertex method to handle adjacency details.
Parameters:
Name Type Attributes Description
u_i integer Source vertex id
v_i integer Target vertex id
weight number <optional>
 Edge weight/cost
Implements:
Author:
  • Muhammad Al-Hashimi
Source:
See:

adjacentByIDImpl() → {Array.<integer>}

Get id of adjacent vertices in an array
Implements:
Source:
Returns:
Array containing id of adjacent vertices in edge input order by default
Type ▸ Array.<integer>

better_input(v, e)

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).
Parameters:
Name Type Description
v Array.<object> Vertex input (configuration) objects
Properties
Name Type Description
label string Vertex label
e object Array of edge input (configuration) objects
Properties
Name Type Attributes Description
u integer Source vertex id
v integer Target vertex id
w number <optional>
 Edge weight
Implements:
Author:
  • Muhammad Al-Hashimi
Source:

better_output()

Output graph data
Implements:
Deprecated:
Author:
  • Muhammad Al-Hashimi
Source:
See:

bfsImpl(v_i)

Traverse a connected component breadth-first starting at passed vertex. Inserts visited vertex id in visit order in #bfs_order.
Parameters:
Name Type Description
v_i number Starting vertex id
Implements:
Author:
  • Muhammad Al-Hashimi
Source:

componentInfoImpl() → {string}

Report connectivity information if available
Implements:
Source:
Returns:
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
Type ▸ string

dfsImpl(v_i)

Recursively traverse a connected component depth-first starting at passed vertex. Inserts visited vertex id in visit order in #dfs_push.
Parameters:
Name Type Description
v_i number Starting vertex id
Implements:
Source:

incidentEdgesImpl() → {Array.<enode>}

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 Vertex#adjacentByID.
Implements:
Author:
  • Muhammad Al-Hashimi
  • Sandy Bridge
Source:
Returns:
Array of custom objects containing edge information, in input order by default.
Type ▸ Array.<enode>

insertAdjacentImpl(v_i, weightopt)

Insert a new edge node in the adjacency list of vertex. Currently only updates the internal adjacency list representation.
Parameters:
Name Type Attributes Description
v_i number Edge target vertex id
weight number <optional>
 Edge weight (for weighted graphs), if specified
Implements:
Source:

isConnectedImpl() → {boolean}

Return connected status based on internal connectivity field
Implements:
Source:
Returns:
True if graph is connected
Type ▸ boolean

listVertsImpl()

Output a vertex list using descriptive strings returned by the Vertex object
Implements:
Author:
  • Muhammad Al-Hashimi
Source:
See:

makeAdjMatrixImpl()

Generate adjacency matrix representation of graph - obsolete naïve implementation, see notes below.
Implements:
Deprecated:
  • Use Graph#makeAdjMatrixImpl3 instead. This function doesn't support weighted edges, and is not coded optimally.
Author:
  • Muhammad Al-Hashimi
Source:

makeAdjMatrixImpl2()

Generate adjacency matrix representation of graph - obsolete first weighted implementation, see notes below.
Implements:
Deprecated:
  • Use Graph#makeAdjMatrixImpl3 instead. This version illustrates a point about better object-oriented design consistent with principles of encapsulation and proper hiding of implementation details.
Author:
  • Sandy Bridge
Source:

makeAdjMatrixImpl3()

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.
Implements:
Author:
  • Muhammad Al-Hashimi
Source:

makeGraphImpl(n, m, w)

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?
Parameters:
Name Type Description
n number Number of vertices
m number Number of edges
w boolean Weighted if true
Implements:
Source:

printGraphImpl()

Output graph properties and list its vertices (replaces better_output). This function depends on the vertex lister method of the graph.
Implements:
Author:
  • Muhammad Al-Hashimi
Source:
See:

topoSearchImpl(fun) → {integer}

Implement a versatile caller for search-like topological traversals of vertices (initially support DFS and BFS). Updates and returns the number of connected components Graph#connectedComp. Stores the id of vertices in visit order in Graph#dfs_push or Graph#bfs_order depending on requested search.
Parameters:
Name Type Description
fun Design left for students
Implements:
Author:
  • Muhammad Al-Hashimi
Source:
Returns:
Number of connected components
Type ▸ integer

vertexInfoImpl() → {string}

Get vertex details in a printable string
Implements:
Source:
Returns:
Formatted vertex information
Type ▸ string
Example

Sample output.

   VERTEX: 0 {a} - VISIT: false - ADJACENCY: 3,2,4

Type Definitions

enode

Workaround to document a literal object returned by function
Type ▸ object
Properties:
Name Type Attributes Description
adjVert_i integer id of target vertex
edgeLabel string a text label (not implemented, always "" for now)
edgeWeight number <optional>
 weight/cost, if any
Source:
See: