Example Two-Dimensional Node Arrays

The following example uses a node_matrix<bool> to check if a given graph is bidirected. It has running time O(|V|*|V|+|E|), because of the time for initializing the node_matrix.

Remark: There is an algorithm that needs only time O(|E|) to test if a graph is bidirected.

Notice that () instead of [] is used to access the entries of the matrix.

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

using namespace leda;

int main()
{
  graph G;
  random_graph(G,50,100);

  node_matrix<bool> M(G,false);

  edge e;
  forall_edges(e,G) M(G.source(e),G.target(e))=true;
		
  forall_edges(e,G) {
    if (!M(G.target(e),G.source(e))) {
      std::cout << "Graph is not bidirected!" << std::endl;
      break;
    }
  }

  return 0;
}

See also:

Two-Dimensional Node Arrays

Associate Information with Graphs

Graph Generators

Manual Entries:

Manual Page Two-Dimensional Node Arrays

User Defined Parameter Types