Building a Social Network Relationship Manager

This challenge focuses on creating a robust system for managing relationships between entities in a Python application. You'll implement a class that can represent individuals and their connections, allowing for various relationship types and efficient querying of these connections. This is a fundamental task in many applications, from social networks and recommendation engines to knowledge graphs and project management tools.

Problem Description

You need to design and implement a Python class called RelationshipManager. This class will be responsible for storing and querying relationships between entities.

Key Requirements:

1. Entity Representation: The RelationshipManager should be able to store distinct entities. For simplicity, let's assume entities are identified by unique string identifiers.
2. Relationship Storage: The manager must store directed relationships between entities. A relationship should consist of a source entity, a target entity, and a type (e.g., "friend", "follows", "colleague", "family").
3. Adding Relationships: Implement a method to add a new relationship. This method should handle cases where entities or relationships might already exist.
4. Querying Relationships: Implement methods to retrieve relationships based on various criteria:
   • Get all relationships originating from a specific entity.
   • Get all relationships pointing to a specific entity.
   • Get all relationships of a specific type.
   • Get all relationships between two specific entities (regardless of direction or type).
   • Get all entities directly connected to a given entity (both as source and target, of any relationship type).
5. Removing Relationships: Implement a method to remove a specific relationship.
6. Entity Existence: The manager should implicitly handle entity creation when relationships are added. There should also be a way to check if an entity exists.

Expected Behavior:

• Adding a duplicate relationship should not cause errors or duplicate entries.
• Querying for non-existent entities or relationship types should return empty results.
• Removing a non-existent relationship should not cause errors.

Edge Cases to Consider:

• Self-referential relationships (an entity relating to itself).
• Multiple relationships between the same two entities with different types.
• Case sensitivity of entity identifiers and relationship types. (Assume case-sensitivity for this challenge).

Examples

Example 1:

manager = RelationshipManager()

# Adding relationships
manager.add_relationship("Alice", "Bob", "friend")
manager.add_relationship("Alice", "Charlie", "follows")
manager.add_relationship("Bob", "Alice", "friend")
manager.add_relationship("Charlie", "Alice", "follows")
manager.add_relationship("Alice", "David", "colleague")
manager.add_relationship("Bob", "Charlie", "friend")

# Querying
print(manager.get_relationships_from("Alice"))
# Expected Output: [('Alice', 'Bob', 'friend'), ('Alice', 'Charlie', 'follows'), ('Alice', 'David', 'colleague')]

print(manager.get_relationships_to("Alice"))
# Expected Output: [('Bob', 'Alice', 'friend'), ('Charlie', 'Alice', 'follows')]

print(manager.get_relationships_by_type("friend"))
# Expected Output: [('Alice', 'Bob', 'friend'), ('Bob', 'Alice', 'friend'), ('Bob', 'Charlie', 'friend')]

print(manager.get_relationships_between("Alice", "Bob"))
# Expected Output: [('Alice', 'Bob', 'friend'), ('Bob', 'Alice', 'friend')]

print(manager.get_all_connected_entities("Alice"))
# Expected Output: ['Bob', 'Charlie', 'David'] (order might vary)

Explanation: Demonstrates basic addition and querying of relationships.

Example 2:

manager = RelationshipManager()
manager.add_relationship("Alice", "Alice", "self-aware")
manager.add_relationship("Alice", "Bob", "friend")
manager.add_relationship("Alice", "Bob", "friend") # Duplicate, should be ignored

print(manager.get_relationships_from("Alice"))
# Expected Output: [('Alice', 'Alice', 'self-aware'), ('Alice', 'Bob', 'friend')]

print(manager.entity_exists("Bob"))
# Expected Output: True

print(manager.entity_exists("Eve"))
# Expected Output: False

Explanation: Shows handling of self-referential relationships and duplicate additions.

Example 3:

manager = RelationshipManager()
manager.add_relationship("Alice", "Bob", "friend")
manager.add_relationship("Alice", "Bob", "acquaintance")

print(manager.get_relationships_between("Alice", "Bob"))
# Expected Output: [('Alice', 'Bob', 'friend'), ('Alice', 'Bob', 'acquaintance')]

manager.remove_relationship("Alice", "Bob", "friend")
print(manager.get_relationships_between("Alice", "Bob"))
# Expected Output: [('Alice', 'Bob', 'acquaintance')]

manager.remove_relationship("Alice", "Bob", "friend") # Non-existent, should do nothing
print(manager.get_relationships_between("Alice", "Bob"))
# Expected Output: [('Alice', 'Bob', 'acquaintance')]

Explanation: Illustrates handling multiple relationship types between the same entities and removing specific relationships.

Constraints

• The number of entities can be up to 10,000.
• The number of relationships can be up to 100,000.
• Entity identifiers and relationship types are strings, with lengths between 1 and 50 characters.
• Methods like get_relationships_from and get_relationships_to should aim for an average time complexity better than O(N), where N is the total number of relationships.
• The get_relationships_between method should also be efficient, ideally not requiring a full scan of all relationships in the worst case.

Notes

• Consider appropriate data structures to store entities and relationships efficiently for the given constraints.
• Think about how to optimize the querying methods.
• The order of results in queries that return multiple relationships is not strictly defined, but it should be consistent for a given set of data and query.
• You are welcome to add helper methods within your RelationshipManager class to improve organization and readability.
• The get_all_connected_entities method should return a list of unique entity identifiers.