Types of Graphs: Exploring Graph Classifications in JavaScript

8.1.2 Types of Graphs

Graphs are fundamental structures in computer science, used to model pairwise relations between objects. Understanding the different types of graphs is crucial for selecting the right graph structure for a given problem. In this section, we will explore various classifications of graphs, their characteristics, and practical applications. We will also provide JavaScript code examples to illustrate how these graphs can be implemented.

Simple Graphs

A simple graph is an undirected graph that does not contain any loops (edges connected at both ends to the same vertex) or multiple edges between the same pair of vertices. Simple graphs are the most basic form of graphs and are often used in theoretical studies.

Characteristics:

• No loops or multiple edges.
• Undirected edges.

Example:

Consider a graph representing a social network where each node is a person and each edge is a friendship. In a simple graph, each friendship is represented only once.

         graph TD
	        
	         
	         Alice[👩‍💼 Alice] -- "Friends with" --> Bob[👨‍💼 Bob]
	         Bob -- "Friends with" --> Carol[👩‍🎤 Carol]
	         Carol -- "Friends with" --> David[👨‍🔧 David]
	         David -- "Friends with" --> Alice
	         Alice -- "Friends with" --> Carol
	         
	         class Alice,Bob,Carol,David person;

Weighted Graphs

In a weighted graph, each edge has an associated weight or cost. These weights can represent various metrics such as distance, cost, or capacity. Weighted graphs are widely used in scenarios where the cost of traversing an edge is significant.

Characteristics:

• Edges have weights.
• Can be directed or undirected.

Example:

A map where cities are nodes and roads are edges with distances as weights.

    flowchart TD
	
	    %% Nodes with Descriptive Labels
	    NewYork["🗽 New York"]
	    Boston["🐟 Boston"]
	    Chicago["🌆 Chicago"]
	    Denver["⛰️ Denver"]
	
	    %% Edges with Distance Weights
	    NewYork -->|5 miles| Boston
	    Boston -->|3 miles| Chicago
	    Chicago --> |4 miles| Denver
	    Denver -->|2 miles| NewYork
	    NewYork -->|7 miles| Chicago

JavaScript Implementation:

class WeightedGraph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    addEdge(vertex1, vertex2, weight) {
        this.adjacencyList[vertex1].push({ node: vertex2, weight });
        this.adjacencyList[vertex2].push({ node: vertex1, weight });
    }
}

const graph = new WeightedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B', 5);

Unweighted Graphs

An unweighted graph is a graph where all edges are considered equal, meaning they do not have weights. These graphs are useful when the relationship between nodes is binary (exists or not) without any additional cost or distance.

Characteristics:

• Edges have no weights.
• Can be directed or undirected.

Example:

A network of computers where each connection is equally significant.

    graph TD
	    %% Styling Nodes and Edges
	    classDef computer fill:#bbf,stroke:#333,stroke-width:2px;
	
	    %% Nodes Representing Computers
	    compA[💻 Computer A]
	    compB[💻 Computer B]
	    compC[💻 Computer C]
	    compD[💻 Computer D]
	
	    %% Edges Representing Connections
	    compA -- Connection --- compB
	    compB -- Connection --- compC
	    compC -- Connection --- compD
	    compD -- Connection --- compA
	    compA -- Connection --- compC
	
	    %% Apply Classes to Nodes
	    class compA,compB,compC,compD computer

Directed Graphs (Digraphs)

A directed graph or digraph is a graph where edges have a direction, indicating a one-way relationship. Directed graphs are essential for modeling scenarios where relationships are not mutual.

Characteristics:

• Edges have directions.
• Can be weighted or unweighted.

Example:

A website’s hyperlink structure where each page links to another.

    graph TD;
	    A --> B;
	    B --> C;
	    C --> D;
	    D --> A;
	    A --> C;

JavaScript Implementation:

class DirectedGraph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
    }
}

const digraph = new DirectedGraph();
digraph.addVertex('A');
digraph.addVertex('B');
digraph.addEdge('A', 'B');

