Introduction to Graphs: Definition, Applications, and Traversal Methods

Introduction to Graph Data Structures

• Graphs are considered a highly flexible and powerful data structure with extensive real-world applications and interesting algorithms.
• A graph is fundamentally composed of two main components:
  • Nodes: Also known as Vertices.
  • Edges: Also known as Arcs, transitions, lines, or arrows.
• Nodes often represent locations, entities, or states, while edges represent the paths, relationships, or transitions between them.
• Graphs can be viewed as an abstraction of tree data structures:
  • Trees have specific constraints (e.g., a root node, left/right children, no cycles).
  • Graphs remove these constraints, allowing multiple parents, child nodes linking back to each other, and connections that go back up the hierarchy.

Real-World Applications and Use Cases

• Relationship and Social Media Networks:
  • Nodes represent individuals (e.g., characters in Game of Thrones).
  • Edges represent interactions or friendships.
  • Graphs allow for the analysis of social clusters (groups that interact mostly within themselves) and the identification of bridge connections between disparate groups.
• Recommendation Systems:
  • Used to model user preferences. By analyzing what items a person likes and finding connections to other users with similar interests, systems can recommend new items.
• Genealogy and Whakapapa:
  • While family trees are often modeled as tree structures, real-world complexity (adoption, marriage, divorce) requires the flexibility of a graph to model connections that are not strictly parent-to-child.
• Location and Navigation Data:
  • Nodes represent geographical locations.
  • Edges represent road networks, flight paths, or walking trails.
  • Google Maps uses a massive graph to calculate the shortest path between locations.
  • Video Game Pathfinding: Graphs model locations on a map to allow AI characters to navigate around obstacles while seeking the shortest route.
• Network Data and the Internet:
  • The internet can be visualized as a graph where nodes are servers or websites and edges are links or traffic flow.
  • In a 2011 visualization, large nodes represented high-traffic sites like Facebook, google.com, and google.co.uk.
  • Google's PageRank algorithm: Treats websites as nodes and hyperlinks as edges; a website is ranked higher if it has many incoming links (edges) from reputable sources.
  • Peer-to-Peer (P2P) Networks: Computers are nodes, and connections for file sharing are edges. Algorithms find the quickest route or the one with the fewest "hops."
• Knowledge and Semantic Graphs:
  • Nodes represent entities, and edges represent specific semantic relationships (e.g., "$\text{Dogs}$ is $\text{Animals}$", "$\text{Cows}$ eat $\text{Herbs}$").
• Dialogue Systems:
  • Often called "dialogue trees," these are effectively graphs because options can loop back to previous states or multiple parents can converge on a single child node.
• Puzzle Analysis:
  • Sokoban: Nodes represent configurations of blocks and the character's position. Edges represent moves ($\text{up}$, $\text{down}$, $\text{left}$, $\text{right}$). Difficulty is analyzed by looking for narrow corridors in the graph or potential deadlock states.
  • Rush Hour: Nodes represent positions of cars in a grid. Finding the solution involves traversing the graph until a winning state node is reached.

Graph Structure and Formal Representation

• A graph is defined as a set of vertices $(V)$ and a set of edges $(E)$.
• Edges are typically written as tuples or triples:
  • A connection between node $a$ and node $b$ is written as $(a, b)$.
  • In a directed graph, the order matters ($(a, b)$ means $a \rightarrow b$).
  • In a weighted graph, a weight is added to form a triple: $(a, b, w)$.
• Edges can be represented as an Edge Class containing:
  • from node
  • to node
  • weight (e.g., distance, cost, time, or terrain difficulty).

Categories of Graphs

• Directed vs. Undirected:
  • Undirected: Connections are two-way (drawn as simple lines). Example: Two-way streets.
  • Directed: Connections have a specific direction (drawn as arrows). Example: One-way streets, cliffs, or parasocial relationships on social media.
• Weighted vs. Unweighted:
  • Weighted: Edges have values associated with them (e.g., a distance of $2014\,km$ between Los Angeles and Chicago). Weights can represent cost, fuel, time, etc.
  • Unweighted: All edges are considered equal in value.
• Cyclic vs. Acyclic:
  • Cyclic: It is possible to follow edges and return to the starting node (a loop).
  • Acyclic: There are no cycles/loops. This is particularly relevant in directed graphs (Directed Acyclic Graphs or DAGs).
• Sparse vs. Dense:
  • Sparse: Very few edges relative to the number of nodes.
  • Dense: Most nodes are connected to most other nodes.

Graph Operations

• Construction Operations:
  • Add Node: Add a new vertex to the collection.
  • Add Edge: Create a connection between existing nodes.
  • Remove Node: Deleting a node requires also removing any edges associated with it to prevent "floating edges."
  • Remove Edge: Simply delete the transition from the collection.
• Query Operations:
  • Find Node: Check if a specific vertex exists.
  • Find Edge: Check if two specific nodes are connected (e.g., "Are these two people friends?").
  • Find Neighbors: Retrieve all nodes directly connected to a specific node in one step.
• Traversal and Pathfinding:
  • Find Path: Determine if a route exists between two nodes.
  • Shortest Path: Identify the path with the minimum number of edges or the minimum sum of weights (using algorithms like Dijkstra's or A* (A-Star)).

Graph Traversal Techniques

• Depth-First Traversal (DFS):
  • Process: Start at a node, visit an adjacent node, and continue moving as "deep" as possible into the graph before backtracking.
  • Applications: Useful for detecting cycles and checking for path validity between two locations.
• Breadth-First Traversal (BFS):
  • Process: Start at a node (distance $0$) and visit all immediate neighbors (distance $1$), then all neighbors of those nodes (distance $2$), expanding outwards layer by layer.
  • Applications: Finding the shortest path in unweighted graphs (the fewest number of transitions).
• Cycle Handling: Unlike trees, graphs require algorithms to keep track of "visited" nodes to avoid falling into infinite loops caused by cycles.

Questions & Discussion

• Multi-Edge Graphs: It is possible to have multiple edges connecting the same two nodes (e.g., a route between two cities that could be traveled by plane, road, or train, each with different weights).
• Disconnected Nodes: A graph can contain nodes that are not reachable from other parts of the graph. For instance, if a storm closes all flights to New York City, that node remains in the graph but becomes temporarily unreachable.
• Implementation Trade-offs:
  • Graphs can be implemented similarly to linked lists (nodes containing references/pointers to other nodes).
  • Alternatively, they can be implemented using arrays/matrices, which might be more efficient for dense graphs.
• Course Logistics:
  • Assignment 4 involves Priority Queues and simulating plane landings based on fuel levels.
  • The instructor discussed the use of AI tools for generating test cases, noting a split in student preference between AI-assisted and manual test writing.