Shortest Path Edge Inserter ( ShortestPathInserter )

Baseclasses

Definition

The module ShortestPathInserter takes as input a planar graph G = (V, E) and an edge set F and computes a (combinatorial) embedding of the graph G' = (V, E $\cup$ F) with `few' crossings. The crossings are substituted by artificial vertices, thus leading to a new plane graph. This module is typically used as the second phase of a planarization routine using planar subgraphs.

The algorithm starts with computing a combinatorial embedding $\Pi$ of G and inserts the edges in F iteratively. An edge e of F is inserted by computing a shortest path in the dual graph of G. Crossings of e with edges of G are replaced by artificial vertices. This leads to a new planar graph G^$\prime$. The next edge f of F is inserted into G^$\prime$ by the same approach. In the case that | F| = 1, this gives the crossing minimal solution (in the case that the embedding of G should be kept).

In the basic version of the ShortestPathInserter (invoked by call_basic()) the edges of F are inserted in the given order. It is not difficult to see that different insertion orders lead to different numbers of crossings. One idea to exploit this fact is to test some insertion orders and use the solution with the smallest number of crossings. This can be easily implemented by permuting the order of the edges in F and then calling the basic heuristics.

Another idea is to insert first the edge with the shortest shortest path in the dual graph. This variant is invoked by call_sf().

After all edges are inserted the result can be improved using the following idea. Remove each edge e of F and reinsert it again by a shortest path computation in the dual graph. Since only one edge at a time is removed and reinserted, it can always be inserted with the same number of crossings as before. However, it is possible that it can be inserted with fewer crossings by avoiding crossings with other edges of F. The function call_rr() calls the basic heuristics and removes and reinserts all edges of F in the given order until no improvement is achieved in one round.

We can extend the above idea by removing and reinserting not only the edges of F but all edges that are involved in crossings. The function call_err() calls the basic heuristics and removes and reinserts all edges of F $\cup$ E until no improvement is achieved in one round. The order in which the edges are removed and reinserted is as follows. First the edges of F are considered in the given order, then the edges of E in an arbitrary but fixed order. This variant is the default if call() is invoked.

General Information

Algorithm
name	Shortest Path Inserter
long name	Shortest Path Edge Inserter
author

Implementation
author	Th. Ziegler
date	March 2001
version

Pre- and Postcondition

precondition	=	{planar, simple, no self loops}
postcondition(PRE)	=	{planar, simple, no self loops}

#include < AGD/ShortestPathInserter.h >

Creation

ShortestPathInserter

I

creates an instance I of type ShortestPathInserter.

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base class (EdgeInsertionModule).

bool	I.check(const PlaneGraphCopy& G, leda_list<leda_edge>& e_insert, AgdKey& p)
void	I.call(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)

Operations

void	I.call_basic(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)
		inserts the edges in e_insert into PG in the given order.
void	I.call_sf(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)
		inserts the edges in e_insert into PG in the following order. First a shortest path in the dual graph is computed for all remaining edges in e_insert. Then the edge with the shortest shortest path is inserted.
void	I.call_rr(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)
		inserts the edges in e_insert into PG in the given order. Then the edges of e_insert are removed and reinserted again until no improvement is achieved in one round.
void	I.call_err(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)
		inserts the edges in e_insert into PG in the given order. Then the edges of e_insert and PG are removed and reinserted again until no improvement is achieved in one round. Default for function call()
void	I.set_to_basic()	sets the call()-function to call_basic().
void	I.set_to_shortest_first()	sets the call()-function to call_sf().
void	I.set_to_rr()	sets the call()-function to call_rr().
void	I.set_to_err()	sets the call()-function to call_err().
int	I.get_insert_method()	returns 0 (1,2,3) if call() corresponds to call_basic() (call_sf(), call_rr(), call_err()).

Example

The following program shows how to use the different variants of ShortestPathInserter and the module SubgraphPlanarizer.

#include <LEDA/graph.h>
#include <AGD/PlanarSubgraph.h>
#include <AGD/ShortestPathInserter.h>
#include <AGD/SubgraphPlanarizer.h>

int main()
{
  int basic=0,sf=0,rr=0,err=0,num=0,sp=0;
  int i;
  for (i=30;i<40;i++) {
    num++;
		
    //generate random graph
    graph G; random_graph(G,i,2*i,true,true,true);
    cout << "n: " << G.number_of_nodes() << " m: " << G.number_of_edges();
    GraphCopy GC(G);

    //compute planar subgraph
    PlanarSubgraph P;P.runs(100);
    list<edge> del_edges;
    P.call(GC,del_edges);
    cout << " |F|: " << del_edges.size();

    //basic shortest path inserter
    ShortestPathInserter SPI;
    PlaneGraphCopy PGCbasic(GC);
    SPI.call_basic(PGCbasic,del_edges);
    //SPI.set_to_basic();SPI.call(PGCbasic,del_edges); //alternatively
    cout << " b: " << PGCbasic.number_of_nodes()-G.number_of_nodes();
    basic+=(PGCbasic.number_of_nodes()-G.number_of_nodes());

    //shortest first variant
    ShortestPathInserter SPI_sf;		
    PlaneGraphCopy PGCsf(GC);
    SPI_sf.call_sf(PGCsf,del_edges);
    //SPI.set_to_shortest_first();SPI.call(PGCsf,del_edges);
    cout << " sf: " << PGCsf.number_of_nodes()-G.number_of_nodes();
    sf+=(PGCsf.number_of_nodes()-G.number_of_nodes());

    //remove and reinsert improvement
    ShortestPathInserter SPI_rr;
    PlaneGraphCopy PGCrr(GC);
    SPI_rr.call_rr(PGCrr,del_edges);
    //SPI.set_to_rr();SPI.call(PGCrr,del_edges);
    cout << " rr: " << PGCrr.number_of_nodes()-G.number_of_nodes();
    rr+=(PGCrr.number_of_nodes()-G.number_of_nodes());

    //extended remove and reinsert improvement
    ShortestPathInserter SPI_err;
    PlaneGraphCopy PGCerr(GC);
    SPI_err.call_err(PGCerr,del_edges);
    //SPI.set_to_err();SPI.call(PGCerr,del_edges);
    cout << " err: " << PGCerr.number_of_nodes()-G.number_of_nodes() << endl;
    err+=(PGCerr.number_of_nodes()-G.number_of_nodes());

    //Usage of SubgraphPlanarizer
    SubgraphPlanarizer SP;
    //PlanarSubgraph SP_P;SP_P.runs(100);SP.set_subgraph(SP_P);
    //ShortestPathInserter SP_SPI;SP_SPI.set_to_rr();SP.set_inserter(SP_SPI);
    PlaneGraphCopy GC2;
    SP.call(G,GC2);
    cout << " SP: " << GC2.number_of_nodes()-G.number_of_nodes();
    sp+=(GC2.number_of_nodes()-G.number_of_nodes());
  }

  //output some statistics
  cout << "num: " << num
       << " b: " << double(basic)/num << " sf: " << double(sf)/num
       << " rr: " << double(rr)/num << " err: " << double(err)/num;
       << " sp: " << double(sp)/num << endl;

  return 0;
}

Implementation

The running time of the basic algorithm is $\protectO$(kn), where k is the number of edges in F and n is the number of nodes in G''.