1

OGDF: An Open Graph Drawing Framework

LS11: Algorithm Engineering

Prof. Dr. Petra MutzelMarkus Chimani, Karsten Klein, Carsten Gutwenger

Überblick PG OGDF

� Was ist „Graphenzeichnen“?

� Aufgabenstellungen

� Voraussetzungen

� Grobplanung

Graphenzeichnen

� Visuelle Vermittlung von Informationen

� Informatik & Mathematik:Graphentheorie, Graphenalgorithmen, komb. Optimierung, lineare Programmierung,…

� Beispiel diagramm zu graph zu diag

Graphenzeichnen

� Vielzahl von Anwendungen in� Software-Engineering (UML)

� Bioinformatik

� Datenbanken

� Technische Prozesse

� VLSI

Anwendungsbeispiel Fahndung

fand statt im

fand statt am

?

beteiligt an

wurde getragen von

hat aus dem Lokal laufen sehen in hellroter Stickerei auf

wurde schwer verletzt durch

beteiligt an

reist zeitweise mit

wurde gefunden beiwurde gefunden bei

fuer Uebernachtung am

Messerstecherei

ALI BABA

10.12.199223:45

UPm Blousonjacke, schwarz,Glanzoberflaeche

Orkan, Mehmet PortlandTigers Baseball-Team

Rabula, Georg

Drueckerkolonne

Zettel mit NotizHotelrechnung

02.11.1992

Vernehmungsprotokoll

2

Anwendungsbeispiel Fahndung

beteiligt an

in hellroter Stickerei auf

wurde schwer verletzt durch

ist verheiratet mit

Leiter des Aussendienstes

beteiligt an

?

GesellschafterEinlage 100.000 DM

fand statt bei

Inhaber von

Geschaeftsfuehrer von

Gesellschafter100.000 Einlage

fand statt im fand statt am

wurde getragen von

hat aus dem Lokallaufen sehen

reist zeitweise mitwurde gefunden bei

fuer Uebernachtung am

wurde gefunden bei

ist Betreiber von

Gastwirt

befand sich im

befand sich im

wurden gestohlen

fand statt am

Messerstecherei

ALI BABA 10.12.1992

23:45

UPm

Blousonjacke, schwarz, Glanzoberflaeche

Orkan, Mehmet PortlandTigers Baseball-Team

Rabula, Georg

Drueckerkolonne Zettel mit Notiz

Hotelrechnung

02.11.1992

Langenbach, HermannMangan, Julian

Lukullus-Gaststaetten

Hubart, Christof

Roth, Rosa

Taperti, Horst Haman, LotharINTER-TRUCK

Einbruchdiebstahlin Lagerhaus

Klein, Klaus

Lederwaren

03.11.1992

04:30--5:10

Datenbankabfrage

Anwendungsbeispiel

beteiligt an

in hellroter Stickerei auf

wurde schwer verletzt durch

ist verheiratet mit

Leiter des Aussendienstes

beteiligt an

?

GesellschafterEinlage 100.000 DM

fand statt bei

Inhaber von

Geschaeftsfuehrer von Gesellschafter100.000 Einlage

fand statt im

fand statt am

wurde getragen von

hat aus dem Lokallaufen sehen

reist zeitweise mit

wurde gefunden bei

fuer Uebernachtung am

wurde gefunden bei

ist Betreiber von

Gastwirt

befand sich im

befand sich im

wurden gestohlenfand statt am

Messerstecherei

ALI BABA

10.12.1992

23:45

UPm

Blousonjacke, schwarz, Glanzoberflaeche

Orkan, Mehmet

PortlandTigers Baseball-Team

Rabula, Georg

Drueckerkolonne

Zettel mit Notiz

Hotelrechnung

02.11.1992

Langenbach, Hermann

Mangan, Julian

Lukullus-Gaststaetten

Hubart, Christof

Roth, Rosa

Taperti, Horst

Haman, Lothar

INTER-TRUCK

Einbruchdiebstahlin Lagerhaus

Klein, Klaus

Lederwaren03.11.1992

04:30--5:10

Layoutoptimierte Datenbankabfrage

Optimierungskriterien

� Kreuzungsminimierung

� Knickminimierung

� Verteilung

� Angular Resolution

� Symmetrie

� Kompaktheit

� Einhaltung spezifischer Constraints, Motor,UML, Fluss

Optimierungskriterien

Wann ist eine Zeichnung „gut“ ???

Optimierungskriterien

� Kreuzungen

Optimierungskriterien

