1

When using mindmaps, you order them based on how you think it fits best.

So for instance (tab means subtree)

requirements
  dinner
    food
    forks
    spoons
  breakfast
    food
    forks

this could be written using

food
  at
    dinner
    breakfast
forks
  at
    dinner
    breakfast
spoons
  at
    dinner

What would an algorithm look like that finds the best sorting in the manner described. Best means, the least amount of redundancy?

(The 2nd example might not actually reduce redundancy but it shows what is meant by sorting/reordering)

1 Answer 1

2

Your algorithm could resemble graph theory. I understand the hierarchical lists above are shown for simplicity. Given your requirements, the limits of a hierarchical structure are revealed!

The nodes need to be managed before they can be processed. My approach to this problem, not having a background in graph structures, would be to review the material on graph structures first, for example this this and this and get my data encoded using them. Once that's done then process and analyze the structures, for example, create a hash counting the parents, sort the list by the count and generate a new hierarchical representation without changing the underlying graph.

for example, borrowing from the code in the first link, in python3

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connected_to = {}

    def add_neighbor(self, nbr, weight=0):
        self.connected_to[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connected_to: ' + str([x.id for x in self.connected_to])

    def get_connections(self):
        return self.connected_to.keys()

    def get_id(self): return self.id

    def get_weight(self, nbr): return self.connected_to[nbr]


class Graph:
    def __init__(self):
        self.vert_list = {}
        self.num_vertices = 0

    def add_vertex(self, key):
        self.num_vertices += 1
        new_vertex = Vertex(key)
        self.vert_list[key] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vert_list:
            return self.vert_list[n]
        else:
            return None

    def __contains__(self, n): return n in self.vert_list

    def add_edge(self, f, t, cost=0):
        if f not in self.vert_list:
            self.add_vertex(f)
        if t not in self.vert_list:
            self.add_vertex(t)
        self.vert_list[f].add_neighbor(self.vert_list[t], cost)

    def get_vertices(self): return self.vert_list.keys()

    def __iter__(self): return iter(self.vert_list.values())


# the main graph
g = Graph()

# populate the main graph
g.add_vertex('dinner')
g.add_edge('dinner', 'food')
g.add_edge('dinner', 'fork')
g.add_edge('dinner', 'spoon')
g.add_vertex('breakfast')
g.add_edge('breakfast', 'food')
g.add_edge('breakfast', 'fork')

print("\nThe main graph is:")
for v in g:
    for c in v.get_connections():
        print("( %s , %s )" % (v.get_id(), c.get_id()))

# flip the graph by populating a new one with the main's children
flipped_g = Graph()
for v in g:
    for c in v.get_connections():
        flipped_g.add_edge(c.get_id(), v.get_id())

print("\nThe main graph inverted is:")
for v in flipped_g:
    for c in v.get_connections():
        print("( %s , %s )" % (v.get_id(), c.get_id()))

produces the following output:

The main graph is:
( breakfast , food )
( breakfast , fork )
( dinner , food )
( dinner , fork )
( dinner , spoon )

The main graph inverted is:
( food , breakfast )
( food , dinner )
( spoon , dinner )
( fork , breakfast )
( fork , dinner )

This is certainly not a complete solution but it is a framework you can use to get the information you need.

Bear in mind that the add_vertex() method checks the list of connections and only adds a node if it isn't already there. For example, there is only one dinner node and only one fork node.

Here are all the vertices as retrieved with: flipped_g.get_vertices()

dict_keys(['food', 'spoon', 'fork', 'dinner', 'breakfast'])
4
  • The algorithm described in the OP seems relatively straightforward. Do you have an example? Commented Jan 15, 2014 at 18:13
  • @Robert Thanks for the prompt, edited in an example Commented Jan 15, 2014 at 21:22
  • Your solution simply creates a programming backbone for my examples but I cannot see optimization(if possible only one item with the same name resp. as little repetition as possible) going on. Or is there? Also please keep in mind that complexity can increase. Please note that my second example is not the best solution, I just chose it to show what I understand by reordering.
    – Gewinn
    Commented Jan 16, 2014 at 0:06
  • Optimization seems a subjective term -- especially when it comes to mind maps. For example, i personally don't want a fork for breakfast, i'd rather have two spoons. Others may differ. The data for the structures above actually IS optimized by your definition. I've edited it into the answer. Commented Jan 16, 2014 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.