מבוא ל- JGraphT

1. סקירה כללית

לרוב, כאשר אנו מיישמים אלגוריתמים מבוססי גרף, עלינו גם ליישם כמה פונקציות שירות.

JGraphT היא ספריית Java בקוד פתוח אשר לא רק מספקת לנו סוגים שונים של גרפים, אלא גם אלגוריתמים שימושיים רבים לפתרון בעיות גרפים שנמצאות לעתים קרובות ביותר.

במאמר זה נראה כיצד ליצור סוגים שונים של גרפים וכמה נוח להשתמש בכלים המסופקים.

2. תלות של Maven

נתחיל בהוספת התלות לפרויקט Maven שלנו:

 org.jgrapht jgrapht-core 1.0.1 

הגרסה העדכנית ביותר נמצאת במרכז Maven Central.

3. יצירת גרפים

JGraphT תומך בסוגים שונים של גרפים.

3.1. גרפים פשוטים

בתור התחלה, בואו ליצור גרף פשוט עם קודקוד מסוג חוּט:

גרף g = SimpleGraph חדש (DefaultEdge.class); g.addVertex ("v1"); g.addVertex ("v2"); g.addEdge (v1, v2);

3.2. גרפים מכוונים / לא מופנים

זה גם מאפשר ליצור גרפים מכוונים / לא מכוונים.

בדוגמה שלנו, ניצור גרף מכוון ונשתמש בו להדגמת פונקציות שירות ואלגוריתמים אחרים:

DirectedGraph directedGraph = DefaultDirectedGraph חדש (DefaultEdge.class); directorGraph.addVertex ("v1"); directorGraph.addVertex ("v2"); directorGraph.addVertex ("v3"); directorGraph.addEdge ("v1", "v2"); // הוסף קודקודים ושוליים שנותרו

3.3. גרפים שלמים

באופן דומה, אנו יכולים גם ליצור גרף מלא:

חלל ציבורי createCompleteGraph () {completeGraph = חדש SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = חדש CompleteGraphGenerator (גודל); VertexFactory vFactory = VertexFactory חדש () {int פרטי פרטי = 0; מחרוזת ציבורית createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (completeGraph, vFactory, null); }

3.4. רב גרפים

מלבד גרפים פשוטים, API מספק לנו גם מולטיגרפים (גרפים עם נתיבים מרובים בין שני קודקודים).

חוץ מזה, בכל גרף יכולים להיות לנו קצוות משוקללים / לא משוקללים או מוגדרים על ידי המשתמש.

בואו ניצור מולטיגרף עם קצוות משוקללים:

חלל ציבורי createMultiGraphWithWeightedEdges () {multiGraph = Multigraph חדש (DefaultWeightedEdge.class); multiGraph.addVertex ("v1"); multiGraph.addVertex ("v2"); DefaultWeightedEdge edge1 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (edge1, 5); DefaultWeightedEdge edge2 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (edge2, 3); }

בנוסף לכך, אנו יכולים לקבל גרפים בלתי ניתנים לשינוי (לקריאה בלבד) וניתנים להאזנה (מאפשרים למאזינים חיצוניים לעקוב אחר שינויים) וכן לתצלומי משנה. כמו כן, תמיד נוכל ליצור את כל הקומפוזיציות של הגרפים הללו.

פרטים נוספים על API ניתן למצוא כאן.

4. אלגוריתמים API

כעת, לאחר שיש לנו אובייקטים גרפיים מן המניין, בואו נסתכל על כמה בעיות נפוצות והפתרונות שלהם.

4.1. איטרציה של גרפים

אנו יכולים לחצות את הגרף באמצעות איטרטורים שונים כגון BreadthFirstIterator, DepthFirstIterator, ClosestFirstIterator, RandomWalkIterator לפי הדרישה.

עלינו פשוט ליצור מופע של איטרטורים בהתאמה על ידי העברת אובייקטים גרפיים:

DepthFirstIterator depthFirstIterator = DepthFirstIterator חדש (directGraph); BreadthFirstIterator breadthFirstIterator = חדש BreadthFirstIterator (directedGraph);

ברגע שנקבל את חפצי האיטרציה, נוכל לבצע את החזרה באמצעות hasNext () ו הַבָּא() שיטות.

4.2. מציאת הדרך הקצרה ביותר

הוא מספק יישומים של אלגוריתמים שונים כגון דייקסטרה, בלמן-פורד, אסטאר ופלוידווארשל ב org.jgrapht.alg.shortestpath חֲבִילָה.

בואו נמצא את הדרך הקצרה ביותר באמצעות האלגוריתם של דייקסטרה:

@ מבחן ציבורי בטל כאשר GetDijkstraShortestPath_thenGetNotNullPath () {DijkstraShortestPath dijkstraShortestPath = DijkstraShortestPath חדש (directorGraph); רשימה shortestPath = dijkstraShortestPath .getPath ("v1", "v4"). GetVertexList (); assertNotNull (shortestPath); }

באופן דומה, כדי להגיע למסלול הקצר ביותר באמצעות האלגוריתם של בלמן-פורד:

@ מבחן ציבורי בטל כאשר GetBellmanFordShortestPath_thenGetNotNullPath () {BellmanFordShortestPath bellmanFordShortestPath = חדש BellmanFordShortestPath (directorGraph); רשימה shortestPath = bellmanFordShortestPath .getPath ("v1", "v4") .getVertexList (); assertNotNull (shortestPath); }

4.3. מציאת תמונות משנה מחוברות חזק

לפני שנכנס ליישום, בואו נסתכל בקצרה על משמעות המשמעות של תצלומי משנה. אומרים שתצלום מחובר חזק רק אם יש נתיב בין כל זוג קודקודיו.

בדוגמה שלנו, {v1, v2, v3, v4} יכולים להיחשב כ subgraph מחובר מאוד אם אנו יכולים לעבור לכל קודקוד ללא קשר למה קודקוד הנוכחי.

אנו יכולים לפרט ארבעה תצלומי משנה כאלה עבור הגרף המכוון המוצג בתמונה שלעיל:

{v9}, {v8}, {v5, v6, v7}, {v1, v2, v3, v4}

יישום לרשימת כל תצלומי המשנה המחוברים היטב:

@ מבחן ציבורי בטל כאשר GetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = KosarajuStrongConnectivityInspector חדש KosarajuStrongComment; רשימה sterkConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); רשום staarkConnectedVertices = ArrayList חדש (sterkConnectedSubgraphs.get (3) .vertexSet ()); מחרוזת randomVertex1 = sterkConnectedVertices.get (0); מחרוזת randomVertex2 = staarkConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = AllDirectedPaths חדשים (directGraph); רשימה possiblePathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, starkConnectedVertices.size ()); assertTrue (possiblePathList.size ()> 0); }

4.4. מעגל אוילריאן

מעגל אוילריאן בגרף ז הוא מעגל שכולל את כל הקודקודים והקצוות של ז. גרף שיש בו הוא גרף אוילרי.

בואו נסתכל על הגרף:

חלל ציבורי createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = חדש SimpleWeightedGraph (DefaultEdge.class); IntStream.range (1,5) .forEach (i-> simpleGraph.addVertex ("v" + i)); IntStream.range (1,5) .forEach (i-> {int endVertexNo = (i + 1)> 5? 1: i + 1; simpleGraph.addEdge ("v" + i, "v" + endVertexNo);} ); }

כעת נוכל לבדוק האם גרף מכיל מעגל אוילריאני באמצעות ה- API:

@Test ציבורי בטל givenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = HierholzerEulerianCycle חדש); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test ציבורי בטל כאשר GetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = HierholzerEulerianCycle חדש) (); נתיב GraphPath = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. מעגל המילטוניאן

א GraphPath שמבקר בכל קודקוד בדיוק פעם אחת מכונה בשם המילטון המסלול.

מחזור המילטוניאן (או מעגל המילטוניאן) הוא מסלול המילטוניאן כך שיש קצה (בגרף) מהקודקוד האחרון לקודקוד הראשון של השביל.

אנו יכולים למצוא מחזור המילטוניאן אופטימלי עבור גרף מלא עם HamiltonianCycle.getApproximateOptimalForCompleteGraph () שיטה.

שיטה זו תחזיר סיור מינימלי מוערך של מוכרי נסיעה (מחזור המילטוניאן). הפיתרון האופטימלי הוא NP-complete, ולכן זהו קירוב ראוי שעובר בזמן פולינומי:

חלל ציבורי כאשר GetHamiltonianCyclePath_thenGetVerticeSequence () {List verticeList = HamiltonianCycle .getApproximateOptimalForCompleteGraph (completeGraph); assertEquals (verticeList.size (), completeGraph.vertexSet (). size ()); }

4.6. גלאי מחזור

אנחנו יכולים גם לבדוק אם יש מחזורים בגרף. כַּיוֹם, CycleDetector תומך רק בגרפים מכוונים:

@Test הציבור בטל כאשרCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = CycleDetector חדש (directedGraph); assertTrue (cycleDetector.detectCycles ()); הגדר cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. ויזואליזציה של גרפים

JGraphT מאפשר לנו ליצור הדמיות של גרפים ולשמור אותם כתמונותראשית, הוסף את תלות הרחבה jgrapht-ext ממייבען סנטרל:

 org.jgrapht jgrapht-ext 1.0.1 

לאחר מכן, בואו ליצור גרף מכוון פשוט עם 3 קודקודים ושלושה קצוות:

@ לפני הריק הציבורי createGraph () {File imgFile = קובץ חדש ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = new DefaultDirectedGraph (DefaultEdge.class); מחרוזת x1 = "x1"; מחרוזת x2 = "x2"; מחרוזת x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

כעת אנו יכולים לדמיין גרף זה:

@Test הציבור בטל givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () זורק IOException {JGraphXAdapter graphAdapter = חדש JGraphXAdapter (g); פריסת mxIGraphLayout = mxCircleLayout חדש (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage image = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); קובץ imgFile = קובץ חדש ("src / test / resources / graph.png"); ImageIO.write (תמונה, "PNG", imgFile); assertTrue (imgFile.exists ()); }

כאן יצרנו א JGraphXAdapter שמקבל את הגרף שלנו כטיעון קונסטרוקטור והחלנו א mxCircleLayout לזה. זה מציג את ההדמיה בצורה מעגלית.

יתר על כן, אנו משתמשים ב- mxCellRenderer ליצור BufferedImage ואז כתוב את ההדמיה לקובץ png.

אנו יכולים לראות את התמונה הסופית בדפדפן או במעבד המועדף עלינו:

אנו יכולים למצוא פרטים נוספים בתיעוד הרשמי.

6. מסקנה

JGraphT מספק כמעט את כל סוגי הגרפים ומגוון אלגוריתמי הגרפים. סקרנו כיצד להשתמש במעט ממשקי API פופולריים. עם זאת, תמיד תוכלו לחקור את הספרייה בדף הרשמי.

ניתן למצוא את היישום של כל הדוגמאות וקטעי הקוד באתר Github.