Example input files : layers(3). width(0,9). in_layer(0,n1). in_layer(0,n2). in_

Question

Example input files :

layers(3).
width(0,9).
in_layer(0,n1).
in_layer(0,n2).
in_layer(0,n3).
in_layer(0,n4).
in_layer(0,n5).
in_layer(0,n6).
in_layer(0,n7).
in_layer(0,n8).
in_layer(0,n9).
width(1,9).
in_layer(1,n10).
in_layer(1,n11).
in_layer(1,n12).
in_layer(1,n13).
in_layer(1,n14).
in_layer(1,n15).
in_layer(1,n16).
in_layer(1,n17).
in_layer(1,n18).
width(2,9).
in_layer(2,n19).
in_layer(2,n20).
in_layer(2,n21).
in_layer(2,n22).
in_layer(2,n23).
in_layer(2,n24).
in_layer(2,n25).
in_layer(2,n26).
in_layer(2,n27).
edge(n5,n16).
edge(n17,n25).
edge(n15,n20).
edge(n15,n23).
edge(n10,n26).
edge(n15,n21).
edge(n15,n19).
edge(n17,n24).
edge(n4,n10).
edge(n6,n17).
edge(n1,n14).
edge(n12,n21).
edge(n14,n21).
edge(n1,n13).
edge(n3,n18).
edge(n16,n26).
edge(n1,n18).
edge(n1,n11).
edge(n11,n25).
edge(n10,n25).
edge(n1,n10).
edge(n8,n16).
edge(n13,n23).
edge(n10,n23).
edge(n5,n12).
edge(n1,n15).
edge(n11,n20).
edge(n6,n11).
edge(n8,n17).
edge(n11,n19).
edge(n14,n27).
edge(n2,n16).

layers(3).
width(0,9).
in_layer(0,n1).
in_layer(0,n2).
in_layer(0,n3).
in_layer(0,n4).
in_layer(0,n5).
in_layer(0,n6).
in_layer(0,n7).
in_layer(0,n8).
in_layer(0,n9).
width(1,9).
in_layer(1,n10).
in_layer(1,n11).
in_layer(1,n12).
in_layer(1,n13).
in_layer(1,n14).
in_layer(1,n15).
in_layer(1,n16).
in_layer(1,n17).
in_layer(1,n18).
width(2,9).
in_layer(2,n19).
in_layer(2,n20).
in_layer(2,n21).
in_layer(2,n22).
in_layer(2,n23).
in_layer(2,n24).
in_layer(2,n25).
in_layer(2,n26).
in_layer(2,n27).
edge(n16,n26).
edge(n2,n18).
edge(n15,n22).
edge(n11,n27).
edge(n8,n16).
edge(n14,n19).
edge(n18,n24).
edge(n7,n12).
edge(n6,n11).
edge(n1,n15).
edge(n11,n21).
edge(n12,n23).
edge(n2,n15).
edge(n7,n15).
edge(n6,n12).
edge(n12,n26).
edge(n11,n22).
edge(n3,n13).
edge(n13,n21).
edge(n2,n13).
edge(n5,n14).
edge(n1,n16).
edge(n4,n17).
edge(n18,n22).
edge(n4,n15).
edge(n2,n14).
edge(n17,n23).
edge(n16,n23).
edge(n17,n21).
edge(n13,n26).
edge(n16,n25).
edge(n13,n23).

A standard approach for creating meaningful layered graphics is to apply k-level crossing minimization. The problem is defined as follows the nodes in the graph are assigned levels producing a k-level graph (nodes from layer n have edges only to nodes in layer n+1), nodes are assigned an order so as to minimize edge crossings. You will implement the k-level crossing minimization in python that takes a file as program argument and prints the minimum number of edge crossings in the console output. For example: python cross.py test2.txt will print 15 The input file contains lines with the relations: layers/1, wi in layer/2, edge/2. For example: idth/2, layers(2) width(0, 2). in layer(0,n1) in layer(0,n2) width(1, 2). in layer (1n3). in layer (1,n4). edge(n1, n4). edge(n2,n3) edge(n2,n4) The output for this example should be 0 because the first level can be ordered n2,n1, while the second level can be ordered n3,n4, in which case there are no crossings.

Explanation / Answer

main.py

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.