89 lines
1.9 KiB
C#
89 lines
1.9 KiB
C#
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using System;
|
|
|
|
namespace Rokojori
|
|
{
|
|
public abstract class GraphWalker<N> where N:class
|
|
{
|
|
public virtual int NumConnectedFrom( N node ){ return 0;}
|
|
public virtual N GetConnectedFrom( N node, int index ){ return default(N);}
|
|
|
|
public abstract int NumConnectedTo( N node );
|
|
public abstract N GetConnectedTo( N node, int index );
|
|
|
|
public int NumConnectedAll( N node )
|
|
{
|
|
return NumConnectedTo( node ) + NumConnectedFrom( node );
|
|
}
|
|
|
|
public N GetConnected( N node, int index )
|
|
{
|
|
var fromConnections = NumConnectedFrom( node );
|
|
|
|
return index < fromConnections ? GetConnectedFrom( node, index ) : GetConnectedTo( node, index - fromConnections );
|
|
}
|
|
|
|
|
|
public bool IsConnectedTo( N source, N destination )
|
|
{
|
|
var processed = new HashSet<N>();
|
|
var toDo = new List<N>();
|
|
|
|
toDo.Add( source );
|
|
|
|
while ( toDo.Count > 0 )
|
|
{
|
|
var current = Lists.RemoveFirst( toDo );
|
|
|
|
if ( processed.Contains( current ) )
|
|
{
|
|
continue;
|
|
}
|
|
|
|
processed.Add( current );
|
|
|
|
var numConnected = NumConnectedTo( current );
|
|
|
|
for ( int i = 0; i < numConnected; i++ )
|
|
{
|
|
var connected = GetConnected( current, i );
|
|
|
|
if ( connected == destination )
|
|
{
|
|
return true;
|
|
}
|
|
|
|
if ( ! processed.Contains( connected ) )
|
|
{
|
|
toDo.Add( connected );
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
public bool IsDirectlyConnectedTo( N node, N other )
|
|
{
|
|
if ( node == null || other == null )
|
|
{
|
|
return false;
|
|
}
|
|
|
|
var connected = NumConnectedTo( node );
|
|
|
|
for ( int i = 0; i < connected; i++ )
|
|
{
|
|
if ( GetConnected( node, i ) == other )
|
|
{
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
}
|
|
} |