� Knicke

3

Optimierungskriterien

� Platzverbrauch und Kantenlänge

Optimierungskriterien

� Winkelauflösung und Verteilung

Optimierungskriterien

� Teilprobleme für ästhetische Kriterien sind häufig NP-schwer

� Kriterien widersprechen sich teilweise

� Gute Heuristiken gesucht

Verfahren

Wie berechnet man eine „gute“Zeichnung???

Verfahren

� Physikalische Modelle

Verfahren

� Hierarchisch

4

Verfahren

� Planaritätsbasiert – z.B. Orthogonal

Verfahren

� Spezialverfahren (Baum)

«Enquiry»Requisition Inquiry

PO requisition

Requisition Status

«Enquiry»GRV Inquiry

Goods Received Voucher

-GR A No.-Qty Retu rned-Reaso n

GRA

GRV Status

-GRV No-Supplier Co de-Supplier De scription-GRV Status-Auth ority No-Purchase Order No.-Suppliers Invoice/Del ivery No te-Date R eceived

GRV Header

-U OM-Qty Orde red-Qty Receive d to Date-Qty on Del ivery Note-Qty Coun ted-Qty Inspected OK-Qty Rejected-Qty Accepted-U nit Ne t Price-Qty on GR A-Sup plie r Invoice No.-Sup plie r Invoice Value-GRV Total (Excl . Vat)

GRV Detail

GRN Inquiry

Goods Returned Note

-GRN No-Supplier Co de-Supplier De scription-Suppliers Invoice/Del ivery No te-GRV Ref. No-Purchase Order No.-Auth ority No.-Date R eturn ed

GRN Header-Ite m Cod e-Ite m Descrip tio n-Qty on GRN-Qty Returned-Uni t Net Pri ce-GRN R eason Code-Rea son Description-Supp lier Credit Note-Supp lier Value

GRN Detail

-Da te Requ ired-Qty Requi red

Split line Item

«Enquiry»PO Inquiry

Purchase Order PO Status

-Ware house-Supplier Co de-UOM-Qty Re quired-Due Date-Pri ce-Trade Disco unt 1-Trade Disco unt 2-Line Statu s

PO Requisition Detail

-quest No-Requistio n Type-Created By-Requested By-Au tho ri sed By-Date Time Created-Request Status

PO Requisition Header

-Purchase Ord er No-Supp lier Code-Supp lier Description-Order Type-Buyer-Date Time Cre ate d-Order Status : PO Status-Settl ement D iscount-Authority N o-W/H Cod e-W/H Descrip tion-Version No

Purchase Order Header-Spe cial Instructions-R equisi tio n N o-Ordering UOM-Qty Requ ired-Qty received-D ate Req uired-Standa rd Co st-Sup plie r Price-Trade Discou nt 1-Trade Discou nt 2-R equested By-Total Value (Excl. Vat)-L ine Item Status : PO Sta tus

Purchase Order Detail

«Enquiry»Supplier Inquiry

Supplier Status

-Supp lier Code-Supp lier Name-Supp lier Sta tus-Settlement Discount %-Payment Terms (Days)-Street No .-Street Na me-Subu rb-Ci ty-Physical Postal Code-P.O. Bo x No.-Postal Code-Banking Details-E-mail Add re ss-Cred itor Co nta ct Person-MD Name-MD Number-Phon e N umber-Fax No-Statement De livery Method-Method of Payment-Supp lier Rating-Da te Created-Trade Discoun t 1-Trade Discoun t 2

Supplier Master File

Transaction Type

-Item Code-Item Description

Stock Items

-Expe nce Code-Cost Cen ter-Description of Prod uct-Quoted Reference No.

Non-Stock Item

GL Account Stock Account

Employee GL Accounts

Budget

-Emplo ye e N o.-Na me-Surna me-ID No.

Employee Master File

«Enquiry»Cardex Report

«Enquiry»Item Inquiry

-Sup plier Code-Item Co de-W/H C ode-Sup plier Price-Da te On-Da te Off-Max Stock Level-Min imum Stock Level-Mul tip les-Type (MRP or ROP)-Re cord Qty on D/Note?-Re cord Qty Coun ted ?-Inspected OK?-Re jected?-Accepted?-EOQ-Sup plier Lea d Time-Ordering UOM-Co nversion Fa ctor

Supplier W/H Item Matrix

-Warehouse Code-Warehouse Descriptio n

Warehouse

