To solve this problem it is important to consider how you want to represent the Graph. In your sketch you have assigned a weight both to nodes and to edges, but it seems that the edge weight is irrelevant. A good representation might be a pair of the weight and an array of neighbours:
Node(weight: Int, name: String, neighbours: Set of Node)
During the building of the initial undirected graph, you maintain a dictionary of nodes by their name.
For each path in the input, you look up or create all nodes in the dictionary. You then increment the weight of all nodes, and connect the nodes on each pair of the graph to each other:
var nodes = path.split("-").map(s => dict.lookupOrCreate(s));
// increment the weight
for var node <- nodes { node.weight++ }
// add the connections
for var i <- (1 upto nodes.length) {
nodes[i ].neighbours.add(nodes[i-1]);
nodes[i-1].neighbours.add(nodes[i ]):
}
We now have an undirected, unconnected graph with weighted nodes:
2 6 3 1 2 1
b ↔ a ↔ c ↔ e d ↔ f
↖_____↗
It is now that you will want to remove cycles. Your example contains the subgraph
e 1 I. a6 → e1 → c3 ↗ e1
/ \ ==> a6 III.
a 6 | II. a6 → c3 → e1 ↘ c3
`- c 3
As you can see, there are three possibilites to eliminate this cycle while starting from a. The 3rd possibility is the easiest to implement.
If you want one of the other orders, you'll have to do more expensive reachability tests: For each two child nodes, skip (but not mark as seen) one of those child nodes if it is reachable by the other without using a path that uses the current node.
Next, we want to get the node with the highest weight. This is a simple sort.
var [..., highest] = dict.values.sortBy(n => n.weight);
Now, we traverse the whole graph starting from that node and build the DAG. We can either build a completely new graph (preferable) or remove the current node from the neighbour set. If this set then contains any nodes that were already visited during DAG buidling, a cycle was detected (which we break by skipping that node). Subgraphs that are not reachable will be forgotten, this would eliminate the d-e part. We can work around of this by deleting any nodes from the dictionary, and creating DAGs until the dict is empty. This would create a forest.
var forest = collect until dict.isEmpty {
var [..., highest] = dict.values.sortBy(n => n.weight);
def recurse(node: Node): DagNode {
// remove current node from dict
dict.delete(node.name);
// remove seen childs – eliminates cycles
var childs = node.neighbours.filter(c => dict.contains(c.name));
// mark all new childs as seen
for var child <- childs { dict.delete(child.name) }
// return the DAG subgraph (here: tree) and recurse into each child
return DagNode(weight: node.weight,
name: node.name,
childs: childs.map(c => recurse(c)));
}
yield recurse(highest);
}
This should create the forest
_a_ d
/ | \ |
b c e f
a, dor “contains no cycles” →trueor “longest path in the graph” →e, c, a? – amon Oct 8 '13 at 23:01d-fambiguity when making it directed? In which direction does the edge go? Otherwise, for each connected subgraph, you can choose the node with the highest weight and build the DAG so that all edges point there, producing a tree. You could also orient all edges so that they point to the node with higher weight, but that won't always produce a tree. When considering these decision, assume the additional rulesg,e,g. – amon Oct 9 '13 at 7:46