Transaction Network Queries

You are tasked with building a small, in-memory library to manage and query a network of customer transactions. Each transaction involves exactly two customers, establishing an undirected connection between them. Once two customers transact, they are considered directly connected. The library should support adding transactions over time and answering connectivity queries at any point. Customer identifiers can be assumed to be strings.

Part 1: Direct/Indirect Existence Query

Implement a method to record a transaction between two customers, and a query method:

• haveEverTransactedTogether(customerA, customerB) -> bool

This method should return true if and only if customerA and customerB have ever been part of the same connected component in the transaction graph, based on all transactions recorded up to the time of the query.

Example

1. haveEverTransactedTogether("Jim", "Pam") returns false.
2. Record transaction: Jim transacts with Pam.
3. haveEverTransactedTogether("Jim", "Pam") returns true.
4. Record transaction: Pam transacts with Michael.
5. haveEverTransactedTogether("Michael", "Jim") returns true (because Michael, Pam, and Jim now form a single connected component).

Part 2: Full Network Query

Implement the following method:

• findNetwork(person) -> list/set

This method should return all customers reachable from person via one or more transactions (i.e., all other nodes in the same connected component as person), excluding person itself.

Example 1 (Two disconnected components)

Given transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork("a") returns {b,c,d,e}
• findNetwork("g") returns {f}

Example 2 (Loop)

Given transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork("a") returns {b,c,d}

Part 3: Network Query with Degree Limit

Extend the findNetwork method to accept a second parameter n:

• findNetwork(person, n) -> list/set

This method should return all customers within at most n degrees of separation from person, excluding person itself.

• Degree 1: Direct transaction partners.
• Degree 2: Partners of partners, and so on.

Example 1

Given transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork("a", 1) returns {b,d}
• findNetwork("g", 1) returns {f}

Example 2 (Loop)

Given transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork("a", 1) returns {b,c}

Example 3

Given transactions: (a,b), (b,c), (c,d), (b,e), (c,f), (d,g), (f,g), (g,h)

• findNetwork("d", 2) returns {c,g,b,f,h}
• findNetwork("h", 3) returns {g,d,f,c}
• findNetwork("a", 1) returns {b}

Expectations

• Clearly define any helper methods and choose appropriate data structures.
• Be careful about cycles and repeated visits when exploring the network.