Is there a Method of Constructing a non intersecting Tree structure from a list of chains / adjacency matrix?

[Al-Layth]

the problem i am dealing with is this:

to illustrate: suppose nodes have connections described as this:

(chain1) A < B < C < D
(chain2) C < E < D < F
(chain3) E < F < D.....

and I would like to create a 'tree network' involving all these elements such that
(1) No 'node' is mentioned twice
(2) No 'arcs' (connections) intersect.

(3) [not a condition, just to explain] each node can accept as many arcs as needed.

in very large list of 'chains' it becomes too hard and time consuming to by heuristic thinking.

And i thought of using a simple adjacency matrix and inputting it into a simple graph constructor the problem with that is it even if the arcs are 'directed' its still very messy because the nodes are placed in a way that makes it hard to see the "flow" from the source node which is kind of the point of this project and i think a tree would be perfect for that, because distance from the source node on the tree itself roughly corresponds with the number of connections between them.

any help is much appreciated


t

 

[blamocur]

I'd start by getting a clearer sense what exactly you need to achieve. It sounds like you need to build a graph in which your "chains" can be represented by a sequence of edges. But when you have both "C < E < D" and "C < D" do you want to have 2 or 3 edges in your graph ?
I.e. just "C-D" and "E-D", or do you want to have the "C-D" edge as well. In the latter case you'll no longer have a tree, but only an acyclic graph.

And i thought of using a simple adjacency matrix and inputting it into a simple graph constructor the problem with that is it even if the arcs are 'directed' its still very messy...

Then which data structure do you want to use to represent you graph (or your tree) ?

 

[umbertonap]

it seems like you are trying to create a tree network that represents connections between nodes while satisfying certain conditions. Specifically, you want to ensure that no node is mentioned twice, no arcs intersect, and you prefer a structure that allows you to observe the "flow" from the source node.
One possible approach to tackle this problem is by utilizing graph algorithms. Instead of constructing a general graph, you can consider using a specific algorithm such as a Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the connections and build the tree structure.
Here's an idea of how you could approach this:

1. Start with the source node as the root of the tree.
2. Initialize an empty tree data structure.
3. Begin traversing the connections using DFS or BFS from the source node.
4. As you traverse the connections, create child nodes for each encountered node, and connect them to their respective parent nodes in the tree.
5. Ensure that each node is visited only once during the traversal, and track the connections to avoid intersecting arcs.
6. Continue the traversal until all nodes in the chains have been visited and incorporated into the tree structure.
7. At the end, you should have a tree representation that satisfies the conditions you mentioned.

By using a tree structure, you can easily observe the flow from the source node, as the distance between nodes in the tree roughly corresponds to the number of connections between them.
Keep in mind that implementing this approach may require adapting existing graph algorithms or developing custom algorithms based on the specific constraints and requirements of your problem.