Undirected Graphs

An undirected graph is a graph where edges have no direction, indicating a mutual relationship between nodes. These graphs are suitable for modeling scenarios where relationships are bidirectional.

Characteristics:

• Edges have no direction.
• Can be weighted or unweighted.

Example:

A friendship network where each friendship is mutual.

    graph TD
	    %% Nodes Representing People
	    Alice["👩 Alice"]
	    Bob["👨 Bob"]
	    Carol["👩 Carol"]
	    David["👨 David"]
	
	    %% Bidirectional Edges Representing Mutual Friendships
	    Alice <--> Bob
	    Bob <--> Carol
	    Carol <--> David
	    David <--> Alice
	    Alice <--> Carol
	
	    %% Optional: Apply Styling to Nodes (classDef not utilized as specific styling is not mandatory here)
	    classDef person fill:#e0f7fa,stroke:#333,stroke-width:2px
	    class Alice,Bob,Carol,David person

Cyclic Graphs

A cyclic graph contains at least one cycle, which is a path that starts and ends at the same vertex without repeating any edges or vertices. Cyclic graphs are common in network topology and circuit design.

Characteristics:

• Contains cycles.
• Can be directed or undirected.

Example:

A network with redundant paths to ensure connectivity.

    graph TD
	    %% Nodes Representing Network Points
	    NodeA[Node A]
	    NodeB[Node B]
	    NodeC[Node C]
	    NodeD[Node D]
	
	    %% Edges Representing Redundant Pathways
	    NodeA --> NodeB
	    NodeB --> NodeC
	    NodeC --> NodeA
	    NodeC --> NodeD
	    NodeA -.-> NodeD
	    NodeB -.-> NodeD
	    NodeB -.-> NodeA

• The diagram includes directed edges and dotted edges to illustrate redundant paths, enhancing the visual representation of backup pathways.
• Redundancies ensure that if a primary path fails, alternative routes maintain network connectivity.

Acyclic Graphs

An acyclic graph is a graph that contains no cycles. In directed graphs, these are known as Directed Acyclic Graphs (DAGs) and are often used in scheduling and dependency resolution.

Characteristics:

• No cycles.
• Can be directed or undirected.

Example:

A project task dependency graph where tasks must be completed in a specific order.

    graph TD
	    %% Task Nodes
	    Start["🏁 Start"]
	    TaskA["🔨 Task A: Initial Setup"]
	    TaskB["📋 Task B: Data Collection"]
	    TaskC["🛠️ Task C: Data Processing"]
	    TaskD["✅ Task D: Final Review"]
	    End["🏆 End"]
	
	    %% Task Dependencies
	    Start --> TaskA
	    TaskA --> TaskB
	    TaskB --> TaskC
	    TaskC --> TaskD
	    TaskD --> End

Connected Graphs

A connected graph is an undirected graph where there is a path between every pair of vertices. Connected graphs are crucial for ensuring that all nodes in a network can communicate with each other.

Characteristics:

• All vertices are connected.
• Only applicable to undirected graphs.

Example:

A fully connected network where each computer can reach any other.

    graph TD
	    %% Nodes Representing Computers
	    compA[💻 Computer A]
	    compB[💻 Computer B]
	    compC[💻 Computer C]
	    compD[💻 Computer D]
	
	    %% Fully Connected Network Edges
	    compA --> compB
	    compA --> compC
	    compA --> compD
	    compB --> compC
	    compB --> compD
	    compC --> compD

Disconnected Graphs

A disconnected graph contains at least one pair of vertices without a path connecting them. These graphs are useful for modeling isolated clusters within a network.

Characteristics:

• Contains isolated vertices or clusters.
• Only applicable to undirected graphs.

Example:

