I am trying to determine the best time efficient algorithm to accomplish the task described below.
I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another. This basically represents an undirected graph, with the records being the vertices and the connection data the edges.
All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).
I want to choose any two records from the set and be able to show all simple paths between the chosen records. By “simple paths” I mean the paths which do not have repeated recordsin the path (i.e. finite paths only).
Note: The two chosen records will always be different (i.e. start and end vertex will never be the same; no cycles).
If I have the following records:
A, B, C, D, E
and the following represents the connections:
[where (A,B) means record A connects to record B]
If I chose B as my starting record and E as my ending record, I would want to find all simple paths through the record connections that would connect record B to record E.
All paths connecting B to E:
This is an example, in practice I may have sets containing hundreds of thousands of records.
More Related Questions
- Finding all cycles in graph How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?
For example, I want something like this:
- Best Graph Drawing Algorithm For Hierarchical Data? I have a collection of directed acyclic graphs that are nearly trees, in the following sense: each graph has a root, and the vertices are organized into levels such that if v1 and v2 are […]
- Algorithm to match preferred partners into groups of three What's a good algorithm to solve this problem?
I have three groups of people - group A, group B, and group C. There are the same number of people in each group. They each have a list of […]
- Is there a repository of test input, with answers, for algorithms (especially graph algorithms)? As a summer project, I have decided to practice basic algorithms and learn Haskell at the same time, by implementing large chunks of CLRS in Haskell.
Things are going pretty swimmingly, […]
- Has anyone actually implemented a Fibonacci-Heap efficiently? Has anyone of you ever implemented a Fibonacci-Heap? I did so a few years back, but it was several orders of magnitude slower than using array-based BinHeaps.
Back then, I thought of it […]
- Worker Scheduling Algorithm The Problem
Here's the essence of the problem I want to solve. We have workers taking care of children in a nursery for set times during the weekend. There's 16 different slots to fill in […]
- Family Tree Algorithm I'm working on putting together a problem set for an intro-level CS course and came up with a question that, on the surface, seems very simple:
You are given a list of people with the […]
- Algorithm to minimize vertex distances – Dwarf Fortress I play Dwarf Fortress game. And the main challenge for me is to design layout of the fortress efficiently. Meaning, that each industry flow should be as dense as possible, to minimize the […]
- How to pair socks from a pile efficiently? Yesterday I was pairing the socks from the clean laundry, and figured out the way I was doing it is not very efficient. I was doing a naive search — picking one sock and "iterating" […]
- Any Open Source Pregel like framework for distributed processing of large Graphs? Google has described a novel framework for distributed processing on Massive Graphs.
I wanted to know if similar to Hadoop […]