Algorithmic Solutions > LEDA > LEDA Guide > Graphs and Related Data Types > Misc. Graph Functions

Miscellaneous Graph Functions

LEDA provides a variety of different functions to test basic properties of graphs, e.g., simple, bidirected, or acyclic. There are also functions to copy graphs, to make graphs connected, biconnected, and triconnected. A complete list of functions can be found on the Manual Page.

Purpose: The main purpose of the miscellaneous graph functions is to provide the programmer a convenient way of basic functions on graphs.

Example

The following small program shows how to use the miscellaneous graph functions Is_Simple(), Is_Loopfree(), Delete_Loops(), Is_Bidirected(), Is_Acyclic(), and Make_Acyclic().

#include <LEDA/graph/graph.h>
#include <LEDA/graph/graph_gen.h>
#include <LEDA/graph/graph_misc.h>

using namespace leda;

int main()
{
  graph G;
  complete_graph(G,1000); 
    //creates complete bidirected graph with 1000 nodes

  if (Is_Simple(G)) 
      std::cout << "G is simple" << std::endl;
  else 
      std::cout << "There are parallel edges in G" << std::endl;

  if (Is_Loopfree(G)) 
      std::cout << "G has no loops" << std::endl;
  else {
    std::cout << "There are loops in G" << std::endl;
    list<node> L=Delete_Loops(G);
    std::cout << L.size() << " loops deleted" << std::endl;
  }

  if (Is_Bidirected(G)) 
      std::cout << "G is bidirected" << std::endl;
  else 
      std::cout << "G is not bidirected" << std::endl;

  if (Is_Acyclic(G)) 
      std::cout << "G is acyclic" << std::endl;
  else {
    std::cout << "There are cycles in G" << std::endl;
    int numedges=G.number_of_edges();
    Make_Acyclic(G);
    numedges-=G.number_of_edges();
    std::cout << numedges 
              << " edges deleted for making G acyclic" << std::endl;
  }
	
  return 0;
}

See also:

Graphs and Related Data Types

Graph Algorithms


Manual Entries:

Manual Page Miscellaneous Graph Functions

Manual Page Graph Generators

 




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH