What is Boost Graph?
The Boost Graph (BG) are multi-graph concept, it is factored into much smaller pieces. The reason for this is that any one algorithm cannot fulfill the need for all graph operations.
Furthermore, there are many graph data structures that provide a very effective implementation in the overall view for particular algorithms but are not that effective on all operations implementations. We provide the graph algorithm writer with a good selection from which to choose the concept that is closest to their algorithm by breaking down the graph interface into several smaller concepts.
Boost Graph Library
Boost Graph Library (BGL) is a library that provides Boost graph functions by including in a header.
The Boost Graph Library (BGL) algorithms consist of algorithms like:
- Breadth First Search
- Depth First Search
- Uniform Cost Search
The basic implementation of boost graph algorithms is based on the above 3 algorithms, But now BG algorithms in the BGL include:
- Dijkstra’s Shortest Paths
- Bellman-Ford Shortest Paths
- Johnson’s All-Pairs Shortest Paths
- Kruskal’s Minimum Spanning Tree
- Prim’s Minimum Spanning Tree
- Connected Components
- Strongly Connected Components
- Dynamic Connected Components (using Disjoint Sets)
- Topological Sort
- Transpose
- Reverse Cuthill Mckee Ordering
- Smallest Last Vertex Ordering
- Sequential Vertex Coloring
Iterate over BG to get incoming and outgoing edges of vertex?
To iterate through the edges and vertices BGL for graphs provides functions like in_edges(), out_edges() which iterate through the incoming edges and the outgoing edges respectively.
These functions return pairs denoting how many incoming edges are there on a vertex. Moreover, if you want to know about complexity so it depends on the inside data structure used for the graph. For adjacency lists, the edge function is O(out-degree of v).
Comparison between STL and BGL
Refer to the below code with detailed explanations in the comments.
Note: To run the code download Boost graph library (BGL) in your computer as the iterator in STL is not sufficient to bound the various ways that graph algorithms may traverse. After that Import the below code to your local system.
C++
// In this code we will see how iteration// is done in BG.// We will only focus on directional// and bidirectional graphs#include <boost/graph/adjacency_list.hpp>#include <boost/graph/graph_traits.hpp>#include <iostream>using namespace std;// Only out edges are stored at each vertex.static void Directed();// Adding (A, B) and (B, A) only creates one edgestatic void Bidirectional();int main(int, char*[]){ Directed(); Bidirectional(); return 0;}void Directed(){ cout << std::endl << "Directed()" << std::endl; typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> Graph; // Create a graph object. Graph g; // Adding vertex to graph // vertex 1 boost::graph_traits<Graph>::vertex_descriptor v0 = add_vertex(g); // vertex 2 boost::graph_traits<Graph>::vertex_descriptor v1 = add_vertex(g); // vertex 3 boost::graph_traits<Graph>::vertex_descriptor v2 = add_vertex(g); // Directed graphs can only store out_edges. // That is, a call to add_edge(A, B) will // only produce an edge that is // accessible from A, not from B. // In edges add_edge(v0, v1, g); add_edge(v2, v1, g); // Out edges add_edge(v1, v2, g); add_edge(v1, v0, g); // We can't obtain incoming edges as // with a directed graph only out_edges // are stored on the vertices. // Getting a list of outgoing edges from vertex typedef boost::graph_traits<Graph>::out_edge_iterator out_edge_iterator; std::pair<out_edge_iterator, out_edge_iterator> outEdges = out_edges(1, g); std::cout << std::endl << "Out edges: " << std::endl; for (out_edge_iterator iter = outEdges.first; iter != outEdges.second; ++iter) { cout << *iter << " "; } cout << std::endl;}// Bidirectional graphvoid Bidirectional(){ std::cout << std::endl << "Bidirectional()" << std::endl; typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph; // Create a graph object Graph g; boost::graph_traits<Graph>::vertex_descriptor v0 = add_vertex(g); boost::graph_traits<Graph>::vertex_descriptor v1 = add_vertex(g); boost::graph_traits<Graph>::vertex_descriptor v2 = add_vertex(g); // Add in edges add_edge(v0, v1, g); add_edge(v2, v1, g); // Add out edges add_edge(v1, v2, g); add_edge(v1, v0, g); // List of incoming edges to vertex 1. // We can see the in edges we'd expect ( (0, 1) and (2, // 1) // ). Iterating over incoming edge of vertex // Just like iterator in stl(c++) graphs have associated // types defined in header as graph_traits.hpp so we are // accessing the type of iterator used for traversing // through in_edge typedef boost::graph_traits<Graph>::in_edge_iterator in_edge_iterator; std::pair<in_edge_iterator, in_edge_iterator> inEdges = in_edges(1, g); cout << "In edges: " << endl; for (in_edge_iterator iter = inEdges.first; iter != inEdges.second; ++iter) { cout << *iter << " "; } // List of outgoing edges from vertex 1. // We can see the out edges we'd expect ( (1, 2) and (1, // 0) ). Similarly, here we are accessing the type of // iterator used for traversing through out_edge typedef boost::graph_traits<Graph>::out_edge_iterator out_edge_iterator; std::pair<out_edge_iterator, out_edge_iterator> outEdges = out_edges(1, g); // Iterating over outgoing edge of vertex std::cout << std::endl << "Out edges: " << std::endl; for (out_edge_iterator iter = outEdges.first; iter != outEdges.second; ++iter) { std::cout << *iter << " "; }} |
Python
import boost.graph as bgimport sys# Only out edges are stored at each vertex.def Directed(): print("\nDirected()\n") # Create a graph object. g = bg.AdjacencyList(bg.VecS, bg.VecS, bg.DirectedS) # Adding vertex to graph # vertex 1 v0 = bg.add_vertex(g) # vertex 2 v1 = bg.add_vertex(g) # vertex 3 v2 = bg.add_vertex(g) # Directed graphs can only store out_edges. # That is, a call to add_edge(A, B) will # only produce an edge that is # accessible from A, not from B. # In edges bg.add_edge(v0, v1, g) bg.add_edge(v2, v1, g) # Out edges bg.add_edge(v1, v2, g) bg.add_edge(v1, v0, g) # We can't obtain incoming edges as # with a directed graph only out_edges # are stored on the vertices. # Getting a list of outgoing edges from vertex outEdges = bg.out_edges(1, g) print("\nOut edges: \n") for iter in range(outEdges[0], outEdges[1]): print(iter) print("\n")# Bidirectional graphdef Bidirectional(): print("\nBidirectional()\n") # Create a graph object g = bg.AdjacencyList(bg.VecS, bg.VecS, bg.BidirectionalS) v0 = bg.add_vertex(g) v1 = bg.add_vertex(g) v2 = bg.add_vertex(g) # Add in edges bg.add_edge(v0, v1, g) bg.add_edge(v2, v1, g) # Add out edges bg.add_edge(v1, v2, g) bg.add_edge(v1, v0, g) # List of incoming edges to vertex 1. # We can see the in edges we'd expect ( (0, 1) and (2, 1) # ). Iterating over incoming edge of vertex # Just like iterator in stl(c++) graphs have associated # types defined in header as graph_traits.hpp so we are # accessing the type of iterator used for traversing # through in_edge inEdges = bg.in_edges(1, g) print("In edges: ") for iter in range(inEdges[0], inEdges[1]): print(iter) # List of outgoing edges from vertex 1. # We can see the out edges we'd expect ( (1, 2) and (1, # 0) ). Similarly, here we are accessing the type of # iterator used for traversing through out_edge outEdges = bg.out_edges(1, g) # Iterating over outgoing edge of vertex print("\nOut edges: ") for iter in range(outEdges[0], outEdges[1]): print(iter)if __name__ == "__main__": Directed() Bidirectional() sys.exit(0) |
Java
import java.util.ArrayList;import java.util.Iterator;import java.util.List;import org.jgrapht.Graph;import org.jgrapht.Graphs;import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.SingleSourcePaths;import org.jgrapht.alg.shortestpath.DijkstraShortestPath;import org.jgrapht.graph.DefaultDirectedGraph;import org.jgrapht.graph.DefaultEdge;public class GraphTraversal { public static void main(String[] args) { directedGraph(); bidirectionalGraph(); } public static void directedGraph() { System.out.println("Directed Graph"); Graph<Integer, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class); // Adding vertices to the graph Integer v1 = 1, v2 = 2, v3 = 3; g.addVertex(v1); g.addVertex(v2); g.addVertex(v3); // Adding edges to the graph g.addEdge(v1, v2); g.addEdge(v3, v2); g.addEdge(v2, v3); g.addEdge(v2, v1); // Iterating over outgoing edges from vertex 2 List<DefaultEdge> outEdges = new ArrayList<>(g.outgoingEdgesOf(v2)); System.out.println("Out edges: "); Iterator<DefaultEdge> iter = outEdges.iterator(); while (iter.hasNext()) { DefaultEdge edge = iter.next(); System.out.print("(" + g.getEdgeSource(edge) + ", " + g.getEdgeTarget(edge) + ") "); } System.out.println(); } public static void bidirectionalGraph() { System.out.println("Bidirectional Graph"); Graph<Integer, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class); // Adding vertices to the graph Integer v1 = 1, v2 = 2, v3 = 3; g.addVertex(v1); g.addVertex(v2); g.addVertex(v3); // Adding edges to the graph g.addEdge(v1, v2); g.addEdge(v3, v2); g.addEdge(v2, v3); g.addEdge(v2, v1); // Iterating over incoming edges to vertex 2 List<DefaultEdge> inEdges = new ArrayList<>(g.incomingEdgesOf(v2)); System.out.println("In edges: "); Iterator<DefaultEdge> iter = inEdges.iterator(); while (iter.hasNext()) { DefaultEdge edge = iter.next(); System.out.print("(" + g.getEdgeSource(edge) + ", " + g.getEdgeTarget(edge) + ") "); } System.out.println(); // Iterating over outgoing edges from vertex 2 List<DefaultEdge> outEdges = new ArrayList<>(g.outgoingEdgesOf(v2)); System.out.println("Out edges: "); iter = outEdges.iterator(); while (iter.hasNext()) { DefaultEdge edge = iter.next(); System.out.print("(" + g.getEdgeSource(edge) + ", " + g.getEdgeTarget(edge) + ") "); } System.out.println(); }}// This code is contributed by Akash Jha |
C#
using System;using System.Collections.Generic;using QuickGraph;public class GraphTraversal { public static void Main(string[] args) { DirectedGraph(); BidirectionalGraph(); } public static void DirectedGraph() { Console.WriteLine("Directed Graph"); var g = new BidirectionalGraph<int, Edge<int> >(); // Adding vertices to the graph var v1 = 1; var v2 = 2; var v3 = 3; g.AddVertex(v1); g.AddVertex(v2); g.AddVertex(v3); // Adding edges to the graph g.AddEdge(new Edge<int>(v1, v2)); g.AddEdge(new Edge<int>(v3, v2)); g.AddEdge(new Edge<int>(v2, v3)); g.AddEdge(new Edge<int>(v2, v1)); // Iterating over outgoing edges from vertex 2 var outEdges = new List<Edge<int> >(g.OutEdges(v2)); Console.WriteLine("Out edges: "); foreach(var edge in outEdges) { Console.Write("(" + edge.Source + ", " + edge.Target + ") "); } Console.WriteLine(); } public static void BidirectionalGraph() { Console.WriteLine("Bidirectional Graph"); var g = new BidirectionalGraph<int, Edge<int> >(); // Adding vertices to the graph var v1 = 1; var v2 = 2; var v3 = 3; g.AddVertex(v1); g.AddVertex(v2); g.AddVertex(v3); // Adding edges to the graph g.AddEdge(new Edge<int>(v1, v2)); g.AddEdge(new Edge<int>(v3, v2)); g.AddEdge(new Edge<int>(v2, v3)); g.AddEdge(new Edge<int>(v2, v1)); // Iterating over incoming edges to vertex 2 var inEdges = new List<Edge<int> >(g.InEdges(v2)); Console.WriteLine("In edges: "); foreach(var edge in inEdges) { Console.Write("(" + edge.Source + ", " + edge.Target + ") "); } Console.WriteLine(); // Iterating over outgoing edges from vertex 2 var outEdges = new List<Edge<int> >(g.OutEdges(v2)); Console.WriteLine("Out edges: "); foreach(var edge in outEdges) { Console.Write("(" + edge.Source + ", " + edge.Target + ") "); } Console.WriteLine(); }} |
Javascript
const { Graph, alg } = require("graphlib");function directedGraph() { console.log("Directed Graph"); const g = new Graph({ directed: true }); // Adding vertices to the graph const v1 = 1, v2 = 2, v3 = 3; g.setNode(v1); g.setNode(v2); g.setNode(v3); // Adding edges to the graph g.setEdge(v1, v2); g.setEdge(v3, v2); g.setEdge(v2, v3); g.setEdge(v2, v1); // Iterating over outgoing edges from vertex 2 const outEdges = g.outEdges(v2); console.log("Out edges: "); for (const edge of outEdges) { console.log(`(${edge.v}, ${edge.w})`); } console.log();}function bidirectionalGraph() { console.log("Bidirectional Graph"); const g = new Graph({ directed: true }); // Adding vertices to the graph const v1 = 1, v2 = 2, v3 = 3; g.setNode(v1); g.setNode(v2); g.setNode(v3); // Adding edges to the graph g.setEdge(v1, v2); g.setEdge(v3, v2); g.setEdge(v2, v3); g.setEdge(v2, v1); // Iterating over incoming edges to vertex 2 const inEdges = g.inEdges(v2); console.log("In edges: "); for (const edge of inEdges) { console.log(`(${edge.v}, ${edge.w})`); } console.log(); // Iterating over outgoing edges from vertex 2 const outEdges = g.outEdges(v2); console.log("Out edges: "); for (const edge of outEdges) { console.log(`(${edge.v}, ${edge.w})`); } console.log();}directedGraph();bidirectionalGraph(); |
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
