[Nauty] forbidden subgraphs in directed graphs
Chad Brewbaker
crb002 at iastate.edu
Thu Sep 9 00:38:01 EST 2004
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.
>
More information about the Nauty
mailing list