in graphLayout/jetbrains.mps.graphLayout.orthogonalLayout/source_gen/jetbrains/mps/graphLayout/flowOrthogonalLayout/QuasiOrthogonalRepresentation.java [287:506]
public static void getRepresentation(EmbeddedGraph embeddedGraph, Map<Dart, Integer> bends, Map<Dart, Integer> angles, Set<Edge> straightEdges) {
Graph graph = embeddedGraph.getGraph();
int c = 100 * graph.getNumNodes();
Graph network = new Graph();
Node networkSource = network.createNode();
Node networkTarget = network.createNode();
Map<Edge, Integer> capacity = MapSequence.fromMap(new HashMap<Edge, Integer>());
Map<Edge, Integer> cost = MapSequence.fromMap(new HashMap<Edge, Integer>());
Map<Node, Node> nodeMap = MapSequence.fromMap(new HashMap<Node, Node>());
for (Node node : ListSequence.fromList(graph.getNodes())) {
Node networkNode = network.createNode();
MapSequence.fromMap(nodeMap).put(node, networkNode);
int deg = ListSequence.fromList(node.getEdges()).count();
Edge edge = null;
if (deg < 4) {
edge = network.connect(networkSource, networkNode);
}
if (deg > 4) {
edge = network.connect(networkNode, networkTarget);
}
if (edge != null) {
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, Math.abs(deg - 4));
}
}
Map<Face, Node> faceMap = MapSequence.fromMap(new HashMap<Face, Node>());
for (Face face : ListSequence.fromList(embeddedGraph.getFaces())) {
Node networkNode = network.createNode();
MapSequence.fromMap(faceMap).put(face, networkNode);
int deg = ListSequence.fromList(face.getDarts()).count();
if (embeddedGraph.isOuterFace(face)) {
Edge edge = network.connect(networkNode, networkTarget);
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, deg + 4);
} else {
Edge edge = null;
if (deg < 4) {
edge = network.connect(networkSource, networkNode);
}
if (deg > 4) {
edge = network.connect(networkNode, networkTarget);
}
if (edge != null) {
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, Math.abs(deg - 4));
}
}
}
Map<Dart, Edge> dartBendMap = MapSequence.fromMap(new HashMap<Dart, Edge>());
Map<Dart, Edge> dartAngleMap = MapSequence.fromMap(new HashMap<Dart, Edge>());
for (Face face : ListSequence.fromList(embeddedGraph.getFaces())) {
Node faceNode = MapSequence.fromMap(faceMap).get(face);
for (Dart dart : ListSequence.fromList(face.getDarts())) {
Edge edge;
edge = network.connect(MapSequence.fromMap(nodeMap).get(dart.getSource()), faceNode);
MapSequence.fromMap(dartAngleMap).put(dart, edge);
MapSequence.fromMap(capacity).put(edge, INF);
MapSequence.fromMap(cost).put(edge, 0);
Dart oppositeDart = embeddedGraph.getOpposite(dart);
Node oppositeFaceNode = MapSequence.fromMap(faceMap).get(embeddedGraph.getFace(oppositeDart));
edge = network.connect(faceNode, oppositeFaceNode);
MapSequence.fromMap(dartBendMap).put(dart, edge);
if (SetSequence.fromSet(straightEdges).contains(edge)) {
MapSequence.fromMap(capacity).put(edge, 0);
} else {
MapSequence.fromMap(capacity).put(edge, INF);
}
MapSequence.fromMap(cost).put(edge, 1);
}
}
Map<Node, Map<Face, Edge>> faceToNodeEdges = MapSequence.fromMap(new HashMap<Node, Map<Face, Edge>>());
Map<Edge, Dart> tempEdgesToDart = MapSequence.fromMap(new HashMap<Edge, Dart>());
for (Node node : ListSequence.fromList(graph.getNodes())) {
if (ListSequence.fromList(node.getEdges()).count() > 4) {
List<Dart> darts = embeddedGraph.getDartWithSource(node);
Map<Face, Node> faceNodes = MapSequence.fromMap(new HashMap<Face, Node>());
Map<Face, Edge> faceEdges = MapSequence.fromMap(new HashMap<Face, Edge>());
for (Dart dart : ListSequence.fromList(darts)) {
Node faceNode = network.createNode();
Face face = embeddedGraph.getFace(dart);
MapSequence.fromMap(faceNodes).put(face, faceNode);
Edge edge;
edge = network.connect(faceNode, MapSequence.fromMap(nodeMap).get(node));
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(faceEdges).put(face, edge);
}
for (Dart dart : ListSequence.fromList(darts)) {
Face face = embeddedGraph.getFace(dart);
Face leftFace = embeddedGraph.getFace(embeddedGraph.getOpposite(dart));
Edge edge;
edge = network.connect(MapSequence.fromMap(faceMap).get(leftFace), MapSequence.fromMap(faceNodes).get(face));
MapSequence.fromMap(cost).put(edge, 1);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(tempEdgesToDart).put(edge, dart);
}
MapSequence.fromMap(faceToNodeEdges).put(node, faceEdges);
}
}
/*
for (Node node : ListSequence.fromList(graph.getNodes())) {
List<Dart> darts = embeddedGraph.getDartWithSource(node);
Map<Face, Node> faceNodes = MapSequence.fromMap(new HashMap<Face, Node>());
Map<Face, Edge> faceEdges = MapSequence.fromMap(new HashMap<Face, Edge>());
for (Dart dart : ListSequence.fromList(darts)) {
Node faceNode = network.createNode();
Face face = embeddedGraph.getFace(dart);
MapSequence.fromMap(faceNodes).put(face, faceNode);
Edge edge = faceNode.addEdgeTo(MapSequence.fromMap(nodeMap).get(node));
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(faceEdges).put(face, edge);
}
for (Dart dart : ListSequence.fromList(darts)) {
Node left = network.createNode();
Node right = network.createNode();
Edge edge = left.addEdgeTo(right);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(cost).put(edge, -c);
edge = right.addEdgeTo(left);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(cost).put(edge, -c);
Face rightFace = embeddedGraph.getFace(dart);
Face leftFace = embeddedGraph.getFace(embeddedGraph.getOpposite(dart));
edge = MapSequence.fromMap(faceMap).get(rightFace).addEdgeTo(right);
MapSequence.fromMap(cost).put(edge, 2 * c + 1);
MapSequence.fromMap(capacity).put(edge, 1);
edge = MapSequence.fromMap(faceMap).get(leftFace).addEdgeTo(left);
MapSequence.fromMap(cost).put(edge, 2 * c + 1);
MapSequence.fromMap(capacity).put(edge, 1);
edge = right.addEdgeTo(MapSequence.fromMap(faceNodes).get(leftFace));
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(tempEdgesToDart).put(edge, dart);
edge = left.addEdgeTo(MapSequence.fromMap(faceNodes).get(rightFace));
MapSequence.fromMap(cost).put(edge, 0);
MapSequence.fromMap(capacity).put(edge, 1);
MapSequence.fromMap(tempEdgesToDart).put(edge, dart);
}
MapSequence.fromMap(faceToNodeEdges).put(node, faceEdges);
}
*/
Map<Edge, Integer> flow = MinCostMaxFlowWithPotentials.getFlow(network, networkSource, networkTarget, capacity, cost);
for (Face face : ListSequence.fromList(embeddedGraph.getFaces())) {
for (Dart dart : ListSequence.fromList(face.getDarts())) {
Node source = dart.getSource();
int angle = MapSequence.fromMap(flow).get(MapSequence.fromMap(dartAngleMap).get(dart)) + 1;
if (MapSequence.fromMap(MapSequence.fromMap(faceToNodeEdges).get(source)).get(face) != null && MapSequence.fromMap(flow).get(MapSequence.fromMap(MapSequence.fromMap(faceToNodeEdges).get(source)).get(face)) > 0) {
angle -= 1;
}
MapSequence.fromMap(angles).put(dart, angle);
}
}
for (Dart dart : SetSequence.fromSet(MapSequence.fromMap(dartBendMap).keySet())) {
MapSequence.fromMap(bends).put(dart, MapSequence.fromMap(flow).get(MapSequence.fromMap(dartBendMap).get(dart)));
}
for (Face face : ListSequence.fromList(embeddedGraph.getFaces())) {
List<Dart> darts = face.getDarts();
for (Dart dart : ListSequence.fromList(darts)) {
Node node = dart.getSource();
Edge edgeToNode = MapSequence.fromMap(MapSequence.fromMap(faceToNodeEdges).get(node)).get(face);
if (edgeToNode != null && MapSequence.fromMap(flow).get(edgeToNode) > 0) {
Dart dartWithBend = embeddedGraph.getOpposite(dart);
MapSequence.fromMap(bends).put(dartWithBend, MapSequence.fromMap(bends).get(dartWithBend) + 1);
}
}
}
/*
for (Face face : ListSequence.fromList(embeddedGraph.getFaces())) {
List<Dart> darts = face.getDarts();
Dart prev = ListSequence.fromList(darts).last();
for (Dart dart : ListSequence.fromList(darts)) {
Node node = dart.getSource();
Edge edgeToNode = MapSequence.fromMap(MapSequence.fromMap(faceToNodeEdges).get(node)).get(face);
if (MapSequence.fromMap(flow).get(edgeToNode) > 0) {
Node faceNode = edgeToNode.getSource();
List<Edge> prevEdges = faceNode.getInEdges();
for (Edge prevEdge : ListSequence.fromList(prevEdges)) {
if (MapSequence.fromMap(flow).get(prevEdge) > 0) {
Dart flowDart = MapSequence.fromMap(tempEdgesToDart).get(prevEdge);
Dart dartWithBend = null;
if (flowDart == dart) {
dartWithBend = embeddedGraph.getOpposite(dart);
}
if (flowDart == embeddedGraph.getOpposite(prev)) {
dartWithBend = embeddedGraph.getOpposite(prev);
}
if (dartWithBend == null) {
throw new RuntimeException("bad bend dart!");
}
MapSequence.fromMap(bends).put(dartWithBend, MapSequence.fromMap(bends).get(dartWithBend) + 1);
}
}
}
prev = dart;
}
}
*/
if (SHOW_INFO > 0) {
for (Node node : ListSequence.fromList(graph.getNodes())) {
System.out.println("node " + node);
for (Dart dart : ListSequence.fromList(embeddedGraph.getDartWithSource(node))) {
System.out.println(dart + " angle = " + MapSequence.fromMap(angles).get(dart) + ", bends = " + MapSequence.fromMap(bends).get(dart) + ", opposite bends = " + MapSequence.fromMap(bends).get(embeddedGraph.getOpposite(dart)));
}
}
int totalCost = 0;
for (Edge edge : ListSequence.fromList(network.getEdges())) {
totalCost += MapSequence.fromMap(flow).get(edge) * MapSequence.fromMap(cost).get(edge);
}
System.out.println("!!! total cost = " + totalCost);
int totalBendsNumber = 0;
for (Integer value : Sequence.fromIterable(MapSequence.fromMap(bends).values())) {
totalBendsNumber += value;
}
System.out.println("!!! total bends number = " + totalBendsNumber);
if (totalBendsNumber != totalCost) {
throw new RuntimeException("total cost is not equal to bends number");
}
}
}