A network with multiple isolated subnetworks.

    graph TD
	    %% Cluster 1
	    A["Node A"]
	    B["Node B"]
	
	    %% Cluster 2
	    C["Node C"]
	    D["Node D"]
	
	    %% Connections within Clusters
	    A --- B
	    C --- D
	
	    %% Styling for Clarity
	    classDef cluster fill:#f0f0f0,stroke:#333,stroke-width:2px,fill-opacity:0.5;
	    class A,B,C,D cluster;

Bipartite Graphs

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to another. Bipartite graphs are used in matching problems and network flow algorithms.

Characteristics:

• Vertices divided into two sets.
• No edges within the same set.

Example:

A job assignment scenario where jobs and applicants are two sets.

    graph TD
	    %% Define Subgraphs with Distinct Sets
	    subgraph Jobs
	        direction TB
	        JobA["Job A"]
	        JobB["Job B"]
	    end
	    
	    subgraph Applicants
	        direction TB
	        ApplicantC["Applicant C"]
	        ApplicantD["Applicant D"]
	    end
	    
	    %% Edges Representing Possible Assignments
	    JobA -- "applies to" --> ApplicantC
	    JobB -- "applies to" --> ApplicantD
	    JobA -- "applies to" --> ApplicantD
	    
	    %% Optional Styling for Clarity
	    classDef jobStyle fill:#f0e68c,stroke:#333,stroke-width:2px;
	    classDef applicantStyle fill:#add8e6,stroke:#333,stroke-width:2px;
	    class JobA,JobB jobStyle;
	    class ApplicantC,ApplicantD applicantStyle;

JavaScript Implementation:

class BipartiteGraph {
    constructor() {
        this.set1 = new Set();
        this.set2 = new Set();
        this.edges = [];
    }

    addVertexToSet1(vertex) {
        this.set1.add(vertex);
    }

    addVertexToSet2(vertex) {
        this.set2.add(vertex);
    }

    addEdge(vertex1, vertex2) {
        if (this.set1.has(vertex1) && this.set2.has(vertex2)) {
            this.edges.push([vertex1, vertex2]);
        }
    }
}

const bipartiteGraph = new BipartiteGraph();
bipartiteGraph.addVertexToSet1('Job1');
bipartiteGraph.addVertexToSet2('Applicant1');
bipartiteGraph.addEdge('Job1', 'Applicant1');

Complete Graphs

A complete graph is a graph where every pair of distinct vertices is connected by a unique edge. Complete graphs are used in scenarios where every node needs to be directly connected to every other node.

Characteristics:

• Every pair of vertices is connected.
• Can be directed or undirected.

Example:

A fully connected mesh network.

    graph TD
	    %% Nodes Representing Network Points
	    nodeA["Node A"]
	    nodeB["Node B"]
	    nodeC["Node C"]
	    nodeD["Node D"]
	
	    %% Complete Graph: Every Node Connects to Every Other Node
	    nodeA --- nodeB
	    nodeA --- nodeC
	    nodeA ---> nodeD
	    nodeB --- nodeC
	    nodeB --- nodeD
	    nodeC --- nodeD

Real-World Applications

Graphs are versatile structures with numerous real-world applications:

• Social Networks: Graphs model relationships between users, where nodes represent users and edges represent friendships or interactions.
• Transportation Networks: Airports connected by flights can be modeled as weighted graphs, with weights representing distances or costs.
• Scheduling: Tasks and their dependencies can be represented in acyclic graphs, ensuring tasks are completed in the correct order.
• Biological Networks: Graphs model interactions between proteins or genes in biological systems.
• Web Page Ranking: The structure of the web can be represented as a directed graph, with pages as nodes and hyperlinks as directed edges.

Experimenting with Graphs

To gain a deeper understanding of graphs, experiment by modifying existing graphs and observing how their classification changes. For instance, add or remove edges to see how a graph transitions from connected to disconnected, or introduce weights to transform an unweighted graph into a weighted one.

Conclusion

Understanding the various types of graphs and their characteristics is essential for effectively modeling complex relationships and solving problems in computer science. By leveraging JavaScript to implement these graphs, you can experiment with different structures and gain practical insights into their applications.

Quiz Time!