[Nauty] forbidden subgraphs in directed graphs

[Chad Brewbaker]

Those graphs are easy to recognize, write a filter. Dissalow all L shapes in the
adjacency matrix.


  1  2  3  4
1    X
2
3    X     X
4

OR

  4  2  3  1
4    
2
3 X  X    
1    X

/*Skeleton program
Usage:
geng <args> | Lfilter >myFile
*/


int i,j,k;
int colCount[n];
int rowCount[n]

for(i=0;i<10;i++){
colCount[i]=rowCount[i]=0;
}

/*Mark possible trouble makers*/
for(i=0;i<n;i++){
for(j=i;j<n;j++){
if(graph[i][j]){
colCount[j]++;
rowCount[i]++;
}
}
}
/*Throw out graphs with "L" in them*/
for(i=0;i<n;i++){
for(j=i;j<n;j++){
if(graph[i][j]){
if(colCount[j]>1 && rowCount[i]>1)
rejectGraph();
}
}
}
acceptGraph();


/*end program*/

To read the graph from g6 format I have some code:
http://www.public.iastate.edu/~crb002/code/readg6.c






> 
> I think, we talked about this some time ago, I don't remember  exactly.
> Or maybe there is something new...
>  
> I can do this with undirected graphs using geng, but I need it with
> directed graphs too.
>  








> 
> I think, we talked about this some time ago, I don't remember  exactly.
> Or maybe there is something new...
>  
> I can do this with undirected graphs using geng, but I need it with
> directed graphs too.
>  
> e.g. I want all acyclic digraphs not containing the "N" digraph   
> 1->2,3->2,3->4
>  
>  
>  
> Guenter.
>