-W/H Code-Item Code-Inven tory on Hold-Inven tory on Order-Supplier Co de-Lead Time-Inven tory on Hand-Minimum Order Qty-Ma ximu m Order Qty-Re-order Point

Warehouse Item

-Wa rehouse-Product Group

Buyer Role

-Item Co de-Item De scription-Standa rd Co st-Stocking UOM-TAX-Material Co st-L ast Cost Price-Inventory Unit-Forecast Method-D /Note inq uiry-MRP - Le ad Time-MRP - Supp lier Code-MRP - W/H

Item Master File

Buyer

UML Klassendiagramm (nachherModelElement

Feature

-body : BooleanExpression

Constraint

-defaultValue : Expression

Parameter

PersonsConstrBehavioralFeature

StructuralFeature

-isRoot : Boolean-isLeaf : Boolean-isAbstract : Boolean

GeneralizableElement

Attribute

OperationMethod

ReturnName

«Datentyp»Datatype«Datentyp»

NameSpace

«Datentyp»Real

«Datentyp»String

«Datentyp»Boolean

«Datentyp»Integer

Package

Model

Classifier

-isActive : Boolean

Class

Klasse17

«Datentyp»Frau

«Datentyp»Mann

«Datentyp»Standort

«Datentyp»Arbeitsleistung

«Datentyp»Person

«Datentyp»Projekt

«Datentyp»bezeichnung

«Datentyp»Name

«Datentyp»budget

-language : Name-body : String

Expression

«Datentyp»InitVal

«Datentyp»Stunden

«Datentyp»getName

«Datentyp»getName

«Datentyp»setName

«Datentyp»setName

«Datentyp»NameToSet

-Ende3

*

-Ende4

*

UML Klassendiagramm (vorher)

ModelElement

Feature

-body : BooleanExpression

Constraint

-defaultValue : Expression

Parameter

PersonsConstr

BehavioralFeature

StructuralFeature

-isRoot : Boolean-isLeaf : Boolean-isAbstract : Boolean

GeneralizableElement

Attribute

Operation

Method

ReturnName

«Datentyp»Datatype

«Datentyp»NameSpace

«Datentyp»Real

«Datentyp»String

«Datentyp»Boolean

«Datentyp»Integer

Package

Model

Classifier

-isActive : Boolean

Class

Klasse17

«Datentyp»Frau

«Datentyp»Mann

«Datentyp»Standort

«datatype»Arbeitsleistung

«Datentyp»Person

«datatype»Projekt

«Datentyp»bezeichnung

«Datentyp»Name

«Datentyp»budget

-language : Name-body : String

Expression «Datentyp»InitVal

«Datentyp»Stunden

«Datentyp»getName

«Datentyp»getName

«Datentyp»setName

«Datentyp»setName

«Datentyp»NameToSet

-Ende3*-Ende4*

UML Klassendiagramm (nachher) Protein Interaktionsnetzwerke

5

Protein Interaktionsnetzwerke Metabolische Netze

Und all das zusammen???

Automatisches Graphenzeichnen

� Entwicklung von effizienten Algorithmen und Datenstrukturen zur Berechnung von Layouts

� Erstellung von Software

� Einbindung in Applikationen

Automatisches Graphenzeichnen

� Softwarebibliothek zum automatischen Graphenlayout

� Einbindung wissenschaftlicher Ergebnisse in Anwendungen

� Experimentelle Analyse neuer Ergebnisse

� schnellere Entwicklung

6

OGDF Historie

� Forschungskooperation mehrerer Universitäten und Institute ab ´97 → AGD

� Abhängigkeit von weiteren, teilweise kommerziellen Bibliotheken (LEDA,…)

� Aufbau einer eigenständigen Bibliothek →OGDF

Aufgabe der PG: Erweiterung der OGDF

Was ist OGDF?

� = Open Graph Drawing Framework

� C++ Klassenbibliothek

� Algorithmen für automatisches Graphenlayout

� Datenstrukturen und Algorithmen für Graphen

� Zur Zeit im Aufbau, ca. 10 Personenjahre

� Open Source

Technische Details

� Statistik: Codezeilen, Klassen, Mannjahre

� eigenständig

� Verfahren, Strukturen

� Aufbau, zb graph klasse, layout hierarchie

Themen der PG

� Compound-Graphen

� Constraint-Manager

� Animations-Manager

� Editorkomponente

Navigation/Abstraktion

Condition

Exploit

Goal

Conditions

Condition

Exploit

Goal

Conditions

vulnerability rather than aggregation

Compounds

Aufgaben:

� Entwicklung einer Datenstruktur für Compounds

� Entwurf und Implementierung von Layoutalgorithmen

� Einbindung in den Editor

� Entwicklung eines Dateiformats

7

Themen der PG

� Compound-Graphen

� Constraint-Manager

� Animations-Manager

� Editorkomponente

ConstraintsMetabolischer Reaktionsweg

Constraints Constraints

Aufgaben:

� Konsistenzprüfung

� Visuelle Darstellung von Constraints

� Schnittstelle für Eingabe bzw. Formulierung von Constraints

� Erweiterung von Layoutverfahren

� Managementmechanismus (interne Repräsentation)

Constraints

� Klassifikation

� Konsistenz

� Darstellung

� Managementmechanismus

Geometrische, topologische, arithmetische Constraints, Hierarchien, Gruppierung, Fixierung von Teillayouts, Kantenrichtung, Ansatzpunkte, Schranken für Knicke, Kreuzungen, …

Themen der PG

� Compound-Graphen

� Constraint-Manager

� Animations-Manager

� Editorkomponente

8

Animation Animation

Aufgaben:

� Entwicklung und Implementierung von Transformationsmodellen

� Einbindung in den Editor

� Evaluierung

Themen der PG

� Compound-Graphen

� Constraint-Manager

� Animations-Manager

� Editorkomponente

Ziele

� Unterstützung von Compounds inklusive Layoutalgorithmus

� Constraintmechanismus inklusive geeigneter Layoutalgorithmen

� Unterstützung eines geeigneten Dateiformats

� Lauffähiger Editor

� Teilberichte und Abschlussbericht

Voraussetzungen

� C++ Kenntnisse

� Programmiererfahrung

� Effiziente Algorithmen/Komplexitätstheorie

� (Softwaretechnik)

Planung

� 2W – Seminarphase, Einarbeitung GD

� 2W – Planungsphase, Spezifikation

� 16W – Bearbeitung der einzelnen Schwerpunktthemen in Kleingruppen,Zwischenberichte

� 4W – Integrationstests, Verbesserungen

� 3W – Erstellung des Endberichts

9

Informationen

� ls11-www.cs.uni-dortmund.de/gd.jsp

� Kontakt:Markus Chimani (Markus.Chimani@cs.uni-dortmund.de)Karsten Klein (Karsten.Klein@cs.uni-dortmund.de)

DEMO

� GDE

• UML: Standard für Entwurf und Analyse von Softwaresystemen

• Spezifikation von Struktur und Verhalten von Softwaresystemen durch unterschiedliche Diagrammtypen

• Software Development Tools unterstützen UML � Diagramme in Werkzeugen/IDEs

UML Modellierung im Software Engineering

10

Entwurf

Datenbank Modell

Vertrag Person Produktbestand Produktvorgang Provisionssatz

Konditionbestand

Normalvertrag

Vertragsinhaber/Vertrag

Vertreter/Vorgang Vermittler/VorgangProvisionssatz/Produktvorgang

Struktur

Bausparvertrag

Vertragsinshaber

Preis

Vermittler

Buchung

ZKVertrag Konto Vorgang Vertreter

KLVetrag Einlagenvertrag Immobilienvermittl. UnbekVetrag Darlehensvetrag RLVertrag

Datenbank Modell

Vertrag

Person

Produktbestand

Produktvorgang Provisionssatz

Konditionbestand

Normalvertrag

Vertragsinhaber/Vertrag

Vertreter/Vorgang

Vermittler/Vorgang

Provisionssatz/Produktvorgang

Struktur

Bausparvertrag

Vertragsinshaber

Preis Vermittler

Buchung

ZKVertrag

Konto Vorgang

Vertreter

KLVetrag

EinlagenvertragImmobilienvermittl.

UnbekVetrag

Darlehensvetrag

RLVertrag

Datenbank Modell

Vertrag

Person

Produktbestand ProduktvorgangProvisionssatz

Konditionbestand

Normalvertrag

Vertragsinhaber/Vertrag

Vertreter/Vorgang Vermittler/Vorgang

Provisionssatz/Produktvorgang

Struktur

Bausparvertrag

Vertragsinshaber

Preis

Vermittler

Buchung

ZKVertrag

Konto

VorgangVertreter

KLVetrag

Einlagenvertrag Immobilienvermittl.

UnbekVetrag

Darlehensvetrag

RLVertrag

Datenbank Modell

11

UML Klassendiagramm (vorher) UML Klassendiagramm (nachher)