Brits Wearing Red Flower In November

Topology Management

Algorithm:

The topological management is a system of law of a graph acyclic, ie has no cycles, which consists in organizing linearly or in list or ascending descending , a set of vertices in disorder, for which you must first start a "vertex father bone, a vertex without predecessors and after visiting their neighbors, after you have visited their cough overlooked, will now examine another vertex , and similarly identify all its neighbors, and so recursively until it has visited all vertices . Briefly not visit a vertex until all its predecessors have been visited.

After already visited all vertices the directed graph, are arranged in a list d either ascending or descending , as required, and settle on the basis time cost of vertices .

Example: This is a common example applied to everyday life as simple as dressing.

• Above each vertex shows the cost of time.
• Distance / Completion

• The algorithm us back a linked list with nodes in the graph, in descending order time finalization.

• Once ordered and topologically can see precedence of the tasks:

1. Get the shirt before the belt and jersey.
2. Get the pants before shoes and belt .
3. Put on socks before shoes.

Pseudocode:

1. For each vertex "or" that the graph belongs to:
2. The state "or" not visited, that algorithm is started .
3. The parent should be null, because it has no predecessors.
4. The time starts from 0, obviously that starts the algorithm.
5. Then, if the state = not visited then: It starts the topological management.
6. Visited The state will change to that and was visited and analyzed their s predecessors.
7. So we add a 1 at the time because it is so slow at the apex .
8. Then for each vertex adjacent do:
9. If Status = Not visited then:
10. 's father will now be the vertex , as is next in order.
11. When the state of vertex = Completed:
12. times are added together and this would be the total cost for the system.
13. result is inserted in the list sorting algorithm topological .

Asymptotic Analysis :

The analysis asymptotic algorithm of of topological management is costly to pursue vertex without predecessors, several times.

The solution would pre-calculate how many predecessors of each vertex , store data in a vector update whenever adding a new vertex to solution.

Time Cost:

• Initialization:

First loop: O (n) --- means that will depend on the number of vertices that has the graph.

Second loop: Examination of all edges.

O (a + n) --- For adjacency lists.

O (n ^ 2) --- For adjacency matrix.

• Main Loop:

O (a + n) --- For adjacency lists.

O (n ^ 2) --- For adjacency matrix.

Data Structures:

• linked list: For this algorithm topological management, linked lists are used as the management already completed is a simple linear list of edges connecting the same way it had before.
• Isomorphism: Something has to do with ismorfismo , but are not related and is acyclic graph algorithm allows align vertices, while keeping the links between each of the vertices , ie accommodates only priority, but retains its structure .
• Trees: can also be said that this related to trees as these contain nodes also called vertices, and the trees come in different forms of organization.
• depth Search (DFS ): The topological management needs search algorithm DFS because you need to apply to go exploring nodes, and finally reach a linear order .
  

Applications:

• can be applicable to the reprecentacion phase of a project, where vertices represent tasks and edges relations time to them.
• Evaluation phase a semantic compiler.
• In everyday life it could implement simple things such as organizing utility bills to pay, because these days come in different , and differ in price and maturity, and to apply this algorithm, could sort in order of priority due to paying cash them in order, but we spend and spend no money to pay.
• We also would serve to find any cycle in a graph and identify it.
• also to find a problem or defect in a topological order algorithm.
  

Self

Personally this project and the other four I have been very helpful since the majority of topics covered were new to me, and I realized that are of great usefully applied to everyday life in relation to the management of topological, since I left as teaching to cases in which I can apply this algorithm. learned that a particular task is a (s) by seniority and other (s) as a result of this task, and that ultimately after are linked to one another. In conclusion from now on things that have to do that you can implement this algorithm, I facilitate the task, and therefore time and effort.

any doubt or question you have to leave your comment and I will answer the earliest possible time.